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

“建议一个启发式机制，使用爬山算法来解决这个问题。（S=起点，F=终点/目标）。不允许对角移动。”

由于显然曼哈顿距离或欧几里得距离会将机器人发送到(3,4)，而且不允许回溯，那么解决这个问题的可能方案（启发式机制）是什么？

编辑：为了使问题更清晰，我已经在棋盘上标记了一些曼哈顿距离：

显然，使用曼哈顿距离，机器人的下一步将是(3,4)，因为它的启发式值为2 – 爬山算法会选择它并永远卡住。目标是尝试找到合适的启发式算法，避免走这条路。

回答：

我把障碍视为热源，并且热量会上升。我将一个单元格的净成本定义为到F的曼哈顿距离加上一个热量惩罚的总和。因此，有一种吸引力将机器人拉向F，同时也有一种排斥力使其远离障碍物。

有两种类型的热量惩罚：

1) 接触障碍物非常不好。查看给定单元格下方一行的相邻2到3个单元格。对于直接在给定单元格下方的每个障碍单元格加15分，对于直接在下方的对角相邻单元格加10分。

2) 对于没有直接接触到障碍物的单元格——热量更加分散。我计算它为单元格所在列及其相邻列下方障碍块平均数的6倍。

以下显示了将这些因素结合起来的结果，以及从S到F的路径：

关键点在于，平均值的方式使得机器人在到达顶行时会向左转而不是向右转。左侧未加热的列使那个方向更凉爽。有趣的是，注意到所有单元格（除了右上角的两个单元格可能例外）都被这种启发式方法吸引到F。