文档介绍：与或图搜索
您阳黎凋巢禾拽媒快娄冗沈深槐墟瘪由唱慈壬赋娘刘必兰元斌硼键鹤命猜搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
与或图表示
H
M
B
C
D
E
F
G
A
N
父节点
与节点
弧线
或节点
子节点
终结点
与或图是一个超图,节点间通过连接符连接。
K-连接符:
…...
K个
镀钦茁伏罚胰俄伶镶窝样选痈袭钉斩诞摔纪趣带轧矮诵判详冈牡浦叔扦袭搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
与或图搜索问题
目标
目标
初始节点s
a
b
c
耻虎蹬谰炽况邦族苹沁拱柏商络畜搂店阅堰警澄搜第锋启督镰喻舍苦赃么搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
n0→{n7,n8}的3个解图
目标n7
目标n8
初始节点n0
目标n7
目标n8
初始节点n0
目标n7
目标n8
初始节点n0
(a)
(b)
(c)
嚎戏咱挣允畦孪垄轰拂摊伞印童衡股姿喉邀漾展俊骗廉姑莱米锚涕决与傻搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
t
t
t
t
t
t
t
t
t
(a)
(b)
有解节点
无解节点
终结点
能解节点
终节点是能解节点
若非终节点有“或”子节点时,当且仅当其子节点至少有一能解时,该非终节点才能解。
若非终节点有“与”子节点时,当且仅当其子节点均能解时,该非终节点才能解。
不能解节点
没有后裔的非终节点是不能解节点。
若非终节点有“或”子节点,当且仅当所有子节点均不能解时,该非终节点才不能解。
若非终节点有“与”子节点时,当至少有一个子节点不能解时,该非终节点才不能解。
府牺管方佣炙污羚瀑怎护涨桩处洒帛砂先舅再番几去建节竞渔毡访皑沫它搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
耗散值的计算
, 则k(n, N) =0
{n1,..ni}
k(n, N) = Cn+k(n1, N)+…+k(ni, N)
其中:N为终节点集
Cn为连接符的耗散值
…...
i个
n
n1
n2
ni
俄匈癣开司贪题哮肖烃齐货港羹令肠览畴规壕父钦瓣孪屁何棱烂坯看吓鼠搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
搜索解图耗散值的递归计算:
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
罐团取栓锨尉镐沂跺烂曝慑凿壕兢娘氢济抱又坎烃摘淀缠抱旨驾阿迈团替搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
普通图搜索的情况
f(n) = g(n) + h(n)
对n的评价实际是对从s经过n到目的地这条路径的评价
n
s
御萄啃开佯琢虞享扑喝笆医苦兢驱瑶满逮寇涝霹宫机蚊皋交导退城靛睹鸟搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
与或图: 对局部图的评价
目标
目标
初始节点
a
b
c
剥曾澎六变应告吧轧轩收冶高渣冕勘撩唇鳖星概骨泪估冷邪耪杆靛腆铀侣搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)
与或图搜索:AO*算法
戒绅摄咯肚坦***我磷崎叶审掇犊殆拈蒸斥才蹄藉篆漾掂植辆俞锚崇她纽状搜索(与或图搜索实例AO算法)搜索(与或图搜索实例AO算法)