0

3つのジャグの水の問題について：

3 つの水差しがあり、最初の水差しの容量は 12、2 番目の水差しの容量は 8、3 番目の水差しの容量は 3 です。初期状態は (0,0,0) 後継関数は次のとおりです。

  1. 追加: ギザギザを完全に埋める
  2. 別のものに注ぐ: 1 つの水差しの内容物を 2 番目の水差しに注ぎます (最初の水差しが空になるか、2 番目の水差しが完全にいっぱいになるまで)。
  3. Empty is: jar の内容をすべて空にする

目標状態は (1,1,1) です。

その状態ツリーを描きたいです。私は自分でそれをやったが、それが正しいかどうかはよくわからない.

         (0,0,0)
        /   |    \
       /    |     \
      /     |      \
(12,0,0) (0,8,0) (0,0,3)

(12,0,0) の子ノードは、(12,0,0),(12,8,0),(12,8,3),(0,8,3),(0,0, 3),(0,0,0),(9,8,3),(12,8,0),(4,8,3),(12,0,3),(12,5,3) ,(12,5,3),(12,8,0)

which (12,0,0),(0,0,0)==>ルートにあるため、(12,8,0)==>は失敗ノードであり、展開しません。

(0,0,3) を拡張すると、目標の状態に到達すると思います: ノード (0,0,3) の子: (3,0,0),(0,3,0), (0,0,3),(1,1,1) (1,1,1) は目標状態ですよね?

質問:正しく理解できていますか? これらは状態と生成されたツリーですか?

4

1 に答える 1

3

グラフは最初のステップでは正しいですが、兄弟 (12,0,0)、(0,8,0)、および (0,0,3) を間違って展開しています。
各反復で複数ではなく、単一のステップを実行する必要があり、多くのステップを実行しようとしないでください。

したがって：

successors((12,0,0)) = { (12,0,3), (12,8,0), (0,0,0), (9,0,3), (4,8,0) }
successors((0,8,0)) = { (12,8,0), (0,8,3), (8,0,0), (0,5,3), (0,0,0) }
successors((0,0,3)) = { (12,0,3), (0,8,3), (3,0,0), (0,3,0), (0,0,0) }

(各状態から、許可された操作は 1 つだけ実行できます。それ以上は実行できません - 後続/次の状態を取得するため)。

これらを拡張し続けることで、最終的にすべての可能性を手に入れることができます。

参考までに、この問題はThe Die Hard Problemと呼ばれることもあり、状態グラフを構築してA*やBFSなどの経路探索アルゴリズムを実行することにより、グラフ アルゴリズムへのリダクションを使用して問題を解決する典型的な例です。

于 2012-12-13T09:53:53.340 に答える