我正在学习公开提供的CS 188课程，课程链接在edx.org。目前，我需要为A*搜索开发一个启发式函数，以便吃掉所有像这里展示的豆子：
我原本确信会有效的启发式函数（既可接受又一致）是这样的：
- 初始化启发式累加器h为0
- 初始化pos为当前吃豆人的位置
- 当豆子未被吃完时：
- 使用A*搜索（以曼哈顿距离作为启发式函数）从pos获取最近的豆子
- 将距离加到h中
- 从豆子列表中移除该豆子
- 将pos设置为该豆子的位置
我还缓存了之前计算的距离，因此如果在另一个状态计算中已经完成过寻找最近豆子的A*搜索，就不会再次进行。它能够非常快速地解决问题，并且结果是最优的。
当我在自动评分系统中使用这个算法时，它未能通过可接受性测试。
不用担心，我不是在寻求问题的解决方案，只是想知道为什么我当前的解决方案不满足可接受性？当我在脑海中回顾图片中的例子时，启发式函数似乎从未高估成本。
所以，如果有人能理解这一点，并且有任何想法，您的意见将非常受欢迎！
回答：
A*算法的启发式函数需要提供一个数字，这个数字不应超过最佳可能成本。你的启发式函数是一个看似合理的贪婪解决方案，但它并不能保证这一点。假设有一排豆子，而吃豆人在这排豆子的中心位置稍偏离。最便宜的解决方案是找出哪一端更近，吃完那端的所有豆子，然后朝另一个方向移动，吃掉剩下的所有豆子，而不必在线段较长的部分倒退。
你的贪婪启发式函数首先移动到离吃豆人最近的豆子，这可能不是距离最短的那一侧，因此在这种情况下，它可能不会返回一个不高于最优成本的成本 – 它返回的是一个可能的解决方案的成本，但这可能不是最优的。
