人に聞けない痔の悩み、これでスッキリ >>

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個目の位置決めするだけ。

A 回答 (2件)

うろ憶えなんですが, 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も不可能にならないでしょうか。

補足日時:2008/05/24 00:48
    • good
    • 0

や, 私の方もうろ憶えで「理論上の最小回数ではできない例があるってどこかで読んだ記憶があるなぁ」くらいで書いてますので.


ところで, これと P=NP とどのように関係しているのか見えないのですが....

この回答への補足

理論上の回数に対してアルゴリズムがあるかどうかは、P=NP問題の表現(あるいは言い換え)の一つだったような。
アルゴリズムの有無が定かでないので未解決ですよね。
どういう状況でのアルゴリズムの有無を証明すればよいのかについては、具体例が多く提示されています。
道順の最適化とか並び替えの問題とかです。
アルゴリズムが無いと証明されてしまっているなら、P=notNPの証明になっているのではと考えます。
繋がりが遠くて断言できるほどの知識はありませんが。

補足日時:2008/05/25 13:15
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング