曼哈顿如何远离可接受的启发式？
在计算1个瓦片的移动数量时是否会导致其他瓦片达到其目标状态？ 因此，为每个瓦片计数可以给我们一个比达到目标状态所需的最小移动更多的计数？
这个问题是在曼哈顿距离为15-益智。
这是用不同的话来说的问题：
我们可以使用曼哈顿距离作为N-Puzzle的可接受启发法。 为了实现A *搜索，我们需要一个可接受的启发式。 曼哈顿启发式是候选人吗？ 如果是的话，你如何反驳上述论点（问题中的前三句话）？
定义：A *是一种搜索算法。 它使用启发式函数来确定到目标的估计距离。 只要这种启发式功能永远不会高估与目标的距离，该算法将找到最短路径，可能比广度优先搜索更快。 满足该条件的启发式是可以接受的。
可接受的启发法不能高估解决此问题的举措数量。 由于每次只能在4个方向中的一个方向上移动块1，因此每个块的最佳方案是它具有通向其目标状态的清晰无障碍路径。 这是1的MD。
对于一对块的其余状态是次优的，这意味着它需要比MD更多的动作才能将块放在正确的位置。 因此，启发式不会高估并且可以接受。
当有人发布正确的正式版本时，我会删除。
正式证明：根据h，h（s *）= 0的定义，如果s *是目标状态。 假设通过矛盾论证C * <h（s0）为某个初始状态s0。 请注意，由于每个动作只能移动一个图块，因此执行动作最多可以将h减1。 由于可以在C *行为中达到目标，所以我们有h（s *）≥h（s0） - C *> 0，这引起了矛盾，因为h（s *）应该为零。 因此，我们必须有h（s0）≤C* s0，并且h是可接受的。 （ 来源 ：加州大学欧文分校）
链接地址: http://www.djcxy.com/p/65555.html