问启发式函数与评价函数的区别

EN

在这个问题上可能会出现混乱，因为启发式在不同的上下文中意味着不同的事情。那么，让我谈谈启发式的不同含义。然后，我们可以返回到评估函数。

单Agent启发式搜索

在单agent启发式搜索(如A*，IDA*)中，启发式通常以可接受或一致的词语限定。在这种情况下，启发式是达到目标的成本的下限。也就是说，它们是返回数值的函数的结果。如果启发式是可接受的，返回的值不会高估到目标的真实距离。如果启发式是一致的，相邻状态之间的启发式变化永远不会超过边缘代价。如果目标的启发式为0，则一致启发式是可接受的，但并不是所有允许的启发式都是一致的。

启发式和算法的结合证明了许多特性。A*和IDA*将用一致的启发式找到最优路径。A*在具有一致启发式的必要节点展开中是最优的，但用不一致的启发式A*可以执行N状态的2^N展开。(有关发生这种情况的示例，请参阅这个演示。)

游戏玩

在使用α-β算法或蒙特卡洛树搜索算法(MCTS)的游戏程序中，启发式算法代表了游戏胜负值的近似。例如，该值可能在-1 (损失)和+1 (win)之间进行缩放，其中的值在两者之间表示对真实值的不确定性。这里没有关于低估或过高估计的保证，但是值的排序越好(wins > Here >损耗)，算法的性能就越好。即使将仿射变换应用于启发式，α-β剪枝也会返回相同的结果，因为α-β使用了值的相对顺序进行搜索。有关MCTS中的启发式示例，请参见本论文。请注意，在这种情况下，启发式仍然有一个数值。

优化

在寻找诸如SAT (可满足性问题)或CSP (约束满意问题)这样的优化问题时，如果能快速找到好的解，算法就会效率更高。因此，他们不是以一种天真的方式进行搜索，而是以一种期望更有效的方式进行搜索。如果排序良好，搜索可能会提前结束，但这并不能保证。在这种情况下，启发式是排序选择的一种方式，最终可能会更快地找到解决方案。(在SAT或CSP.中令人满意的变量分配)工作的下面是一个例子，为这些问题探索不同的排序启发式。

在这种情况下，启发式被用于排序，所以它不必是基于数字的。如果它是基于数字的，那么这些数字不一定像在其他类型的搜索中那样具有全局意义。除了SAT和CSP之外，还有许多优化问题的变体，在这些问题中，启发式是以这种方式使用的。

评价函数

那么，什么是评价功能呢？它可能是最常用的第二种情况下的游戏，其中启发式和评估函数可以互换，但它更一般地指的是一种状态的数值评估。主要的一点是，评价函数比启发式函数更具体，因为启发式在更广泛的上下文中有广泛的应用。

评估函数(或评分函数)检查解决方案是否可行以及它有多好。通过比较2种解决方案的得分，可以看出哪一种更好(如果两者都可行)。例如:如果你从布鲁塞尔到马德里通过巴黎、里昂和马赛，距离是1000公里(=实际的道路距离)。

启发式函数也会返回类似分数的内容，但它适用于部分解，并且不需要精确。对于A*搜索，它必须是可接受的。例如:如果你通过巴黎从布鲁塞尔到马德里(其余的你还不知道)，这段距离是800公里(=从布鲁塞尔到巴黎的实际公路距离加上从巴黎到马德里的乌鸦飞行距离)。

启发式函数是问题特定的，并编码到最近的目标节点的距离。然而，评估函数并不是特定于问题的，而是由算法来决定下一步要扩展哪个节点。