0

关于三壶水的问题：

我们有 3 个水壶，第一个水壶的容量为 12，第二个水壶的容量为 8，第三个水壶的容量为 3。初始状态为：(0,0,0) 后继函数为：

  1. 加：完全填满一个锯齿
  2. 倒入另一个：将一个水壶的内容物倒入第二个（直到第一个空或第二个完全装满）
  3. Empty 是：清空一个 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)

其中 (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 回答