当前位置:首页 >> 其它课程 >>

第3章 图搜索与问题求解


第3章

图搜索与问题求解

推理与搜索
?

图搜索技术是人工智能的核心技术之一。

?
?

任一搜索过程也都是一个推理过程。
隐式图的搜索过程是一种利用局部性知识构 造全局性答案的过程。 在各种搜索过程中,人工智能最感兴趣的是 那些具有很强选择性的启发式方法,即那些 利用很局部的状态空间可以有效地找到问题 的解的方法。 机器学习等很多过程都是在假设空间中搜索 目标的过程。
人工智能 2

?

?

2013-8-18

第3章 图搜索与问题求解
3.1 3.2 3.3 3.4 3.5 状态图知识表示(状态图搜索问题求解) 状态图搜索 与或图知识表示(与或图搜索问题求解 ) 与或图搜索 博弈树搜索

2013-8-18

人工智能

3

3.1 状态图知识表示
3.1.1 3.1.2 3.1.3 3.1.4 3.1.5 状态、操作和状态空间 修道士和野人的状态空间 梵塔问题的状态空间 重排九宫问题和隐式图 问题求解的基本框架

2013-8-18

人工智能

4

3.1.1状态、操作和状态空间(1)
例3.1走迷宫

走迷宫问题就是从该有向图的初始节点出发,寻找目 标节点的问题,或者是寻找通向目标节点的路径问题。
2013-8-18 人工智能 5

3.1.1 状态、操作和状态空间(2)
例3.2八数码难题(重排九宫问题)
2 8
1

3
4

1 8

2

3 4

7 6

5

7

6

5

初始棋局

目标棋局

棋局作为节点,相邻节点通过移动数码一个一个产生 出来,所有节点由它们的相邻关系连成一个有向图。 以上两个问题抽象来看,都是某个有向图中寻找目标 或路径的问题,在人工智能技术中,把这种描述问题 的有向图称为状态空间图,简称状态图。
2013-8-18 人工智能 6

3.1.1 状态、操作和状态空间(3)
?

状态(State)p62 ? 为了描述某一类事物中各个不同事物之间 的差异而引入的最少的一组变量q的有序 组合,表征了问题的特征和结构。 ? 表示成矢量形式:
?q 0 ? ? q1 ? T Q ? ? ?=?q 0,q1,q 2, ? ? ?q 2 ? ? ? ???
?

状态在状态图中表示为节点。
人工智能 7

2013-8-18

3.1.1 状态、操作和状态空间(4)
?

状态转换规则(操作 operator)
?

?

? ?

引起状态中某些分量发生改变,从而使一个 具体状态变化到另一个具体状态的作用。 它可以是一个机械性的步骤、过程、规则或 算子。 操作描述了状态之间的关系。 状态转换规则在状态图中表示为边。在程序 中状态转换规则可用数据对、条件语句、规 则、函数、过程等表示。
人工智能 8

2013-8-18

3.1.1 状态、操作和状态空间(5)
?

状态空间(State Space)
?

?

问题的状态空间是一个表示该问题全部的可 能状态及相互关系的图。 状态空间一般用赋值有向图表示,记为: (S,F,G)
? ? ?

S:问题的可能有的初始状态的集合; F:操作的集合; G:目标状态的集合。

2013-8-18

人工智能

9

3.1.1 状态、操作和状态空间(6)
?

状态空间中问题求解
?

?

?

在状态空间表示法中,问题求解过程转化为在图中 寻找从初始状态Qs出发到达目标状态Qg的路径问题, 也就是寻找操作序列的问题。 状态空间的解为三元组< Qs, a, Qg > ? Qs :某个初始状态 ? Qg :某个目标状态 ? a:把Qs变换成Qg的有限的操作序列 状态转换图
Qs O1 S1 O2 S2 O3 S3 O4 … On Qg
10

2013-8-18

人工智能

3.1.1 状态、操作和状态空间(7)
例 3.7 迷宫问题的状态图表示。 ?
S:So? F:{(So, S4), (S4, So), (S4, S1), (S1, S4), (S1,S2), (S2, S1),

(S2, S3), (S3, S2),
G:Sg

(S4, S7), (S7, S4), (S4, S5), (S5, S4), (S5,

S6), (S6, S5), (S5, S8), (S8, S5), (S8, S9), (S9, S8), (S9, Sg)} 迷宫问题规则集描述了图中所有节点和边。类似于 这样罗列出全部节点和边的状态图称为显式状态图, 或者说状态图的显式表示。
2013-8-18 人工智能 11

3.1.1 状态、操作和状态空间(8)
补充例1 三枚钱币,能否从下面状态翻动三次后 出现全正或全反状态。
正 正 正













初始状态θ s
2013-8-18 人工智能

目标状态集合{θ0, θ7}
12

3.1.1 状态、操作和状态空间(9)
引入一个三元组(q0,q1,q2)来描述总状态,钱币正面为0,反面 为1,全部可能的状态为: Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) Q6=(1,1,0) ; Q4=(1,0,0); Q5=(1,0,1) ; Q7=(1,1,1)。

翻动钱币的操作抽象为改变上述状态的算子, 即F={a, b, c} a:把钱币q0翻转一次 b:把钱币q1翻转一次 c:把钱币q2翻转一次

问题的状态空间为<{Q5},{Q0 Q7}, {a, b, c}>
2013-8-18 人工智能 13

3.1.1 状态、操作和状态空间(10)
状态空间图

a
(1,0,0) b c b

c

(0,0,0) c

(0,0,1) a (1,0,1)
b

(1,1,0) a (0,1,0)
c

b

(1,1,1) a (0,1,1)

2013-8-18

人工智能

14

3.1.2 修道士和野人问题的状态空间(1) 补充例2 修道士和野人问题。在河的左岸有三个 修道士、三个野人和一条船,修道士们想用这 条船将所有的人都运过河去,但受到以下条件 的限制: (1)修道士和野人都会划船,但船一次最 多只能运两个人; (2)在任何岸边野人数目都不得超过修道 士,否则修道士就会被野人吃掉。 假定野人会服从任何一种过河安排,试规划 出一种确保修道士安全过河方案。
2013-8-18 人工智能 15

3.1.2 修道士和野人问题的状态空间(2) 解:先建立问题的状态空间。问题的状态可以用 一个三元数组来描述: S=(m, c, b) m:左岸的修道士数 c:左岸的野人数 b:左岸的船数 右岸的状态不必标出,因为: 右岸的修道士数m’=3-m 右岸的野人数c’=3-c 右岸的船数b’=1-b
2013-8-18 人工智能 16

3.1.2 修道士和野人问题的状态空间(3)
状态 m, c, b 状态 m, c, b 状态 m, c, b 状态 m, c, b

S0 S1
S2 S3 S4 S5 S6 S7

3 3 1
3 2 1

S8
S9

1 3 1 S16 3 3 0 S24 1 3 0
1 2 1 S17 3 2 0 S25 1 2 0

3 1 1 S10 1 1 1 S18 3 1 0 S26 1 1 0 3 0 1 S11 1 0 1 S19 3 0 0 S27 1 0 0 2 3 1 S12 0 3 1 S20 2 3 0 S28 0 3 0 2 2 1 S13 0 2 1 S21 2 2 0 S29 0 2 0 2 1 1 S14 0 1 1 S22 2 1 0 S30 0 1 0 2 0 1 S15 0 0 1 S23 2 0 0 S31 0 0 0
2013-8-18 人工智能 17

3.1.2 修道士和野人问题的状态空间(4)
操作符 p01 p10 p11 p02 p20 q01 q10 q11 q02 q20 条 件 b=1, m=0或3, c≥1 b=1, (m=3,c=2)或(m=1,c=1) b=1, m=c, c≥1 b=1, m=0或3, c≥2 b=1, (m=3,c=1)或(m=2,c=2) b=0, m=0或3, c≤2 b=0, (m=0,c=1)或(m=2,c=2) b=0, m=c, c≤2 b=0, m=0或3, c≤2 b=0, (m=0,c=2)或(m=1,c=1) 动 作 b=0, c=c-1 b=0, m=m-1 b=0, m=m-1, c=c-1 b=0, c=c-2 b=0, m=m-2 b=1, c=c+1 b=1, m=m+1 b=1, m=m+1, c=c+1 b=1, c=c+2 b=1, m=m+2

操作集F={p01, p10,p11,p02,p20,q01,q10,q11, q02,q20}
2013-8-18 人工智能 18

3.1.2 修道士和野人问题的状态空间(5)
p02 S0 (3,3,1)

q02 p01
q01 p11 q11

S18 (3,1,0) S17 (3,2,0) S21 (2,2,0)

q01
p01 p10 p02 S1 (3,2,1) q02 q01 S19 (3,0,0) p01 p20 S2 S26 (3,1,1) q20 (1,1,0)

q10
q11 p11

q11 S31 (0,0,0)

p11 p01 q01 p02 q02

S10 (1,1,1) S14 (0,1,1) S13 (0,2,1)

p10 q10 q01 q02 S30 (0,1,0) p02 p01
人工智能 19

p01 S12 (0,3,1) q01

q20 S29 S5 (0,2,0) p20 (2,2,1)

2013-8-18

3.1.3 梵塔问题的状态空间(1) 例3.9 二阶梵塔问题 一号杆有A、B两个金盘, A小于B。要求将AB移至三号杆,每次只可移动 一个盘子,任何时刻B不能在A上。 用二元组(SA ,SB )表示状态,SA 表示A所在 杆号,SB表示B所在杆号,全部状态如下: (1,1),(1,2),(1,3)

(2,1),(2,2),(2,3)
(3,1),(3,2),(3,3)
2013-8-18 人工智能 20

3.1.3 梵塔问题的状态空间(2)

A B 1 2 3 S0:(1,1)

A
1 2 3 S1:(1,2) A B 1 2 3 S4:(2,2) B A

A
1 2 3 S2:(1,3)

B

A
1 2 3 S3:(2,1)

A

B

1 2 3 S5:(2,3)

B

A 1 2 3 S6:(3,1)

A
B 1 2 3 S8:(3,3)
21

1 2 3 S7:(3,2)
人工智能

2013-8-18

3.1.3 梵塔问题的状态空间(3)
转换规则:A(I,j)表示金盘A从第I号杆移到j号杆 B(I,j)表示金盘B从第I号杆移到j号杆 A(1,2),A(1,3), A(2,1) A(2,3),A(3,1), A(3,2) B(1,2),B(1,3), B(2,1) B(2,3),B(3,1), B(3,2) 初始状态(1,1),目标状态(3,3) 梵塔问题用状态图表示为: <{(1,1)},{A(1,2),?,B(3,2)},{(3,3)}>

2013-8-18

人工智能

22

3.1.3 梵塔问题的状态空间(4)

1,1

A(1,3)
2,1

A(2,1)
3,1

B(1,2)

B(3,1)

A(3,2)
3,3

2,3

3,2

A(3,2)

1,3

1,2

2,2

A(2,1)
2013-8-18

B(1,3)
人工智能

A(1,3)
23

n(n≥3)阶梵塔问题
假设金片Pk从小片到大片按下标k顺序编号, 即k=1,2,3,?,n,n阶梵塔问题状态空间 可用矢量表示为: (P1, P2, P3,?, Pk,?, Pn) Pk表示第k个金片穿在编号为Pk的宝石针上, Pk={1,2,3} ? 初始状态 S0=(1,1,1,?,1,?,1) ? 目标状态 Sg1 =(2,2,2,?,2,?,2) Sg2 =(3,3,3,?,3,?,3)
?
2013-8-18 人工智能 24

