artificial-intelligence - 为什么可接受的启发式有效？

Question

我在 A* 搜索算法的上下文中遇到了可接受的启发式算法这个术语。有人可以解释（或给出直觉）为什么启发式函数 h 只有在不高估实际距离的情况下才可接受？

score 2 · Accepted Answer

考虑 A* 的停止条件，如果算法以某个F值到达目标节点，则算法停止，其中F等于G- 从起点构造的路径加上H表示对目标剩余路径的估计的启发式值.

在目标节点，F等于G，因为到达目标的剩余路径的估计为 0。

停止条件只有在H可接受的情况下才有效，因此我们可以确定如果F我们在目标节点计算的值小于F我们在任何其他节点计算的任何其他值，我们肯定可以确定它是最短路径，因为没有其他路径可能以较小的F值到达目标。

如果它不被接受，那么我们计算F的其他节点可能会高估到达目标的剩余路径，并且我们不能停止算法，因为可能存在更短的路径。

score 1 · Accepted Answer

对于那些不寻求免费和免费提供的资源的人。

在计算机科学中，特别是在与寻路相关的算法中，如果启发式函数从不高估达到目标的成本，即它估计达到目标的成本不高于当前可能的最低成本，则认为它是可接受的。指向路径。可接受的启发式也称为乐观启发式。

这是维基百科的链接：

关于第二个问题

当启发式算法没有高估真实成本时，它是可以接受的，仅仅是因为它是这样定义的。