当前位置：文档之家 › 第4章 与或图搜索

第4章 与或图搜索

  • 格式：ppt
  • 大小：1.74 MB
  • 文档页数：48

下载文档原格式

  / 48

合集下载

人工智能 -课程简介+课程大纲模板

人工智能 -课程简介+课程大纲模板

人工智能-课程简介+课程大纲模板(总7页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《人工智能理论与应用》课程简介课程编号：A0940111课程名称：人工智能理论与应用学分/学时：3/48先修课程：《数据结构》、《离散数学》和《高级程序设计语言》适用专业：计算机科学与技术课程性质：限选考核方式：考查考核形式：大作业、实验评估建议教材：人工智能教程，王士同主编，电子工业出版社，2006年2月第2版内容简介：（200字以内）（黑体五号）1、人工智能研究的发展和基本原则：人工智能的研究和应用；人工智能研究的发展；人工智能研究的成果；人工智能研究的基本原则；存在的问题和发展前景2、一般图搜索：回溯策略、图搜索策略、无信息搜索过程、启发式图搜索过程、搜索算法讨论。

3、与或图搜索问题：与或图的搜索、与或图的启发式搜索算法AO*、博弈树的搜索。

4、谓词逻辑与归结原理：命题逻辑、谓词逻辑基础、谓词逻辑归结原理、HERBRAND定理。

5、知识表示：知识、知识表示、知识观、产生式表示方法、语义网络表示、框架表示以及其他表示方法。

6、不确定性推理方法：不确定性推理的基本问题、贝叶斯网络、主观贝叶斯方法、确定性方法、证据理论。

7、机器学习：机器学习概论、实例学习、基于解释的学习、决策树学习、神经网络学习、知识发现与数据挖掘。

8、高级搜索：基本概念、局部搜索算法、模拟退火算法、遗传算法等。

人工智能理论与应用Artificial Intelligence Theory and Application 课程编号：A0940111学分：3学时：48 学时（讲课学时：32 实验学时：16）先修课程：《数据结构》、《离散数学》和《高级程序设计语言》适用专业：计算机科学与技术建议教材：人工智能教程，王士同主编，电子工业出版社，2006年2月第2版主要参考书：（1）高等学校规划教材:人工智能原理及其应用电子工业出版社王万森 2012（2）人工智能及其应用(第4版) 蔡自兴、徐光佑清华大学出版社 2010开课学院：计算机科学与工程学院修订日期：2015年4月一、课程说明（黑体五号）人工智能是一门综合性前沿学科，是计算机学科的重要分支。

人工智能第4章图搜索技术

人工智能第4章图搜索技术
OPEN表的首部，转步2。
例4.4 对于八数码问题，应用
深度优先搜索策略，可得如图4—
6所示的搜索树。
283
深度优先搜索亦称为纵向搜 1 4 765
索。由于一个有解的问题树可能
含有无穷分枝，深度优先搜索如
果误入无穷分枝(即深度无限,但
解不在该分支内)，则不可能找到
目标节点。所以，深度优先搜索
策略是不完备的。另外，应用此
例4.6 设A城是出发地，E城是目的地，边上的数字代表 两城之间的交通费。试求从A到E最小费用的旅行路线。
B 4
6
A
3
4
A
E
C 3
D1
3
4
D2 23
E1 3
C
D
2
(a)
E2
B2 6
深度优先搜索算法：
步1 把初始节点S0放入OPEN表中； 步2 若OPEN表为空，则搜索失败，退出。
步3 取OPEN表头节点N放入CLOSED表中，并冠以顺序编号n；
步4 若目标节点Sg=N，则搜索成功，结束。 步5 若N不可扩展，则转步2； 步6 扩展N，将其所有子节点配上指向N的返回指针依次放入
2831 14 765
第4章 图搜索技术
2 283
14 765
6 83
214 765
7 283 714 65
14 83 214 765
15 283 714 65
22 83 214 765
23 813 24 765
3 23 184 765
8 23
1 84 7 65
9 23 184 765
16 1 23
第4章 图搜索技术
步1 把S0放入OPEN表中，置S0的深度d(S0)=0； 步2 若OPEN表为空，则失败，退出。 步3 取OPEN表头节点N，放入CLOSED表中，并 冠以顺序编号n； 步4 若目标节点Sg=N，则成功，结束。 步5 若N的深度d(N)=dm(深度限制值)，或者若N无 子节点，则转步2； 步6 扩展N，将其所有子节点Ni配上指向N的返回 指针后依次放入OPEN表中前部，置d(Ni)=d(N)+1，转 步2。

与或图搜索问题

与或图搜索问题

与或图搜索问题的特点
组合优化问题
与或图搜索问题是一个典型的组 合优化问题，因为解决方案空间 通常非常大，需要采用高效的搜 索策略来找到最优解。
逻辑约束
与或图中的节点之间存在逻辑约 束，即某些节点必须同时满足与 （AND）或（OR）关系。
决策变量
与或图中的节点代表决策变量， 需要确定它们的取值以最大化目 标函数或满足特定条件。
03
与或图搜索问题的求解算法
深度优先搜索算法
深度优先搜索是一种用于遍历或搜索树 或图的算法。该算法会尽可能深地搜索 树的分支，当节点v的所在边都己被探 寻过，搜索将回溯到发现节点v的那条
边的起始节点。
深度优先搜索算法适合求解与或图中的 AND-OR图问题，可以找到所有解或
最优解。
算法步骤：选择一个起始节点，标记为 已访问，然后递归地搜索与该节点关联 的所有未被访问的节点，直到所有节点
与或图搜索问题的求解目标
找到最优解
与或图搜索问题的求解目标是找到满足所有 逻辑约束的节点组合，以最大化目标函数或 满足特定条件。
高效求解
由于与或图搜索问题通常具有较大的解决方案空间 ，因此需要采用高效的搜索策略和启发式算法来快 速找到最优解。
实际应用
与或图搜索问题在许多实际应用中具有广泛 的应用，如电路设计、计划调度、物流优化 等。
路径规划
在路径规划问题中，与或图搜索问题可以用于寻找满足特定条件的路径， 如最短路径、最少花费路径等，使得路径能够连接起点和终点。
02
与或图搜索问题概述
与或图搜索问题的定义
与或图搜索问题是一种组合优化问题，旨在寻找满足一系列与 （AND）或（OR）逻辑关系的节点组合。
它通常由一个有向图表示，其中节点表示决策变量，边表示 逻辑关系。

第4章 图搜索策略

第4章 图搜索策略

4.1.1 通用或图搜索算法
或图通用搜索算法：
设S0 ：初始状态, Sg：目标状态 1. 产生一仅由S0组成的open表，即open=(S0)； 2. 产生一个空的closed表； 3. 如果open为空，则失败退出； 4. 在 open 表上按某一原则选出第一个优先结点， 称为n，将n放到closed表中，并从open表中去掉 n；
4.1.2 A算法与A*算法
由定义有 f(n’ ） =g(n’ ） +h(n’ ） =g*(n’ ） +h(n’ ） (因为n’在最优路径上） ≤ g*(n’ ） +h*(n’ ） =f*(n’ ） =f*(S0 ） (由于A*的定义h(n) ≤h*(n)) 所以f(n’）≤f*(S0）成立。
4.1.2 A算法与A*算法
推论1 若问题有解，A*算法一定终止。
（2-1）
因为若A*算法不终止，则命题2的
f(n）≥g(n）≥g*(n）≥d*(n）· e
与命题3的
f(n’）≤f*(S0） (2-2）
同时成立，则产生矛盾。
4.1.2 A算法与A*算法
命题 4 若问题有解， A* 算法终止时一定 找到最优解, 即A*算法是可采纳的。
4.1.1 通用或图搜索算法
注1 ： 若生成的后继节点放于：
（ 1 ） Open 表的尾部 —— 相当于 Breadth-firstsearch；
（ 2 ） Open 表 的 首 部 —— 相 当 于 Depth-firstsearch； （3）根据启发式函数f的估计值确定最佳者，放 于Open 表的首部——相当于Best-first-search 最佳优先搜索。
证：A*终止只有两种情况。 (1) 在第3步, 因open为空而失败退出 但由命题 3 可知： A* 终止前， open 表上必 存在一点n’，满足 f(n’）≤f*(S0） 即open表不会空，所以，不会终止于第3步。

与或图

与或图
与或图的搜索 及应用
北京信息科技大学 孙骏 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

(搜索推理技术-与或树搜索)

(搜索推理技术-与或树搜索)

7、无判断起始节点1可解
8、从OPEN中删除含有可解先辈节点的节点
删除
OPEN= { B, C, t1, 10, 11, 12, A, t2, t3 }
CLOSED= { 1, 2, 3, 4, 5, 6, 7, 8, 9 } OPEN= {t1, 10, 11, 12, t2, t3}
CLOSED= {1, 2, 3, 4, 5, 6, 7, 8, 9} 说明：对于OPEN表中的叶节点直接移到 CLOSED表，不作任何处理
OPEN= {9, B, C, t1, 10, 11, 12, A} CLOSED= {1, 2, 3, 4, 5, 6, 7, 8}
第九大循环（3、4、5、6、7、8步）： 3、从OPEN表中取出节点9，并送到CLOSED表 4、扩展节点9，生成后继节点 t2、t3，并送到 OPEN表的末端 5、有叶节点 6、实现可解标志过程（可以判断节点9、4、2可解）
即OPEN是堆栈
注意
由于深度限制，深度优先搜索算法有可能找不 到解
例：
深度界限为4
√
2
1
√
√
6
√
3
Ⅹ A √ √
7 √
C
Ⅹ
4
5
8
t
√
Ⅹ B
t
t
t
t
√
√
√
√
注：后生成的节点画在左边
课堂练习：用宽度和深度优先搜索算法找出解树
提示：对于宽度优先搜索，先生成的节点画在左；
对于深度优先搜索，后生成的节点画在左
CLOSED= { 1, 2, 3, 4, 5, 6, 7, 8, 9, t1, 10 }
搜索过程演示
√

与或图搜索问题


f
0
0 1
d b
0 3
m h
1
1
n e
k i
-3 1
6
a
0
c
-3
3
g
5 4
6
j
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
α-β剪枝
极大节点的下界为α。 极小节点的上界为β。 剪枝的条件：
后辈节点的β值≤祖先节点的α值时， α剪枝 后辈节点的α 值≥祖先节点的β值时， β剪枝
α-β剪枝的其他应用
故障诊断
A 风险投资
B
C
D
1
极大
1
b
0
极小
6
a
0
3
1
0
-3
3
-3
-3
-2
1
-3
6
-3
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
5 α-β剪枝
设某博弈问题如下图所示，应用极小极大方法进行搜索。假设搜索的 顺序为从下到上，从左到右。当计算完a的值为0后，由于b是极大节 点，马上就可以知道b的值大于等于0。接下来求c的值。由于c是极小 节点，由d的值为-3，知道c的值小于等于-3。而a和c都是b的子节点， 所以即便不扩展节点e，也可以知道b的值一定为0了。所以在这种情 况下，没有生成节点e的必要。同样，在知道b的值为0后，由于k是极 小节点，所以立即知道k的值要小于等于0。而通过节点f、g，知道h 的值至少为3。这样即便不扩展A所包围的那些节点，也能知道k的值 一定为0。所以A包围的那些节点也没有生成的必要，不管这些节点取 值如何，都不影响k的值。如果在搜索的过程中，充分利用这些信息， 不就可以少生成很多节点，从而提高搜索的空间利用率吗？α-β过程 正是这样一种搜索方法。

人工智能中图搜索算法(PDF 159页)


图4—5 八数码问题的广度优先搜索
第9页
第4章 图搜索技术
以上两个问题都是在某个有向图中寻找目标或路径问 题，这种问题图搜索问题。把描述问题的有向图称为状态 空间图，简称状态图。图中的节点代表问题中的一种格局， 一般称为问题的一个状态，边表示两个状态之间的联系。 在状态图中，从初始节点到目标节点的一条路径或者所找 到的目标节点，就是问题的解（路径解）。
谓搜索，顾名思义，就是从初始节点出发，沿着与之相连 的边试探地前进，寻找目标节点的过程(也可以反向进行)。 搜索过程中经过的节点和边，按原图的连接关系，形成树 型的有向图，称为搜索树。搜索过程应当随时记录搜索痕 迹。
1.搜索方式 用计算机来实现状态图的搜索，有两种最基本的方式： 树式搜索和线式搜索。 所谓树式搜索，形象地讲就是以“画树”的方式进行 搜索。 即从树根（初始节点）出发一笔一笔地描出来的。
状态图实际上是一类问题的抽象表示。事实上，有许
多智力问题(如梵塔问题、旅行商问题、八皇后问题、农
夫过河问题等)和实际问题（如路径规划、定理证明、演
绎推理、机器人行动规划等）都可以归结为在某一状态图
中寻找目标或路径的问题。因此，研究状态图搜索具有普
遍意义。
第10页
第4章 图搜索技术
4.1.2 状态图搜索 在状态图中寻找目标或路径的基本方法就是搜索。所
第4章 图搜索技术
3. 搜索算法 由于搜索的目的是为了寻找初始节点到目标节点 的路径，所以在搜索过程中就得随时记录搜索轨迹。 为此，我们用一个称为CLOSED表的动态数据结构来 专门记录考查过的节点。显然，对于树式搜索来说， CLOSED表中存储的正是一棵不断成长的搜索树；而 对于线式搜索来说，CLOSED表中存储的是一条不断 伸长的折线，它可能本身就是所求的路径(如果能找到 目标节点的话)。

人工智能技术导论(第三版)

member(X, [_|T])if member(X,T). road(A,B,D):-road(B,A,D).% 因为没向图
road(
“西安”
,”北京”
,1165).
road(
“西安”
,”上海”
,1511)
road(
“西安”
,“广州”
,2129).
road(
“西安”
,”昆明”
,1942)
road(
legal1((X,Y)):-X>=Y,X>=0,Y>=0.
update((X,Y,0),Move,Statu1):-
(A,B)=X,
(C,D)=Y,
(E,F)=Move,
C1 is C+E,
D1 is D+F,
A1 is A-E,
B1 is B-F,
Statu1=((A1,B1),(C1,D1),1).
若传教士和野人的数目均为五人，渡船至多可乘三人，请定义一个启发函数，并给出相 应的搜索树。
解：
( 1)设计该问题的状态。例如：((左岸牧师数，左岸野人数 ),( 右岸牧师数，右岸野人数),船的位置)。(2)定义目标状态。这里是： ((0,0),(3,3),1)(3)描述可能的动作。船上所
能够载人的状态就是可能的操作。用谓词move/2表示。( 4) 判断合法状态( 5)深度优先
update((X,Y,1),Move,Statu1):-
(A,B)=X,
(C,D)=Y,
(E,F)=Move,
C1 is C-E,
D1 is D-F,
A1 is A+E,
B1 is B+F, Statu1=((A1,B1),(C1,D1),0). connect(Statu,Statu1):- move(X,Y), update(Statu,(X,Y),Statu1), legal(Statu1). findroad(X,X,L,L):-write(L). findroad(X,Y,L,L1):- connect(X,Z), not(member(Z,L)), findroad(Z,Y,[Z|L],L1).

与或图搜索

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
与或树的性质
• 可解与不可解标示过程都是自下而上进行 的，即由子节点的可解性确定父节点的可解性。
• 在与或树中搜索解树时，如果已确定某个 节点为可解节点，则其不可解的后裔节点就不 再有用，可从搜索树中删去；同样，如果已确 定某个节点是不可解节点，则其全部后裔节点 都不再有用，可从搜索树中删去，但当前这个 不可解节点还不能删去，因为在判断其先辈节 点的可解性时还要用到它。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

解图的定义：
• 是由能解节点构成的一个子图，是包含一节点（n） 到目的(终)节点集合（N）的、连通的能解节点的子 图. • 在一个与或图 G 中，从节点 n 到节点集 N 的解图 记为 G， G 是 G 的子图. 1．若 n 是N的一个元素，则G由单个节点n组成； 2．若 n 有一个指向节点集 {n1…,nk} 的外向连接 符 K，使得从每一个节点 ni 到 N 有一个解图 (i=1,…,k)，则 G由节点 n，连接符 K，以及 {n1 ,…,nk}中的每一个节点到 N 的解图所组成； 3．否则 n 到 N 不存在解图. • 如果 n=s 为初始节点，则解图为所求解问题的解图.
4 与或图启发式搜索算法 AO*
• 假设：G；G；h(n)是从节点 n 到一组终叶节点的 一个最优解图的一个代价估计，评价函数q(n)=h(n) AO*过程: 1.建立初始搜索图，G:=s，计算 q(s)=h(s)，IF GOAL(s) THEN M(s,SOLVED)； 2. Until s 已标记为 SOLVED, do: 3. Begin 4. G := FIND(G)；根据连接符标记（指针）找出一 个待扩展的侯选局部解图G（连接符在11步标记） 5. n := G 中的任一非终节点; 选一个当前节点 6. EXPAND(n),生成子节点集{ni}，如果 ni G， G:= ADD({ni},G),计算 q(nArtificial Intelligence i)=h(ni)，IF GOAL(ni) THEN M(ni, SOLVED);
k(n, N)= Cn+ k(n1, N)+…+ k(ni, N)
• 具有最小耗散值的解图称为最佳解图，其值 也用 h*(n) 标记。 Artificial Intelligence
• 例：从节点 n 开始，正确选择一个外 向连接符，一直进行下去直到产生的 每一个后继节点成为集合N中的一个元 素为止。下图给出了 n0 →{n7，n8}的 三个解图（耗散值分别为 8，7，5）.
h(n0)=3
AO*搜索算法的过程
• • • • • • 主要步骤 第4步(G’) 第5步(n) 第6步 第7步(S) 第11步 • • • • • • 第1循环 (n0) (n0) (n1,n5,n4) (n0) 比较,选 n0→n1; n1 不可解; • • • • • • 第2循环 n0→n1 (n1) (n2,n3) (n1) 1) 比较,选 n1→n3; n3 不可解; 2)比较,选 n0→n5, n4; n5, n4不可 解; • 1) 加n0 → S; 2)无; • • • • • • 第3循环 • n0→n5, n4 • (n5) • (n6,n7,n8) • (n5) • 比较,选 • n5→n7, n8; 改指针; n7, n8可解, n5 可解 第4循环 n0→n5, n4; (n4) (n5,n8) (n4) 1)比较,选 n4→ n8; n8可解, n4 可解; 2) n4 , n5可 解; n0可解.
• 定义：与或图就是包含与节点和或节点 的图，即存在超弧的图，也称为超图. • 超图与状态空间图有什么区别？ 与或图是一种更一般的图. • 定义：一超弧所相关的边数（K）被称为 该超弧的度，实现的连接称为K-连接. • K—连接符：从一个父节点指向一组含有 K个后继节点的节点集.
Artificial Intelligence
Artificial Intelligence
• 问题: 假定我们已经会求矩形的面积，现在要求 如图所示的五边形的面积。 • 方法分析: 五边形的面积转化为矩形面积。
①
I 1
III ③
2 II
3
②
Artificial Intelligence
求解步骤：
① 求五边形面积 求 1面积 求 I面积 求 2面积 求 II面积 求 3面积 求 III面积 求• 面积 ③ I 1 2 II III ③ 3
②
求• 面积 ①
求• 面积 ②
Artificial Intelligence
小结:
• 问题归约法: 当问题复杂时，可把初始问题分解成若 干简单的子问题，若子问题仍复杂，可再进一步分解， 直到这些子问题的解可直接得到。这种问题的描述和 求解方法，称为~. • 本原问题: 可直接解答的问题称为~ ，它是不必证明 的、自然成立的. • 归约法的组成： 1）一个初始问题的描述； 2）一组把问题变成子问题的算子 (分解或转换)； 3） 一组本原问题的描述 • 不同的算子对应不同的关系,从而使问题归约的描述 可用一个与或图的结构来表示. Artificial Intelligence
7 S:={n}; 建立含 n 的节点集合S.（已扩展待修正） 8 Until S为空, do: 9 Begin (m为S中任一节点) 10 REMOVE(m, S),当 mc{S};（m→mc ,从底层开始修正） 11 修改 m 的耗散值 q(m): 对 m 指向节点集 (n1i， n2i, … nki) 的每一个连接符 i 分别计算qi, qi(m)=Ci+q(n1i)+…+q(nki), 并取 q(m):= min qi (m); 加(或修正)指针到 min qi (m) 的连接符上. IF M(nji, SOLVED) THEN M(m, SOLVED);（j=1，2，…， k）若该连接符的所有子节点都是能解的,则m也能解. 12 IF M(m, SOLVED) (q(m) q0(m)) THEN ADD(ma, S); m 能解或修正的耗散值与原先估算q0不同,则把m的所有先 辈节点ma添加到S中. （能解或修正向上传递） 13 end (与8匹配) 14 end (与2匹配) Artificial Intelligence
二次循环后 (5) n0 n2 4 (2) n5
n4 (1)
2
0 n8
n7 0
四次循环后
不带括号的数是启发函数h(n)值,带括号数是估价函数q（n）的修正值； 短箭头用来标记连接符，标明侯选局部解图；已经标注SOLVED的节点 用黑心圆来表示。
Artificial Intelligence
讨论
• 当节点n无后继节点? 在第11步中对 m (n)赋 一个高的 q 值(会传递到s), 从而排除了含有 n的子图被当作候选局部解图的可能性. • 在 G’ 中存在多个非终节点时,选择什么样的 节点先扩展? 一般选择最能导致该局部解图耗 散值发生较大变化的节点先进行扩展, 可促使 及时修改局部解图的标记. • 同A算法类似,若 s→N 存在解图,当 h(n) ≤ h*(n)且h(n)满足单调限制条件时(对n到其子 节点的每一连接符均需要满足),则 AO* 一定 能找到最佳解图.
n0 n1 n2 n3 n5 n6
n7
与或图
• 在与或图中，节 点 n0 有两个连接 符：1-连接符指 n4 向节点 n1；2-连 接符指向节点集 合{n4、n5}； • 对于节点 n0 来讲， n1 可称为或节点， n8 n4、n5 可称为与 节点。
Artificial Intelligence
AO*搜索算法过程分析
• 两个过程的重复:
–自上而下的图生长过程（4-6步）: 先通过有标 记的连接符，找到目前为止最好的一个局部解 图，然后对其中一个非终节点进行扩展，并对 其后继节点赋估计耗散值和加能解标记. –自下而上的估价函数值的修正、连接符的标记 和SOLVED的标注过程(7-12): 耗散值的修正从 刚被扩展的节点n开始，其修正耗散值q(n)取所 有估计值中最小的一个，然后根据耗散值递归 计算公式逐级向上修正其先辈节点的耗散值.只 有下层节点耗散值修正后，才可能影响到上一 层节点的耗散值，如此一直修正到初始节点.
2 与或图
• 与节点：把单个问题分解为几个子问题来求解。只 有当所有子问题都有解，该父辈节点才有解。表示 一种 “与” 关系。 • 或节点：同一问题被转换为几种不同的后继问题。 只要有一个后继问题有解，则原问题有解。表示一 种 “或” 关系。
P P
R (a)
Q
R (b)
Q
• 与节点由与运算连接（超弧），如图（a）. Artificial Intelligence • 或节点由或运算连接，如图（b）.
Artificial Intelligence
n0 n1 h(n1)=2 n3 h(n3)=4
n2 h(n2)=4
n6 h(n6)=2
n7 h(n7)=0
• 例: 各节点启发值如 图，k-连接符的耗散值 = k, 求最佳解图. • 应用 AO* 算法，经 n4 四个循环，可找到解图. h(n4)=1 n5 • 在第一次循环扩展节 h(n5)=1 点 n0；然后,依次扩展 节点 n1、n5、n4。 • 在节点 n4 被扩展之 n8 后，节点 n0 便被标注 h(n8)=0 SOLVED，此时，通过向 下跟踪有标记的连接符， 便获得了解图. Artificial Intelligence
Artificial Intelligence
• 定义：不能解节点的递归定义为:
1．没有后裔的非终节点是不能解的节点； 2．若非终节点有 “或” 子节点时，当且仅 当所有子节点均不能解时，该非终节点才不 能解； 3．若非终节点有 “与” 子节点时，当至少 有一子节点不能解时，该非终节点才不能解.
Artificial Intelligence
3 与或图搜索
• 含义：在与或图上执行搜索的过程，其目的在于标明 起始节点是有解的，即，搜索不是去寻找到目标节点 的一条路径，而是寻找一个解图。 • 定义：一个节点被称为能解节点，其递归定义为： 1．终节点是能解节点（直接与本原问题相关联）； 2．若非终节点 有 “或” 子节点时，当且仅当其子 节点至少有一个能解 ，该非终节点才能解； 3．若非终节点有 “与” 子节点时，当且仅当其子 节点均能解，该非终节点才能解。