第二章与或图搜索问题
简记为:
极小≤极大,剪枝 极大≥极小,剪枝
-剪枝(续)
f
0 0 1
d b
0 3
m h
1
1
n
e g
k
i
1
6
a
0
c
-3
3
5 4
-3
6
j
0
5
-3
3
3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
-剪枝注意点
1)在不同类型节点间比较:极大 VS 极小 2)与“先辈层”而不只是“父辈层”有值的节点比较 3)只有节点值固定后,才能向上层传递 4) -剪枝不影响极大极小算法的结果
n3
=2+2+k(n5,N)+k(n6,N)
=4+2+k(n7,N)+k(n8,N) +2+ k(n7,N)+k(n8,N) =8 目标n8
n6
目标n7
• 解图3: 初始节点n0
n1
n2 n5
n4
K(n0,N) =2+k(n4,N)+k(n5,N) =3+2k(n5,N) =3+2×2
n3
n6 目标n8 目标n7
第二章 与或图搜索
2.1 基本概念
与或图是一个超图,节点间通过连接符连接。 k-连接符:k>1为“与”节点,k=1为“或”节点
…...
k个
与或图
n0
n1
n2 n4 n5 n0有2个外向连接符, 分别为1-连接符(n1), 2-连接符(n4,n5);n8 是n4的或子节点,同时 又是n5的与子节点
n7
目标
n0
n1 n2
初始节点
红色:5
黄色:6
n1
5 n0
初始节点
n4
n2(4)
1 n4(1)
n3
n5 n3(4)
n5(1)
2
n6
h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0
n8
n6(2)
n8(0)
目标
(3,1,1,1,1)
MIN
MIN
(2,2,1,1,1)
MAX
注:若有n0至{n1,n2}的解图,则我方胜; (2,1,1,1,1,1) n2 但不存在! 22
中国象棋
一盘棋平均走50步,总状态数约为10161 假设1毫微秒走一步,约需10145年。 结论:对于许多博弈问题(国际跳棋、围棋 等),不可能穷举。
7
• 解图1:
初始节点n0
n1
n2 n5
n4
K(n0,N) =2+k(n4,N)+k(n5,N) =2+1+k(n8,N)+2+ k(n7,N)+k(n8,N) =5
n3
n6 目标n8 目标n7
• 解图2:
初始节点n0 K(n0,N)
n1
n2 n5
n4
=1+k(n1,N) =1+1+k(n3,N)
=7
AO*算法思路: 对局部图的评价
初始节点
c
a
b 目标 目标
两个过程
扩展节点的图生成过程(自上而下)
从最优的局部图中选择一个节点扩展
计算耗散值的过程(自下而上)
对当前的局部图重新计算耗散值 判断祖先节点的可解/不可解性 删去无用的后裔节点
AO*算法举例
n0
初始节点
n1
n …... n1 n2
ni
i个
解图(对于无环与或图而言) 递归定义:
一个与或图G中,从节点n到节点集N的解图记为G’ ,G’是G的子图 1. 如果n是N的一个元素,则G’由单一节点n 组成; 2. 如果n有一个外向连接符k指向节点{n1, n2,…, nk}使得从每一个ni到N有一个解图,则G’由n、连 接符k和每一个ni到N的解图组成; 3. 否则n到N不存在解图。
MIN
MAX
注:若有n0至N的解图,则我方必胜
分钱币问题
我方(MAX)先走, 或节点
对方(MIN)后走, 与节点 (7)
n0 MAX
(6,1)
(5,2) (3,2,2)
(4,3)
MIN
(5,1,1) (4,2,1)
(3,3,1)
MAX
(4,1,1,1) (3,2,1,1) (2,2,2,1) n1
目标
n0 n1 n2
初始节点
n1 n4
2,5*
n0
初始节点
n4(1) n2(4)
n3
n5 n3(4)
n5(1) 初始q(n1)=h(n1)=2; 扩展后: q(n1)=min{1+4,1+4}=5>2; n8
n6
目标
n7
目标
红色:4
黄色:6
h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0
分钱币问题
对方(MIN)先走, 与节点
我方(MAX)后走, 或节点 (7)
n0 MIN
(6,1)
(5,2) (3,2,2)
(4,3)
MAX
(5,1,1) (4,2,1)
(3,3,1)
MIN
(4,1,1,1) (3,2,1,1) (2,2,2,1) (3,1,1,1,1) (2,1,1,1,1,1) (2,2,1,1,1)N
-3
3
3
-3
0 2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
29
-剪枝
边生成估值边计算倒推值,从而剪去某些分支的 技术 极大节点的下界为。 极小节点的上界为。 顺序:剪枝顺序自左至右或自右至左 剪枝的条件:
后辈节点的值≤祖先节点的值时, 剪枝 后辈节点的 值≥祖先节点的值时, 剪枝
5* n4(1) n2(4) n0
初始节点
n4
n3
n5 n3(4)
n5(1)
2*
n6
h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0
n8
n6(2)
n8(0)
目标
n7(0)
n7,n8为终节点,故可解; 于是,标记n5可解; n0尚未可解; 选择红色局部图继续扩展(n4非终节点)
n7(0)
q(n4)=1,不变,q(n0)=5不变。n4可解;故 n0可解,算法成功退出。
n7
目标
AO*算法与A*的比较性质
1)AO*应用于与或图搜索,搜索的是解图;而A*则应用于一般图的 搜索,搜索的是解路径。 2)AO*选择估价最小的局部解图优先扩展;而 A*选择估价最小的路 径(节点序列)加以优先扩展。 3)AO*无需考虑评价函数f(n)的分量g(n),只需对新扩展出的节点n 计算h(n),并倒推修正上层节点估值;而A*则需同时计算分量g(n)和 h(n),以评价节点n是否在代价最小的路径上。 4)AO*存放候选的待扩展局部解图,并依据fi(n0)值排序(i个连接 符);而A*则应用OPEN表和CLOSE表分别存放待扩展节点和已扩展节 点,并依据f(n)值排序。 当h(n)≤h*(n)且h(n)满足单调性约束时,AO*一定能找到最佳解图。
极小极大分析法
不生成(也无法生成)完整的博弈树(因而也不搜索 解图);而是在有限的深度范围内,引入节点评估值, 进而寻求当前较好的一种走法;模拟人类对弈的思维。 当前己方所处状态作为根节点,按照宽度优先搜索策 略,扩展出预定深度(偶数,成对)的与或搜索树, 端节点用给定的估价函数估值,交替使用极小-极大的 原则,倒推上层节点估值,直至根节点。 对己方有利的估值大,反之对对方有利。 博弈树扩展深度越大越精确,但计算量庞大,通常一 定深度。
+ ∞,
p是A方胜局 p是B方胜局
e(p)=
- ∞,
e(+p)-e(-p), p是未定局 0, p是和局
e(+p):可使a成为三子一线的数目 e(-p ):可使b成为三子一线的数目 e(+p)=4; e(-p)=6; e(p)=-2, 对B方有利。
a b
我方先手
1
MAX
a
-1
a
-2
a
1
MIN
a b
n3
n6 n8
n7
2
与或图搜索问题
初始节点n0
n1
n2 n4 n5 搜索的目的:考察n0到目标 (终节点)集合N={n7,n8} 是否有解并找到解图
n3
n6
目标 n8 目标 n7
能解节点
终止(目标)节点可解 若非终节点有“或”子节点时,当且仅当其 子节点至少有一能解时,该非终节点才能解。 若非终节点有“与”子节点时,当且仅当其 子节点均能解时,该非终节点才能解。
初始节点
黄色:6
n1
5*
n0
初始节点
n4(1)
n5(1)
2*
n8
n6(2)
n8(0)
目标
n7(0)
初始q(n5)=h(n5)=1; 扩展后q(n5)=min{1+2,2+0+0}=2;指 针选择2-连接;q(n0)=min{6,2+2+1}=5;