n(n≥3)阶梵塔问题
n阶梵塔问题的操作集合表示为: F={Rk(i,j) | i,j={1,2,3},k={1,2,?,n}} ? 全部可能状态数为3n个,最佳解长度为2n-1。 ? 三阶梵塔问题状态图
?

S0=(1,1,1)

2013-8-18

Sg2=(3,3,3)

人工智能

Sg1=(2,2,2)

25

3.1.4 重排九宫问题和隐式图(1) 例3.8重排九宫问题(八数码难题)
2 8 1 3 4 1 8 7 6 2 3 4 5 X1 X2 X3 X8 X0 X4

7 6

5

X7 X6 X5

目标棋局 将棋局用向量A=(X0,X1 , X2 , X3 , X4 , X5 , X6 , X7 , X8)
表示,其中Xi为变量,值表示方格Xi内的数字。 初始状态 目标状态 24条规则,分为9组。
2013-8-18 人工智能 26

初始棋局

S0 =(0,2,8,3,4,5,6,7,1) Sg =(0,1,2,3,4,5,6,7,8)

数码的移动规则就是该问题的状态变化规则。经分析,该问题共有

3.1.4 重排九宫问题和隐式图(2)
0组规则

r1(X0=0 r2(X0=0 r3(X0=0 r4(X0=0 1组规则

) ) ) )

? ? ? ?

(X2=n (X4=n (X6=n (X8=n

) ) ) )

? ? ? ?

X0 X0 X0 X0

= = = =

n n n n

? ? ? ?

X2 X4 X6 X8

=0; =0; =0; =0;

r5(X1=0 ) ? (X2=n ) ? X1 = n ? X2 =0; r6(X1=0 ) ? (X8=n ) ? X1 = n ? X8 =0;

8组规则:

……
r22(X8=0 ) ? (X1=n ) ? X8 = n ? X1 =0; r23(X8=0 ) ? (X0=n ) ? X8 = n ? X0=0; r24(X8=0 ) ? (X7=n ) ? X8 = n ? X7 =0;

2013-8-18

人工智能

27

3.1.4 重排九宫问题和隐式图(3) 八数码的状态图可表示为 ({S0}, {r1 , r2 ,? , r24 }, {Sg}) 八数码问题状态图仅给出了初始节点 和目标节点,其余节点需用状态转换规则 来产生。类似于这样表示的状态图称为隐 式状态图,或者说状态图的隐式表示。

2013-8-18

人工智能

28

3.1.4 重排九宫问题和隐式图(4)
?

如何隐式的描述一个状态空间
?

?

有描述问题状态的有关知识,包括该问题的 各状态分量的取值情况,开始条件、结束条 件、各种约束条件等等。 需要由任何一个状态生成其所有直接后继节 点的的有关知识。

2013-8-18

人工智能

29

3.1.4 重排九宫问题和隐式图(5)
例3.10 旅行商问题(Traveling?SalesmanProblem,简 称TSP)。设有n个互相可直达的城市,某推销商准备从 其中的A城出发,周游各城市一遍,最后又回到A城。 要求为该推销商规划一条最短的旅行路线。 该问题的状态为以A打头的已访问过的城市序 列:A… S0:A。 Sg:A,…,A。其中“…”为其余n-1个城市的一个序列。 状态转换规则: 规则1 如果当前城市的下一个城市还未去过,则去该 城市,并把该城市名排在已去过的城市名序列后端。 规则2 如果所有城市都去过一次,则从当前城市返回 A城,把A也添在去过的城市名序列后端。
2013-8-18 人工智能 30

3.1.5 问题求解的基本框架(1)
?

问题求解所需要的知识 ? 与描述问题的状态有关的各种叙述性知识。 ? 描述状态之间的变换关系的各种过程性知识。
一般以一组操作的形式出现的。任何一个操作都含有 条件和动作两部分,条件给定了操作的适用范围,动作 描述了由于操作而引起的状态中某些分量的变化情形。
?

描述如何根据当前状态和目标状态选择合适的操 作的控制性知识。 ? 根据叙述性和过程性知识可以构造问题的状态空 间。一般讲状态空间是一个赋值有向图,节点对应 着问题的状态,边对应操作。
?
2013-8-18 人工智能 31

3.1.5 问题求解的基本框架(2)
?

问题求解就是在图中寻找一条从初始节点到 达目标节点的通路或操作序列。 ?首先从操作集中选择可作用在当前状态上 的操作; ?如果符合条件的操作有许多个,则要从挑 选出最有希望导致目标状态的操作施加到当 前状态上,以便克服组合爆炸; ?如果解的长度很大,还需要更为复杂的克 服组合爆炸的技术。

2013-8-18

人工智能

32

3.2 状态图搜索 3.2.1状态图搜索 3.2.2穷举式搜索 3.2.3启发式搜索 3.2.4加权状态图搜索 3.2.5启发式图搜索的A算法和A*算法 3.2.6状态图搜索策略小结

2013-8-18

人工智能

33

3.2.1 状态图搜索(1)
?

?

?

搜索:从初始节点出发,沿着与之相连的边试 探地前进,寻找目标节点的过程。 搜索过程中经过的节点和边,按原图的连接关 系,便会构成一个树型的有向图,这种树型有 向图称为搜索树。 搜索进行中,搜索树会不断增长,直到当搜索 树中出现目标节点,搜索便停止。这时从搜索 树中就可很容易地找出从初始节点到目标节点 的路径(解)来。

2013-8-18

人工智能

34

3.2.1 状态图搜索(2) 1 搜索方式
?

?

树式搜索 在搜索过程中记录所经过的所有节点和边。树式 搜索所记录得轨迹始终是一棵树,这棵树也就是搜 索过程中所产生得搜索树。 线式搜索 在搜索过程中只记录那些当前认为在所找路径上 的节点和边。
? ?

不回溯线式搜索 可回溯线式搜索

2013-8-18

人工智能

35

3.2.1 状态图搜索(3) 2 搜索策略
?

?

?

盲目搜索 无向导的搜索,树式盲目搜索就是穷举搜索,不 回溯的线式搜索是随机碰撞式搜索,回溯的线式搜 索也是穷举式搜索。 启发式搜索 是利用“启发性信息”引导的搜索策略。“启发 性信息”就是与问题有关的有利于尽快找到问题解 的信息或知识。启发式搜索分为不同的策略,如全 局择优,局部择优,最佳图搜索。 按扩展顺序不同分为广度优先和深度优先。
人工智能 36

2013-8-18

3.2.1 状态图搜索(4) 3 搜索算法
?

? ?

搜索的目的是为了寻找初始节点到目标节点的路径, 搜索过程中就得随时记录搜索轨迹。 ClOSED表动态数据结构来记录考察过的节点。 OPEN表的动态数据结构来专门登记当前待考查的节 点。
OPEN表 CLOSED表

节点 父节点编号

编号

节点

父节点编号

2013-8-18

人工智能

37

3.2.1 状态图搜索(5)
?

树式搜索算法
步1 把初始节点S0放入OPEN表中。
步2 若OPEN表为空,则搜索失败,退出。 步3 取OPEN表中第一个节点N放在CLOSED表中; 并冠以顺序编号n; 步4 若目标节点Sg=N,成功退出。

步5 若N不可扩展,转步2。
步6 扩展N,生成一组节点,对这组子节点作如下处 理:
2013-8-18 人工智能 38

3.2.1 状态图搜索(6)
(1)删除N的先辈节点(如果有的话)。

(2)对已存在于OPEN表中的节点(如果有的话)也删 除之;删除之前要比较其返回初始节点的新路径与原 路径,如果新路径“短”,则修改这些节点在OPEN 表中的原返回指针,使其沿新路径返回。
(3)对已存在于CLOSED表的节点,作与(2)同样的 处理,并且将其移出CLOSED表,放入OPEN表中重 新扩展。

(4)对其余子节点配上指向N的返回指针后放入OPEN 表中某处,或对OPEN表进行重新排序,转步2。

2013-8-18

人工智能

39

3.2.1 状态图搜索(7)
?

树式算法的几点说明
? ?

?

返回指针指的是父节点在CLOSED表中的编号。 步6中修改指针的原因是返回初始节点的路径有两 条,要选择“短”的那条路径。 这里路径长短以节点数来衡量,在后面将会看到以 代价来衡量。按代价衡量修改返回指针的同时还要 修改相应的代价值。

2013-8-18

人工智能

40

3.2.1 状态图搜索(8)

图 3-5 修改返回指针示例

2013-8-18

人工智能

41

3.2.1 状态图搜索(9)
?

树式搜索例
?

对于已存在于OPEN表中的节点(如果有的话)也删除之;删 除之前要比较其返回初始节点的新路径与原路径,如果新路 径短,则修改这些节点在OPEN表中的原返回指针,使其沿原 路径返回。 S0 如图所示:说明从S0→P至 Path2 少有两条路,这时有两 Path1 种情况: n
先扩展 f(Path2)< f(Path1), 当前路径较好,要修改P 的指针,使其指向n,即 搜索之后的最佳路径。 否则,原路径好。
42

m

后扩展

P P在n之前已是某一节点m的后继
2013-8-18 人工智能

3.2.1 状态图搜索(10)
?

对已存在于CLOSED表的节点,作与(2)同样的处理,并将其 移出CLOSED表,放入OPEN表中重新扩展。

S0
现在生成 过去对Ps的 n P的路径 最优路径

k
Ps P

过去生成 P的路径 b.P在Closed表中,说明P的后 继也在n之前已经生成,称为 Ps。对Ps而言同样可能 由于 m n→P这一路径的加入,又必须 比较多条路径之后而取代价小 的一条,如图左部所示。

a.P在n之前已是某一节点m的 后继,所以需要做如同(2) 同样的处理,如图右部所示。

2013-8-18

人工智能

43

3.2.1 状态图搜索(11) 例:设当前搜索图和搜索树如图所示
S0

S0

n

n

F

P

F

P

m
Ps Ps’ Ps Ps’

m

2013-8-18

人工智能

44

3.2.1 状态图搜索(12)
?

若启发函数f(n)为从S0到节点n的最短路径的长度,用 边的数目来考察,当前扩展的节点是搜索图中的n,P是 n的后继
S0 S0

n

n

F

F
P m Ps P m Ps’
45

Ps
2013-8-18

Ps’
人工智能

3.2.1 状态图搜索(13)
?

P的指针改变后,修改搜索树结果如下:
S0

n

F
P Ps
2013-8-18

m P’s
人工智能 46

3.2.1 状态图搜索(14)
?

不回溯线式搜索算法
步1 把初始节点S0放入CLOSED表中; 步2 令N= S0 ; 步3 若N是目标节点,则搜索成功,结束。 步4 若N不可扩展,则搜索失败,退出。

步5 扩展N,选取其一个未在CLOSED表中出现过的
子节点N1放入 CLOSED表中,令N=N1,转步3。

2013-8-18

人工智能

47

3.2.1 状态图搜索(15)
?

可回溯的线式搜索

步1 把初始节点S0放入CLOSED表中; 步2 令N= S0 ; 步3 若N是目标节点,则搜索成功,结束。 步4 若N不可扩展,则移出CLOSED表中的末端节点Ne ,若Ne=S0, 则搜索失败,退出。否则以CLOSED表新的末端节点Ne作为 N,即令N= Ne,转步4;

步5 扩展N,选取其一个未在CLOSED表中出现过的子节点N1放入
CLOSED表中,令N= N1 ,转步3。

2013-8-18

人工智能

48

3.2.2 穷举式搜索(1)
?

广度优先搜索(算法A???ed)
?

策略
算法

始终在同一级节点中考查,当同一级节点考查完了之后,才 考查下一级节点。搜索树自顶向下一层一层逐渐生成。
?

