我最近开始了一门人工智能的入门课程，并被布置了一个任务，要求在Python中实现一个可接受的启发式函数，用于通过A*搜索解决15拼图问题。
我实现了曼哈顿距离以及其他一些启发式方法。Python代码运行得很好，算法确实解决了问题，但我不确定曼哈顿距离启发式方法是否对这个问题是可接受的。
根据理论，如果一个启发式方法从不高估达到目标的成本，那么它就是可接受的。这意味着该启发式方法是乐观的，它返回的成本永远不会大于实际成本。
当初始状态如下时（0表示空位）：
1 2 3 40 6 7 85 9 10 1213 14 11 15我的程序用5步解决了问题，但所有错位的瓷砖的曼哈顿距离之和等于10，是实际成本的两倍。因此，实际成本远低于估计值。这是否意味着该启发式方法不可接受，还是我的逻辑有问题？
我想过只计算空块的曼哈顿距离，但这会导致当空块在正确位置而其他瓷砖错位时，估计成本为零的状态。
回答：
曼哈顿距离启发式方法是可接受的，因为它独立考虑每个瓷砖（虽然实际上瓷砖之间会相互干扰）。所以它是乐观的。
在你的例子中，所有瓷砖到目标位置的距离之和是5（瓷砖5、9、10、11、15各需要移动一步）。
