数字の並び換えの最適手順

Ｎ個の異なる数字があります。これを大小の順にならべ換えます。
最適手順数は計算上はＬｏｇ（Ｎ！）／Ｌｏｇ（２）です。
その最適手順の一般化は可能でしょうか。

例１：Ｎ＝４のとき
Ａ、Ｂ，Ｃ，Ｄと４個の数字があって
１回目　ＡとＢを比較　結果Ａ＞Ｂが判明
２回目　ＣとＤを比較　結果Ｃ＞Ｄが判明
３回目　ＡとＣを比較　結果Ａ＞Ｃが判明
４回目　ＢとＣを比較する　
Ｂ＞Ｃのときは、Ａ，Ｂ，Ｃ，Ｄとなって並び替え終了。
こういう都合の良い結果での並び換え終了は手順からはずします。
Ｃ＞Ｂのとき
５回目　ＢとＤを比較する
Ｂ＞Ｄのとき　Ａ、Ｃ，Ｂ，Ｄ　で終了
Ｄ＞Ｂのとき　Ａ，Ｃ、Ｄ、Ｂ　で終了

例２：Ｎ＝５のとき　Ａ、Ｂ，Ｃ，Ｄ、Ｅと４個の数字があって
１回目　ＡとＢを比較　結果Ａ＞Ｂが判明
２回目　ＣとＤを比較　結果Ｃ＞Ｄが判明
３回目　ＡとＣを比較　結果Ａ＞Ｃが判明
４回目　ＥとＣを比較　
５回目　Ｅ＞ＣのときＥとＡを比較、Ｃ＞ＥのときＥとＤを比較
６回目　ここから場合わけひどくなります。
例としてＡ＞Ｅ＞Ｃ＞ＤのときＢとＣを比較
７回目Ｂ＞ＣのときＢとＥを比較、Ｃ＞ＢのときＢとＤを比較

例３：Ｎ＝６であれば１０回、Ｎ＝７であれば１３回でした。
これらはＮ＝５の手順のあと６個目、７個目の位置決めするだけ。

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2008/05/24 00:46

うろ憶えなんですが, n=12 か 13 あたりで「理論上の最小回数 (つまり log n! / log 2) ではできない」こと

が証明されていたと思います.

この回答への補足

n=12が可能ならn=13は１２個並べて４手で１個足すだけです。
だからｎ＝１２が可能かどうかが鍵です。
n=12のときは解答ありです。29回手順は、
A>B、C>D、E>F、G>H、H>I、J>K　6回
A>C　７回目
AEGHIの５個並びさせて7回手順で１４回目
残り１５手順
最悪はAが最大のときですが、このときは5個並び手順を中断します。
最大が確定する前に他の手順に入ります。場合わけひどく中略。
Aが２番目以降になったとき、残り１５手は可能なのです。
ありがとうございます。
証明はコンピューターでのしらみつぶし処理でしょうか。
では私の解答に抜けがあるのかもしれません。

専門家の意見を聞きたいのですが、
これが不可能と証明されたらｐ＝ｎｐも不可能にならないでしょうか。

補足日時：2008/05/24 00:48

No.2 回答者： Tacosan 回答日時： 2008/05/24 21:35

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

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

この回答への補足

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

補足日時：2008/05/25 13:15