可接受启发式曼哈顿距离
我最近开始了一门人工智能的入门课程，并且我已经被赋予了一个任务，在Python中实现一个可接受的启发式函数，通过A *搜索解决15-Puzzle。
我实施了曼哈顿距离以及其他一些启发式。 Python代码工作得很好，算法实际上解决了这个问题，但是我对曼哈顿距离启发式是否适用于这个特定问题有一些疑问。
根据理论，如果启发式不会 高估实现目标的成本，那么启发式算法是可以接受的。 这意味着启发式是乐观的，它返回的成本永远不会比实际成本高。
初始状态如下（0表示空插槽）：
1 2 3 4
0 6 7 8
5 9 10 12
13 14 11 15
我的程序通过5次移动解决了这个问题，但是每个错位瓷砖的曼哈顿距离的总和等于10，这是实际成本的两倍。 所以实际成本远低于估算成本。 这是否意味着启发式是不可接受的或者我的逻辑有问题吗？
我考虑过只计算空白区块的曼哈顿距离，但当空白区块位于正确位置但其他区块放错位置时，会导致状态的估计成本为零。
曼哈顿距离启发式算法是可以接受的，因为它可以独立地考虑每个瓦片（实际上瓦片彼此干扰）。 所以这是乐观的。
在你的例子中，所有瓦片的目标位置距离总和为5（瓦片5,9,10,11,15每个需要移动一次）。
链接地址: http://www.djcxy.com/p/65571.html