
N個の異なる数字があります。これを大小の順にならべ換えます。
最適手順数は計算上はLog(N!)/Log(2)です。
その最適手順の一般化は可能でしょうか。
例1:N=4のとき
A、B,C,Dと4個の数字があって
1回目 AとBを比較 結果A>Bが判明
2回目 CとDを比較 結果C>Dが判明
3回目 AとCを比較 結果A>Cが判明
4回目 BとCを比較する
B>Cのときは、A,B,C,Dとなって並び替え終了。
こういう都合の良い結果での並び換え終了は手順からはずします。
C>Bのとき
5回目 BとDを比較する
B>Dのとき A、C,B,D で終了
D>Bのとき A,C、D、B で終了
例2:N=5のとき A、B,C,D、Eと4個の数字があって
1回目 AとBを比較 結果A>Bが判明
2回目 CとDを比較 結果C>Dが判明
3回目 AとCを比較 結果A>Cが判明
4回目 EとCを比較
5回目 E>CのときEとAを比較、C>EのときEとDを比較
6回目 ここから場合わけひどくなります。
例としてA>E>C>DのときBとCを比較
7回目B>CのときBとEを比較、C>BのときBとDを比較
例3:N=6であれば10回、N=7であれば13回でした。
これらはN=5の手順のあと6個目、7個目の位置決めするだけ。
No.1ベストアンサー
- 回答日時:
うろ憶えなんですが, n=12 か 13 あたりで「理論上の最小回数 (つまり log n! / log 2) ではできない」こと
が証明されていたと思います.この回答への補足
n=12が可能ならn=13は12個並べて4手で1個足すだけです。
だからn=12が可能かどうかが鍵です。
n=12のときは解答ありです。29回手順は、
A>B、C>D、E>F、G>H、H>I、J>K 6回
A>C 7回目
AEGHIの5個並びさせて7回手順で14回目
残り15手順
最悪はAが最大のときですが、このときは5個並び手順を中断します。
最大が確定する前に他の手順に入ります。場合わけひどく中略。
Aが2番目以降になったとき、残り15手は可能なのです。
ありがとうございます。
証明はコンピューターでのしらみつぶし処理でしょうか。
では私の解答に抜けがあるのかもしれません。
専門家の意見を聞きたいのですが、
これが不可能と証明されたらp=npも不可能にならないでしょうか。
No.2
- 回答日時:
や, 私の方もうろ憶えで「理論上の最小回数ではできない例があるってどこかで読んだ記憶があるなぁ」くらいで書いてますので.
ところで, これと P=NP とどのように関係しているのか見えないのですが....
この回答への補足
理論上の回数に対してアルゴリズムがあるかどうかは、P=NP問題の表現(あるいは言い換え)の一つだったような。
アルゴリズムの有無が定かでないので未解決ですよね。
どういう状況でのアルゴリズムの有無を証明すればよいのかについては、具体例が多く提示されています。
道順の最適化とか並び替えの問題とかです。
アルゴリズムが無いと証明されてしまっているなら、P=notNPの証明になっているのではと考えます。
繋がりが遠くて断言できるほどの知識はありませんが。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
統計における危険率
-
ボンフェローニの補正について...
-
れいわ新選組を、分析して下さい。
-
二つのデータの波形が似てるか...
-
決定係数がマイナスになる例っ...
-
アポロのレーザ反射鏡
-
切片あり回帰と切片なし回帰
-
読書量と年収の関係
-
【統計学】重回帰分析と正準相...
-
アクセス2003 レポートの総ペ...
-
修正済み決定係数(R2乗)がマ...
-
ダミー変数での相関係数の算出...
-
TSOのデータセット格納場所の検索
-
メチルエステル化
-
相関係数Rの2乗について
-
分析バリデーションにおける真...
-
EXCELで両対数を取った重回帰分...
-
VB.NETでODBC接続のデータベー...
-
正準判別関数係数の符号
-
回帰式と近似式について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
統計における危険率
-
サンプル数の違うものの比較
-
統計で比較するサンプル数について
-
SPSS 多重比較ボンフェロー二...
-
8ミクロンって手で触ったり目で...
-
積について可換なn次正方行列...
-
統計的検定法について
-
数学A整数の性質について質問で...
-
算数の和差算の解き方について...
-
鳩の巣原理
-
統計の有意差について教えて下...
-
統計:多群の比較:Tukey-Krame...
-
測定日の異なるデータで有意差...
-
ボンフェローニの補正について...
-
二つのデータの波形が似てるか...
-
切片あり回帰と切片なし回帰
-
決定係数がマイナスになる例っ...
-
読書量と年収の関係
-
れいわ新選組を、分析して下さい。
-
回帰式と近似式について
おすすめ情報