有人可以向我解释一下在解决 n 谜题时直线距离启发式会是什么样子吗？例如，对于 8x8 的拼图，您将如何应用直线距离？这是一个谜题示例:
7 3 4
5 _ 6
8 2 1
最佳答案
让我们回顾一下基本几何，众所周知，两点之间的最短路径是一条直线。
因此，考虑一个 8 拼图，两个图 block 之间的直线距离是从图 block A 到图 block B 所需的图 block 数量，无论是对角线、水平线还是垂直线。
考虑到您问题中的示例，我们将 d(a,b) 称为图 block a 和 b 之间的直线距离:
- d(1,_) = 1
- d(1,2) = 1
- d(1,3) = 2 = d(1,6) + d(6,3) = d(1,_ ) + d(_,3)
- d(1,4) = 2
等等。
我们现在可以将该定义推广到 n 谜题。请记住，允许对角线、水平、垂直 3 个步骤。在这种情况下，启发式通常是最佳的。
注意:记住城市之间的直线定义。
关于heuristics - n 谜题的直线距离启发式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33185115/