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