algorithm - 为什么需要选择接近实际路径成本的启发式算法？

Question

我是一名计算机科学专业的学生，​​目前正在学习有关人工智能的类(class)。本主题涵盖各种最佳优先搜索寻路算法，例如 A* 搜索。

我的学习 Material 声称通常会按照以下规则选择启发式:

0 ≤ h(n) ≤ h(n)*

我明白这一点，但在那之后 Material 声称你的启发式应该是乐观的或接近 f(n)。根据 Material ，这应该导致更少的节点被扩展。

为什么(并且您应该)选择一个尽可能接近 f(n) 的启发式算法，为什么这会导致(大量)较少的节点被扩展？

预先感谢您的回复，您将在我的下一次考试中帮助我!

Answer 1

示例:

在棋盘状带障碍物的 field 上找到通往特定 field 的最短路径。假设您只能向左向右向上或向下移动。启发式让您猜测在每次迭代中您可以到达的四个可能字段中的每一个字段需要多少步才能达到目标。

现在您的启发式可以是:

始终是最优的:如果是这种情况，您将始终转到正确的下一个字段并最初找到您的最佳路径。

始终较低或最优:这里可能会出现您有时去错了字段，但如果您达到了目标(或稍后查看字段)，您的算法将看到您找到的路径(或实际的启发式)大于您之前应该去过的领域的启发式。

换句话说:您的启发式方法总是比您必须执行的实际步数要少或相等。因此，如果您发现一条路径短于或等于您未访问过的所有启发式文件，您可以确定您的路径是最优的。

“有时更高”如果您的启发式算法有时给您的步数比您实际需要的步数多，您永远无法确定您找到的路径是最佳路径!

因此，最糟糕的情况是您的启发式方法高估路径，因为您可能找不到最佳路径。因此你有条件 0 ≤ h(n) ≤ h(n)*并且您越接近最佳启发式，您在搜索中访问的“错误字段”就越少。您访问的错误字段越少，您的速度就越快。