步1 把初始节点S0放入OPEN表中; 步2 若OPEN表为空,则搜索失败,退出。 步3 取OPEN表中第一个节点N放 在CLOSED表中;并冠以顺序编号n; 步4 若节点N为目标节点,成功退出。 步5 若N不可扩展,转步2; 。 步6 扩展N,将其所有子节点配上指向N的指针放入OPEN尾部,转步2

2013-8-18

人工智能

49

3.2.2 穷举式搜索(2)
开始 把S0送入OPEN表
OPEN表空? N 把OPEN表的第一个节 点(节点N)从表中移 出,放入CLOSED表中
节点N为目标节点? N N 节点N可扩展? Y Y

Y

失败,退出

成功,退出

扩展节点N,将其子节 点放入OPEN表尾部, 并为每个子节点配置 指向节点N的指针。

2013-8-18

人工智能

50

3.2.2 穷举式搜索(3)
?

广度优先搜索的特点
?

? ?

? ?

广度优先中OPEN表是一个队列,CLOSED表是一个顺 序表,表中各节点按顺序编号,正被考察的节点在 表中编号最大。 广度优先搜索又称为宽度优先或横向搜索。 广度优先策略是完备的,即如果问题的解存在,则 它一定可以找到解,并且找到的解还是最优解。 广度优先搜索策略与问题无关,具有通用性。 缺点搜索效率低。

2013-8-18

人工智能

51

3.2.2 穷举式搜索(4)
?

八数码问题
2 8 3 1 4 7 6 5 8 1 3 2 4 7 6 5

初始状态

目标状态

2013-8-18

人工智能

52

3.2.2 穷举式搜索(5)
2 8 3 1 4 7 6 5

1 4
2 8 3 1 4 7 6 5

2
2 8 3 1 4 7 6 5

3
2 3 1 8 4 7 6 5

5
2 8 3 1 6 4 7 5

6
8 3 2 1 4 7 6 5

7
2 8 3 7 1 4 6 5

8
2 3 1 8 4 7 6 5

9
2 3 1 8 4 7 6 5

10
2 8 1 4 3 7 6 5

11
2 8 3 1 4 5 7 6

12
2 8 3 1 6 4 7 5

13
2 8 3 1 6 4 7 5

14
8 3 2 1 4 7 6 5

15
2 8 3 7 1 4 6 5

16
2 3 4 1 8 7 6 5

17
1 2 3 8 4 7 6 5

18
2 8 1 4 3 7 6 5

19
2 8 3 1 4 5 7 6

20
2 8 3 6 4 1 7 5

21
2 8 3 1 6 7 5 4

22
8 3 2 1 4 7 6 5

23
8 1 3 2 4 7 6 5

八数码广度优先搜索
人工智能 53

2013-8-18

3.2.2 穷举式搜索(6)
?

深度优先搜索(过程Apd )
?

搜索策略
在搜索树的每一层始终先扩展一个子节点,不断地向纵深前

进,直到不能再前进,才从当前节点返回到上一级节点,从另一

方向继续前进。
?

算法
步1 把初始节点S0放入OPEN表中; 步2 若OPEN表为空,则搜索失败,退出。 步3 取OPEN表中第一个节点N放在CLOSED表中;并冠以编号n; 步4 节点N为目标节点,成功退出。 步5 若N不可扩展,转步2;

步6 扩展N,将其所有子节点配上指向N的指针放入OPEN首部,转
2013-8-18

步2。

人工智能

54

3.2.2 穷举式搜索(7)
开始 把S0送入OPEN表
OPEN表空? N 把OPEN表的第一个节 点(节点N)从表中移 出,放入CLOSED表中
节点N为目标节点? N N 节点N可扩展? Y Y

Y

失败,退出

成功,退出

扩展节点N,将其子节 点放入OPEN表首部, 并为每个子节点配置 指向节点N的指针。

2013-8-18

人工智能

55

3.2.2 穷举式搜索(8)
?

深度优先搜索的特点
? ? ? ?

?

OPEN表为一个堆栈。 深度优先又称纵向搜索。 一般不能保证找到最优解。 当深度限制不合理时,可能找不到解,可以将算 法改为可变深度限制,即有界深度优先搜索。 最坏情况时,搜索空间等同于穷举。

2013-8-18

人工智能

56

3.2.2 穷举式搜索(9)
2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5

1 2
2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5

3
2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5

4
2 8 3 1 6 7 5 4

5
2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4

八数码深度优先搜索
2013-8-18 人工智能



57

3.2.2 穷举式搜索(10)
?

有界深度优先搜索(过程Acd ) ? 搜索策略
给出搜索树深度的限制,当从初始节点出发沿某一分支扩展到一定 深度限制时,就不能再继续往下扩展,而只能改变方向继续搜索。
?

算法
步1 把初始节点S0放入OPEN表中,臵S0的深度d( S0 )=0;
步2 若OPEN表为空,则搜索失败,退出。 步3 取OPEN表中第一个节点N放在CLOSED表中;并冠以编号n; 步4 若节点N为目标节点,成功退出。 步5 若N的深度d(N)=dm(深度限制值),或者若N无子节点, 则转步2; 步6 扩展N,将其所有子节点Ni配上指向N的指针放入OPEN首部,

臵的d( Ni )=d(N)+1,转步2。
2013-8-18 人工智能 58

3.2.2 穷举式搜索(11)
S

a1

b1

a2

a3

b2

a6

b3

b4

b5
2013-8-18 人工智能 59

3.2.2 穷举式搜索(12)
?

有界深度优先搜索存在的问题 ? 深度界限的选择很重要

dm 若太小,则达不到解的深度,得不到解;若太 大,既浪费了计算机的存储空间与时间,又降低了搜 索效率。由于解的路径长度事先难以预料,所以要恰 当地给出dm的值是比较困难的。
?

即使能求出解,它也不一定是最优解。

2013-8-18

人工智能

60

3.2.2 穷举式搜索(13)
?

有界深度优先搜索改进 ? dm随搜索深度不断加大(迭代加深搜索)

先任意给定一个较小的数作为dm,然后进行上述的有界深 度优先搜索,当搜索达到了指定的深度界限dm仍未发现目标节点, 并且CLOSED表中仍有待扩展节点时.就将这些节点送回OPEN表, 同时增大深度界限dm,继续向下搜索。如此不断地增大dm,只要 问题有解,就一定可以找到它。
?

增加一个R表

此时找到的解不一定是最优解。为找到最优解,可增设一 个表(R),每找到一个目标节点Sg后,就把它放入到R的前,并令 dm等于该目标节点所对应的路径长度,然后继续搜索。由于后求 得的解的路径长度不会超过先求得的解的路径长度,所以最后求 得的解一定是最优解。
2013-8-18 人工智能 61

3.2.2 穷举式搜索(14)
?

迭代加深搜索过程:
步1 把初始节点S0放入OPEN表中,臵S0的深度d( S0 )=0, dm为任意初值。 步2 若OPEN表为空,则考查CLOSED表是否有待扩展节点: ①若无,则问题无解,退出。 ②若有,则取出CLOSED表中待扩展节点放入到OPEN表 中,令 dm=dm+⊿d。

2013-8-18

人工智能

62

3.2.2 穷举式搜索(15)
步3 取OPEN表中第一个节点N放在CLOSED表中;并冠以编号

n;
步4 若节点N为目标节点,成功退出。 步5 若N的深度d(N)>dm(深度限制值),则标N为待扩展

节点,则转步2;
步6 N无子节点,则转步2; 步7 扩展N,将其所有子节点Ni配上指向N的指针放入OPEN

首部, 臵 d( Ni )=d(N)+1,转步2。

2013-8-18

人工智能

63

开始
把S0送入OPEN表,置d(S0) =0;dm=任意初值

OPEN表为空? N 把OPEN表首部节点 N送入CLOSED表 标记N未待 扩展节点 Y d(N)〉>dm? Y N N为目标节点Sg? N N 节点N可扩展? Y

Y

CLOSED表中有 待扩展节点?

N

Y
把CLOSED表中 的待扩展节点放入 OPEN表。令 dm=dm+⊿d

成功退出

失败退出

迭 代 加 深 搜 索 流 程 图

扩展N,将其所有子节点Ni配 上指向N的指针放入OPEN首部 , 置d( Ni )=d(N)+1

3.2.3 启发式搜索(1)
?

启发式搜索的目的
利用知识来引导搜索,达到减少搜索范围,降低问题 复杂度。

?

启发性信息的强弱
强:降低搜索的工作量,但可能导致找不到最优解。
弱:一般导致工作量加大,极限情况下变为盲目搜索, 但可能可以找到最优解。

?

启发性信息的类型
? ? ?

用于扩展节点的选择 用于生成节点的选择 用于删除节点的选择
人工智能 65

2013-8-18

3.2.3 启发式搜索(2)
?

启发函数
?

?

启发函数是用来估计搜索树节点x与目标节点接近 程度的一种函数,通常记为h(x)。 定义启发函数的参考思路
?

?
?

一个节点到目标节点的某种距离或差异的量度。 一个节点处在最佳路径上的概率 根据主观经验的主观打分等。

?

启发式搜索算法
?

启发式搜索要用启发函数来导航,其搜索算法就要 在状态图一般搜索算法基础上再增加启发函数值的 计算与传播过程,并且由启发函数值来确定节点的 扩展顺序。
人工智能 66

2013-8-18

3.2.3 启发式搜索(3)
?

全局择优搜索
?

全局择优搜索就是利用启发函数制导的一种 启发式搜索方法。该方法亦称为最好优先搜 索法。
基本思想:在OPEN表中保留所有已生成而未 考察的节点,并用启发函数h(x)对它们全部 进行估价,从中选出最优节点进行扩展,而 不管这个节点出现在搜索树的什么地方。

?

2013-8-18

人工智能

67

3.2.3 启发式搜索(4)
?

全部择优搜索算法
把初始节点S0放入OPEN表中,计算h( S0 ); 若OPEN表为空,则搜索失败,退出。 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以序号n; 步4 若目标节点Sg =N,则搜索成功结束。 步5 若N不可扩展,则转步2。 步6 扩展N,计算每个子节点x的函数值h(x),并 将所有子节点配以指向N的返回指针后放入OPEN表中, 再对OPEN表中所有子节点按其函数值的大小以升序排 列,转步2。 步1 步2 步3

2013-8-18

人工智能

68

3.2.3 启发式搜索(6)
2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 4 7 6 5

S0
2 3 1 8 4 7 6 5

8 1 3 2 4 7 6 5 Sg 2 8 3 1 6 4 7 5

S1 4

5

4
2 3 1 8 3 7 6 5

5

8 3 2 8 3 2 1 4 S2 7 1 4 7 6 5 3 6 5 8 3 2 1 4 7 6 5 8 3 2 1 4 7 6 5 2013-8-18

5

2 3 1 8 4 7 6 5 4

5

S3 1
8 1 3 2 4 7 6 5

启发函数h(x)为节点x与目标格局相比 数码不同的位置个数。
Sg 0
人工智能 69

从图看出解为: S0 ,S1 ,S2 ,S3, Sg。

3

3.2.3 启发式搜索(7)
?

局部择优搜索
?

?

局部择优搜索是一种启发式搜索方法,是对 深度优先搜索方法的一种改进。 基本思想是当每一个节点被扩展后,按h(x) 对每一个子节点计算启发值,并选择最小者 作为下一个要考察的节点,由于每次都只是 在子节点的范围内选择下一个要考察的节点, 范围比较狭窄,所以称为局部择优搜索。

2013-8-18

人工智能

70

3.2.3 启发式搜索(8)
?

