一致启发式函数的总和是否也一致?

人工智能 搜索 证明 启发式 可接受的启发式 一致启发式
2021-11-07 16:04:04

假设我们有一组启发式函数{hi}i=1N, 其中每个hi是可接受的和一致的(单调的)。i=1Nhi是否仍然一致?

是否有任何证据或反例来证明这一矛盾?

1个回答

不,它不一定是一致的或可接受的。考虑这个例子,其中s是开始,g是目标,它们之间的距离是1。

小号 --1-- 克

假使,假设h0h1是完美的启发式。然后h0(s)=1h1(s)=1. 在这种情况下,启发式是不可接受的,因为h0(s)+h1(s)=2>d(s,g). 类似地,作为无向图,启发式将是不一致的,因为|h(s)h(g)|>d(s,g).

如果您想了解启发式总和一致且可接受的条件,我会查看关于additive PDB heuristics的工作。