algorithm - 为什么我的 A* 算法启发式算法 Not Acceptable ？

Question

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

我确定会起作用的启发式方法(既可接受又一致)是这样的:

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

我还缓存了先前计算的距离，因此如果之前在另一个状态计算中已经完成，则不会完成 astar 搜索以查找最近的弹丸。它能够很快解决问题，并且结果是最优的。

当我在 autograder 中使用这个算法时，它没有通过可接受性测试。

别担心，我不是要解决问题，只是为什么我现在的解决方案不被接受？当我在脑海中浏览图片中的示例时，启发式永远不会高估成本。

因此，如果有人能够理解这一点，并且有任何想法，我们将不胜感激!

Answer 1

A* 的启发式算法需要提供一个不超过最佳成本的数字。您的启发式方法是一种貌似贪婪的解决方案，但不能保证这一点。假设只有一行弹丸，而吃 bean 人稍微偏离这条线的中心。最便宜的解决方案是找出线的哪一端最近，吃掉所有的颗粒直到该线的末端，然后向另一个方向移动以吃掉所有其他颗粒，而不必在线的较长一半处倒转。

你的贪婪启发式算法首先移动到离吃 bean 人最近的那个球，它可能不是距离最短的那一侧，所以在这种情况下，它可能不会返回不大于最优成本的成本 - 它返回成本可能不是最优的解决方案。