artificial-intelligence - 可接受的启发式函数

Question

我知道可接受的启发式函数低估了目标的实际成本，但我想得出结论，作为两个可接受的启发式函数(h1 和 h2)之和的启发式函数 h3 都可以接受，如果没有进一步给出了关于 h1 和 h2 的信息。您认为这是正确的主张吗？

谢谢

Answer 1

可接受的启发式算法永远不会高估从节点到目标节点的最小成本路径的成本。因此，启发式算法特定于特定的状态空间，也特定于该状态空间中的特定目标状态。对于该搜索空间中的所有状态，它必须是可接受的。为了帮助记住它是“永不高估”还是“永不低估”，只需记住可接受的启发式过于乐观。它将导致 A* 搜索结果证明比最优路径成本更高的路径。它不会通过产生过高的启发式 h 值来阻止 A* 扩展最佳路径上的节点。对启发式的更强要求是它是一致的，有时称为单调的。如果启发式 h 的值沿路径不递减，则启发式 h 是一致的。从数学上讲，如果对于父节点 p 的每个节点 n，启发式 h 是一致的，