artificial-intelligence - 什么时候一种启发式比另一种更好？

Question

我回答了一个问题，其中给出了两个启发式算法，要对其进行 A* 以找到从起始状态到目标状态的路径。

其中一种启发式方法通过减少一个节点的扩展找到了一条路径 - 现在出于这个原因，我们可以说这种启发式方法比另一种更好吗？

谢谢!

Answer 1

我们不能仅仅因为一种启发式算法在一个问题示例上扩展的节点较少就说它比另一种“更好”。在下一个示例中，“更好”的启发式可能会比另一个扩展更多的节点。

我们知道，启发式估计不能超过实际距离，如果它是可接受的。换句话说，启发式函数的构建方式必须使其在任何情况下都不会高估到目标的距离。

那么，如果一种启发式方法更接近而不超过实际距离，则可以认为它“更好”，这是有道理的。如果您使用的启发式算法表明任意两个节点之间的距离为 1(或任何小于最短边长的值)，您最终会扩展很多节点。随着估计值越来越接近实际距离，您更有可能更早地消除路径。

当然，还有其他定义“更好”的方法，例如更容易计算。