algorithm - 解决 N 谜题的 A* 启发式比较

Question

我正在尝试使用具有 3 个不同启发式函数的 A* 算法来解决 N 难题。我想知道如何在时间复杂度方面比较每种启发式方法。我正在使用的启发式方法是：曼哈顿距离、曼哈顿距离 + 线性冲突、N-max 交换。特别是对于 8 拼图和 15 拼图。

Answer 1

正如@Harold 在他的评论中所说，比较启发式函数时间复杂度的方法通常是通过实验测试。在您的情况下，为 8-puzzle 和 15-puzzle生成一组n 个随机问题，并使用不同的启发式函数解决它们。需要注意的是：

1. 比较总是取决于几个因素，如硬件预期、编程语言、实现算法时的技能……

2. 一般而言，信息较多的启发式算法总是会比信息较少的启发式算法扩展更少的节点，并且可能会更快。

最后，为了比较每个问题集的三个启发式方法，我建议使用平均运行时间的图形（例如每个问题重复 5 次），其中：

1. 问题在 x 轴上按难度排序。
2. 每个启发式函数的运行时间在 y 轴上（如果无法轻易看出备选方案之间的差异，则可能采用对数刻度）。

以及带有探索状态数量的类似图形。

Answer 2

N-puzzle 通常是 NP 很难找到最短的解决方案，因此无论您使用什么启发式算法，您都不太可能找到它们之间复杂性的任何差异，因为您无法证明任何界限。

如果您将自己限制在 8 拼图或 15 拼图上，那么具有任何可接受启发式的 A* 算法将在 O(1) 时间内运行，因为棋盘位置的数量是有限的（尽管很大）。