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

Question

5

我正在学习公开课程CS 188，网址为edx.org。目前我需要为A*搜索开发一种启发式算法以吃掉所有的小球，如下所示： Pacman

我设计的启发式算法应该是可行且一致的，具体步骤如下：

初始化启发式累加器h为0
将pos初始化为pacman的当前位置
当小球未被吃完时：
- 使用astar搜索（以曼哈顿距离作为启发式）获取最近的小球
- 将距离添加到h中
- 从小球列表中删除该小球
- 将pos设置为小球的位置

我还缓存了先前计算的距离，因此在另一个状态的计算中已经完成寻找最近小球的astar搜索时，不必再进行搜索。它能够快速解决问题，并且结果是最优的。

当我在自动评分程序中使用这个算法时，它未通过可接受性测试。

不要担心，我不是在寻求解决问题的方法，只是想知道为什么我的当前解决方案不可接受？当我在脑海中浏览图片示例时，启发式算法从未高估成本。

因此，如果有人能够理解这一点，并且有任何想法，您的意见将不胜感激！

- Zach

你确定你的距离函数正确地考虑了墙壁吗？ - Leeor

5

整个过程不是旨在进行A*搜索，而仅仅是为了到达最近的豆子吗？ - Bernhard Barker

@Dukeling，整个搜索如何使用A*算法？搜索中没有单一的“目标”。@Zach：你能发布或链接到问题或疑问的确切描述吗？曼哈顿距离肯定是可接受的；也许你的代码存在一个偏差错误，当路上没有障碍物时，启发式函数的值比实际代价多1？ - tobias_k

1

@tobias_k 吃掉所有的小球似乎是一个非常合理的目标。 - Bernhard Barker

@Dukeling 你说得对，我想得太多只是关于路径规划的问题了... - tobias_k

@Zach，您是否需要尽量缩短路程以吃掉所有的颗粒？如果是，则您的启发式算法是局部算法，因此不能保证获得良好的解决方案。 - Vikram Bhat

2个回答

1

这是一种为您的问题设置启发式的方法。首先，如果您的目标是在最短距离内吃掉所有小球，那么您的解决方案过于贪心，无法实现可行的解决方案。以下是重新设计启发式的方法：

目标：在最短路径长度内吃掉所有小球。

启发式估计值：

1. 使用A*独立计算当前位置到小球的所有最短路径。

2. 成本函数：（从当前位置出发到所有未访问的小球最短路径之和）* 2 + 到起始状态的总距离。

成本函数是上限。

注意：可能有更有效的方法来计算每个状态下到未吃掉的小球的最短路径。需要进行一些研究。

- Vikram Bhat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mcdowella · Accepted Answer

A*算法的启发式函数需要提供一个不超过最佳路径长度的数字。你的启发式函数是一种可行的贪心解决方案，但不能保证这一点。假设有一条小球线，并且吃豆人略微偏离于该线的中心。最便宜的解决方案是找出哪一端距离更近，吃掉该线末端的所有豆子，然后向另一端移动以吃掉所有其他豆子而无需在较长的一半线路中倒车。

你的贪心启发式策略会先移动到距离吃豆人最近的豆子，这可能不是最短距离的那一端，所以在这种情况下它可能不能返回一个不大于最优路径长度的代价值——它返回的是一个可能不是最优的解决方案的代价值。