与或树的搜索策略搜索的完备性与效率.pptx

第10次课 10月07日
上次课程回顾




与或图搜索:搜索从初始节点到一组终节点集N的一个 解图。 对于与或图搜索，是通过对局部图的评价来选择待扩 展的节点。 解图的求法是：从节点n开始，正确选择一个外向连接 符，再从该连接符所指的每一个后继结点出发，继续 选一个外向连接符，如此进行下去直到由此产生的每 一个后继节点成为集合N中的一个元素为止。 具有最小耗散值的解图称为最佳解图。 能解节点 不能解节点
算法

极大极小过程MINIMAX：
1. T:=(s, MAX)，OPEN:=(s)，CLOSED:=( );开始时树由初始节点 构成，OPEN表只含有S. 2. LOOP1: IF OPEN =( ) THEN GO LOOP2; 3. n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED);将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); ni达到深度k,计算各端节点f值.
n5(1)
2
n6
n8
n8(0)
目标
n7
目标
n7(0)
红色：5 蓝色：6
3次循环之后
n0 n1 n2
初始节点
n1 n4 5
n0
初始ห้องสมุดไป่ตู้点
1 n4(1)
n2(4)
n3
n5 n3(4) n6(2)
n5(1)
2
n6

(c)
[3,3] B
[3, +∞]
A
4
3
8
(d)
[3,3] B
[3, +∞]
A
[-∞,2] C
4
3
8
2
-搜索策略: 剪枝示例(3)
(e)
[3,3] B [3,14] A
[-∞,2] C
[-∞,14] D
(f )
4 3 8 2 14
[3,3] A
[3,3] B
[-∞,2] C
[2,2] D
4
3
8
极大极小策略分析
MAX A 3
MIN
B
3
C
2
D
2
MAX
3
12
8
2
4
6
14
5
2
– 端节点的棋局值通过f(s)计算得到，其余节点采取倒推法计算； – B、C、D是MIN走步节点，MAX考虑最坏情况，取子节点估值最小(MIN取极小)； – Ａ是MAX走步节点，可考虑最好情况，取子节点估值最大者(MAX取极大)
极大极小搜索过程
• 算法分两阶段：
– 2-4步用宽度优 先法生成规定 深度的全部博 弈树，并计算 端节点棋局值 – 6-8步从底向上 逐级倒推非端 节点的棋局值。
• 算法的结果(求当 前状态的最佳走 子算法)：当前棋 局的一步走法， 而图搜索找到的 是从初始状态到 目标状态的解路 径
极大极小策略的应用示例
(剪枝: 终止后辈节点以下的搜索过程)
• 简记为：
– 极小≤极大，剪枝 – 极大≥极小，剪枝
-搜索策略
MAX MIN 0
f
0 1
d
3
m h

或节点
或
变换 问题n为 n1 …. nk个新问题。 只要解决某个问 题就可解决其父辈 问题的节点集合。
A
B
E
F
D
ቤተ መጻሕፍቲ ባይዱ
G
I
Q
Q1
Q2
Q11
Q12
Q13
Q11’
Q12’
Q13’
Q21
Q22
Q23
Q21’
Q22’
Q23’
思考： 问题Q解决方案：？

概念与术语
本原问题：直接可解的简单问题（不能再分解或变换）。
节点：对应问题
子节点：对应子问题（由节点分解或变换） 与或树的节点代表问题，其中既有与关系又有或关系， 整个树表示问题空间。
与节点 与
分解 问题n为n1 …. nk个 子问题。 只有解决所有子问题，才 能解决其父辈问题的子问题集 合。 问题分解过程用图表示： 图中节点代表问题。与关 系集合中，各个结点之间用一 段小圆弧连接标记。
问题求解过程就是在一个与或树中寻找一个从初始节点（原 始问题）到目标节点（可解的简单问题）的路径问题。
例1: t 是终止节点,1 可解性？
1 3 5 B t1 2 3 5 B t1 1 2 4
4
t4
t3
t4
t3
t2
A
t2
A
例2：
Q作为初始节点，把子问题Q11，Q12，Q13· · · · · · 作为目标节点， 则对问题Q的求解就是在与或树中寻找从Q到Q11，Q12，Q13· · · · · · 的路径 问题。
Q
Q1
Q2
Q11
Q12
Q13
Q11’
Q12’
Q13’

