与或树搜索3启发式搜索.ppt

1

有序搜索
解树的代价
希望树
与或树的有序搜索过程
2
盲目搜索是按确定路线进行的,当要选择一个节点进行扩展时,只是根据节点在与或树中所处的位置,而没有考虑要付出的代价,因而求得的解树不一定是代价最小的解树,即不一定是最优解树。
盲目搜索小结
3
为了求得最优解树,就要在每次确定欲扩展的节点时,先往前多看几步,计算一下扩展这个节点可能要付出的代价,并选择代价最小的节点进行扩展。
根据代价决定搜索路线的方法称为与或树的有序搜索,它是一种重要的启发式搜索策略。
有序搜索
4
计算方法:
设g(x)表示节点x的代价,c(x,y)表示节点x到其子节点y的代价(即边xy的代价),则:
(1)若x是终止节点,g(x)=0;
(2) 若x是或节点, g(x)=min{c(x,yi)+g(yi)}(1≤ i≤ n, 其中 y1,y2 ,y3… yn是x的子节点)
(3) 若x是与节点, x则有两种计算公式
g(x)=∑{c(x,yi)+g(yi)} 称为和代价法;
g(x)=max{c(x,yi)+g(yi)}(1≤ i≤ n)称为最大代价法(其中 y1,y2 ,y3… yn是x的子节点)。
(4)对非终止的端节点x, g(x)=∞
解树的代价
n
i=0
x
yi
x
yi
5
例1:如图所示的与或树。
在与或树中,t1,t2,t3,t4,t5为终止节点;E,F是端节点,其代价均为∞;边上的数字是该边的代价。
由右边的解树可得:
按和代价:g(A)=11,g(S0)=13
按最大代价:g(A)=6,g(S0)=8
由左边的解树可得:
按和代价:g(G)=3, g(D)=4, g(B)=6, g(S0)=8
按最大代价:g(G)=2, g(D)=3, g(B)=5, g(S0)=7
S0
B
A
D
G
F
E
t5
t4
t3
t2
t1
2
1
1
3
2
2
1
2
1
c
5
6
2
按和代价计算,左边的解树是最优解,其代价为8; 按最大代价计算,左边的解树仍是最优解,其代价为7;
有时用不同的计算代价方法得到的最优解树不相同。
图中与或树包括两棵解树:
由S0,A,t1和t2组成;
由S0,B,D,G,t4和t5组成。
6
计算任一节点x的代价g(x)时,都要求已知其子节点yi的代价g(yi):
根据问题本身提供的启发性信息定义一个启发函数
由启发函数估算出子节点yi的代价g(yi),
按和代价或最大代价算出节点x的代价值g(x)
当节点yi被扩展后:
先用启发函数估算出其子节点的代价
然后再算出g(yi)
此时,算出的g(yi)可能与原先估算的g(yi)不相同,则:
用后算出的g(yi)代替原先算出的g(yi)
并且按此g(yi)自下而上地重新计算各先辈节点的g值
当节点yi的子节点又被扩展时,上述过程又要重复进行一遍。总之,每当有一个新的节点生成时,都要自下而上地重新计算其先辈节点的代价g,这是一个自上而下地生成新节点,又自下而上地计算代价g的反复进行的过程。
希望树
解树的代价就是树根的代价。
树根的代价是从树叶开始自下而上逐层计算求得的。
x
yi
7
希望树的定义
初始节点S0在希望树T中;
如果节点x在希望树T中,则一定有:
如果x是具有子节点y1,y2 ,y3 …… yn的“或”节点,则具有 min{c(x,yi)+g(yi)}(1≤ i≤ n) 值的那个子节点yi也应在T中;
如果x是“与”节点,则它的全部子节点都应在T中。
有序搜索的目的是求出最优解树,即代价最小的解树。也就是说在搜索过程中的任何时刻都要搜索代价最小的部分解树,找出最有希望成为最优解树的一部分的节点进行扩展,这些节点及其先辈节点(包括初始节点S0)所构成的与或树有可能成为最优解树的一部分,因此称它为“希望树”。
8
与或树的有序搜索过程
步1 把初始节点S0放入OPEN表中;
步2 求出希望树T,即根据当前搜索树中节点的代价g, 求出以S0为根的希望树T。
步3 依次把OPEN表中T的端节点N选出放入CLOSED表中。
步4 如果节点N是终止节点,则做下列工作:
(1)标示N为可解节点;
(2)对T应用可解标记过程,把N的先辈节点中的可解节点都标记为可解节点;
(3)若初始节点S0能被标记为可解节点,则T就是最优解树,成功退出;
(4)否则,从OPEN表中删去具有可解先辈的所有节点。
9
步5 如果节点N不是终止节点,且它不可扩展,则做下列工作:
(1) 标示N为不可解节点;
对T应用不可解标记过程,把N的先辈节点中的不可解节点都标记为不可解节点;