algorithm - 具有未知结束状态的 Astar-like 算法

Question

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

例如，数独谜题是否可以用类似 Astar 的算法来解决？我们不知道最终状态会是什么样子(哪个数字在哪里)，但我们知道数独游戏的规则，即获胜状态的标准。因此，我有一个起始节点和一个结束节点的标准，要使用哪种算法？

Answer 1

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

搜索数独解空间实际上并没有最小化遍历成本，只有全局成本( Unresolved 方 block 数)，所以所有遍历的成本都是相等的，所以 A* 并没有真正帮助 - 任何单元格您可以分配成本一步，让您更接近目标，因此 A* 不会比随机选择下一步更好。

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