27
3X3棋盘的一字棋例子
X X
X X X
X
X
X
X
X
X
X
X
X
X
28
X X
X
X X
1
-∞ -∞
XX X
X X X
-∞
X XX
-∞
X X X
A XX X
B
C XX X
D XX X
-∞
XX X
29
2、-搜索过程
• -过程的基本思想
30
-剪枝
1
极大
1
b
≤0
a
0
极小
6
00 ≥0
-3
3
≥3
3
26
THEN f(np) :=max{f(nci)},REMOVE(np,CLOSED) IF(np ϵ MIN) ᴠ cj ϵ MAX) 有值) (f(n THEN f(np) :=min{f(ncj)},REMOVE(np,CLOSED) 7、GO LOOP2 8、LOOP3: IF f(s) ≠ NIL THEN EXIT(END ᴠ M(Move,T))
13
7、S := {n} 8、Until S为空，do: 9、begin 10、REMOVE(m,S) 11、修改m的耗散值 12、IF M(nji,SOLVED) ᴠ (q(m)≠q (m)) THEN ADD(ma,S) 13、end 14、end
0 14
AO*算法举例
n0 n1 n2 n4
20
AO*与A的区别
21
2.3 博弈树搜索
• 博弈问题
– 双人 – 一人一步 – 双方信息完备 – 零和
22
分钱币问题
对方先走 （7）
（6,1）
（5,2）
（3,2,2）
（4,3）
（3,3,1）
（5,1,1） （4,2,1）
（4,1,1,1） （3,1,1,1,1）
（3,2,1,1）
（2,2,2,1） 我方必胜
• 简记为：
– 极小≤极大， 剪枝 – 极大≥极小， 剪枝
32
-剪枝应注意的问题
• 在实际程序实现时，首先规定一个搜索深 度，然后按照类似于深度优先搜索的方式 ，生成结点。 • 在结点的生成过程中，如果在某一个结点 处发生了剪支，则该结点其余未生成的结 点就不再生成。
33
-剪枝（图2.11）
初始节点
n3
n5
n6
n8
目标
n7
其中： 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 设：K连接符 的耗散值为K
15
目标
n0 n1 n2
初始节点
n1(2) n4
n0
初始节点
n4(1)
n3
n5
n5(1)
（2,2,1,1,1）
（2,1,1,1,1,1）
23
中国象棋
• 一盘棋平均走50步，总状态数约为10的161 次方。 • 假设1毫微秒走一步，约需10的145次方年。 • 结论：不可能穷举。
24
1、极小极大过程
• 极大极小搜索策略 • 评价函数(静态估算函数)
25
过程MINMAX
1、T := (s,MAX),OPEN := (s),CLOSED := () 2、LOOP1: IF OPEN=() THEN GO LOOP2 3、n := FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED) 4、IF n可直接判定 THEN f(n) := ∞ ᴠ ᴠ 0,GO LOOP1 -∞ ELSE EXPAND(n)→{ni},ADD({ni},T) IF d(ni)<k THEN ADD({ni},OPEN),GO LOOP1 ELSE 计算f(ni),GO LOOP1 5、LOOP2: IF CLOSED = NIL THEN GO LOOP3 ELSE np := FIRST(CLOSED) 6、IF(np ϵ MAX) ᴠ ci ϵ MIN) 有值) (f(n
2
n6
n8
n8(0)
目标
n7
目标
n7(0)
红色：5 黄色：6
18
n0 n1 n2
初始节点
n1 n4 5
n0
初始节点
1 n4(1)
n2(4)
n3
n5 n3(4) n6(2)
n5(1)
2
n6
n8
n8(0)
目标
n7
目标
n7(0)
红色：5 黄色：6
19
AO*算法的若干问题
• 若n不存在后继接结点 • G’中非终结点的选择 • 满足单调限制条件时具有可采纳性
n6
n8
目标
n7
红色：4
黄色：3
目标
16
n0 n1 n2
初始节点
n1 n4 5
n0
初始节点
n4(1) n2(4)
n3
n5 n3(4)
n5(1)
n6
n8
目标
n7
红色：4
黄色：6
目标
17
n0 n1 n2
初始节点
n1 n4 5
n0
初始节点
n4(1) n2(4)
n3
n5 n3(4) n6(2)
n5(1)
-3 -3
1
0
-2
1
-3
6
-3
≤-3
-3 3 3 -3 0 2 2 -3
0
5
0
-2
3 5 4
1
-3
0 6
8 9
-3
α剪支
β剪支
31
-剪枝
• 极大节点的下界为。 • 极小节点的上界为。 • 剪枝的条件：
– 后辈节点的值≤祖先节点的值时， 剪枝 – 后辈节点的 值≥祖先节点的值时， 剪枝
f
0 0 1
d b
0 3
m h
1
1
n e
k
6
a
0
c
-3
3
g
5 4
i
-3
1
6
j
0
5
-3
3
3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
34
作业
• 习题2.1 • 习题2.6
35
1、建立一个搜索图G，G := s，计算q(s) = h(s),IF GOAL(s) THEN M(s,SOLVED); 2、Until s已标记上SOLVED，do: 3、begin 4、G’ := FIND(G); 5、n := G’中的任一非终节点; 6、EXPAND(n),生成子节点集{nj},计算 q(nj)=h(nj),G := ADD({nj},G),IF GOAL(nj) THEN M(nj,SOLVED)
3
• 解图： 初始节点ຫໍສະໝຸດ 目标 目标4耗散值的计算
k(n, N) = Cn+k(n1, N)+…+k(ni, N) 其中：N为终节点集 Cn为连接符的耗散值
n
…...
n1 n2 i个
5
ni
• 局部图
6
能解节点
• 终节点是能解节点
• 若非终节点有“或”子节点时，当且仅当 其子节点至少有一能解时，该非终节点才 能解。 • 若非终节点有“与”子节点时，当且仅当 其子节点均能解时，该非终节点才能解。
7
不能解节点
• 没有后裔的非终节点是不能解节点。
• 若非终节点有“或”子节点，当且仅当所 有子节点均不能解时，该非终节点才不能 解。 • 若非终节点有“与”子节点时，当至少有 一个子节点不能解时，该非终节点才不能 解。
8
2.2 与或图的启发式搜索算法AO*
• 通过评价函数f(n)来引导搜索过程
9
普通图搜索的情况
s
n
f(n) = g(n) + h(n) 对n的评价实际是对从s到n这条路径的评价
10
与或图: 对局部图的评价
初始节点
c
a
b 目标 目标
11
两个过程
• 图生成过程，即扩展节点
– 从最优的局部图中选择一个节点扩展
• 计算耗散值的过程
– 对当前的局部图重新计算耗散值
12
AO*算法
第二章 与或图搜索问题
初始节点s
a c b
目标 目标
1
2.1 与或图的搜索
• 与或图是一个超图，节点间通过连接符 连接。 • K-连接符：
…...
K个
2
可分解产生式系统
• “可分解”是指初始状态可以分解成n个分 量，分量还可再分解，逐一解决。 • 能够分解产生式系统的综合数据库和结束 条件的产生式系统称为可分解产生式系统。