第二章与或图搜索问题.ppt

第二章与或图搜索问题
与或树的广度优先搜索
1. 把初始节点S0放入OPEN表。
2. 把OPEN表中的第一个节点（记为节点n)取出放入CLOSED表。
3. 如果节点n可扩展，则作下列工作：
扩展节点n，将其子节点计算：示例
解树：S0, A, t1和t2。S0, B, D, G, t4和t5。
由左边的解树可得：
和代价：h(A)=11,h(S0)=13
最大代价： h(A)=6,h(S0)=8
由右边的解树可得：
和代价：h(G)=3,h(D)=4,h(B)=6,h(S0)=8
最大代价： h(G)=2,h(D)=3,h(B)=5,h(S0)=7
显然，若按和代价计算，右边的解树是最优解树，其代价为8；若按最大代价计算，右边解树解树仍然是最优解树，其代价为7。
S0
A
t1
t2
E
B
C
D
F
G
t4
t5
t3
2
6
5
1
2
2
1
2
3
1
1
2
17
与或树的有序搜索
计算任一节点x的代价h(x)时，都要求已知其子节点yi的代价h(yi)。但搜索是自上而下进行的，即先有父节点，后有子节点，除非节点x的全部子节点都是不可扩展节点，否则子节点的代价是不知道的。那么如何计算x的代价值h(x)呢？
解决的办法是根据问题本身提供的启发式信息定义一个启发函数，由此函数估算出子节点yi的代价h(yi)，然后再按和代价或者最大代价计算出节点x的代价值h(x)。有了h(x)，节点x的父节点、祖父节点以及直到初始节点S0的各先辈节点的代价h都可自下而上的逐层推算出来。
18
与或树的有序搜索
当节点yi被扩展后，也是先用启发函数估算出其子节点的代价，然后再算出h(yi)。此时算出的h(yi)可能与原先估算出的h(yi)不相同，这时应该用后算出的h(yi)取代原先估算出的h(yi)，并且按此h(yi)自下而上地重新计算各先辈节点的h值。当节点yi的子节点又被扩展时，上述过程又要重新进行一遍。总之，每当有一代新的节点生成时，都要自下而上地重新计算其先辈节点的代价，这是一个自上而下地生成节点，又自下而上地计算代价h的反复进行的过程。
19
与或树的有序搜索：希望树
有序搜索的目的是求出最优解树，即代价最小的树。这就是要求搜索过程中任一时刻求出的部分解树其代价是最小的。为此，每次选择欲扩展的节点时都应挑选有希望成为最优解树一部分的节点进行扩展。由于这些节点及其先辈节点（包括初始节点S0）所构成的与/或树有可能成为最优解树的一部分，因此称它为希望树。
希望树：
1. 初始节点在希望树T中;
2. 如果节点x在希望树中，则一定有：
如果x是具有节点y1，y2，…，yn的“或” 节点，则具有 h(x) = min{c(x, yi) + h(yi)}值 的那个子节点也应在T中。
如果x 是“与”节点，则它的全部子节点 都应在T中。
20
与或树的有序搜索：算法
1. 把初始节点S0放入OPEN表中。
2. 求出希望树T，即根据当前搜索树中节点的代价h求出以S0为根 的希望树T。
3. 依次把OPEN表中T的端节点N选出放入CLOSED表中。
4. 如果节点N是终止节点，则作如下工作：
标识N为可解节点。
对T应用可解标识过程，把N的先辈节点中的可解节点都标 识为可解节点。
若初始节点S0能被标识为可解节点，则T就是最优解树，成 功退出。
否则，从OPEN表中删去具有可解先辈的所有节点。
21
与或树的有序搜索：算法（续）
5. 如果节点N不是终止节点，且它不可扩展，则作下列工作：
标识N为不可解节点。
对T应用不可解 标识过程，把N的先辈节点中的不可解节点 都标识为不可解节点。
若初始节点S0也被标识为不可解节点，则失败退出。
否则，从OPEN表中删去具有不可解先辈的所有节点。
，但它可扩展，则作下列工作：
扩展节点N，产生N的所有子节点。
把这些子节点都放入OPEN表中，并为每个子节点配置指向 父节点（节点N）的指针。
计算这些子节点的h值及其先辈节点的h值。
7. 转第2步。
22
与或树的有序搜索：示例
S0
A
B
C
D
E
F
3
3
3
2
h(A)=8, h(D)=7, h(S0)=8, 右子树为希望树
S0
A
B
C
G
D
E
H
2
2
2
3
2
F
H(G)=7, h(H)=6,