3

D ディスク、P 極、およびディスクの初期開始位置と、必要な極の最終目的地が与えられた場合、問題の一般的な解決策をどのように記述できるでしょうか?

例えば、

D=6 と P=4 の場合、最初の開始位置は次のようになります。

5     1
6 2 4 3

数字は円盤の半径を表し、極には左右に 1 ～ 4 の番号が付けられており、すべての円盤を極 1 に積み重ねたいと考えています。

次の動きをどのように選択しますか？

解決策は次のとおりです（手動で解決します）：

3 1
4 3
4 1
2 1
3 1

(形式: <from-pole> <to-pole>)

最初の動きは明らかです。「4」を「5」の上に移動します。これは、最終的なソリューションで必要な位置だからです。

次に、おそらく次に大きい数字、つまり「3」を移動したいと思います。しかし、最初にそれをアンベリーする必要があります。つまり、次に「1」を移動する必要があります。しかし、それをどこに置くかをどのように決めるのでしょうか?

それは私が得た限りです。考えられるすべての場所を試す再帰的アルゴリズムを作成できますが、それが最適かどうかはわかりません。

4

1 に答える 1

1

できません。

より正確には、http://en.wikipedia.org/wiki/Tower_of_Hanoi#Four_pegs_and_beyondが言うように、4 つ以上のペグの場合、最適なソリューションが何であるかを証明することは未解決の問題です。円盤の山が 1 つのペグにあり、その山全体を別のペグに移したいという単純なケースでは、最適であると広く信じられている非常に優れたアルゴリズムが知られています。ただし、任意の開始位置に対するアルゴリズムはなく、既知のヒューリスティックでさえありません。

提案されたアルゴリズムがあった場合、未解決の問題はおそらくはるかに簡単になります。

于 2012-07-03T05:54:55.800 に答える