5.3.1 回溯策略
end; 将CS加入PS；
end else
begin 将CS子状态（不包括PS、NPS和NSS中已有的） 加入NPS； CS：= NPS中第一个元素；
将CS加入到PS； end end； return FAIL; end.
5.3.1 回溯策略
回溯搜索示意图的回溯轨迹： 初值：PS=[A]； NPS=[A]； NSS=[ ]； CS=A。
为了保证找到解，应选择合适的深度限制值，或 采取不断加大深度限制值的办法，反复搜索，直 到找到解。
5.3.3 深度优先搜索策略
深度优先搜索过程：
Procedure depth_first_search
begin
open:=[start];closed:=[ ];d:=深度限制值
while open[ ] do
A BC
(a) 初始状态
积木问题
A B C
(b) 目的状态
5.3.2 宽度优先搜索策略
操作算子为MOVE（X，Y）：把积木X搬到Y（积 木或桌面）上面。
MOVE（A，Table）：“搬动积木A到桌 面上”。
操作算子可运用的先决条件：
（1）被搬动积木的顶部必须为空。 （2）如果 Y 是积木，则积木 Y 的顶部也必须为空。 （3）同一状态下，运用操作算子的次数不得多于一次。
第3章 搜索策略
第3章 搜索求解策略
3.1 搜索的概念 3.2 状态空间的搜索策略 3.3 盲目的图搜索策略 3.4 启发式图搜索策略 3.5 与/或图搜索策略
第3章 搜索求解策略
3.1 搜索的概念 3.2 状态空间知识表示方法 3.3 盲目的图搜索策略 3.4 启发式图搜索策略 3.5 与/或图搜索策略

与或图的搜索 及应用
北京信息科技大学 孙骏 2014.05.13
与或图的搜索策略
1 与或图的一般搜索过程 2 与或图的广度优先搜索
3 与或图的深度优先搜索
4 与或图的有序搜索 5 博弈树的启发式搜索
1 与或图的一般搜索过程

与图: 把一个原问题分解为若干个子问题，P1，P2， P3，…可用“与图”表示；P1，P2，P3，…对应的子问
S0 2
A 6 t1 5 t2 E C 1 t3 2 F 3 1 2 B 2
D 1 G 1
t4 2 t5
解：左边解树， 按和代价：h(A)=11 h(S0)=13; 按最大代价：h(A)=6 h(S0)=8; 右边解树， 按和代价：h(G)=3, h(D)=4, h(B)=6, h(S0)=8; 按最大代价：h(G)=2, h(D)=3, h(B)=5, h(S0)=7
P
E
F
2
G
0 0 2 2 0 0
H
3
2
h(N)=2, h(P)=7, h(C)=3, h(A)=8 左子树h(S0)=9
3
2
2
2
三阶梵塔问题
1 2 3 1 2 3
A
A
B C
B C
初始配置
目标配置

问题描述: 采用三元组表示状态: S=(i,j,k) 其中，i, j, k分别表示金片C,B，A所在的钢针号。 初始状态（1，1，1），目标状态（3，3，3）
a
4-5=-1 b
5-4=1
5-5=0
5-5=0
6-6=0
程可用一个“与或图”来表示
P P1 P11 P12 P2 P31 P3 P32 P33

8
• 解图：
初始节点
目标
目标
该解图的耗散值为: (1+(1+1))+(1+1)=5
9
局部解图的耗散值计算
如果我们也将局部图的耗散值记为k(n,N),则: ① 若n是局部图的一个叶节点，则
k(n,N)=h(n)；
② 若n是一个外向连接符指向后继节点{n1,…, ni}，并设该连接符的耗散值为Cn，则
1
与或图例子
2
2.1 基本概念
与或图是一个超图，节点间通过连接符连接。
超图是图的最一般的表达形式，无论什 么图，你都可以说它是超图，就像无论 整数，无理数，复数，反正都是数一样。
超图的定义由两个集合构成：一个点集A， 另一个是点集A中元素的子集的集合B(B 中所有元素的并集就是集合A)。A中的元 素叫节点；B中的元素就叫边，这样超图 H=(A,B)。
17
与或树的一般搜索过程(续)
• 由上述搜索过程所形成的节点和指针 结构称为搜索树。 • 与或树搜索的目标是寻找解树，从而 求得原始问题的解。如果在搜索的某一 时刻，通过可解标示过程可确定初始节 点是可解的，则由此初始节点及其下属 的可解节点就构成了解树。
18
与或树的一般搜索过程(续)
• 如果在某时刻被选为扩展的节点不可扩 展，并且它不是终止节点，则此节点就 是不可解节点。此时可应用不可解标示 过程确定初始节点是否为不可解节点，
如果可以确定初始节点是不可解的，则搜 索失败；否则继续扩展节点。
19
与或树的性质
• 可解与不可解标示过程都是自下而上进行 的，即由子节点的可解性确定父节点的可解性。
• 在与或树中搜索解树时，如果已确定某个 节点为可解节点，则其不可解的后裔节点就不 再有用，可从搜索树中删去；同样，如果已确 定某个节点是不可解节点，则其全部后裔节点 都不再有用，可从搜索树中删去，但当前这个 不可解节点还不能删去，因为在判断其先辈节 点的可解性时还要用到它。

