我最近开始了人工智能的入门课程，并且我已经获得了在Python中实现可接受的启发式功能的任务，该功能通过A *搜索解决了15-Puzzle .
我实施了曼哈顿距离以及其他一些启发式算法 . Python代码运行得很好，算法实际上解决了这个问题，但我对曼哈顿距离启发式是否可以接受这个特定问题有一些疑问 .
根据理论，启发式是可以接受的，如果它达到目标的成本 . 这意味着启发式是乐观的，它返回的成本永远不会超过实际成本 .
当初始状态如下（0表示空槽）时：
1 2 3 4
0 6 7 8
5 9 10 12
13 14 11 15
我的程序通过5次移动解决了问题，但是每个放错位置的瓦片的曼哈顿距离之和等于10，这是实际成本的两倍 . 因此，实际成本远低于估计成本 . 这是否意味着启发式不可接受或我的逻辑有什么问题？
我想过只计算空块的曼哈顿距离，但是当空块在正确的位置而其他瓷砖放错位置时，这会导致估计成本为零的状态 .
1 回答
Manhattan Distance启发式是可以接受的，因为它独立地考虑每个瓦片（而事实上瓦片彼此干扰） . 所以它很乐观 .
在您的示例中，距离所有图块的目标位置的距离之和为5（图块5,9,10,11,15每个需要一次移动） .