当计算一个牌的移动次数时,会导致其他牌进入目标状态,这不是真的吗?因此,计算每一个平铺可以给我们一个比达到目标状态所需的最小移动更多的计数?
这个问题是在曼哈顿距离15个谜题的背景下提出的。
这里有一个不同的问题:
我们能用曼哈顿距离作为n字谜的一个可容许启发式吗?为了实现一个*搜索,我们需要一个可容许的启发式算法。曼哈顿的启发是候选人吗?如果是,你如何反驳上述论点(问题的前三句话)?
定义:A*是一种搜索算法。它使用启发式函数来确定到目标的估计距离。只要这个启发式函数永远不会高估到目标的距离,算法就会找到最短的路径,可能比广度优先搜索要快。满足该条件的启发式是可接受的。
最佳答案
可接受的启发式方法不能高估解决这个问题的步骤数。由于一次只能在4个方向中的一个方向移动块1,因此每个块的最佳方案是,它有一条清晰、无障碍的路径指向其目标状态。这是1的医学博士。
一对块的其余状态是次优的,这意味着它需要比M.D.更多的移动才能使块位于正确的位置。因此,启发式永远不会过度估计,并且是可接受的。
我会删除当有人张贴一个正确的,正式的版本。