搜索(与或图搜索实例AO算法)
- 格式：ppt
- 大小：694.50 KB
- 文档页数：34
下载文档原格式
合集下载
AI03-2与或图搜索
E H 5 4
F I
G
反向更新代价 g(E)=5, g(D)=9, g(Q0)=10 g(I)=0, g(F)=1, g(D)=8, g(Q0)=9
3.3.3 启发式与或树搜索
例 3.18
A D Q0
B
C K L
E H 5 4
F I
J
G
反向更新代价 g(J)=0, g(K)=0, g(B)=2, g(A)=7, g(Q0)=8 g(L)=0, g(C)=1, g(A)=5, g(Q0)=6
Q21 Q22 Q23
Q’21 Q’22 Q’23
3.3.1 与或图
与或图/与或树
n0 n1 n2 n4 初始节点
n3
n5
n6
n8 目标 n7 目标
3.3.1 与或图
问题求解
状态图/或图
一个问题可以有几种求解方法 只要其中一种方法可以求解问题，则该问题被求解，方法之 间是"或"的关系
与图：
在用一种方法求解时，又可能需要求解几个子问题 这些子问题必须全部求解，才可能用该方法求解原始问题， 这些子问题之间是"与"的关系
3.3.3 启发式与或树搜索
例 3.18
A D Q0
B 3 3
C
E 3 2
F
左局部树： g(B)=3, g(C)=3, g(A)=8, g(Q0)=9 右局部树： g(E)=3, g(F)=2, g(D)=7, g(Q0)=8
希望树
3.3.3 启发式与或树搜索
例 3.18
A D Q0
B 3 3
C
3.3.3 启发式与或树搜索
例 3.18
A √ D √ √ K √ C √ L E H 5 4 F I Q0 √
中国海洋大学人工智能课程大纲（理论课程）
中国海洋大学人工智能课程大纲（理论课程）中国海洋大学人工智能课程大纲（理论课程）英文名称（Artificial Intelligence）【开课单位】信息学院【课程模块】专业知识【课程编号】【课程类别】选修【学时数】64 （理论48 实践16 ）【学分数】 3.5一、课程描述本课程大纲根据2011年本科人才培养方案进行修订或制定。
（一）计算机科学与技术专业第三学年春季学期（二）教学目标及修读要求1、教学目标本课程讲解人工智能的一般性原理和基本方法，包括搜索策略、谓词逻辑归结、知识表示、不确定性推理、机器学习等，要求学生了解人工智能的研究范围和发展现状，能运用一般性原理和基本方法解决一些简单的人工智能问题。
修读要求本课程是在学生掌握了高级程序设计语言、数据结构、离散数学、操作系统等基本理论和技能的基础上，进一步学习人工智能的主要原理、技术和方法。
要求学生具有一定的算法设计能力、编程能力和抽象思维能力。
先修课程（参照2011版人才培养方案中的课程名称，课程名称要准确）高级程序设计语言、高级程序设计语言实验、数据结构、离散数学、操作系统二、教学内容（一）第０章绪论1、主要内容：了解人工智能的内涵、发展史和研究范围。
2、教学要求：（按照掌握、理解、了解三个层次对学生学习提出要求）要求学生理解人工智能的内涵及相关哲学问题、了解其发展史和研究范围。
3、重点、难点：无4、其它教学环节：（如实验、习题课、讨论课、其它实践活动）：（二）第一章搜索问题1、主要内容：回溯策略、图搜索策略、无信息图搜索过程、启发式图搜索过程。
2、教学要求：掌握回溯策略的递归法实现、一般的图搜索过程、深度优先和宽度优先的图搜索过程，以及启发式图搜索A*算法；理解A*算法的启发式函数的下界约束和单调约束，理解A*算法的改进算法及其主要依据。
3、重点、难点：重点：回溯策略、A*算法难点：A*算法的启发式函数相关引理及定理的证明其它教学环节：（如实验、习题课、讨论课、其它实践活动）：综合性设计项目1：滑动积木块问题的启发式搜索算法及其实现。
第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步。
(搜索推理技术-与或树搜索)
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 }
搜索过程演示
√
人工智能第三章_搜索策略-2
30
与或图搜索
1)与或图搜索的基本概念 3、解图的生成★
解图纯粹是一种“与”图 解图中，节点或节点组间不存在“或”关系； 所有叶节点都是终节点
与或图中存在“或”关系，搜索到多个解图；
2019/12/21
31
与或图搜索
2) 解图、解图代价、能解节点和不能解节点的定义
(1)解图——与或图（记为G）任一节点（记为n）到终 节点集合的解图（记为G‘）是G的子图。
5
回溯策略和爬山法
2）回溯策略
三种失败状态：
不合法状态（如传教士和野人问题中所述的那样） 旧状态重现（如八数码游戏中某一棋盘布局的重现，会导 致搜索算法死循环）， 状态节点深度超过预定限度（例如八数码游戏中，指示解 答路径不超过6步）。
回溯条件
失败状态，由算法第（2）句指示； 搜索进入“死胡同”，由该算法的第(4)句定义。
引入K-连接
父子节点间可以存在“与”关系 结果——解图。
解答路径往往不复存在，代之以广义的解路径—— 解图。
2019/12/21
24
与或图搜索
1)与或图搜索的基本概念 1、K-连接★ 从父节点到K个子节点的连接，子节点间有“与”关系； 以圆弧指示这些子节点间的“与”关系； 一个父节点可以有多个K-连接
(1,3,3)(3,3,3)
2019/12/21
(3,1,1)(3,2,1)
22
(1,2,3)(1,3,3)
梵塔问题
子问题间有交互作用， 问题分解注意正确的顺序
(1,1,1)(3,3,3)
1
5
6
(1,1,1)(2,2,1) (2,2,1)(2,2,3) (2,2,3)(3,3,3)
与或图搜索问题
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的值。如果在搜索的过程中，充分利用这些信息， 不就可以少生成很多节点，从而提高搜索的空间利用率吗？α-β过程 正是这样一种搜索方法。
与或图搜索
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+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
与或树的性质
• 可解与不可解标示过程都是自下而上进行 的，即由子节点的可解性确定父节点的可解性。
• 在与或树中搜索解树时，如果已确定某个 节点为可解节点，则其不可解的后裔节点就不 再有用，可从搜索树中删去；同样，如果已确 定某个节点是不可解节点，则其全部后裔节点 都不再有用，可从搜索树中删去，但当前这个 不可解节点还不能删去，因为在判断其先辈节 点的可解性时还要用到它。
人工智能模拟试题(120分钟)
人工智能模拟试题(120分钟）1. 填空题（共12分，每小题2分）1）知识表示的性能应从以下二个方面评价：____________________和________________；后者又分二个方面______________和________________。
2) 框架系统的特性继承功能可通过组合应用槽的三个侧面来灵活实现，它们是______________________________________________________。
3）KB系统通常由以下三个部分组成：__________________________________________；KB系统的开发工具和环境可分为以下三类：____________________________________。
4）按所用的基本学习策略可以将机器学习方法划分为以下几类：________ _____________________________________________________________。
5) 主观Bayes方法将推理规则表示为P Q形式，称__________为先验似然比，__________ 为条件似然比，_________为规则的充分性因子。
6）自然语言理解中，单句理解分二个阶段：____________和____________，后者又分二个步骤：________________和_________________。
2、问答题（共20分，每小题5分）1）阐述示例学习所采用的逐步特化学习策略，并说明学习过程中正、反例的作用。
2）为什么要在框架系统中实行相容匹配技术？如何实现？3）阐述Xps的冲突解法和推理引擎，并说明综合数据库中事实元素的时间标签在冲突解法中起的作用。
4）什么是问题归约？问题归约的操作算子与一般图搜索有何不同？与或图启发式搜索算法AO*的可采纳性条件是什么？3、简单计算题（共35分，每小题7分）1）按书上图8.5中给定的文法规则，再追加2条：N → football, V → play；画出英语句子”The boy play little football”的句法分析树。
人工智能复习参考(带答案)
复习参考题一、填空1．构成产生式系统的基本元素有综合数据库、规则库、控制系统,控制策略按执行规则的方式分类,分为正向、逆向、双向三类。
2．归结过程中控制策略的作用是给出控制策略，以使仅对选择合适的子句间方可做归结，避免多余的、不必要的归结式出现或者说，少做些归结仍能导出空子句。
常见的控制策略有线性归结策略、支持集策略、单元归结、输入归结。
3．公式G和公式的子句集并不等值，但它们在不可满足的意义下是一致的。
4．与或图的启发式搜索算法（AO*算法）的两个过程分别是图生成过程即扩展节点和计算耗散值的过程。
5．人工智能的研究途径主要有两种不同的观点，一种观点称为符号主义,认为人类智能基本单元是符号。
另一种观点称为连接主义（仿生主义），认为职能的基本单元是神经元。
6．集合{P(a, x, f (g(y)), P(z, f（z）,f(u)))的mgu（最一般合一置换）为{z/a, f(x)/x, u/g(y)}。
7．语义网络是对知识的有向图表示方法，一个最简单的语义网络是一个形如节点1、弧、节点2的三元组，语义网络可以描述事物间多种复杂的语义关系、常用ISA、AKO弧表示节点间具有类属的分类关系。
语义网络下的推理是通过继承和匹配实现的。
8．当前人工智能研究的热点之一就是机器学习。
常见的机器学习方法可分为连接学习、归纳学习、分析学习和遗传算法与分类器系统等。
一个机器学习系统应有环境、知识库、学习环节和执行环节四个基本部分组成。
9．常用的知识表示法有逻辑表示法、产生式规则表示法、语义网络表示法、框架理论表示法、过程表示法等。
10．有两个A*算法A1和A2，若A1比A2有较多的启发信息，则h1(n)>h2(n)。
11．关于A算法与A*算法，若规定h(n)≥0，并且定义启发函数：f*(n)=g*(n)+h*(n) 表示初始状态S0经点n到目标状态S g最优路径的费用。
其中g*(n)为S0到n的最小费用, h*(n)为到S g的实际最小费用。
4-与或图搜索
全信息
对垒过程中，双方都了解当前格局及过去的历史
非偶然
双方都是理智的分析决定自己的行动，不存在“碰运气”的偶然因
素
11
人工智能
sspu 王帅
博弈树
在博弈过程中，任何一方都希望自己取得胜利。因此，在 某一方当前有多个行动方案可供选择时，他总是挑选对自 己最有利而对对方最不利的那个方案行动。 如果我们站在A方立场，则可供A选择的若干方案之间是 “或”关系，因为主动权在A方手里，他或者选择这个方 案，或者选择另一个方案，完全由A决定 但若B也有若干可供选择的方案，则对A来说这些方案之间 是“与”关系，因为这时主动权在B，这些可供选择的方 案中的任何一个都可能被B选中，A必须考虑对自己最不利 的情况的发生 把上述博弈过程用图表示出来，得到的是一棵“与／或” 树 注意：该“与／或”树是始终站在某一方（例如Ａ方）的 立场上得出的，不能一会站在Ａ方立场，一会又站在Ｂ方 立场
24
人工智能 sspu 王帅
极大极小法—计算倒推值示例
1
b
0
1
a
0
3
1
6
极大
极小
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
25
人工智能
sspu 王帅
-剪枝
S0
3 ≥3 S2 ≤2
S1
3
3 5 S3 S4
2 S5 S6
设有博弈树，各端点的估值如 图所示，其中S6还没计算估值。 由S3与S4的估值得到S1的倒推 值为3，这表示S0的倒推值最小 为3。另外，由S5的估值得知S2 的倒推值最大为2，因此S0的倒 推值为3。 这里，虽然没有计算S6的估值， 仍然不影响对上层节点倒推值 的推算，这表示S6这个分枝可 以从博弈树中剪去
对垒过程中，双方都了解当前格局及过去的历史
非偶然
双方都是理智的分析决定自己的行动，不存在“碰运气”的偶然因
素
11
人工智能
sspu 王帅
博弈树
在博弈过程中，任何一方都希望自己取得胜利。因此，在 某一方当前有多个行动方案可供选择时，他总是挑选对自 己最有利而对对方最不利的那个方案行动。 如果我们站在A方立场，则可供A选择的若干方案之间是 “或”关系，因为主动权在A方手里，他或者选择这个方 案，或者选择另一个方案，完全由A决定 但若B也有若干可供选择的方案，则对A来说这些方案之间 是“与”关系，因为这时主动权在B，这些可供选择的方 案中的任何一个都可能被B选中，A必须考虑对自己最不利 的情况的发生 把上述博弈过程用图表示出来，得到的是一棵“与／或” 树 注意：该“与／或”树是始终站在某一方（例如Ａ方）的 立场上得出的，不能一会站在Ａ方立场，一会又站在Ｂ方 立场
24
人工智能 sspu 王帅
极大极小法—计算倒推值示例
1
b
0
1
a
0
3
1
6
极大
极小
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
25
人工智能
sspu 王帅
-剪枝
S0
3 ≥3 S2 ≤2
S1
3
3 5 S3 S4
2 S5 S6
设有博弈树，各端点的估值如 图所示，其中S6还没计算估值。 由S3与S4的估值得到S1的倒推 值为3，这表示S0的倒推值最小 为3。另外，由S5的估值得知S2 的倒推值最大为2，因此S0的倒 推值为3。 这里，虽然没有计算S6的估值， 仍然不影响对上层节点倒推值 的推算，这表示S6这个分枝可 以从博弈树中剪去
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
(c)
普通图搜索的情况
s
n
f(n) = g(n) + h(n) 对n的评价实际是对从s经过n到目的地这条路径的评价
与或图: 对局部图的评价
初始节点
c
a b 目标 目标
与或图搜索:AO*算法
两个过程
• 图生成过程，即扩展节点
自顶向下, 从最优的局部途中选择一个节点扩展
• 计算耗散值的过程
自下向顶, 对当前的局部图重新计算耗散值
AO*算法搜索例子
q=5 初始节点 n0 q=5 n1
连接符1
n2
连接符2
q=1 n4
n3
q=2 n5
n6
n8
n7
在重新计算n0耗散的小循环中: … 由于n4,n5为SOLVED, 则n0为SOLVED q(n0)=5, 找到解
G={n0,n1,n2,n3,n4,n5,n6,n7,n8} 第四个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图G’{n0,n4,n5,n7,n8} 2. n=G’中非终结点, 此时n=n4 3. 扩展结点n=n4, 生成后继结点集合{n5, n8}, q(n5)=2, q(n8)=0 4. 小循环(修改结点耗散值),直到S为空: a. S={n=n4} b. 保证n的后代不在S中 c. m=n5的连接符有两条, 计算q1(m)=1+q(n5)=1+2=3 q2(m)=1+q(n8)=1+0=1 令q(m)=q(n4)=min(q1,q2)=1 d.修改指针到q2对应的连结符上去 e. n8为SOLVED,则m=n4也为SOLVED f. m=n4也为SOLVED,则需要也对m的父结点 进行修改, 即将m=n1的父结点n0加到S中 g.小循环结束 5.大循环结束
AO*算法搜索例子
AO*算法搜索例子
q=4 q=5 初始节点 n0 q=5 n1
连接符1
n2
连接符2
n4 q=1 q=2 n5
n3
n6
n8
n7
G={n0,n1,n2,n3,n4,n5} 第三个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图G’{n0,n4,n5} 2. n=G’中非终结点, 此时n=n5 3. 扩展结点n=n5, 生成后继结点集合 {n6,n7,n8}, q(n6)=2, q(n7)=0, q(n8)=0 把结点加到G中 4. 小循环(修改结点耗散值),直到S为空: a. S={n=n5} b. 保证n的后代不在S中 c. m=n5的连接符有两条, 计算q1(m)=1+q(n6)=1+2=3 q2(m)=1+q(n7)+q(n8)=2+0+0=2 令q(m)=q(n5)=min(q1,q2)=2 d.修改指针到q2对应的连结符上去 e.n7,n8为SOLVED,则m=n5也为SOLVED f. q(m=n5)被修改过,则需要也对m的父结 点进行修改, 即将m=n5的父结点n0加到S中 g.小循环结束 5.大循环结束
n1
连接符1
连接符2
n4
n5
G中只有一个结点n0 第一个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图G’{n0} 2. n=G’中任意结点, 此时n=n0 3. 扩展结点n=n0, 生成后继结点集合{n1,n4,n5}, q(n4)=1, q(n5)=1, q(n1)=2, 都不是终结点, 把结点加到G中 4. 小循环(修改结点耗散值),直到S为空: a. S={n=n0} b. 保证n的后代不在S中 c. m=n0的连接符有两条, 计算q1(m)=1+q(n1)=1+2=3 q2(m)=2+q(n5)+q(n4)=2+1+1=4 令q(m)=q(n0)=min(q1,q2)=3 d.修改指针到q1对应的连结符上去 e.如果n1为非SOLVED,则m=n0也为非SOLVED f.如果m=n0为SOLVED,或者q(m)被修改过,则 需要也对m的父结点进行修改, 即将m的父结点 加到S中 g.小循环结束 5.大循环结束
n4
n5
目标n8 目标n7
k(5, N)= min(2+k(7,N)+k(8, N),…) = 2 k(4, N)= min(1+k(5, N), 1+k(8,N)) = min(3, 1)=1 N0= 2+1+2=5 (a)的解图耗散值为8 (b)的解图耗散值为7 具有最小耗散值的解图称为最佳 解图,其值也用h*(n)标记.上例中 的h*(n)=5
G={n0,n1,n4,n5} q=3 q=4 第二个大循环(扩展结点),直到n0是SOLVED: n0 初始节点 1. 找到待扩展的局部图G’{n0,n1} 2. n=G’中非终结点, 此时n=n1 q=5 3. 扩展结点n=n1, 生成后继结点集合{n2,n3}, 连接符1 n1 连接符2 q(n2)=4, q(n3)=4, 都不是终结点,把结点加 n2 到G中 n4 4. 小循环(修改结点耗散值),直到S为空: a. S={n=n1} n3 b. 保证n的后代不在S中 n5 c. m=n1的连接符有两条, 计算q1(m)=1+q(n3)=1+4=5 q2(m)=1+q(n2)=1+4=5 令q(m)=q(n0)=min(q1,q2)=5 继续小循环: d.修改指针到q1对应的连结符上去 … e.如果n3非SOLVED,则m=n1也为非SOLVED c. m=n0的连接符有两条,计算 f. q(m=n1)被修改过,则需要也对m的父结点 q1(m)=1+h(n1)=1+5=6 进行修改, 即将m=n1的父结点n0加到S中 q2(m)=1+h(n5)+h(4)=4 g.小循环结束 令 q(m)=q(n1)=min(q1,q2)=4 d.修改指针到q2对应的连结符上去 5.大循环结束 …
G={n0,n1,n4,n5} q=3 q=4 第二个大循环(扩展结点),直到n0是SOLVED: n0 初始节点 1. 找到待扩展的局部图G’{n0,n1} 2. n=G’中非终结点, 此时n=n1 q=5 3. 扩展结点n=n1, 生成后继结点集合{n2,n3}, 连接符1 n1 连接符2 q(n2)=4, q(n3)=4, 都不是终结点,把结点加 n2 到G中 n4 4. 小循环(修改结点耗散值),直到S为空: a. S={n=n1} n3 b. 保证n的后代不在S中 n5 c. 取出m=n1的连接符有两条, 计算q1(m)=1+q(n3)=1+4=5 q2(m)=1+q(n2)=1+4=5 令q(m)=q(n0)=min(q1,q2)=5 继续小循环: d.修改指针到q1对应的连结符上去 … e.如果n3非SOLVED,则m=n1也为非SOLVED c. m=n0的连接符有两条,计算 f. q(m=n1)被修改过,则需要也对m的父结点 q1(m)=1+h(n1)=1+5=6 进行修改, 即将m=n1的父结点n0加到S中 q2(m)=2+h(n5)+h(4)=4 g.小循环结束 令 q(m)=q(n1)=min(q1,q2)=4 d.修改指针到q2对应的连结符上去 5.大循环结束 …
n4
n5
目标n8 目标n7
k(5, N)= min(2+k(7,N)+k(8, N),…) = 2 k(4, N)= min(1+k(5, N), 1+k(8,N)) = min(3, 1)=1 N0= 2+1+2=5 同理可计算得： (a)的解图耗散值为8 (b)的解图耗散值为7 具有最小耗散值的解图称为最佳 解图,其值也用h*(n)标记.上例中 的h*(n)=5
…
AO*算法的最优性: 若s→ N存在解图,当h(n)≤h*(n),且h(n)满足单调限制条件,则AO* 一定能够找到最佳解图, 即AO*具有可采纳性 单调限制条件指对于图中从结点到n→{n1,…,nk}的每一个连接符都 施加限制h(n)≤C+ h(n1)+..+ h(nk),如果同时有h(ti)=0(ti∈N),那 么单调限制意味着h是h*的下界范围,即对所有的结点n有h(n)≤h*(n)
耗散值的计算
1.若n是N的一个元素, 则k(n, N) =0 2.若n是一个外向连接符指向后继结点{n1,..ni} k(n, N) = Cn+k(n1, N)+…+k(ni, N) 其中：N为终节点集 Cn为连接符的耗散值
n …... n2
n1
ni
i个
初始节 点n0
搜索解图耗散值的递归计算: n0=2+k(4, N)+k(5, N)
目标n8 目标n7
目标n8
目标n7
(a)
(c)
目标n8 目标n7
(b)
无解节点
有解节点
终结点 t t t t
t
t
t
t t （b） （a） 能解节点 • 终节点是能解节点 • 若非终节点有“或”子节点时，当且仅当其子节点至少有一能解时，该非终节点 才能解。 • 若非终节点有“与”子节点时，当且仅当其子节点均能解时，该非终节点才能解。 不能解节点 • 没有后裔的非终节点是不能解节点。 • 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不 能解。 • 若非终节点有“与”子节点时，当至少有一个子节点不能解时，该非终节点才不 能解。
q=3 n0 初始节点
n1
连接符1
连接符2
n4
n5
即h(n)
G中只有一个结点n0 第一个大循环(扩展结点),直到n0是SOLVED: 1. 找到待扩展的局部图G’{n0} 2. n=G’中任意结点, 此时n=n0 3. 扩展结点n=n0, 生成后继结点集合{n1,n4,n5}, q(n4)=1, q(n5)=1, q(n1)=2, 都不是终结点, 把结点加到G中 4. 小循环(修改结点耗散值),直到S为空: a. S={n=n0} b. 保证n的后代不在S中 c. 取出m=n0的连接符有两条, 计算q1(m)=1+q(n1)=1+2=3 q2(m)=2+q(n5)+q(n4)=2+1+1=4 令q(m)=q(n0)=min(q1,q2)=3 d.修改指针到q1对应的连结符上去 e.如果n1为非SOLVED,则m=n0也为非SOLVED f.如果m=n0为SOLVED,或者q(m)被修改过,则 需要也对m的父结点进行修改, 即将m的父结点 加到S中 g.小循环结束 5.大循环结束