s k0 = 2 s k0 = 3 s k0 = 1 s k0 = 3 s k0 = 1 s k0 = 2 s k1 = 2 s k1 = 3 s k1 = 1 s k1 = 3 s k1 = 1 s k1 = 2
17
第七章 搜索策略
根本概念 状态空间的搜索策略 与/或图的搜索策略 博弈树搜索
➢ 7.1.2 状态图表示法
P
P1
P2
P3
27
第七章 搜索策略
根本概念 状态空间的搜索策略 与/或图的搜索策略 博弈树搜索
3) “与/或〞树：
上述两种方法也可结合起来使用,此时的图称为“与/或 〞树。其中既有“与〞节点,又有“或〞节点。
注意：状态图是与/或图的特殊形式,即与/或图中既有与关系 又有或关系,而状态图只有或关系。
描述； 2) 叶节点：无子节点的节点,亦称端节点； 3) 终止节点：有解的叶节点,对应本原问题。即终止节点一定
是端节点,但端节点不一定是终止节点。
29
第七章 搜索策略
根本概念 状态空间的搜索策略 与/或图的搜索策略 博弈树搜索
4) 可解节点：满足以下条件之一者： 它是一个终止节点。 它是一个“或〞节点,且其子节点中至少有一个是可解节点。 ③它是一个“与〞节点,且其子节点全部是可解节点。 5) 不可解节点：关于可解节点的三个条件全部不满足的节点
其中：a表示q1的变化, b表示q2的变化, c表示q3的变化。
9
第七章 搜索策略
根本概念 状态空间的搜索策略 与/或图的搜索策略 博弈树搜索
➢ 7.1.2 状态图表示法
把这种描述得到的有向图称为状态〔空间〕图。
其中的节点代表一种格局〔或称为状态〕,而两节 点之间的连线表示两节点之间的联系,它可视为某种操 作、规则、变换等。

6 10 14
11 13 75 13 2
9 15 4 12 86 10 14
11 9 13 75 13 2
15 4 12 86 10 14
11 9 13 75 13 2
4 15 12
86 10 14
5.1.3 与/或树表示法 回顾
对于一个复杂问题，直接求解往往比较困 难。此时可通过下述方法进行简化：
采用某种策略，在知识库中寻找可利用的知 识，从而构造一条代价较小的推理路线，使 问题得到解决的过程称为搜索。
5.1.1 什么是搜索
搜索分为盲目搜索和启发式搜索。
盲目搜索是按照预定的控制策略进行搜索，在
搜索过程中获得的中间信息不用来改进控制策 略。
启发式搜索是在搜索中加入了与问题有关的启发性
信息，用以指导搜索朝着最有希望的方向前进，加速 问题的求解过程并找到最优解。
适用于其状态空间图是树状结构的一类问题。
启发式搜索
使用与问题有关的启发性信息，并以这些启发性 信息指导搜索过程，可以高效地求解结构复杂的 问题。
5.2.1 状态空间的一般搜索过程
一个复杂问题的状态空间一般都是十分庞大的。如 64阶梵塔问题共有3的64次方个不同的状态。 把问题的所有状态空间都进行存储有时候是不可能的。 把问题的所有状态空间都进行存储也是不必要的。因 为与解题有关的状态空间往往只是整个状态空间的一 部分，只要能生产并存储这部分状态空间就可以求出 问题的解。
5.2.1 状态空间的一般搜索过程
OPEN表和CLOSE表
OPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在 OPEN表中的排列顺序是不同的。
CLOSE表用于存放将要扩展的节点。对一个节点的扩展是指：用所 有可适用的算符对该节点进行操作，生成一组子节点

5.3.1 回溯策略
end; 将CS加入PS；
end else
begin 将CS子状态（不包括PS、NPS和NSS中已有的） 加入NPS； CS：= NPS中第一个元素；
将CS加入到PS； end end； return FAIL; end.
5.3.1 回溯策略
回溯搜索示意图的回溯轨迹： 初值：PS=[A]； NPS=[A]； NSS=[ ]； CS=A。
then return FAIL;
*回老路退回
if Goal(Data) then return NIL;
*达到目的地成功返回
if DeadEnd(Data) then return FAIL;
*达到不合理状态，退出
if Length(DataList) > Bound then return FAIL; *已到深度限制，退回
5.2.1 状态空间表示法
例1 八数码问题的状态空间。
状态集 S ：所有摆法
操作算子： 将空格向上移Up 将空格向左移Left 将空格向下移Down 将空格向右移Right
5.2.2 状态空间的图描述
（状态）
（操作算子 ）
状态空间的有向图描述
5.2.2 状态空间的图描述
八数码状态空间图
5.2.2 状态空间的图描述
5.3.2 宽度优先搜索策略
Procedure breadth_first_search begin open：= [start]; closed：= [ ] *初始化 while open [ ] do
begin 从open表中删除第一个状态，称之为n； 将n放入closed表中； if n = 目的状态 then return (success);