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

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

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

将名为h的启发式累加器初始化为0

将pos初始化为pacman的当前位置

虽然没有吃颗粒:

使用astar搜索(曼哈顿距离作为启发式)从pos获取最近的颗粒

添加到h的距离

从颗粒中取出颗粒

将pos设置为颗粒的位置

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

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

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

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