1

假设我们有一个 8 谜题，空的瓷砖用零标记。目标状态是：

  • 1 2 3
  • 4 5 6
  • 7 8 0

初始状态是：

  • 0 1 3
  • 8 2 4
  • 7 6 5

...我的问题是，A * 树中的孩子是否有可能“复制”或与其祖先具有相同的状态？或者“f(n) = g(h) + h(n)”[其中 g(h) = # of move made... h(n) = manhattan distances of each tile] 已经使这成为不可能并且因此我不需要担心这个？..例如，从初始状态：

  • 0 1 3
  • 8 2 4
  • 7 6 5

然后发生以下状态，从而在 A* 树中产生更多的子节点

（动作：向上）

  • 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) 会解决这个问题？感谢那些会回答的人，任何帮助将不胜感激！

4

1 回答 1

0

您不必担心您在问题中描述的情况。初始状态在 A* 的第一次迭代中扩展，这导致算法将该节点包含在 CLOSED 列表中，并带有相关成本（为零，因为它是初始状态）。如果您再次找到该状态作为任何其他状态的后继状态，则该算法将在 CLOSED 列表中以较低的成本找到该状态，并且不会再次扩展它，从而丢弃搜索树中的该分支。

如果你打算在 Java 中实现这个问题，也许你会发现使用像Hipster这样的启发式搜索库很有用。这个库是开源的（参见Github）并且有一些用它解决的搜索问题的例子。包括用 A* 解决的 8-puzzle 问题。

希望我的回答有帮助

于 2015-02-16T17:13:39.810 回答