容许启发式曼哈顿距离

Question

我最近开始了一门人工智能入门课程，我被指派在Python中实现一个可接受的启发式函数，它解决了A*搜索中的15-难题。

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

根据理论，如果启发式算法从不高估实现目标的成本，那么启发式是可以接受的。这意味着启发式是乐观的，它返回的成本永远不会超过实际的成本。

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

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

我的程序用5次移动就解决了这个问题，但是每个错位瓷砖的曼哈顿距离之和等于10，是实际成本的两倍。因此，实际成本比估计的要低得多。这是否意味着启发式是不可接受的，还是我的逻辑有问题？

我曾想过，仅仅计算空旷街区的曼哈顿距离，但这将导致各州的估算成本为零，当空置区在其正确的位置，但其他瓷砖是错误的。

Answer 1

曼哈顿距离启发式是可接受的，因为它独立地考虑每个瓷砖(而实际上，tiles相互干扰)。所以这很乐观。

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

​

​