文档介绍：与或图搜索
与或图表示
H
M
B
C
D
E
F
G
A
N
父节点
与节点
弧线
或节点
子节点
终结点
与或图是一个超图,节点间通过连接符连接。
K-连接符:
…...
K个
与或图搜索问题
目标
目标
初始节点s
a
b
c
n0→{n7,n8}的3个解图
目标n7
目标n8
初始节点n0
目标n7
目标n8
初始节点n0
目标n7
目标n8
初始节点n0
(a)
(b)
(c)
t
t
t
t
t
t
t
t
t
(a)
(b)
有解节点
无解节点
终结点
能解节点
终节点是能解节点
若非终节点有“或”子节点时,当且仅当其子节点至少有一能解时,该非终节点才能解。
若非终节点有“与”子节点时,当且仅当其子节点均能解时,该非终节点才能解。
不能解节点
没有后裔的非终节点是不能解节点。
若非终节点有“或”子节点,当且仅当所有子节点均不能解时,该非终节点才不能解。
若非终节点有“与”子节点时,当至少有一个子节点不能解时,该非终节点才不能解。
耗散值的计算
, 则k(n, N) =0
{n1,..ni}
k(n, N) = Cn+k(n1, N)+…+k(ni, N)
其中:N为终节点集
Cn为连接符的耗散值
…...
i个
n
n1
n2
ni
搜索解图耗散值的递归计算:
n0=2+k(4, N)+k(5, N)
k(5, N)= min(2+k(7,N)+k(8, N),…)
= 2
k(4, N)= min(1+k(5, N), 1+k(8,N))
= min(3, 1)=1
N0= 2+1+2=5
(a)的解图耗散值为8
(b)的解图耗散值为7
具有最小耗散值的解图称为最佳解图,其值也用h*(n)*(n)=5
(c)
n4
n5
目标n7
目标n8
初始节点n0
普通图搜索的情况
f(n) = g(n) + h(n)
对n的评价实际是对从s经过n到目的地这条路径的评价
n
s
与或图: 对局部图的评价
目标
目标
初始节点
a
b
c
与或图搜索:AO*算法