Tip:
Highlight text to annotate it
X
给你们一个直观感受
为什么最优启发函数h可以找到最小消耗路径
当A*搜索结束,他会返回一条路径p,和预计消耗c
c还是实际消耗
因为在目标处h为0
所以路径消耗是由h函数估计出的总消耗
现在,所有在边界上的所有路径
它们的估计值都大于c
然后由于边界节点的访问顺序是最小消耗优先
如果h最优
那么估计得消耗应该小于实际消耗
所以路径p的消耗应该小于
边界上任何一条路径的实际消耗
所有超过边界的路径
都应该比这个要大
因为我们一致同义每一步的消耗应该大于0
这意味着路径p一定为最小消耗路径
我必须说这段推理
只适用于树搜索
对于图搜索情况会更复杂一些
但直观的感受其实差不多