局部择优搜索算法
步1 把初始节点S0放入OPEN表中,计算h( S0 ); 步2 若OPEN表为空,则搜索失败,退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以序号n; 步4 若目标节点Sg =N,则搜索成功结束。 步5 若N不可扩展,则转步2。 步6 扩展N,计算N每个子节点x的函数值h(x),并 将N的子节点按估计值升序排列放入OPEN表的首 部,为每个子节点配臵指向节点N的指针,转步 2。

2013-8-18

人工智能

71

3.2.4加权状态图搜索(1)
例3.6 交通图A城是出发地,E是目的地,数字表示两城 之间交通费用。求A到E的最小费用的旅行路线。
B 4 A 4 6 E

3

3

C 2 D

2013-8-18

人工智能

72

3.2.4加权状态图搜索(2)
?

加权状态图与代价树
?

?

边上附有数值的状态图称为加权状态图或赋权状态 图,这种数值称为权值。 加权状态图的搜索
加权状态图的搜索与权值有关,并且要用权值来导航。具体 来讲,加权状态图的搜索算法,要在一般状态图搜索算法基 础上再增加权值的计算与传播过程,并且要由权值来确定节 点的扩展顺序。

?

代价的计算
g(x)表示从初始节点S0到节点x的代价。 c(xi,xj)表示父节点xi到子节点xj的代价 g( xj )=g( xi )+ c(xi,xj) g( x0 )=0

2013-8-18

人工智能

73

3.2.4加权状态图搜索(3)
?

加权状态图转换为代价树搜索
?

?

从初始节点出发,先把每一个与初始节点相邻的 节点作为该节点的子节点。 然后对其他节点依次类推,但对其他节点x,不 能将其父节点及祖先再作为x的子节点。
B 4 6 3 E 2 4 C1 4 4 B1 6

A

3

3

3 E2 6

D1 4
B2 6 E4

D2 2
C2

E1
3 E2 3 D3 2

C
2013-8-18

2

D

B3
人工智能

C3
74

3.2.4加权状态图搜索(4)
?

分支界限法( A*eg )
?

?

其基本思想是:每次从OPEN表中选出g(x)值最小的 节点进行考察,而不管这个节点在搜索树的什么位 臵上。 与全局择优法的区别
选取扩展节点标准 分支界限 法 代价值g(x) 计算方法 g(x)与节点所处的位臵有 关,与边也有关系,从初始节 点S0计算而来。

全局择优 启发函数值h(x) h(x)与节点有关,与边可 法 能有关或无关,从目标节点方 向计算而来。
2013-8-18 人工智能 75

3.2.4加权状态图搜索(5)
?

分支界限搜索算法

步1 把初始节点S0放入OPEN表中,计算g( S0 ); 步2 若OPEN表为空,则搜索失败,退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以序号n; 步4 若目标节点Sg =N,则搜索成功结束。 步5 若N不可扩展,则转步2。 步6 扩展N,并将所有子节点配以指向N的返回指针后放 OPEN表中;计算每个子节点x的函数值g(x), 再对OPEN表中所有子节点按g(x)值的大小以升 序排列,转步2。
2013-8-18 人工智能 76

3.2.4加权状态图搜索(6)
?

最近择优法(瞎子爬山法)
?

?

基本思想:每次仅考察N的子节点的g(x),选取N 的子节点中代价最小的子节点进行扩展。 最近择优法与局部择优法的区别:
选取扩展节点标 准 最近择优 法 代价值g(x) 计算方法 g(x)与节点所处的位臵有关, 与边也有关系,从初始节点S0 计算而来。

局部择优 法

启发函数h(x) h(x)与节点有关,与边可能 有关或无关,从目标节点方向 计算而来。
人工智能 77

2013-8-18

A 3 4 4 D2 2 B2 6 E4 3

编号
B1 6
E1 3 D3 2 C3

节点 父节点

C1
2 3 E2 6 B3 D1 4

C2

E2

3.2.4加权状态图搜索(7)
?

代价树的有界深度优先法
?

与直接树的有界深度优先相比,用gm来代替 最大深度dm。

2013-8-18

人工智能

79

3.2.4加权状态图搜索(8)
?

代价树深度优先搜索
3 C1 2 3 E2 6 B3 D1 4 B2 6 D2 2 C2 4 3 E3 4 B1 6 E1 3 D3 2 C3

E4

搜索的解为A -〉C -〉D -〉E
2013-8-18 人工智能 80

内容回顾:树形图树式搜索策略比较
标准 穷举式搜索 启发式搜索 加权状态图搜索 2 6 7 g d 范围

全局

局部

深度d(x) 启发值h(x) 代价值g(x)
S0 3 b 5 4 h i 9 Sg f 5

宽度优先搜索 深度优先搜索 全局择优搜索 局部择优搜索 分支界限法 瞎子爬山法
h(x),有利于搜索纵向发展, 提高搜索效率,但影响完备性。 j 8 k g(x),有利于搜索横向发展,

a c 4

1 3

提高完备性,但影响搜索效率。

2013-8-18

人工智能

81

3.2.5启发式图搜索的A算法和A*算法(1) 1.估价函数 将启发函数与代价函数相结合,为了防止在 单独利用启发函数的时候误入歧途。 f(x) =g(x)+h(x) wh(x)
f(x)是初始节点S0到达节点x处已付出的代价与 节点x到达目标节点Sg的接近程度估计值总和。 是g(x)与h(x)的折中。 通过调整w的值,使结果偏重效率或偏重完备性。

2013-8-18

人工智能

82

3.2.5启发式图搜索的A算法和A*算法(2) 2.A算法 步1 把附有f(S0)的初始节点S0放入OPEN表中; 步2 若OPEN表为空,则搜索失败,退出。 步3 移出OPEN表中第一个节点N放入CLOSED表中, 并冠以顺序编号n; 步4 若目标节点Sg=N,则搜索成功,结束。 步5 若N不可扩展,则转步2;

2013-8-18

人工智能

83

3.2.5启发式图搜索的A算法和A*算法(3)
步6 扩展N,生成一组附有f(x)的子节点,对这组节点 作如下处理: (1)考察是否有已在OPEN表或CLOSED表中存在的节点; 若有则再考察其中有无N的先辈节点,若有则删除之;对 于其余节点,也删除之,但由于它们被第二次生成,需考 虑是否修改已经存在于OPEN表或CLOSED表中的这些节点及 其后裔的返回指针和f(x)的值,修改原则是抄f(x)值 小的路走”。 (2)对其余子节点配上指向N的返回指针后放入OPEN表中 ,并对OPEN表按f(x)以升序排列,转步2。

2013-8-18

人工智能

84

回顾:树式搜索一般算法(1)
?

树式搜索例
?

对于已存在于OPEN表中的节点(如果有的话)也删除之;删 除之前要比较其返回初始节点的新路径与原路径,如果新路 径短,则修改这些节点在OPEN表中的原返回指针,使其沿原 路径返回。 S0 如图所示:说明从S0→P至 Path2 少有两条路,这时有两 Path1 种情况: n
先扩展 f(Path2)< f(Path1), 当前路径较好,要修改P 的指针,使其指向n,即 搜索之后的最佳路径。 否则,原路径好。
85

m

后扩展

P P在n之前已是某一节点m的后继
2013-8-18 人工智能

回顾:树式搜索一般算法(2)
?

对已存在于CLOSED表的节点,作与(2)同样的处理,并将其 移出CLOSED表,放入OPEN表中重新扩展。

S0
现在生成 过去对Ps的 n P的路径 最优路径

k
Ps P

过去生成 P的路径 b.P在Closed表中,说明P的后 继也在n之前已经生成,称为 Ps。对Ps而言同样可能 由于 m n→P这一路径的加入,又必须 比较多条路径之后而取代价小 的一条,如图左部所示。

a.P在n之前已是某一节点m的 后继,所以需要做如同(2) 同样的处理,如图右部所示。

2013-8-18

人工智能

86

3.2.5启发式图搜索的A算法和A*算法(4)

3.估价函数定义探讨
f(x) =g(x)+h(x) g(x):对某一确定的节点,是确定的值。

h(x):不同的问题启发函数的定义不同,相同的 问题也可以定义出不同的启发函数。
衡量h(x)优劣的标准是看其是否能够准确反映出 节点x到达目标的难易程度(距离)。 探讨九宫重排问题的估价函数的设计过程。

2013-8-18

人工智能

87

3.2.5启发式图搜索的A算法和A*算法(5) 九宫重排问题(八数码难题)
2 8 1 3 4 1 8 2 3 4 X1 X2 X3 X8 X0 X4

7 6 5 7 6 5 X7 X6 X5 初始棋局 目标棋局 将棋局用向量A=(X0,X1 , X2 , X3 , X4 , X5 , X6 , X7 , X8) 表示,其中Xi为变量,值表示方格Xi内的数字。 初始状态 目标状态 24条规则,分为9组。
2013-8-18 人工智能 88

S0 =(0,2,8,3,4,5,6,7,1) Sg =(0,1,2,3,4,5,6,7,8)

数码的移动规则就是该问题的状态变化规则。经分析,该问题共有

3.2.5启发式图搜索的A算法和A*算法(6)
0组规则 r1(X0=0 r2(X0=0 r3(X0=0 r4(X0=0 1组规则 ) ) ) ) ? ? ? ? (X2=n (X4=n (X6=n (X8=n ) ) ) ) ? ? ? ? X0 X0 X0 X0 = = = = n n n n ? ? ? ? X2 X4 X6 X8 =0; =0; =0; =0;

r5(X1=0 ) ? (X2=n ) ? X1 = n ? X2 =0; r6(X1=0 ) ? (X8=n ) ? X1 = n ? X8 =0;

……
8组规则: r22(X8=0 ) ? (X1=n ) ? X8 = n ? X1 =0; r23(X8=0 ) ? (X0=n ) ? X8 = n ? X0=0; r24(X8=0 ) ? (X7=n ) ? X8 = n ? X7 =0;
2013-8-18 人工智能 89

3.2.5启发式图搜索的A算法和A*算法(7)
例1:九宫重排问题如下图所示初始节点S0与目标节点 Sg。
2 8 3 1 4 7 6 5
S0

1 2 3 8 4 7 6 5

Sg

如何定义?

估价函数f(x)=g(x)+h(x) g(x)用节点深度d(x)来衡量 因素1 格局中将牌是否在家 h(x)用 x的格局与目标节点格局相比,不在家的 将牌数目w(x)来衡量。
2013-8-18 人工智能 90

扩展顺序

f(x)值

1

2 8 3 1 4 7 6 5

3

1 2 3 8 4 7 6 5

Sg

2 8 3 1 4 7 6 5

2
4

2 3 1 8 4 7 6 5

3
4

2 8 3 1 4 7 6 5

5

2 8 3 1 6 4 7 5

5

8 3 2 1 4 7 6 5

5

2 8 3 7 1 4 6 5

6

2 3 1 8 4 7 6 5

4
4

2 3 1 8 4 7 6 5

6

1 2 3 8 4 7 6 5

5
4

1 2 3 7 8 4 6 5

6

1 2 3 8 4 7 6 5

6
4

3.2.5启发式图搜索的A算法和A*算法(9)
问题:是否对于所有的节点w(x)都能反映出从x节点 变化到目标节点的难易程度(到目标的距离)?
8 1 2 6 3 7 5 4 2 8 1 4 6 3 7 5 1 2 3 8 4 7 6 5

a

b

Sg

w(a)=7 w(b)=6,从w(x)值看a格局离目标格局更远。 a格局真的比b格局距离目标更远吗?

2013-8-18

人工智能

92

w(a)=7

8 1 2 6 3 7 5 4

a 1

1 2 8 6 3 7 5 4

实际距离为8
8 1 2 6 3 7 5 4

