algorithm - 预先计算 A* 的结果

Question

目前正在学习A*搜索算法并使用它来找到最快的解决方案N-Puzzle。对于初始起始状态的一些随机种子，谜题可能无法解决，这将导致非常长的等待时间，直到算法搜索整个搜索空间并确定给定起始状态没有解决方案。

我想知道是否有一种方法可以预先计算A*算法是否无法避免这种情况。我已经阅读了一些关于它是如何可能的，但找不到关于如何做到这一点的直接答案。

任何指导或选项表示赞赏。

Answer 1

我认为 A* 并没有为您提供一种机制来了解问题是否可以解决。具体来说N-Puzzle，我认为这可以帮助您检查它是否可以解决：

http://www.geeksforgeeks.org/check-instance-8-puzzle-solvable/

似乎如果您处于奇数反转的状态，您肯定知道该排列的问题是不可行的。

Answer 2

特别是对于 N-puzzle，只有两个可能的奇偶校验，所以你只需要检查当前拼图是哪个奇偶校验。

有关如何在数学 stackexchange上执行此操作的深入解释

对于一般的 A* 问题，不，如果图是可解的，则无法预先计算。