artificial-intelligence - A* 搜索算法启发式函数

Question

我正在尝试使用 A* 算法找到任何长度的 slider 拼图的最佳解决方案。

slider 拼图是一种游戏，白色 (W) 和黑色 (B) 瓷砖排列在带有单个空白空间 (-) 的线性游戏板上。给定棋盘的初始状态，游戏的目的是将瓷砖排列成目标图案。

例如，我目前在板上的状态是 BBW-WWB，我必须达到 BBB-WWW 状态。
瓷砖可以通过以下方式移动:
1. 滑入相邻的空白空间，成本为 1。
2. 跳过另一 block 瓷砖进入空白区域，费用为 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)。

我尝试了两个版本。虽然分割的距离为实现的目标提供了更好的最终路径成本，但它访问了更多的节点 => 比未分割的节点花费了更多的时间。计算它的正确方法是什么？我应该使用哪一个？

Answer 1

对我来说，这个问题的可接受启发式函数是什么样的并不明显，所以我不会 promise 说，“使用除以二的函数”。但是我会告诉你，你想出的幼稚函数是 Not Acceptable ，因此不会给你带来好的性能。为了使 A* 正常工作，使用的启发式必须是可接受的；为了被接受，启发式必须绝对总是给出一个乐观的估计。这不是，正是您在示例中突出显示的原因。

(虽然现在我想起来了，除以二似乎是一种强制可接受性的合理方式。我只是不打算这样做。)