5
1 2 3 8 6 7 5 4

1 2 3 8 4 7 6 5

Sg

2
1 2 8 6 3 7 5 4 1 2 3 8 6 4 7 5

6

3
1 2 8 6 3 7 5 4 1 2 3 8 6 4 7 5

7

4
1 2 3 8 4 7 6 5

8 Sg

2 8 1 4 6 3 7 5

8 1 3 2 4 7 6 5

w(b)=6

1
2 8 1 4 3 7 6 5

7
8 1 3 2 4 7 6 5

1 2 3 8 4 7 6 5

Sg

实际距离为11

2
2 8 1 4 3 7 6 5

8
8 1 3 2 4 7 6 5

3
8 1 2 4 3 7 6 5

9
1 3 8 2 4 7 6 5

4
8 1 2 4 3 7 6 5

10
1 3 8 2 4 7 6 5

5
8 1 2 4 3 7 6 5

11
1 2 3 8 4 7 6 5

6

3.2.5启发式图搜索的A算法和A*算法(12)
w(x)并不能很好地反映从x节点变化到目标节点 的难易程度。w(x)启发信息不够。
8 1 2 6 3 7 5 4 2 8 1 4 6 3 7 5 1 2 3 8 4 7 6 5

a

b

Sg

影响x节点到达目标节点难易程度的因素有哪些? 因素2 格局中将牌离家的远近(直线距离之和)

2013-8-18

人工智能

95

3.2.5启发式图搜索的A算法和A*算法(13)
考虑因素2,定义h(x)=p(x) p(x)是x格局中每个将牌离家(Sg中的位置)的最短 距离(不论路上是否放有其他将牌)的总和。
1 11
8 1 2 2 6 3 0 7 5 4

1 1

a

1 2 3 8 4 7 6 5

Sg

1 实际距离为8

p(a)=8
1 2 2
2 8 1 2 4 6 3 1 0 7 5 0

b

仍未反映出a,b到达目标 格局的难易程度

实际距离为11 p(b)=9
2013-8-18

1
人工智能 96

3.2.5启发式图搜索的A算法和A*算法(14)
8 1 2 6 3 7 5 4 2 8 1 4 6 3 7 5 1 2 3 8 4 7 6 5

a

b

Sg

因素3 格局中将牌回家的顺序
沿着周围非中心方格上依顺时针检查x格局 中的每一个将牌,如果其后紧跟着的将牌正好是目标 格局中该将牌的后续者,该将牌得0分,否则得2分。 因素4 中心位置是否有将牌 在正中方格上有将牌得1分,否则得0分。 综合因素3和因素4的值,记为s(x)
2013-8-18 人工智能 97

3.2.5启发式图搜索的A算法和A*算法(15)
考虑因素2(p(x)),因素3和4(s(x)) s(x)比p(x)对到达目标的难易程度影响更大,故: 定义h(x)=p(x)+3s(x)
0 00
1 2 3 8 4 7 6 5
Sg

8 1 2 2 6 3 0 a 2 7 5 4 0

s(a)=6 p(a)=8

h(a)=8+3×6=36

2 2 02
2 8 1 2 4 6 3 2 b 2 7 5 2
1
2013-8-18 人工智能 98

s(b)=13 h(b)=9+3×13=48 p(b)=9

3.2.5启发式图搜索的A算法和A*算法(16)
例2:利用上面定义的h(x)解下列九宫重排问题。
1 2 3 8 4 7 6 5

2 1 6 4 8 7 5 3

s0

Sg

2013-8-18

人工智能

99

1 2 3 8 4 7 6 5

Sg

2 1 6 4 8 7 5 3

1
S0
2 1 6 4 8 7 5 3 2 1 4 8 6 7 5 3 2 1 6 4 8 3 7 5

2 1 6 4 8 7 5 3
1 6 2 4 8 7 5 3

2
57

2 6 4 1 8 7 5 3
2 1 6 7 4 8 5 3 2 1 4 8 6 7 5 3

3
57

59

2 1 6 4 5 8 7 3 2 1 6 4 8 3 7 5

59

2 8 1 4 6 3 7 5 2 8 1 4 6 3 7 5 2 8 1 4 3 7 6 5

13
55

4
57

5
57

59

59

57
2 1 4 8 3 7 6 5

2 8 1 4 3 7 6 5

14
46
2 8 1 4 3 7 6 5

8
58

6
57

15
43

49

47

2 1 4 8 6 7 5 3 2 8 1 4 6 7 5 3

59

2 8 1 4 6 7 5 3 2 8 1 4 6 7 5 3

9
58

2 1 6 4 8 3 7 5
2 8 1 4 5 6 7 3

7
54

2 1 6 4 3 7 8 5
2 1 6 8 3 4 7 5

62

8 1 2 4 3 7 6 5
8 1 2 4 3 7 6 5 8 1 2 4 3 7 6 5

16
45

2 8 1 7 4 3 6 5

51

10
55

11
55

17
45

57

61

8 1 2 4 6 7 5 3

57

2 8 1 7 4 6 5 3

57

2 8 4 6 1 7 5 3

57

2 8 1 4 6 3 7 5

12
55

18
45

8 4 1 2 3 7 6 5

46

8 1 2 4 3 7 6 5 8 1 3 2 4 7 6 5 8 1 3 2 4 7 6 5 1 3 8 2 4 7 6 5

18
45

19
36

8 1 3 2 4 5 7 6 8 1 3 2 6 4 7 5

47

20
27

8 3 2 1 4 7 6 5 8 1 3 7 2 4 6 5

41

47

22
27

29

1 3 8 2 4 7 6 5

23
27

1 2 3 8 4 7 6 5

24
18

1 3 8 2 4 7 6 5

29

3.2.5启发式图搜索的A算法和A*算法(13)
?

A*算法
?

对A算法再限制其估价函数中的启发函数h(x)满足: 对所有的节点x均有:

h(x)<=h* (x)
其中h* (x)是从节点x到目标节点的最小 代价,这就称为A*算法。 A*算法也称为最佳图搜索算法,利用A*算法,如果 问题存在最优解,就保证能找到最优解。

?

2013-8-18

人工智能

102

3.2.5启发式图搜索的A算法和A*算法(18) 例:修道士和野人问题。在河的左岸有五个修 道士、五个野人和一条船,修道士们想用这条 船将所有的人都运过河去,但受到以下条件的 限制: (1)修道士和野人都会划船,但船一次最 多只能运三个人; (2)在任何岸边及船上野人数目都不得超 过修道士,否则修道士就会被野人吃掉。 假定野人会服从任何一种过河安排,试规划 出一种确保修道士安全过河方案。请定义启发 函数,并给出相应的搜索树。
2013-8-18 人工智能 103

3.2.5启发式图搜索的A算法和A*算法(15)

解:先建立问题的状态空间。问题的状态 可以用一个三元数组来描述: S=(m, c, b) m:左岸的修道士数 c:左岸的野人数 b:左岸的船数

2013-8-18

人工智能

104

3.2.5启发式图搜索的A算法和A*算法(16) 定义启发函数,若满足h(n)≤h*(n),即 满足A*条件的。 启发函数1:h(n)=0; 启发函数2:h(n)=M+C;
对状态(1,1,1),启发函数2不满足h(n)≤h*(n) 提示:不考虑限制条件的运送次数一定小于有限制条 件的运送次数。

2013-8-18

人工智能

105

3.2.5启发式图搜索的A算法和A*算法(17)
?

先考虑船在左岸的情况:
如果不考虑限制条件,至少需要 [(M+C-3)/2]*2+1 化简后为: [(M+C-3)/2]*2+1=M+C-2
?

?

再考虑船在右岸的情况:
?

同样不考虑限制条件。船在右岸,需要一个人将船 运往左岸,因此,对于状态(M,C,0),需要的 摆渡数,相当于船在左岸的(M+1,C,1)或(M, C+1,1),所以需要的最少摆渡数为:M+C+12+1=M+C

?

综合条件,需要的最少摆渡数为M+C-2B。
人工智能 106

2013-8-18

1 (5,5,1) h=8 f=9 h=8 2 h=8 20 (5,4,0) h=9 11 h=7 12 (5,3,0) (4,4,0) (5,2,0) f=10 f=9 f=9 f=8 10 (5,4,2) h=7 3 (5,3,1) h=6 f=8 f=9 8 (3,3,0) h=6 9 (5,1,0) h=6 4 (5,0,0) h=5 f=9 f=8 f=9 19 (4,4,1) h=6 6 (5,2,1) h=5 5 (5,1,1) h=4 f=10 f=8 f=9 7 (2,2,0) h=4 f=9 13 (3,3,1) h=4 f=10 14 (0,3,0) h=3 f=10

14 (0,3,0) h=3 f=10

15 (0,4,1) h=2 f=10
16 (0,1,0) h=1 f=10 (0,2,0)

(0,5,1)

h=3 f=11

h=2 f=11

17 (1,1,1) h=8 18 (0,2,1) h=7 f=9 f=8 21 (0,0,0) h=0 f=11

(0,3,1)

h=8 f=9

3.2.6状态图搜索策略小结(1)

树式搜索

盲目搜索

穷举式

广度优先 深度优先 有界深度优先

启发式搜索

全局择优(最好优先,基于启发函数h(x))
局部择优(瞎子爬山,基于h(x)) 分支界限(全局最小代价优先,基于代价g(x)) 最近择优(瞎子爬山,局部最小代价优先,基于g(x)) A算法(基于估价函数f(x)=g(x)+h(x)) A*算法(最佳图搜索,h(x)<=h*(x))

线式搜索

盲目搜索

随机碰撞 回溯穷举(生成-测试法)

启发式搜索

不回溯(瞎子爬山,基于h(x)、g(x)、f(x)) 智能回溯(启发式生成-测试法)

2013-8-18

人工智能

109

3.2.6状态图搜索策略小结(2)
?

搜索策略的诸要素分类
?

选择下一个被考察节点的范围
?

全局的(用下标e表示)
?

?
?

广度优先 分支界限法 全局择优

?

局部的(用下标p表示)
? ? ?

深度优先 瞎子爬山 局部择优

2013-8-18

人工智能

110

3.2.6状态图搜索策略小结(3)
?

选择下一个被考察节点标准
?

?

?

?

d(N)(用下标d表示)搜索树中从S0到N的路径长 度。 g(N)(用下标g表示)代价树从S0到N的路径的代 价。 f(N)(用下标f表示)代价树中从S0出发经过N节 点到Sg的路径的最小代价 范围和标准是最基本的要素,由他们演变出了 A*ed, Apd, A*eg, A*pg, Aef和Apf

2013-8-18

人工智能

111

3.2.6状态图搜索策略小结(4)

在p型策略中,又有两个要素需要考虑
?

试探性
?

?

e型策略本质都是试探型的,因为它必须用OPEN 表保存已生成的未考察节点以备选择。 P型则不同,无OPEN表一样可以工作
? ?

无OPEN表,不可撤回(用下标pn表示,一般用n) 有OPEN表,可撤回

?

有界性
?

?

e型策略不会误入无穷分支路径,所以无须设搜 索界限,不可撤回n无须设界。 试探性P型需要设界(有界用pc表示,一般用c)
112

2013-8-18

人工智能

3.3与或图知识表示
3.3.1与或图基本概念 3.3.2与或图知识表示(p78) 3.3.3博弈问题的与或图表示

2013-8-18

人工智能

113

3.3.1与或图基本概念(1) 例3.15 证明四边形全等。
B B? A?

A

D

C

D?

C?

分析:连接BD, B?D?,原来问题可以分解为两个子问题:

Q1:证明Δ ABC ≌ Δ A′B′C′
Q2:证明Δ BCD ≌ Δ B′C′D′ 原来问题可以分为两个子问题解决。

