algorithm - '3 jugs of water' 的状态图

标签 algorithm artificial-intelligence graph-algorithm

<分区>

关于三壶水问题:

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

添加:完全填满锯齿
倒到另一个 jar 里:将一个 jar 里的东西倒入第二个 jar 里(直到第一个 jar 倒空或第二个 jar 完全装满)
清空是:清空一个 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 ) 目标状态对吗？

问题:我的理解正确吗？这些是状态和生成树吗？

最佳答案

该图对于第一步是正确的，但是 - 您扩展兄弟 (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 ，并且是通过构建状态使用图算法约简来解决问题的经典示例 graph并运行寻路算法，例如 A*或 BFS .

关于algorithm - '3 jugs of water' 的状态图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13857062/

上一篇：algorithm - 最小生成树的基本问题

下一篇：algorithm - 二叉树的数组实现

相关文章：

algorithm - 在 GA 中执行依赖项交叉的好方法是什么？

algorithm - 弗洛伊德·沃歇尔(Floyd Warshall)受到限制

python - 使用类在 python 中创建图形数据结构

artificial-intelligence - 人工智能 - 清洁和油漆的智能代理

r - 二次形式的公式运算

python - 在 Python 中更改 bool 函数的值

algorithm - 将排列转换为反转表示

Java 牛顿迭代

javascript - 比较两个 URL 模板的优化算法

algorithm - 在排序数组中查找所有重复项和缺失值