Miz*_*zor 2 language-agnostic algorithm a-star sudoku
A-star用于查找图中startnode和endnode之间的最短路径.使用什么算法来解决某些问题,目标状态并不是专门知道的,而是我们只有目标状态的标准？
例如,可以用类似Astar的算法解决数独难题吗？我们不知道国家的样子(哪个数字在哪里),但我们知道数独的规则,一个获胜国家的标准.因此,我有一个startnode,只是endnode的标准,使用哪种算法？
A*需要图形,用于遍历该图形的成本函数,关于图形中的节点是否比另一个节点更接近目标的启发式算法,以及测试是否达到目标.
搜索Sudoku解决方案空间实际上没有最小化的遍历成本,只有全局成本(未解决的正方形的数量),因此所有遍历都是相等的成本,因此A*实际上没有帮助 - 您可以分配的任何单元格花费一个动作并让你更接近目标,所以A*不会比随机选择下一步更好.
可以基于在每个点处应用不同技术的估计/测量成本来应用A*搜索,然后尝试以最小的计算成本找到通过解空间的路径.在这种情况下,图表不仅仅是解谜的解决方案状态,而是你要在这一点上选择适用的技术 - 你知道过渡成本的估计,而不是那个过渡的地方'除非如果成功,它离目标更近了一步.
您不必知道确切的目标最终状态。这一切都归结为启发式函数，当它返回 0 时，您可以假设已经找到（至少）有效的最终状态之一。
因此，在 a* 期间，不要检查 current_node == target_node，而是检查 current_node.h() 是否返回 0。如果是这样，它应该无限接近和/或重叠目标/最终状态。