Akh*_*hil 8 algorithm artificial-intelligence heuristics a-star
在计算1个瓷砖的移动时,是否可以导致其他瓷砖达到目标状态？因此,计算每个瓷砖可以给我们的计数超过达到目标状态所需的最小移动量？
这个问题是针对15-Puzzle的曼哈顿距离.
以下是不同的问题:
我们可以使用曼哈顿距离作为N-Puzzle的可接受启发式算法.要实现A*搜索,我们需要一个可接受的启发式算法.曼哈顿启发式是候选人吗？如果是,你如何反驳上述论点(问题的前3个句子)？
定义: A*是一种搜索算法.它使用启发式函数来确定到目标的估计距离.只要这个启发式函数永远不会高估到目标的距离,算法将找到最短路径,可能比广度优先搜索更快.满足该条件的启发式是可以接受的.
San*_*nto 13
可接受的启发式方法不能高估解决此问题的动作数量.由于您一次只能在4个方向中的一个方向上移动块1,因此每个块的最佳方案是它具有到目标状态的清晰,无障碍的路径.这是1的MD.
状态的一对块的其余部分是次优的,这意味着它会采取比MD更多的动作来获得在正确的地方块.因此,启发式算法永远不会过度估计并且是可以接受的.
当有人发布正确的正式版本时,我会删除.
形式证明:根据h的定义,h(s*)= 0,如果s*是目标状态.假设通过矛盾证明某些初始状态s0的C*<h(s0).请注意,由于每个动作只能移动一个图块,因此执行动作最多可以将h减少一个.由于可以在C*动作中达到目标,我们有h(s*)≥h(s0) - C*> 0,这使我们产生矛盾,因为h(s*)应该为零.因此,我们必须有h(s0)≤C*forall s0,并且h是可接受的.(资料来源:加州大学欧文分校)