为什么A*算法的启发式不可接受？

Question

我会通过CS 188菱向公众edx.org.现在我必须为A*搜索开发一个启发式算法来吃掉所有的颗粒,如下所示:

我确信可行的启发式方法(可接受和一致)是这样的:

• 将名为h的启发式累加器初始化为0
• 将pos初始化为pacman的当前位置
• 虽然没有吃颗粒:
  • 使用astar搜索(曼哈顿距离作为启发式)从pos获取最近的颗粒
  • 添加到h的距离
  • 从颗粒中取出颗粒
  • 将pos设置为颗粒的位置

我还缓存了先前计算的距离,因此如果在另一个状态计算之前已经完成,则不进行寻找最近的颗粒的astar搜索.它能够非常快速地解决问题,并且结果是最佳的.

当我在自动编程器中使用此算法时,它未通过可接受性测试.

别担心,我不是要求解决问题,只是为什么我目前的解决方案不被允许？当我在脑海中的图片中看到这个例子时,启发式算法永远不会过高估计成本.

因此,如果有人能够理解这一点,并有任何想法,您的意见非常感谢!

Answer 1

A*的启发式算法需要提供一个不超过最佳成本的数字.你的启发式算法是一种看似合理的贪婪解决方案,并不能保证这一点.假设有一行药丸,而且这个药品的pac-man略微偏离中心.最便宜的解决方案是找出最接近线的末端,将所有颗粒吃到该线的末端,然后沿另一个方向移动以吃掉所有其他颗粒而不必在线的较长半部分反转.

你贪婪的启发式先取小球是最近吃豆人可能不具有最短距离的一面,所以在这种情况下,它可能不会返回成本不超过最优性价比更高的动作 - 它返回一个可能的成本解决方案可能不是最佳的.