A*搜索算法启发式函数

Question

我正在尝试使用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）。

我尝试了两个版本。虽然分割距离给出了更好的到达目标的最终路径成本，但它访问了更多的节点=>花费的时间比未分割的要多。如何正确计算？我应该使用哪一个？

- safyia

Answer 1

对于这个问题，什么是一个可接受的启发式函数并不明显，所以我不会说：“使用除以二的函数。”但我会告诉你，你提出的那个朴素函数是不可接受的，因此不会给你良好的性能。为了使A*正常工作，必须使用可接受的启发式；为了是可接受的，启发式必须绝对始终给出乐观的估计。正如你在例子中强调的那样，这个启发式函数并没有做到这一点。

（虽然现在我想起来，除以二似乎是强制可接受性的一个合理方法。但我不会承诺。）

- Novak

---

我愿意承诺除以2。你能做到的最好的事情就是以1的代价移动2个空间。因此，除以2会给你一个最佳情况，这将是可接受和一致的。 - seaotternerd

Answer 2

你的启发式不可接受，因此你的A*算法不能保证每次都找到最优解。一个可接受的启发式必须永远不会高估成本。

比将启发式成本除以3更好的启发式是：不是将每个字母的距离D加到其最终位置，而是加上ceil(D/2)。这样，距离为1或2的字母得到1的值，距离为3或4的字母得到2的值，依此类推。

- nbarriga