2013-8-18

人工智能

114

3.3.1与或图基本概念(2)
问题Q1还可以再被分解为: Q11 :证明AB= A′B′ Q12 :证明AD= A′D ′ Q13 :证明∠A=∠ A′ 或 Q11 ? :证明AB=A′B′ Q12 ? :证明AD=A′D ′ 或 Q21 ? :证明BC= B ′C′ Q22 ? :证明CD=C ′D′ 问题Q2还可以再被分解为: Q21 :证明BC= B′C′ Q22 :证明CD= C′D′ Q23 :证明∠ C= ∠ C ′

Q13 ? :证明BD=B′D ′

Q23 ? :证明BD= B′D′ ?

2013-8-18

人工智能

115

3.3.1与或图基本概念(3)
将原问题用图的形式表示如下:

Q 不带弧线的边 为或关系 Q1

弧线表示所连边为 “与”的关系 Q2

问题的解

Q11
2013-8-18

Q12

Q13 Q11 ' Q12 ' Q13 'Q21 Q22 Q23 Q21 ' Q22 ' Q23 '
人工智能 116

3.3.1与或图基本概念(4)
?

与或图的概念来源于问题求解
?

一个复杂的问题P常常可以分解为与之等价的一组 子问题P1, P2 , ? Pn,当这些问题全部可解时, 问题可解;任何一个子问题无解时,都将导致原问 题P无解。即一个问题与一组子问题的与等价。
一个复杂的问题P常常可以分别归约为与之等价的 一组子问题P1, P2 , ? Pn,其中任何一个子问题 可解时,问题可解;全部子问题无解时,原问题P 无解。即一个问题与一组子问题的或等价。

?

2013-8-18

人工智能

117

3.3.1与或图基本概念(5)

一个典型的与或图
2013-8-18 人工智能 118

3.3.2与或图知识表示(1)
?

与或图的几个概念
? ? ? ? ?

直接可解的问题称为本原问题。 本原问题对应的节点称为终止节点。 无子节点的节点称为端节点。 子节点为与关系,则该节点为与节点。 子节点为或关系,则该节点为或节点。

?

与或图一般表示问题的变换过程,就是从原问 题出发,运用某些规则不断的进行问题的分解 (得到与分支)和变换(得到或分支),而得 到一个与或图,与或图的节点一般代表问题, 整个图就表示问题空间。
人工智能 119

2013-8-18

3.3.2与或图知识表示(2)

与或图也是一个三元组 (Q0 , F , Qn) Q0表示初始问题 F表示问题变换规则集 Qn表示本原问题集 ?

2013-8-18

人工智能

120

3.3.2与或图知识表示(3) 例3.19 三阶梵塔问题。 对于梵塔问题,我们也可以这样考虑:为 把1号杆上的n个盘子搬到3号杆,可先把上面 的n-1个盘子搬到2号杆上;再把剩下的一个大 盘子搬到3号杆;然后再将2号杆上的n-1个盘 子搬到3号杆。这样,就把原来的一个问题分 解为三个子问题。这三个子问题都比原问题简 单,其中第二个子问题已是直接可解的问题。 对于第一和第三两个子问题,可用上面n个盘 子的方法,做同样的处理。 梵塔问题示例
2013-8-18 人工智能 121

回顾:二阶梵塔问题的状态空间图

1,1

A(1,3)
2,1

A(2,1)
3,1

B(1,2)

B(3,1)

A(3,2)
3,3

2,3

3,2

A(3,2)

1,3

1,2

2,2

A(2,1)
2013-8-18

B(1,3)
人工智能

A(1,3)
122

3.3.2与或图知识表示(4)
(1,1,1)=>(3,3,3)

(1,1,1)=>(1,2,2)

(1,2,2)=>(3,2,2)

(3,2,2)=>(3,3,3)

(1,1,1)=>(1,1,3)

(1,2,3)=>(1,2,2) (3,2,2)=>(3,2,1)

(3,3,1)=>(3,3,3)

(1,1,3)=>(1,2,3)

(3,2,1)=>(3,3,1)

三阶梵塔问题的与或树
2013-8-18 人工智能 123

3.3.2与或图知识表示(5)
?

把本原问题的解按照从左至右的顺序排列,就得到了 原始问题的解: (1,1,1)=>(1,1,3) (1,1,3)=>(1,2,3) (1,2,3)=>(1,2,2) (1,2,2)=>(3,2,2) (3,2,2)=>(3,2,1) (3,2,1)=>(3,3,1) (3,3,1)=>(3,3,3) 任何一个状态图都可以转化为与或图。

2013-8-18

人工智能

124

3.3.2与或图知识表示(6)
?

解不定积分问题的状态空间 进行不定积分求解的基本思想是:状态直接 用积分表达式表示;操作集内含有三部分知识。 第一部分:基本积分公式。 第二部分:积分变换公式。 第三部分:被积函数等价变化法则和变量替换 法则。

2013-8-18

人工智能

125

3.3.2与或图知识表示(7)
?

基本积分公式
?
? ? ? ? ?

r11:? adx ? ax;
r12:? x m dx ? x m ?1 /(m ? 1)(当m ? ?1);
当 当 r13:? x ?1dx ? lnx( x ? 0)或ln(-x)( x ? 0); a x dx ? a x / lna; r14:?

r15

e x dx ? e x ; :?

r16:? sinxdx ? ?cosx;

?

可以直接给出积分结果的,是本原问题
人工智能 126

2013-8-18

3.3.2与或图知识表示(8)
?

积分变换公式
?
? ?

r21:? (u ? v)dx ? ? udx ? ? vdx;

(和的积分公式 )

