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

Question

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

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

谢谢！

Answer 1

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

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

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

当然还有其他定义方法"better"，比如更容易计算。