搜索问题3.ppt

人工智能基础
A*算法和其他搜索算法
1
A*算法分析
完备的
最优的
效率最优的
但,在搜索空间中处于目标等值线内的节点数仍然是解长度的指数级,
并且,它在内存空间中保存了所有的节点。
2
最佳图搜索算法A*(A*算法)
在A算法中,如果满足条件:
h(n)≤h*(n)
则A算法称为A*算法。
评估函数f *:
f*(n) = g* (n)+h* (n)
g* (n)为起始节点到节点n的最短路径的代价,
h* (n)是从n到目标节点的最短路径的代价。
这样f * (n)就是从起始节点出发通过节点n到达目标节点的最佳路径的总代价的估值。
3
A*条件举例
8数码问题
h1(n) = “不在位”的将牌数
h2(n) = 将牌“不在位”的距离和
2 8 3
1 6 4
7 5
1 2 3
4
5
7 6
8
将牌1:1
将牌2:1
将牌6:1
将牌8:2
4
A*算法的性质
A*算法的假设
设ni、nj是任意两个节点,有:
C(ni, nj) > 
其中为大于0的常数
几个等式
f*(s) = f*(t) = h*(s) = g*(t) = f*(n)
其中s是初始节点,t是目标节点,n是s到t的最佳路径上的节点。
5
A*算法的性质(续1)
:
对有限图,如果从初始节点s到目标节点t有路径存在,则算法A一定成功结束。
6
A*算法的性质(续2)
:
对无限图,若有从初始节点s到目标节点t的路径,则A*不结束时,在OPEN表中即使最小的一个f值也将增到任意大,或有f(n)>f*(s)。
7
A*算法的性质(续3)
:
A*结束前,OPEN表中必存在f(n)≤f*(s)。
存在一个节点n,n在
最佳路径上。
f(n) = g(n) + h(n)
= g*(n)+h(n)
≤g*(n)+h*(n)
= f*(n)
= f*(s)
8
A*算法的性质(续3)
:
对无限图,若从初始节点s到目标节点t有路径存在,则A*一定成功结束。
:A*如果不结束,则OPEN中所有的n有f(n) > f*(s)
:在A*结束前,必存在节点n,使得 f(n) ≤ f*(s)
所以,如果A*不结束,将导致矛盾。
9
A*算法的性质(续4)
:
OPEN表上任一具有f(n)<f*(s)的节点n,最终都将被A*选作扩展的节点。
,知A*一定结束,由A*的结束条件,OPEN表中f(t)最小时才结束。而
f(t) ≥ f*(t) = f*(s)
所以f(n)<f*(s)的n,均被扩展。得证。
10