r22 : udv ? u ? dv ? ? vdu;(分部积分公式) ?
式) r23:? af(x)dx? a ? f(x)dx;(常系数因式分解公

?

这些变换公式可以将一个复杂的积分问题分解

成若干简单的积分问题。如果各简单问题可积,
则原复杂问题也可积,故是一种与的分解,可 用与节点表示。
2013-8-18 人工智能 127

3.3.2与或图知识表示(9)
?

被积函数变换规则
?
?

r31:

? f (x)dx ? ? g(x)dx; (如果f (x) ? g(x)时) r32 : f (x)dx ? f (g(t ))g' (t )dt; ? ?

?

这些规则可以把一个积分表达式等价地变换为另一
个表达式,如果新表达式可解,则可反变换出原表 达式的解。若一个积分表达式可以分别变换成多个 不同的积分表达式,如此形成的是一个或节点。

2013-8-18

人工智能

128

3.3.2与或图知识表示(10)
?

补充例:

x dx 2 5/ 2 ? (1? x )

4

2013-8-18

人工智能

129

x4 ? (1 ? x 2 )5 / 2 dx
r32:x=siny

?
r31:三角恒等式

sin 4 y dy 4 cos y

r32:y=zarctgz

r31:三角恒等式

? cot

?4

ydy

? tg
r32:y=arctgz

4

ydy

32z4 ? (1 ? z 2 )(1 ? z)4 dz

z4 ? 1 ? z 2 dz
r32:分子除以分母

1 ? (z ? 1 ? 1 ? z 2 )dz
2

(z 2 ? 1 ? ?

1 )dz 2 1? z
r21

? ?dz
r32:z=-u

? z dz
2

1 ? 1 ? z 2 dz
r32:z=tgw

1/3z3=1/3tg3(arcsinx)

?

du

?

dw

u=-tg(arcsinx)

w=arcsinx

3.3.2与或树知识表示(13)

x4 ? (1? x 2 )5 / 2 dx 1 3 ? arcsinx? tg (arcsinx) ? tg(arcsinx)3 3

2013-8-18

人工智能

132

3.3.3博弈问题的与或图表示(1)
?

?

博弈问题中用节点代表棋局。开局是初始状态, 终局有很多个,且有胜局、和局和败局之分。 棋子合法地任走一个棋子,棋局从一个状态变 到另一个状态。 对弈与迷宫问题的区别 ? 对弈问题 对弈双方只有一半选择权,双方 利益是完全冲突地。 ? 迷宫问题 探索者有完全的选择权,沿着他 认为有利的路线走下去。

2013-8-18

人工智能

133

3.3.3博弈问题的与或图表示(2)
?

对弈问题
?

?

?

我方(MAX)每走一着棋(半回合),都力图使自 己通往取胜的目标。轮到MAX走棋时,由于它掌握 着出棋的主动权,只要此时的各种招数中有一个能 通向胜局,它就会毫不犹豫的选择这一招,因此, MAX出棋的节点具有或节点的性质。 对手(MIN)每走一着棋(半回合),都力图干扰 MAX的选择,使其偏离取胜的目标。轮到MIN走棋时, 由于它掌握着对棋的主动权,因此只要此时只要全 部的着法中有一个能导致败局,它就会毫不犹豫的 出这一着,因此由MIN出棋的节点具有与节点的性 质。 博弈问题的状态空间一般都是与或树。
人工智能 134

2013-8-18

3.3.3博弈问题的与或图表示(3)
?

补充例 分火柴游戏。设有七根火柴,由MAX和 MIN两人轮流来分它们,要求每次都要把某堆 火柴分成不相等的两份,最后不能分下去的为 负,对方为胜。

2013-8-18

人工智能

135

3.3.3博弈问题的与或图表示(4)
MIN 7 MAX 6,1 MIN 5,1,1 MAX 4,1,1,1 MIN 3,1,1,1 MAX 2013-8-18 2,1,1,1,1,1 MIN 4,2,1 MAX 3,2,1,1 MIN 2,2,1,1,1 MAX 5,2 MIN 3,2,2 MAX 4,3 MIN 3,3,1 MAX 2,2,2,1

人工智能

136

3.4与或图搜索

3.4.1与或图搜索 3.4.2启发式与或树搜索

2013-8-18

人工智能

137

3.4.1与或图搜索(1)
?

?

?

搜索方式 与或图搜索也分为树式和“线”式 两种类型。对于树式搜索来讲,其搜索过程也 是不断地扩展节点,并配以返回指针,而形成 一棵不断生长的搜索树。 与或树搜索解图(树)是边扩展节点边进行逻 辑判断,以确定初始节点是否可解。一旦能够 确定初始节点的可解性,则搜索 停止。 解图(树)是由可解节点形成的一个子图 (树),这个子图(树)的根为初始节点,叶 为终止节点。
人工智能 138

2013-8-18

3.4.1与或图搜索(2)
?

可解性判别
?

可解节点要满足下列条件之一
? ? ?

终止节点是可解节点; 一个与节点可解,当且仅当其子节点全部可解; 一个或节点可解,只要其子节点至少有一个可解。 非终止节点的端节点是不可解节点; 一个与节点不可解,只要其子节点至少有一个不 可解; 一个或节点不可解,当且仅当其子节点全部不可 解。
人工智能 139

?

不可解节点要满足下列条件之一
? ?

?

2013-8-18

3.4.1与或图搜索(3)
?

搜索策略
深度优先搜索 穷举式搜索

盲目搜索
盲目碰撞搜索 与或图搜索

广度优先搜索

启发式搜索
2013-8-18 人工智能 140

3.4.1与或图搜索(4)
?

广度优先搜索策略

步1 把初始节点S0放入OPEN表。 步2 把OPEN表中的第一个节点(记为节点N)取出放入CLOSED 表,并冠以编号n。 步3 如果节点n可扩展,则作下列工作: (1)扩展节点N,将其子节点放入OPEN表尾部,并为每个子节点 配臵指向父节点的指针,以备标示过程中使用。 (2)考查这些节点中是否有终止节点。若有,将它们放入CLOSED表, 标示这些节点为可解节点,并用可解标示过程对其先辈节点中的 可解节点进行标示。 如果S0也被标示为可解节点,就得到解树, 搜索成功,退出。 (3)若S0不能确定为可解节点,则从OPEN表中删除具有可解先辈节 点。转步2。
2013-8-18 人工智能 141

3.4.1与或图搜索(5)
步4 如果节点N不可扩展,则作如下工作: (1)标示节点N为不可解节点。 (2)应用不可解节点标示过程对节点N的先辈节点中不可解的节点 进行标示。如果初始节点S0也被标示为不可解节点,则搜索 失败,退出搜索过程; (3)如果不能确定S0为不可解节点,则从OPEN表中删去具有不可 解先辈的节点。转步2。

2013-8-18

人工智能

142

3.4.1与或图搜索(6)
开始 把S0送入OPEN表 把OPEN表的第一个节点(节点 n)从表中移出,放入CLOSED表 Y 节点n可扩展? N

扩展节点n,将其子节点放 入OPEN表尾部,并为每个子 节点配置指向节点n的指针 N 子节点中有终止节点? Y 标示这些节点为可解节点 应用可解标示过程 Y 成功退出
2013-8-18

标示这些节点为不可解节点 应用不可解标示过程 肯定S0为不可解节点? N
人工智能
从OPEN表中删除具有不可解先辈节点

肯定S0为可解节点? N
从OPEN表中删除具有可解先辈节点

Y 失败退出
143

3.4.1与或图搜索(7)
?

有界深度优先搜索算法

步1 把初始节点S0放入OPEN表。 步2 把OPEN表中的第一个节点(记为节点N)取出放入CLOSED 表,并冠以编号n。 步3 如果节点N的深度大于等于深度界限,则转步5第(1)点。 步4 如果节点N可扩展,则作下列工作: (1)扩展节点N,将其子节点放入OPEN表首部,并为每个子节点 配臵指向父节点的指针,以备标示过程中使用。 (2)考查这些节点中是否有终止节点。若有,标示这些节点为可 解节点并用可解标示过程对其先辈节点中的可解节点进行标 示。如果也被标示为可解节点,就得到解树,搜索成功,退 出。 (3)若不能确定为可解节点,则从OPEN表中删除具有可解先辈 节点。转步2
2013-8-18 人工智能 144

3.4.1与或图搜索(8)
步5 如果节点N不可扩展,则作如下工作: (1)表示节点N为不可解节点。 (2)应用不可解节点标示过程对节点N的先辈节点中不可解的节点 进行标示。如果初始节点S0也被标示为不可解节点,则搜索 失败,退出搜索过程;如果不能确定S0为不可解节点,则从 OPEN表中删去具有不可解先辈的节点。 (3)转步2。

2013-8-18

人工智能

145

3.4.1与或图搜索(9)
开始 把S0送入OPEN表 把OPEN表的第一个节点(节点 n)从表中移出,放入CLOSED表 节点n深度>=深度界限? N Y 节点n可扩展? N Y

扩展节点n,将其子节点放 入OPEN表首部,并为每个子 节点配置指向节点n的指针 N 子节点中有终止节点? Y 标示这些节点为可解节点 应用可解标示过程 Y 成功退出 肯定S0为可解节点? N
从OPEN表中删除具有可解先辈节点

标示这些节点为不可解节点 应用不可解标示过程 肯定S0为不可解节点? N
从OPEN表中删除具有不可解先辈节点

Y 失败退出

2013-8-18

人工智能

146

3.4.1与或图搜索(10)
例3.16 设有与或树如图所示,其中1号节点为初始节 点,t1、t2、t3、t4均为终止节点,A和B是不可解的端

节点。采用广度搜索策略,搜索过程如: 1
编号 节点 1 2 3 4 5 6 7 8 9 返回 可解 指针 性 1 * ∨ 2 1 ∨ t1 1 ∨ 3 1 ∨ 4 2 ∨ t2 5 ∨ 5 4 ∨ t3 7 ∨ t4 7 ∨
147

3

2

B

5

t1

4

t4
2013-8-18

t3

t2

A
人工智能

3.4.1与或图搜索(11)
(1)扩展1号节点,得2号和3号节点,依次放入OPEN表尾部。 由于这两个节点都非终止节点,所以接着扩展2号节点。此时OPEN 表中只有3号节点。 (2)2号节点扩展后,得4号节点和t1节点。此时OPEN表中依 次有3号、4号和t1节点。 (3)扩展3号节点,得5号节点和B节点。两者均非终止节点, 所以继续扩展4号节点。 (4) 4号节点扩展后得节点A和t2。t2是终止节点,标记为可解

节点,放入CLOSED表。
(5) 扩展5号节点得t3 和t4 。由于t3 和t4 都为终止节点 (放入 CLOSED表),故可推得节点5、3、1均为可解节点。搜索成功,结

束。
2013-8-18 人工智能 148

3.4.2启发式与或树搜索(1)
?

盲目搜索的特点 ? 搜索从初始节点开始,先自上而下地进行搜 索,寻找终止节点及端节点,然后再自下而 上地进行可解性标记,搜索终止条件是初始 节点被标记为可解节点或不可解节点。 ? 搜索都是按确定路线进行的,选择节点进行 扩展时,只考虑位臵,而没考虑代价,因而 求得的解树不一定是代价最小的解树,即不 一定是最优解树。

2013-8-18

人工智能

149

3.4.2启发式与或树搜索(2)
?

有序搜索
为求得代价最小的解树,在每次确定欲扩
展的节点时,先往前多看几步,计算扩展这个

节点可能要付出的代价,并选择代价最小的节
点进行扩展,这种根据代价决定搜索路线的方 法称为与或树的有序搜索。

2013-8-18

人工智能

150

3.4.2启发式与或树搜索(3)
?

解树的代价(树根的代价)
?
?

状态图从初始节点计算代价。
与或树中解树的代价从树叶开始自下而上逐 层计算而求得的。 而解树的根对应的是初始节点S0。这就是说, 在与或树的搜索过程中,代价的计算方向与 搜索树的生长方向相反。

?

2013-8-18

人工智能

151

3.4.2启发式与或树搜索(4)
?

解树代价的计算方法
g(x)表示节点x的代价,c(x,y)表示节点x到其子 节点y的代价(即边xy的代价),则 (1)若x是终止节点,g(x)=0; (2)若x是或节点 g ( x) ? minn {c( x, yi ) ? g ( yi )} 1?i ? (3)若x是与节点x,则有两种计算公式。 n ①和代价法 g ( x) ? ?{c( x, yi ) ? g ( yi )}
i ?1

②最大代价法

g ( x) ? max {c( x, yi) ? g ( yi )}
1?i ? n

(4)对非终止的端节点x,g(x)=∞
2013-8-18 人工智能 152

3.4.2启发式与或树搜索(5) 例3.17 如下图所示的与或树。
S0 2 B 2 D 1 G 2 t5 1 t4 3 F 2 t3 1 C 1 E 5 t2 2 A 6 t1

2013-8-18

人工智能

153

3.4.2启发式与或树搜索(6)
由右边的解树可得 按和代价:g(A)=11,g(S0)=13 按最大代价:g(A)=6,g(S0)=8 由左边的解树可得: 按和代价:g(G)=3,g(D)=4,g(B)=6,g(S0)=8 按最大代价:g(G)=2,g(D)=3,g(B)=5,g(S0)=7 显然,若按和代价计算,左边的解树是最优解树, 其代价为8;若按最大代价计算,左边的解树仍然是最 优解树,其代价是7。 但有时用不同的计算代价方法得到的最优解树不 相同。
2013-8-18 人工智能 154

3.4.2启发式与或树搜索(7)
S 4 4

a1 5 a2
2 a4 a5 4 4 a6

b1 6
a3 3 5 b3 3

2

4

b2
7 b4

b5
2013-8-18 人工智能 155

3.4.2启发式与或树搜索(8)

左 解 树 右 解 树

节点

和代价
最大代价 节点 和代价 最大代价

a6 0 0

a5 0 0 b5 0 0

a4 0 0 b4 3 3

a3 4 4 b3 0 0

a2 6 4 b2 15 10

a1 21 10 b1 19 14

S 25 14 S 23 18

2013-8-18

人工智能

156

3.4.2启发式与或树搜索(7)
?

希望树
问题 计算代价g(x)时,都要求已知其子节点yi的 代价g(yi),但是,搜索是自上而下进行的,即先 有父节点,后有子节点,除非节点x的全部子节点 都是不可扩展节点,否则子节点的代价是不知道。 ? 解决方法 ①定义启发函数,由启发函数来计算子节点代价 g(yi),从而计算代价g(x)。 ②当yi被扩展时,也用启发函数计算yi的子节点的代 价,再计算g(yi),这时应该用后计算出的g(yi)代 替原先估计出的g(yi),并按此g(yi)自下而上重新 计算各先辈节点的代价值。 ③如此重复计算。
?

2013-8-18

人工智能

157

解决方法例
S 4 X a1 5 a2 2 a4 a5 4 4 a6 6 a3 3 4

b1
4

2013-8-18

人工智能

158

3.4.2启发式与或树搜索(8)
?

希望树
?

有序搜索的目的是求得最优解树,这就要求在搜索过程中 任一时刻求出的部分解树都是代价最小的。每次挑选欲扩 展的节点是都应该挑选有希望成为最优解树一部分的节点 进行扩展。由这些节点及其先辈节点所构成的与或树都有 可能成为最优解树的一部分,称为希望树。 搜索过程中希望树也是不断变化的。 希望树T (1)初始节点S0在希望树中。 (2)节点x在希望树T中,则一定有

? ?

①如果x是具有子节点的或节点,则具有最小值的那个 min {c( x, yi ) ? g ( yi )} 子节点一定在T中
1?i ? n

②如果x是与节点,则它的全部子节点都在T中。

2013-8-18

人工智能

159

3.4.2启发式与或树搜索(9)
?

与或树的有序搜索过程
(1)把初始节点S0放入OPEN表中。 (2)求出希望树T,即根据当前搜索树中节点的代价g求出以S0 为根 的希望树T。 (3)依次把OPEN表中T的端节点N选出放入CLOSED表中。 (4)如果节点N是终止节点,则做下列工作: ①标示N为可解节点。 ②对T应用可解标记过程,把N的先辈节点中的可解节点都标 记为可解节点。 ③若初始节点S0能被标记为可解节点,则T就是最优解树,成 功退出。 ④否则,从OPEN表中删去具有可解先辈的所有节点。

2013-8-18

人工智能

160

3.4.2启发式与或树搜索(10)
(5)如果节点N不是终止节点,且它不可扩展,则做下列工作:

①标示N为不可解节点。 ②对T应用不可解标记过程,把N的先辈节点中的不可解节点 都标记为不可解节点。 ③若初始节点S0也被标记为不可解节点,则失败退出。 ④否则,从OPEN表中删去具有不可解先辈的所有节点。 (6)如果节点N不是终止节点,但它可扩展,则可做下列工作: ①扩展节点N,产生N的所有子节点。 ②把这些子节点都放入OPEN表中,并为每一个子节点配臵指 向父节点(节点N)的指针。 ③计算这些子节点的g值及其先辈节点的g值。 (7)转(2)。

2013-8-18

人工智能

161

3.4.2启发式与或树搜索(11)
开始 把S0送入OPEN表,计算g(S 0) 由g(x)计算T 依次把OPEN表中T0的端节点N选 出放入CLOSED表中,冠以编号n N是终止节点 Y Y 标记N为可解节点,并对T0 应用可解标记过程 S0可解? N 成功退出
从OPEN表中删除具 有可解先辈节点

Y N N可扩展 N

标示N为不可解节点,并对T0 应用不可解标记过程 S0为不可解节点? N
从OPEN表中删除具 有不可解先辈节点

Y

Y 失败退出

扩展N,将其子节点放入OPEN表 中,并配以指向N的返回指针, 计算各子节点的g(x)值及其 先辈节点的g(x)值 N

2013-8-18

人工智能

162

3.4.2启发式与或树搜索(11)
例3.18 下面我们举例说明有序搜索过程。(边代价按1 算)
用和代价 法计算

8

7

(a)

设初始节点为S0,每次扩展两层,并设S0经扩展后得到 (a)所示的与或树

2013-8-18

人工智能

163

3.4.2启发式与或树搜索(11)
?

扩展右边的子树:

8 7 7

11

6

2013-8-18

人工智能

164

3.4.2启发式与或树搜索(11)

8 3 2 6

11

2013-8-18

人工智能

165

3.4.2启发式与或树搜索(11)

S可解,搜索结束

8 3 2 2 3

2013-8-18

人工智能

166

3.5博弈树搜索(1)
?

二人零和、全信息、非偶然博弈
?

?

?

对垒的A,B双方轮流采取行动,博弈的结果 只有三种情况:A方胜,B方败;B方胜,A方 败;双方战成平局。 在对垒过程中,任何一方都了解当前的格局 及过去的历史。 任何一方在采取行动前都要根据当前的实际 情况,进行得失分析,选取对自己最为有利 而对对方最为不利的对策,不存在“碰运气” 的偶然因素。即双方都是很理智地决定自己 的行动。
人工智能 167

2013-8-18

3.5博弈树搜索(2) 3.5.1博弈树概念 3.5.2极小极大分析法 3.5.3α -?剪枝技术

2013-8-18

人工智能

168

3.5.1博弈树概念(1)
?

博弈的过程
在博弈过程中,任何一方都希望自己取 得胜利。因此,当某一方当前有多个行动方 案可供选择时,他总是挑选对自己最为有利 而对对方最为不利的那个行动方案。这样, 如果站在某一方(如A方,即在A要取胜的意 义下),把上述博弈过程用图表示出来,则 得到的是一棵“与或树”。

2013-8-18

人工智能

169

3.5.1博弈树概念(2)
?

博弈树的特点
?
?

博弈的初始格局是初始节点。
在博弈树中,“或”节点和“与”节点是逐 层交替出现的。自己一方扩展的节点之间是 “或”关系,对方扩展的节点之间是“与” 关系。双方轮流地扩展节点。 所有自己一方获胜的终局都是本原问题,相 应的节点是可解节点;所有使对方获胜的终 局都是不可解节点。

?

2013-8-18

人工智能

170

3.5.2极小极大分析法(1)
?

极小极大分析法的基本思想
1. 设博弈的双方中一方为A,另一方为B。然 后为其中的一方(例如A)寻找一个最优行 动方案。 2. 为了找到当前的最优行动方案,需要对各 个可能的方案所产生的后果进行比较。 3. 为计算得分,需要根据问题的特性信息定 义一个估价函数,用来估算当前博弈树端 节点的得分。这时估算出来的得分为静态 估值。

2013-8-18

人工智能

171

3.5.2极小极大分析法(2)
4. 当端节点的估值计算出来后,再推算出父节点的 得分,推算的方法是:
? 对“或”节点,选其子节点中一个最大的得分作为父节 点的得分,这是为了使自己在可供选择的方案中选一个 对自己最有利的方案; 对“与”节点,选其子节点中一个最小的得分作为父节 点的得分,这是为了立足于最坏的情况。这样计算出的 父节点的得分称为倒推值。

?

5.

如果一个行动方案能获得较大的倒推值,则它就 是当前最好的行动方案。

2013-8-18

人工智能

172

3.5.2极小极大分析法(3)

图3—19 倒推值的计算
2013-8-18 人工智能 173

3.5.2极小极大分析法(4)

例3.22 一字棋游戏。设有如图3—19(a)所 示的九个空格,由A,B二人对弈,轮到 谁走棋谁就往空格上放一只自己的棋子, 谁先使自己的棋子构成“三子成一线” 谁就取得了胜利。
b a
(a)
2013-8-18

图3—19 一字棋
人工智能

(b)
174

3.5.2极小极大分析法(5)

设A的棋子用“a”表示,B的棋子用“b”表示。 为了不致于生成太大的博弈树,假设每次仅扩展 两层。

估价函数定义如下:设棋局为P,估价函数为 e(P)。 (1)若P是A必胜的棋局,则e(P)=+∞。 (2)若P是B必胜的棋局,则e(P)=-∞。 (3)若P是胜负未定的棋局,则e(P)=e(+P)-e(-P)
2013-8-18 人工智能 175

3.5.2极小极大分析法(6)
e(+P):棋局P上有可能使a成为三子成一线的数目; e(-P):棋局P上有可能使b成为三子成一线的数目。

b a

b

a b

b

(a) (b) 上图(a)所示棋局,e(P)=6-4=2 对图(b)所示棋局,e(P)=6-4=2 (a)和(b)具有对称性,可以作为一个棋局。

2013-8-18

人工智能

176

3.5.2极小极大分析法(7)
用这样的静态估值可得第一步的极小极大分析图, 其中扩展深度为2 1

a

-1

a

-2

a

1

a b

a

b a b

a b

a b

b a

b a a

b a b a b

1

0

1

0

-1

-1

0
人工智能

-1

-2

0
a

b
a b 177

2013-8-18

1

2

3.5.2极小极大分析法(8)
b a

1

a b a

a

b a

b

0

1

1

a a

b

0

a a

b a b a b a b a b a b a b a b b a a b a b b a b a a a b a

b a b a

b a b

1

0

0

0

0

0
b

1

2

1

a b b a b a b a b a b a b a a b a a a b a b b b

b

a a b

a a
b

b b a a

b b a a

b

b

a a b

a a b

2

2 2013-8-18 1

1

1

1

1 人工智能

0

0

1

0

0 178

3.5.2极小极大分析法(9) 按照a方走步最佳得分为1
a a b a b a

不利得分为
a b a a a

b

a

b a

如果a方按这一估计选择 种最佳选择,实际上,除了 都立即出现a方的胜局。
2013-8-18 人工智能

,则b方有4 a b 之外, a
b

179

3.5.2极小极大分析法(10) 可见此时b方应先考虑占领a方已有两个棋子的路, 而不能仅仅考虑增多自己的路, e(p)在这 一点不能作出正确的估计。 下面定义一种比较精确的启发式函数,为此先引 入几个概念: (1)如果一条路上没有任何棋子占位,则称它 是0阶路。 (2)如果一条路上仅有一个a方(b方)的棋子 占位,则称为a方的1阶路。 (3)如果一条路上有两个a方的棋子占位,则称 它为a方的2阶路。
2013-8-18 人工智能 180

3.5.2极小极大分析法(11)

h2(n)= (a方一阶路-b方一阶路)+ 4×(a方二阶路-b方二阶路)+a 其中 +2,若a方占领b方二阶路 a= -2,若b方占领a方二阶路 0 其他
若n为终局节点:a胜 h2(n)= +∞ b胜 h2(n)= -∞ 和局 h2(n)= 0 利用新的启发函数第二步扩展的结果为
2013-8-18 人工智能 181

3.5.2极小极大分析法(12)
b a

-2

a b a

a

b
a

b

-2

-4

-4

a a

b

-4

a a

b
a b a b a b a b a b a b a b b a a b a b b a b a a a b a

b a b
a

b
a b

1

0

3

3

-2

3
b a a b a a b b

-1

-3

-4

a b b a b a b a b a b a b a a b a a a b a b b b

b b a a

b b a a

b a a b a a b

b

7

2

-4

4

4

4

-4
人工智能

0

0

1

3

3
182

2013-8-18

a b a b

-2

a a b a b

-8

a b a a b

-4

a b a a b

-3

a a b a b b

a a b a a b a a b a a b a b b b b b

a b a b a b

a b a b a b a a b b a b

b a b a a b

a b a b a b b a b a a a a b a a a a b b b b b b

-2

-8

-2

0
a b a a b

-4 -7

-2

-2

-2
a b a b a

0 -2

0

-3

2

a b a a b b

a b a a b b

a b a a b b

b a b a a b

a b a b b a

a b a b b a

a b b a b a

b a b a b a

-7

-5

-2

2

4

4

1

-2

0

b a b a a b b a

b a b a a b b a

b a b b a a b a

0

4

0

b a b a a b a

b a b a a b a

0
b a b a a b a

b a b a b a

-6

b a b b a a b a

b a b a a b b a

-6

0

0

3.5.3 α -?剪枝技术(1)
?

极小极大分析法的缺点是效率低,在此 基础上用α -?剪枝技术。基本思想为:
?

对于一个与节点MIN,若能估计出其倒推值的 上确界β ,并且这个β 值不大于MIN的父节点 (一定是或节点)的估计倒推值的下确界α , 即α ≥β ,则就不必再扩展该MIN节点的其余 子节点了(因为这些节点的估值对MIN父节点 的倒推值已无任何影响了)。这一过程称为 α 剪枝。

2013-8-18

人工智能

185

3.5.3 α -?剪枝技术(2)
?

对于一个或节点MAX,若能估计出其倒推值的 下确界α ,并且这个α 值不小于MAX的父节点 (一定是与节点)的估计倒推值的上确界β , 即α ≥β ,则就不必再扩展该MAX节点的其余 子节点了(因为这些节点的估值对MAX父节点 的倒推值已无任何影响了)。这一过程称为 β 剪枝。

2013-8-18

人工智能

186

3.5.3 α -?剪枝技术(3)

≥2
≤2 N 2

S

2
≤ 0V

≥2

G

2
≤ -1

≥6
I

M

≥0
R

U

0
≤-5 T

2 D ≤1 F

L 6 D 0

J K Q A B C E H P 2 9 3 1 -1-1 3 6 8 -1 2 0 3 -5 7 4 -2 6 -1 8 -7 0 3 -1
2013-8-18 人工智能 187

3.5.3 α -?剪枝技术(4)
N

1

3 2 3 -1 -2 1 4 3 4 6 5 4 1 -5 6 1 7 5 3 2 6

2013-8-18

人工智能

188

3.5.3 α -?剪枝技术(5)
N

0 5 -3 3 3 -3 0 2 -2 3 5 4 1 -3 0 6 8 9 -3
2013-8-18 人工智能 189

3.5.3 α -?剪枝技术(6)
N

V

F

I

L

D

R

T

J K Q C E H P 0 5 -3 3 3 -3 0 2 -2 3 5 4 1 -3 0 6 8 9 -3
2013-8-18 人工智能 190

The End!


赞助商链接
相关文章:
《人工智能》实验二 图搜索问题求解
《人工智能》实验 图搜索问题求解_计算机软件及应用_IT/计算机_专业资料。淮海...3 《人工智能》实验报告 实验体会通过这次实验更加加深了我对 prolog 使用的理解...
智能信息处理 图搜索问题求解 实验报告
武 夷 学 院 实验报告课程名称: 实验题目: 学生班级: 学生姓名: 学生学号: 指导教师: 完成日期: 智能信息处理 图搜索问题求解 09 级计科一班 陈宏菱 20094011...
学号-姓名-实验二图搜索问题求解
第3章 图搜索与问题求解作... 9页 2财富值 AI图搜索与问题求解作业讲......如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处...
prolog实验报告PROLOG语言编程练习及图搜索问题求解
语言编程练习及图搜索问题求解 人工智能及应用 专业班级: 学号: 学生姓名: 成绩...实验目的及要求 、所用仪器、设备 三、实验原理 四、实验方法与步骤 五、...
更多相关文章: