求解N-难题的A*启发式算法比较

Question

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

Answer 1

一般来说，N字谜很难找到最短的解，所以无论你使用什么启发式，你都不太可能找到它们之间的任何复杂性差异，因为你无法证明任何界限的紧密性。

如果您将自己限制在8个拼图或15个拼图中，则具有任何可接受的启发式启发式的A*算法将在O(1)时间内运行，因为存在有限(尽管很大)数量的董事会位置。

Answer 2

正如@Harold在他的评论中所说，比较启发式函数的时间复杂性的方法通常是通过实验测试来实现的。需要注意的是：

1. 比较总是取决于几个因素，比如硬件预期，编程语言，你在实现算法时的技能，...
2. 一般来说，更有见地的启发式总是比不那么有见地的启发式扩展更少的节点，并且可能会更快。

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

对于每个启发式函数，问题在x轴上，按difficulty.

• The运行时间排序在y轴上(如果不容易看出备选方案之间的差异，则可能是对数刻度)。

以及与探索状态的数量类似的图表。