algorithm - 可接受的启发式曼哈顿距离

Question

我最近开始了一门人工智能入门类(class)，我接到了一项任务，要在 Python 中实现一个可接受的启发式函数，用 A* 搜索解决 15 题。

我实现了曼哈顿距离以及其他一些启发式方法。 Python 代码工作得很好，算法实际上解决了问题，但我对曼哈顿距离启发式算法是否适用于这个特定问题有一些疑问。

根据理论，如果启发式从不高估达到目标的成本，则它是可接受的。这意味着启发式是乐观的，它返回的成本永远不会大于实际成本。

当初始状态如下(0表示空槽):

1  2  3  4
0  6  7  8
5  9  10 12
13 14 11 15

我的程序用 5 步解决了这个问题，但是每个错放的方 block 的曼哈顿距离之和等于 10，是实际成本值的两倍。所以实际成本比估计的要少得多。这是否意味着启发式是 Not Acceptable ，或者我的逻辑有问题？

我考虑过只计算空 block 的曼哈顿距离，但当空 block 位于正确位置但其他方 block 放错位置时，这将导致估计成本为零的状态。

Answer 1

Manhattan Distance启发式是可以接受的，因为它独立地考虑每个图 block (而实际上图 block 相互干扰)。所以这是乐观的。

在您的示例中，所有方 block 与目标位置的距离总和为 5(方 block 5、9、10、11、15 各需要移动一次)。