人工智能第2章与或图搜索pptx
第2章与或图搜索王庆江中国海洋大学计算机科学系《人工智能》2.1
与或图的搜索现实中，一个问题可有几种解法。崂山校区李村海尔路中韩鱼山校区…李村、海尔路、中
韩等中，只要一个
地点可到鱼山校区，则崂山校区可到鱼
山校区。问题被拆解为若干子问题，只要一个子问题可解，则问题可解!这种问题的解是一条路径，可用上一章的搜索算法求得。2.1
与或图的搜索现实中的另外一类问题–一个问题被拆成若干子问题，只有所有子问题可解，问题才可解！去鱼山校区班车零钱公交车自驾车问题被拆解为若干子问题，只有子问题都可解，问题才可解!这时的搜索图怎么表示呢？2.1
与或图的搜索与或图又称超图。父结点与子结点的关系用超弧线（又称k-连接符）标识。父结点子结点…
…1-连接符2-连接符3-连接符k-连接符2.1
与或图的搜索与或图的示例根结点n0端（叶）结点n7和n8或结点n0n1n4n5n2n3对n1而言，n2和n3为或结点。n6与结点对n0而言，n4和n5为与结点。n7终结点直接可解的结点。n82.1
与或图的搜索结点n到终结点集N的解图从n出发，选择一个外向连接符；从连接符指向的每个结点出发，继续选择外向连接符；重复上一步，直到连接符指向的结点都属于N为止。2.1
与或图的搜索解图1n0n1n4n5n2n3n6n7n8n0n1n3n5n6n7n82.1
与或图的搜索解图2n0n1n4n5n2n3n6n7n8n0n4n5n7n82.1
与或图的搜索解图3n0n1n4n5n2n3n6n7n8n0n4n5n7n82.1
与或图的搜索一个与或图G中，从结点n到结点集N的解图G‘是G的子图，它是这样的：–当n∈N时，G’＝{n}；若n有一个k-连接符，指向{n1,n2,…,nk}，使得从ni到N都存在解图，则G’＝{n,
k-连接符,各ni到N的解图}；否则，G’＝Φ。2.1
与或图的搜索局部图单一结点是局部图；选择局部图的任一叶结点，选择其任一个外向连接符，则局部图、该外向连接符及其所指的后继结点组成新
的局部图。搜索n到N解图的过程，就是以n为根的局部图不断“生长”的过程。2.1
与或图的搜索解图的耗散记为k(n,N)。若n∈N，k(n,
N)=0；–若n有一个外向连接符指向{n1,n2,…,ni}，并设该连接符的耗散为Cn，则k(n,
N)
=
Cn
+
k(n1,
N)
+
k(n2,
N)
+
…
+
k(ni,
N)n0n4n5n7n8N
=
{n7,
n8}k(n0,
N)
=
2
+
k(n4,
N)
+
k(n5,
N)=
2
+
(1
+
k(n5,
N))
+
k(n5,
N)=
3
+
2×(2
+
k(n7,
N)
+
k(n8,
N))=
3
+
2×(2
+
0
+
0)=7h*(n)是n-N最佳解图的耗散。h*(n)
＝
min{k(n,
N)}2.1
与或图的搜索n为根的局部图的耗散估计（含义：通过“生长”这个局部图找到n-N解图的耗散估计）记为k(n,N)，表示n经一个k-连接符向N搜索。若n∈{叶结点}，则k(n,N)=h(n)；h(n)是n到N最佳解图的耗散估计。若n有一个外向连接符指向{n1,n2,…,ni}，并设该连接符的耗散为Cn，则k(n,
N)
=
Cn
+
k(n1,
N)
+
k(n2,
N)
+
…
+
k(ni,
N)n0n4n5N
=
{n7,
n8}k(n0,
N)
=
2
+
k(n4,
N)
+
k(n5,
N)=
2
+
h(n4)
+
h(n5)2.1
与或图的搜索已解结点（solved）终结点是已解结点；非终结点已解，当且仅当至少一个“或”结点已解；非终结点已解，当且仅当所有“与”结点已解。未解结点（unsolved）没有后继结点的非终结点是未解结点；非终结点未解，当且仅当所有“或”结点未解；非终结点未解，当且仅当至少一个“与”结点未解。2.2与或图的启发式搜索算法在未找到解图之前，根结点存在一个或多个局部图。n0n1n4n5n2n3n6n7n8n0n1n5n2n3n6n0n4n5n8局部图1局部图2某一个局部图最终“生长”为解图。那么，每次先“生长”哪个局部图？2.2与或图的启发式搜索算法AO*算法的应用举例
–h(n)结点n到N的最佳解图耗散估计–怎样寻找n0到{n7,n8}的解图呢？n0n5n2n7n83n1244
n3n4112
n6002.2与或图的启发式搜索算法第一次生长n0n1n4n5n2n3n6n7n8n1n4n51）扩展n0；2）计算以n0根的局部图的耗散；3）标识耗散最小的n0为根的局部图。211n032.2与或图的启发式搜索算法第二次生长n0n1n4n5n2n3n6n81）沿n0的最佳局部图，找到一个叶结点；n72）扩展此叶结点，计算以叶结点为根的局部图的耗散；3）向上修改非终结点为根的局部图的耗散估计，表示最佳局部图；4）修改n0最佳局部图的标识。n1n4n511n03445
24n3n262.2与或图的启发式搜索算法第三次生长n0n1n4n5n2n3n81）沿n0的最佳局部图，找到一个叶结点；n72）扩展此叶结点，计算以叶结点为根的局部图的耗散；3）向上修改非终结点为根的局部图的耗散估计；4）修改n0最佳局部图的标识。5n4n1511n0444n3n2n6n7n8002
n62n52.2与或图的启发式搜索算法第四次生长n0n1n4n5n2n3n81）沿n0的最佳局部图，找到一个叶结点；n72）扩展此叶结点，计算以叶结点为根的局部图的耗散；3）向上修改非终结点为根的局部图的耗散估计；4）修改n0最佳局部图的标识。5n5n1521n0544n3n2n6n7n8002
n6n412.2与或图的启发式搜索算法以结点n为尾的红色箭头，标识结点n为根的最佳局部图。在第4步得到的n0局部图中，叶结点都属于{n7,n8}。解图：n05n70n412n5n802.2与或图的启发式搜索算法①
G:={s},计算q(s)=h(s),如果GOAL(s),THEN
M(s,SOLVED)②
While(s还没加上SOLVED标记）do{G’
=
FIND(G)n:=G’的任一个非终结点EXPAND(n)
→{nj},
计算q(nj)=h(nj),这里nj∈GG:=G∪{nj};
IF
GOAL(nj),
THEN
M(nj,
SOLVED)S
:=
{n}While
(S≠Φ)
do
{REMOVE(m,
S),
要求m的子结点∈S修改q(m)对m为根的每个局部图，计算qi(m)将指针标记指向最小耗散局部图的k-连接符上如果最小耗散局部图能解，则M(m,SOLVED)c)IF
(m,
SOLVED)∨
q(m)
≠q0(m),
THEN
ADD(ma,
S)g)
}③
}AO*算法生长，对新结点计算q向上修改父辈结点的q当(m,SOLVED)∧q(m)=q0(m)时,q(ma)不必修改,只考虑是否能解当EXPAND(n)={}时,令q(n)=∞2.2与或图的启发式搜索算法AO*算法和A*算法的比较与或图vs
一般图解图vs
解路径评估局部图vs
评估结点无OPEN/CLOSED表vs
有OPEN/CLOSED表都有h(n)≤h*(n)和h(n)满足单调限制的特点2.3
博弈树的搜索弈yì–
(本义:下棋)同本义[play
chess]视君不如弈棋。——《左传·襄公二十五年》今夫弈之为数。——《孟子》又如:弈思(下棋的思路)，弈棋(下棋)–
弈,围棋也。——《说文》射者中,弈者胜。——宋·欧阳修《醉翁亭记》棋局谓之弈。——《小尔雅》又如:弈局(棋局,棋盘);弈具(指棋盘,棋子);弈枰(棋盘);弈楸(棋盘);弈谱(棋谱)–
大[great]。如:弈弈(高大的样子);弈业(大业);弈赫(盛大显赫的样子)2.3
博弈树的搜索博bó–
赌(赌博),博弈[gamble]与闵公博。――《公羊传·庄公十二年》则博塞以游。――《庄子·骈拇》或以游博持掩为事。――《后汉书·王符传》不有博奕者乎。――《论语·阳货》或饮或博。――清·薛福成《观巴黎油画记》取得[get;win]博个封妻荫子。――《水浒传》又如:博笑(谦词。换取别人一笑);博鬻(换取);博名(获取好名声)博弈不有博弈者乎?——《论语·阳货》孔子说:"不闻夫博弈者乎,亦尤贤乎已"2.3
博弈树的搜索弈（即棋）有许多种从参加人数上单人博弈棋双人对弈棋多人博弈棋从对弈规则（即棋子和走法）上围棋中国象棋国际象棋跳棋一字棋余一棋这里只研究双人对弈棋2.3
博弈树的搜索“博弈论”术语
–“双人对弈”双方轮流走步。“信息完备”双方得到的棋局信息是一样的。“零和博弈”属“非合作”博弈,指博弈一方的收益必然意味着另一方的损失,双方的收益和损失相加永远为“零”。2.3
博弈树的搜索博弈可用“特殊的”与或图表达令棋局为结点，一种走法会得到一个新棋局。轮我方走时，可选择任何一种走法。各走法得到的新棋局之间是“或”关系。轮对方走时，我方必须应对对方的各种走法。对方各走法得到的新棋局之间是“与”关系。例：Grundy博弈有N枚钱币，双方轮流分堆；每位棋手把某一堆分为钱币数不等的两堆；如一方不能完成分堆，即认输。2.3
博弈树的搜索76,15,24,35,1,14,2,13,2,23,3,14,1,1,13,2,1,12,2,2,13,1,1,1,12,2,1,1,12,1,1,1,1,1根结点：初始棋局叶结点：终棋局黄方赢橙方赢对于橙方，{A}是终结点集，如有解图，按解图走必赢！ABC
黄方赢对于黄方，{B,C}是终结点集，如有解图，按解图走必赢！与结点或结点或结点与结点或结点我方为黄方由黄方分Grundy博弈的与或图表达2.3
博弈树的搜索从橙方角度理解的与或图76,15,24,35,1,14,2,13,2,23,3,14,1,1,13,2,1,12,2,2,13,1,1,1,12,2,1,1,12,1,1,1,1,1黄方赢橙方赢ABC
黄方赢或结点与结点与结点或结点与结点2.3
博弈树的搜索橙方需要的解图76,15,1,14,2,13,2,1,12,2,1,1,1橙方赢解图176,14,2,13,2,1,12,2,1,1,1橙方赢解图274,34,2,13,3,13,2,1,12,2,1,1,1橙方赢解图3对于橙方，无论黄方第一步怎么走，都能找到解图！而黄方无解图，为什么？2.3
博弈树的搜索解图是从开局到终局的完整博弈策略。只要搜索出解图，就可弈胜！但是，以中国象棋为例，搜索开销巨大！–
假设每步平均有40种走法，则双方共走50步，–
则棋局总数约，深度约100层。∴搜索解图的想法必须放弃！实际上，从任一方来说，许多棋没有解图。(402
)50
»101602.3
博弈树的搜索人是怎样下棋的？如果我走这一步，对方会有多少走法？然后，我再怎么走？…新手只能看一、二个轮次，高手则看几个，甚至十几个轮次。“想出”的若干轮次可表示为一张局部图。根结点代表当前棋局；想n轮次的结果可表示为深度为2n+1的局部图。根结点有多个局部图每个外向连接符，引出一个“根结点为根的局部图”，最佳局部图，意味着当前的最佳走步。怎样寻找最佳局部图呢？2.3
博弈树的搜索对结点n(即棋局)的评估以f(n)表示。f(n)>0,
对我方有利；f(n)