我在阅读关于搜索算法和启发式搜索的内容时，对启发式函数和评估函数有些困惑。人们似乎很随意地使用这两个术语来描述看似相同的事物。我错过了什么？

回答：

这个问题可能会引起混淆，因为启发式在不同语境中有不同的含义。让我先谈谈启发式的不同含义，然后我们再回到评估函数的话题。

单代理启发式搜索

在单代理启发式搜索（例如A*、IDA*）中，启发式通常被描述为“可接受的”或“一致的”。在这种情况下，启发式是达到目标成本的下限。也就是说，它们是一个返回数值的函数的结果。如果启发式是“可接受的”，返回的值不会高估到目标的真实距离。如果启发式是“一致的”，相邻状态之间的启发式值变化不会超过边的成本。一致的启发式在目标的启发式值为0时是可接受的，但并非所有可接受的启发式都是一致的。

关于启发式与算法的组合，已证明了许多特性。A*和IDA*在使用一致的启发式时可以找到最优路径。A*在使用一致的启发式时在必要节点扩展方面是最优的，但如果使用不一致的启发式，A*可能会对N个状态进行2^N次扩展。（参见这个演示以了解这种情况的示例。）

游戏玩法

在使用alpha-beta或蒙特卡洛树搜索（MCTS）等算法的游戏程序中，启发式代表对游戏胜负值的近似。例如，值可能在-1（输）到+1（赢）之间进行缩放，中间值代表对真实值的不确定性。在这里，没有低估或高估的保证，但值的排序越好（赢>平>输），算法的性能就越好。即使对启发式应用仿射变换，alpha-beta剪枝也会返回相同的结果，因为alpha-beta使用值的相对顺序进行搜索。参见这篇论文以了解MCTS中的启发式示例。请注意，在这种情况下，启发式仍然具有数值。

优化

在寻找优化问题（如SAT（可满足性问题）或CSP（约束满足问题））的解决方案时，如果算法能够快速找到好的解决方案，它们的效率会更高。因此，它们不是以天真的方式进行搜索，而是以一种预期更有效的方式对搜索进行排序。如果排序好，搜索可能能够更早终止，但这并不能保证。在这种情况下，启发式是一种排序选择的方式，可能会更快地找到解决方案。（在SAT或CSP中变量的满足赋值。）这里是一个例子，探索了这些问题不同排序启发式的研究工作。

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

评估函数

那么，评估函数是什么呢？它最常用于第二个游戏语境中，在那里启发式函数和评估函数可以互换使用，但更普遍地指的是对状态的数值评估。主要的一点是，评估函数比启发式函数更具体，因为启发式在更广泛的语境中有更广泛的用途。