4

良い「状態空間」を使って「ハノイの塔」の問題を解決したい。適切な状態空間を使用することは、いくつかのAI技術によって提案されている方法です。良好な状態空間があるので、検索ツリーを構築してから、「DFS」（深さ優先探索）などの戦略を使用して解決策を見つけたいと思います。

私の問題は、適切な状態空間を開発し、それを使用して検索ツリーを構築する方法がわからないことです。ハノイの塔の問題のために状態空間を作成する方法を誰かが説明できますか？次に、そのための検索ツリーを構築する方法を教えてください。

4

4 に答える 4

7

次の状態空間をお勧めします。

n個のレンガと0,1,2で示される3つの塔があると仮定します。現在の状態を3桁の数字で表します（例：n = 9の場合）。

987654321
001102020 (current state)

これは、レンガ9、8、5、3、および1が0番目の塔にあることを意味します。1番目のタワーのレンガ7と6、2番目のタワーのレンガ4と2。

これにより、サイズが3 ^ nの状態空間が得られますが、これは大きすぎません。

（これは部分的な回答にすぎません。ただし、すべての状態文字列は正当な状態に対応します。つまり、

  1. 各タワーでは、レンガのサイズが下から上に向かって小さくなります。

  2. 2つの異なるタワーにレンガは表示されません。

したがって、提案された状態空間は最小限であると思います。）。

于 2011-06-19T10:51:06.920 に答える
1

最適な解決策だと思います（2 ^ n-1）

状態空間は3^nで与えられます

これは、状態をカウントするために使用できる樹形図の別のリンクです（これは、状態空間に関する質問に関連していると思います）

于 2011-12-18T03:59:37.590 に答える
1

2 ^（n + 1）-1は、ハノイの塔の問題に対して正しくありません。ここで図2を見ると、n =3を2^（n + 1）-1に適用すると、2^4-1または15の状態が得られます。しかし、図2 は27の状態を示しています。

于 2011-12-18T13:40:15.093 に答える
1

分割統治法を使用すると、この問題を簡単に解決できると思います。補助ペグを使用して、n個のディスクをsrcからdestに移動する問題をUが解決する必要があると仮定します。Uは関数を再帰的に定義できます。

towers(n,src,dest,peg)
{
    if(n==1) //BASE CASE
        move a disc from src to dest. 

   else  //INDUCTIVE CASE
   {
    towers(n-1,src,aux,dest);
    towers(1,src,dest,aux);
    towers(n-1,aux,dest,src)
   }
}

複雑さの分析：T（n）= 2T（n-1）+1

これにより、解T（n）= O（2 ^ n）[指数次数]が得られます。

時間の複雑さをさらに改善するために、すでに解決されたサブ問題の解決策を保存するために、ある種のメモ化を行うこともできますが、これはスペースの複雑さの使用を増やすこととのトレードオフです。

于 2012-09-16T14:18:25.357 に答える