algorithm - 具有未知最终状态的类 Astar 算法

Question

A-star 用于在图中找到起始节点和结束节点之间的最短路径。如果目标状态不是具体已知的，而我们只有目标状态的标准，则使用什么算法来解决问题？

例如，一个数独游戏可以用类似 Astar 的算法来解决吗？我们不知道最终状态会是什么样子（哪个数字在哪里），但我们知道数独的规则，即获胜状态的标准。因此，我有一个 startnode 和一个 endnode 的标准，使用哪种算法？

Answer 1

A* 需要一个图、一个用于遍历该图的成本函数、一个关于图中一个节点是否比另一个节点更接近目标的启发式算法，以及一个是否达到目标的测试。

搜索数独解决方案空间并没有真正需要最小化的遍历成本，只有全局成本（未解决的正方形的数量），所以所有遍历的成本都是相等的，所以 A* 并没有真正的帮助 - 你可以分配的任何单元格花费一步，让你离目标更近一步，所以 A* 不会比随机选择下一步更好。

可以根据在每个点应用不同技术的估计/测量成本来应用 A* 搜索，然后尝试以最少的计算成本找到通过解空间的路径。在这种情况下，图表不仅是拼图的解决方案状态，而且您将在该点应用的技术之间进行选择 - 您将知道转换成本的估计值，但不知道转换的位置'去”，只是如果成功了，那就离目标更近了一步。

Answer 2

是的，当无法识别特定目标状态时可以使用 A*。（Pete Kirkham 的回答暗示了这一点，但并没有过多强调。）

当无法识别特定的目标状态时，有时更难为完成部分解决方案所需的剩余成本提出有用的启发式下限——而 A* 的效率取决于选择有效的启发式。但这并不意味着它不能应用。 任何可以在计算机上解决的问题都可以使用广度优先搜索来解决，再加上一组标志，表明以前是否见过一个状态；这与 A* 相同，具有始终为零的启发式下限。（当然，这不是解决许多问题的最有效算法。）

Answer 3

您不必知道确切的目标最终状态。这一切都归结为启发式函数，当它返回 0 时，您可以假设已经找到（至少）一个有效的最终状态。

所以在 a* 期间，不是检查 current_node == target_node，而是检查 current_node.h() 是否返回 0。如果是，它应该无限接近和/或重叠目标/结束状态。