寻找适当的启发式机制来进行爬山算法

Question

以下问题是我从一门人工智能课程中找到的考试练习题目。

提出一种启发式机制，使用山峰爬升算法解决此问题。（S=起点，F=终点/目标）。不允许对角线移动。由于明显的曼哈顿距离或欧几里得距离会将机器人发送到（3,4），且不允许回溯，因此有什么可能的解决方案（启发式机制）来解决这个问题？编辑：为了使问题更清晰，我在板上标记了一些曼哈顿距离。

很明显，使用曼哈顿距离，机器人的下一步移动将会在(3,4)，因为它具有启发式值2 - HC将选择该点并永远卡住。我们的目标是通过找到合适的启发式算法，尽可能避免走这条路。

- GengisKhan

---

不太清楚你的问题是什么。你是要用“爬山算法”来优化位置还是路径？如果是后者，你可以从起点到终点直接画一条路径，并且通过“爬山算法”逐渐减少路径上的障碍物，直到找到一条完全没有障碍物的路径。 - tobias_k

谢谢您的回复！“机器人”，让我们称其为从S开始的对象，将使用HC算法移动。它不会用于优化-唯一的目的是通过启发式机制强制它移动到F盒子。我们需要找到那种机制，可以避免其困在S盒子下。 - GengisKhan

我认为问题仍未明确定义。我将爬山算法理解为局部搜索，这意味着启发式函数只能考虑局部信息（如相邻的“状态”）。在这种情况下，如果使用位置作为状态（而不是整个路径），我认为这是不可能的。但是，如果您的启发式函数没有其他限制，您可以说：“使用A *搜索算法将移动到距离F最近的相邻方格”（即使用完整的A *搜索作为贪婪搜索的启发式）。 - tobias_k

Answer 1

我认为障碍物是热的，而且热气会向上升。我将一个单元格的净成本定义为到F的曼哈顿距离之和加上一个热度惩罚。因此，有一种吸引力把机器人朝向F，还有一种排斥力使其远离障碍物。

这里有两种类型的热度惩罚：

1）触碰障碍物非常不好。查看给定单元格下面一行中的2或3个相邻单元格。对于每个直接在给定单元格下方的障碍单元格，添加15，对于每个在给定单元格下方的对角线邻居，添加10。

2）对于没有直接接触障碍物的单元格，热度更加扩散。我计算它为每个单元格下面所有阻碍块数的平均值乘以6，包括它所在列和相邻列中的阻碍块数。

以下展示了所有内容的组合结果以及从S到F的路径： 一个关键点是平均化如何导致机器人在撞到顶行时向左转而不是向右。左侧的未加热列使其成为更凉爽的方向。有趣的是，所有单元格（可能除了右上角的两个单元格）都被这种启发式方法吸引到F。

- John Coleman

---

太棒了，非常好的解决方案！ - GengisKhan

这对于特定的地图有效，但它做了很多假设。例如，为什么只计算向南的障碍物？如果F字段在S的北面，并且中间有障碍物，这将会出现问题。此外，如果机器人必须通过狭窄的瓶颈才能到达目标，则会失败。但是，任务中的文本明确要求启发式解决“此问题”，而不是“此类问题”，所以点赞！只是想指出。 - tobias_k

@tobias_k 很好的观点。我认为如果没有回溯，很难找到适用于所有这类问题的通用启发式方法。例如，您可能需要穿过一堆障碍物才能到达目标单元格。 - John Coleman

另一个小修正：对于“死路”的曼哈顿距离应该是2，而不是4，但这并不会改变结果。 - tobias_k

@tobias_k 谢谢 - 现在应该已经修复了。 - John Coleman