8 使用 A* 解决难题：一个 child 节点重复其祖先的状态
8 puzzle solving using A*: a child node repeating its ancestor's state
假设我们有一个 8 拼图问题，空方块标记为零。
目标状态是：
- 1 2 3
- 4 5 6
- 7 8 0
初始状态为：
- 0 1 3
- 8 2 4
- 7 6 5
...我的问题是，A* 树中的 child 是否有可能达到 "copy" 或具有与其祖先相同的状态？还是 "f(n) = g(h) + h(n)" [其中 g(h) = # 移动... h(n) = 每个图块的曼哈顿距离之和] 已经使这不可能，因此我不需要担心这个？ .. 例如，从初始状态：
- 0 1 3
- 8 2 4
- 7 6 5
然后会发生以下状态，从而在 A* 树中产生更多 child 个节点
（动作：向上）
- 8 1 3
- 0 2 4
- 7 6 5
动作：左
- 8 1 3
- 2 0 4
- 7 6 5
动作：向下
- 8 0 3
- 2 1 4
- 7 6 5
动作：对
- 0 8 3
- 2 1 4
- 7 6 5
动作：向上
- 2 8 3
- 0 1 4
- 7 6 5
...然后动作：左、下、右、上、左、下、右发生...从而使状态回到初始状态：
- 0 1 3
- 8 2 4
- 7 6 5
在 8 字谜的 A* 搜索中这可能吗？或者 f(n) 会解决这个问题吗？感谢那些愿意回答的人，我们将不胜感激！
您不必担心您在问题中描述的情况。起始状态在 A* 的第一次迭代中扩展，这导致算法将该节点包含在 CLOSED 列表中，并带有相关成本（为零，因为它是初始状态）。如果您再次发现该状态作为任何其他状态的后继状态，算法将在 CLOSED 列表中以较低的成本找到该状态，并且不会再次展开，丢弃搜索树中的该分支。
如果您打算在 Java 中解决这个问题，也许您会发现使用像 Hipster. This library is open-source (see at Github) and has some examples of search problems solved with it. Including the 8-puzzle problem solved with A*.
这样的启发式搜索库很有用
希望我的回答对您有所帮助，
假设我们有一个 8 拼图问题，空方块标记为零。 目标状态是：
- 1 2 3
- 4 5 6
- 7 8 0
初始状态为：
- 0 1 3
- 8 2 4
- 7 6 5
...我的问题是，A* 树中的 child 是否有可能达到 "copy" 或具有与其祖先相同的状态？还是 "f(n) = g(h) + h(n)" [其中 g(h) = # 移动... h(n) = 每个图块的曼哈顿距离之和] 已经使这不可能，因此我不需要担心这个？ .. 例如，从初始状态：
- 0 1 3
- 8 2 4
- 7 6 5
然后会发生以下状态，从而在 A* 树中产生更多 child 个节点
（动作：向上）
- 8 1 3
- 0 2 4
- 7 6 5
动作：左
- 8 1 3
- 2 0 4
- 7 6 5
动作：向下
- 8 0 3
- 2 1 4
- 7 6 5
动作：对
- 0 8 3
- 2 1 4
- 7 6 5
动作：向上
- 2 8 3
- 0 1 4
- 7 6 5
...然后动作：左、下、右、上、左、下、右发生...从而使状态回到初始状态：
- 0 1 3
- 8 2 4
- 7 6 5
在 8 字谜的 A* 搜索中这可能吗？或者 f(n) 会解决这个问题吗？感谢那些愿意回答的人，我们将不胜感激！
您不必担心您在问题中描述的情况。起始状态在 A* 的第一次迭代中扩展，这导致算法将该节点包含在 CLOSED 列表中，并带有相关成本（为零，因为它是初始状态）。如果您再次发现该状态作为任何其他状态的后继状态，算法将在 CLOSED 列表中以较低的成本找到该状态，并且不会再次展开，丢弃搜索树中的该分支。
如果您打算在 Java 中解决这个问题，也许您会发现使用像 Hipster. This library is open-source (see at Github) and has some examples of search problems solved with it. Including the 8-puzzle problem solved with A*.
这样的启发式搜索库很有用希望我的回答对您有所帮助，