我正在尝试使用 A* 算法找到任何长度的滑动块拼图的最佳解决方案。
滑动块拼图是一种游戏，白色(W)和黑色瓷砖(B)排列在一个线性游戏板上，有一个空的空间(-)。给定棋盘的初始状态，游戏的目的是将瓷砖排列成目标图案。
例如，我目前在板上的状态是 BBW-WWB，我必须达到 BBB-WWW 状态。
瓷砖可以通过以下方式移动:
1.滑入相邻的空白空间，成本为1。
2. 以 1 的成本跳过另一块瓷砖进入空白空间。
3. 以 2 的代价跳过 2 个瓷砖进入空白区域。
我已经实现了一切，但我不确定启发式函数。它计算当前状态下错放的瓷砖到目标状态下最接近的相同颜色瓷砖的最短距离(最小成本)。
考虑到当前状态 BWB-W 和目标状态 BB-WW 的给定问题，启发式函数给了我 3 的结果。(根据最小距离:B=0 + W=2 + B=1 + W=0)。但是达到目标的实际成本不是 3(移动错位的 W => 成本 1 然后移动错位的 B => 成本 1)而是 2。
我的问题是:我应该以这种方式计算最小距离而不关心高估，还是应该将其除以 2？根据瓷砖的移动方式，相同的成本可以克服两倍的瓷砖(参见移动 1 和 2)。
我试过两个版本。虽然划分的距离为实现的目标提供了更好的最终路径成本，但它访问的节点更多 => 比未划分的节点花费更多的时间。计算它的正确方法是什么？我应该使用哪一种？
最佳答案
对于这个问题的可接受启发式函数是什么样的，我不太清楚，所以我不会 promise 说，“使用除以二的函数”。但是我会告诉你，你想出的天真的函数是 Not Acceptable ，因此不会给你很好的表现。为了让 A* 正常工作，所使用的启发式方法必须是可接受的；为了被接受，启发式必须绝对总是给出一个乐观的估计。这个没有，这正是您在示例中突出显示的原因。
(尽管现在我考虑了一下，除以二似乎是强制受理的合理方法。我只是不打算 promise 。)
关于artificial-intelligence - A*搜索算法启发式函数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13547950/