曼哈顿距离是如何允许的启发式？

Question

难道在计算1个磁贴的移动量时会导致其他磁贴达到目标状态吗？因此，为每个图块计数可以使我们获得比达到目标状态所需的最小移动还要多的计数？

此问题与曼哈顿距离有关，为15个谜题。

这里是问题的不同说法：

我们可以使用曼哈顿距离作为N-Puzzle的允许启发式方法。要实施A *搜索，我们需要允许的启发式方法。曼哈顿启发式技术是候选人吗？如果是，您如何反驳上述论点（问题的前3个句子）？

定义：A*是一种搜索算法。它使用启发式函数来确定到目标​​的估计距离。只要此启发式函数永远不会高估到目标的距离，该算法将找到最短的路径，可能比广度优先搜索要快。满足该条件的启发式方法是admissable。

Answer 1

可允许的试探法不得高估解决此问题的步骤数。由于一次只能将块移动1个，并且只能在4个方向中的一个方向上移动，因此每个块的最佳方案是它具有通往目标状态的清晰无阻的路径。这是1的医学博士。

Answer 2

正式证明：根据h的定义，如果s ∗是目标状态，则h（s ∗）= 0。提出矛盾证明对于某些初始状态s0，C ∗ 0，这使我们得出因为h（s ∗）应该为零，所以存在矛盾。因此，我们必须使h（s0）≤C ∗s0，并且h是允许的。（来源