「OI之路」07其他-3启发式搜索

启发式搜索,又称A*算法

基本原则

$估价f(x)<=实际代价g(x)$
作用:
假设有两个状态
非最优A,在堆内是$s(A)+f(A)$
最优B,在堆内是$s(B)+f(B)$
即使A先出来,会拓展出$s(C)+f(C)$也就是$s(A)+g(C)-g(A)+f(C)$
既然A不是最优的,那么我们的B一定能出来

但如果违反了基本原则呢?
因为$s(A)+f(A)<s(B)+f(B)$
所以 有可能 $s(A)+g(A)+f(C)-g(C)<s(B)+f(B)$
所以这个状态又要再出来一次
(这里的ed不一定是最终状态)

练习题

Tag-启发式搜索

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/5f25.html
转载请注明出处,谢谢!