高级搜索之A星算法教材课件.ppt

高级搜索算法之A*
第1页，共46页。
A算法
在BFS搜索算法中，如果能在搜索的每一步都利用估价函数f(n)=g(n)+h(n)对Open表(队列）中的节点进行排序，则该搜索算法为A算法。由于估价函数中带有问题自身的启发性信向父节点的指针，然后转第(2)步。
第8页，共46页。
由于这一算法的第六步仅仅是把刚生成的子节点按其估价函数值从小到大放入Open表中，这样在算法第(3)步取出的节点仅是刚生成的子节点中估价函数值最小的一个节点。因此，它是一种局部择优的搜索方式。
对这一算法进一步分析也可以发现：如果取估价函数f(n)=g(n)，则它将退化为代价树的深度优先搜索；如果取估价函数f(n)=d(n)，则它将退化为深度优先搜索。可见，深度优先搜索和代价树的深度优先搜索是局部择优搜索的两个特例。
第9页，共46页。
A*算法
上一节讨论的启发式搜索算法，都没有对估价函数f(n)做任何限制。实际上，估价函数对搜索过程是十分重要的，如果选择不当，则有可能找不到问题的解，或者找到的不是问题的最优解。为此，需要对估价函数进行某些限制。A*算法就是对估价函数加上一些限制后得到的一种启发式搜索算法。
第10页，共46页。
假设f*(n)为从初始节点S0出发，经过节点n到达目标节点的最小代价值(真实值）。估价函数f(n)则是f*(n)的估计值。显然，f*(n)应由以下两部分所组成：一部分是从初始节点S0到节点n的最小代价，记为g*(n)；另一部分是从节点n到目标节点的最小代价，记为h*(n)，当问题有多个目标节点时，应选取其中代价最小的一个。因此有
f*(n)=g*(n) +h*(n)
把估价函数f(n)与 f*(n)相比，g(n)是对g*(n)的一个估计，h(n)是对h*(n)的一个估计。在这两个估计中，尽管g(n)的值容易计算，但它不一定就是从初始节点S0到节点n的真正最小代价，很有可能从初始节点S0到节点n的真正最小代价还没有找到，故有
第11页，共46页。
有了g*(n) 和h*(n)的定义，如果我们对A算法（全局择优的启发式搜索算法）中的g(n)和h(n)分别提出如下限制：
g(n)是对g*(n)的估计，且g(n)>0；
h(n)是对h*(n)的下界，即对任意节点n均有
则称得到的算法为A*算法。
第12页，共46页。
A * 算法伪代码：
open=[Start]
closed=[]
while open不为空 {
从open中取出估价最小的结点n
if n == Target then
return 从Start到n的路径 // 找到了！！！
else {
for n的每个子结点x {
if x in open {
计算新的f(x)
比较open表中的旧f(x)和新f(x)
if 新f(x) < 旧f(x) {
使用新f(x)来更新open表
}
}
else if x in closed {
计算新的f(x)
比较closed表中的旧f(x)和新f(x)
if 新f(x) < 旧f(x) {
remove x from closed
add x to open
}
}
第13页，共46页。
else {
// x不在open，也不在close，是遇到的新结点
计算f(x) add x to open
}
}
add n to closed //同时需要保存f(x)
}
}
//open表为空表示搜索结束了，那就意味着无解！
第14页，共46页。
1．A*算法的可纳性
一般来说，对任意一个状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法能在有限步内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可纳的。A*算法是可纳的。下面我们分三步来证明这一结论(暂且只考虑有限图）。
第15页，共46页。
定理1
对有限图，如果从初始节点S0到目标节点Sg有路径存在，则算法A*一定成功结束。
第16页，共46页。