copy北航系人工智能课件

1、北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 1 人人 工工 智智 能能 ( 问题求解问题求解基本原理及基本原理及搜索技术搜索技术 ) 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 2 问题求解基本原理 n问题求解：问题求解：在给定条件下，寻求一个能解决某类某类问题问题且能在 有限步骤内完成的算法。 n 问题求解特征：问题求解特征： w 传统软件传统软件： 求解的问题是能够用数学精确描述的良结构良结构 的问题的问题（如，解方程）； 计算机执行的繁杂的统计计算任 务一般不能

2、看成是人工智能活动。 w AI软件软件： 求解的是不可直接用数学模型描述的所谓不良不良 结构问题结构问题（如，几何证明、求不定积分、逻辑演算等），通 常需要采用弱方法进行搜索求解； AI程序程序中符号的内涵不 仅局限于数值计算和数据处理中的一般数据信息，应表现人 类进行推理所需要的各种知识知识。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 3 问题求解基本原理 一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法 二、搜二、搜 索索 技技 术术 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航

3、空航天大学软件开发环境国家重点实验室 Slide 4 问题求解基本原理 n问题求解方法：问题求解方法： w基于基于状态空间状态空间的问题求解方法的问题求解方法 w基于基于问题空间问题空间的问题求解方法的问题求解方法 w基于博弈搜索的问题求解方法 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 5 问题实例问题实例 桌上固定了桌上固定了 3 根柱子，按根柱子，按 1，2，3 次序排例。有次序排例。有 n n 个大小全不一样大个大小全不一样大 的盘子的盘子d1，dn ，按从小到大，小的在上的次序依次插在第一根柱子上，按从小到大，

4、小的在上的次序依次插在第一根柱子上， 要把这要把这 n n 个盘子全部搬到第三根柱子上，每次只许搬一个，任何时候都不个盘子全部搬到第三根柱子上，每次只许搬一个，任何时候都不 允许把大盘子放在小盘子上面，问该允许把大盘子放在小盘子上面，问该如何搬法。如何搬法。 设设 n = 3，该该如何搬法如何搬法？ 1 2 3 1 2 3 梵塔问题 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 6 基于基于状态空间状态空间的问题求解方法的问题求解方法 （1，1，1） （1，1，2） （1，1，1） （1，1，3） （1，1，2） （1，3

5、，2） 。 状态状态合法合法变换规则（满足约束条件）：变换规则（满足约束条件）： 状态定义状态定义 - -（i i大 大, j , j中 中, k , k小 小 ） ）: 设向量下标分别表示大盘、中盘、 小盘；向量值分别表示盘子所在柱 子的编号。 状态描述状态描述 - - 大盘在第 i 根柱子上； 中号盘在第 j 根柱子上，小号盘在 第 k 根柱子上。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 7 基于基于问题空间问题空间的问题求解方法的问题求解方法 n问题：问题：如何将如何将 i i 柱子上的柱子上的 m m 个盘子

6、搬到个盘子搬到 k k 柱子上柱子上 ? ? w 将 i 柱子上的 m 1 个盘子搬到 j 柱子上 ； w 将 i 柱子上的 第 m 个盘子搬到 k 柱子上； w 将 j 柱子上的 m 1 个盘子搬到 k 柱子上 。 n 问题描述：问题描述： 问题（问题（a, b, c):a, b, c): 将 b 柱子上的 a 个盘子搬到 c 柱子上。 问题分解合法规则：问题分解合法规则： （3 3，1 1，3 3）-（2 2，1 1，2 2） (1 (1，1 1，3 3） （2 2，2 2，3 3） 。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验

7、室 Slide 8 基于基于问题空间问题空间的问题求解方法的问题求解方法 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 9 状态空间法状态空间法有关概念有关概念 n 状态空间法状态空间法: : 从问题的从问题的初始状态初始状态出发，通过一系列的出发，通过一系列的状态变换状态变换找到找到目标状态目标状态的的 问题求解方法。问题求解方法。 n 状态状态：描述问题中事物形状或状况的符号或数据结构。描述问题中事物形状或状况的符号或数据结构。 n 状态空间状态空间：所有状态的全体构成的集合；用所有状态的全体构成的集合；用四元组四元组

8、（S, SS, S0 0, O, G), O, G) 表示表示: : S: S: 非空状态子集，非空状态子集，S S0 0 = = 初始状态（非空）。初始状态（非空）。 G: G: 非空目标状态子集。非空目标状态子集。 O: O: 操作算子集合，一个状态操作算子集合，一个状态合法合法转换为转换为另一个状态的描述规则另一个状态的描述规则 n 问题求解过程问题求解过程：隐含隐含求一个求一个普通有向图普通有向图，节点节点 - - 状态，状态，边边 算子算子 n 搜索空间搜索空间：问题求解过程中问题求解过程中到达到达过的所有状态（节点）的集合过的所有状态（节点）的集合。 2021/5/27 北京航空航

9、天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 10 状态空间法状态空间法有关概念有关概念 状态空间、搜索空间及解径的关系：状态空间、搜索空间及解径的关系： n 问题的解（解径）问题的解（解径）：初始状态初始状态到到目标状态目标状态通路上的每一条通路上的每一条 规则规则（或（或 状态）构成状态）构成序列，称为序列，称为解径解径。 解不唯一。解不唯一。 S S0 0 R R1 1 S S2 2 R R2 2 S Sk . k . R Rk k G G n问题有解问题有解：从代表从代表初始状态初始状态 s s 节点出发，节点出发， 存在一条通向存在一条通向目

10、标节点目标节点的路径的路径 。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 11 n9、 人的价值，在招收诱惑的一瞬间被决定。21.6.2121.6.21Monday, June 21, 2021 n10、低头要有勇气，抬头要有低气。20:39:1320:39:1320:396/21/2021 8:39:13 PM n11、人总是珍惜为得到。21.6.2120:39:1320:39Jun-2121-Jun-21 n12、人乱于心，不宽余请。20:39:1320:39:1320:39Monday, June 21, 202

11、1 n13、生气是拿别人做错的事来惩罚自己。21.6.2121.6.2120:39:1320:39:13June 21, 2021 n14、抱最大的希望，作最大的努力。2021年6月21日星期一下午8时39分13秒20:39:1321.6.21 n15、一个人炫耀什么，说明他内心缺少什么。2021年6月下午8时39分21.6.2120:39June 21, 2021 n16、业余生活要有意义，不要越轨。2021年6月21日星期一20时39分13秒20:39:1321 June 2021 n17、一个人即使已登上顶峰，也仍要自强不息。下午8时39分13秒下午8时39分20:39:1321.6.2

12、1 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 12 n9、 人的价值，在招收诱惑的一瞬间被决定。21.6.2121.6.21Monday, June 21, 2021 n10、低头要有勇气，抬头要有低气。20:39:1320:39:1320:396/21/2021 8:39:13 PM n11、人总是珍惜为得到。21.6.2120:39:1320:39Jun-2121-Jun-21 n12、人乱于心，不宽余请。20:39:1320:39:1320:39Monday, June 21, 2021 n13、生气是拿别人做错的事来惩罚自己。21

13、.6.2121.6.2120:39:1320:39:13June 21, 2021 n14、抱最大的希望，作最大的努力。2021年6月21日星期一下午8时39分13秒20:39:1321.6.21 n15、一个人炫耀什么，说明他内心缺少什么。2021年6月下午8时39分21.6.2120:39June 21, 2021 n16、业余生活要有意义，不要越轨。2021年6月21日星期一20时39分13秒20:39:1321 June 2021 n17、一个人即使已登上顶峰，也仍要自强不息。下午8时39分13秒下午8时39分20:39:1321.6.21 北京航空航天大学软件开发环境国家重点实验室北

14、京航空航天大学软件开发环境国家重点实验室 Slide 13 问题空间法问题空间法有关概念有关概念 n问题空间法问题空间法： 首先产生待证问题的首先产生待证问题的所有所有子问题，而后通过解决所有子问题达到子问题，而后通过解决所有子问题达到 问题求解目的的方法。问题求解目的的方法。 n 问题问题：描述问题及其子问题的符号或数据结构描述问题及其子问题的符号或数据结构。 n 问题空间问题空间：初始问题以及其所有子问题的全体构成的集合，用初始问题以及其所有子问题的全体构成的集合，用四元四元 组组（S, SS, S0 0, F, G), F, G) 表示表示: : w S: S: 问题和子问题；问题和子问

15、题； S S0 0 : : 初始问题。初始问题。 w G: G: 具有具有平凡解平凡解的的本原问题本原问题集合。集合。 w F: F: 操作算子集合，用于将问题分解成其若干个子问题的描述规则操作算子集合，用于将问题分解成其若干个子问题的描述规则 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 14 问题空间法问题空间法的有关概念（的有关概念（2 2） n问题空间分解过程问题空间分解过程：隐含求一个隐含求一个与或图与或图 w 节点节点 问题，问题， 边边 - - 分解问题的算子。分解问题的算子。 w “与与” ” 节点：节点：

16、如果节点 A 有边通向一组节点 B1，B2， .Bn ，问题 A 的解决有待于 A 的子问题组 B1,B2.Bn 的全部解决全部解决，则称 A 为“与” 节点。如图 a 所示。 w “或或” ” 节点：节点：若节点有边通向一组节点,2， n，问题的解决有待于子问题或2或或n中某一个子问 某一个子问 题的解决题的解决，则称 A 为“或” 节点。如图 b 所示。 . a : A B1B2Bn . b : A B1B2Bn 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 15 问题空间法问题空间法有关概念（有关概念（2 2） n问

17、题的解（解图）问题的解（解图）：从代表从代表初始问题初始问题的节点出发，搜索到一个完的节点出发，搜索到一个完 整的整的与或与或 子图子图，图中所有叶节点均满足问题求解的结束条件。，图中所有叶节点均满足问题求解的结束条件。 例：例：（C,B,Z) -（M,M) 重写规则: R1: C ( D, L ) R2: C ( B, M ) R3: B ( M, M) R4: Z ( B, B,M ) 解图解图 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 16 小结小结 问题求解方法比较问题求解方法比较 状态空间法状态空间法 问题空

18、间法问题空间法 问题求解问题求解 状态变换 问题分解 搜索过程搜索过程隐含构建普通有向图普通有向图隐含构建与或图与或图 节点节点 状态 问题 边边状态变换规则（算子） 问题分解规则（算子） 求解求解 解径 解图 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 17 问题求解基本原理问题求解基本原理 一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法 二、搜二、搜 索索 技技 术术 （一）（一） 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 18

19、 n搜索技术预备搜索技术预备 n状态空间搜索状态空间搜索 w 有关概念 w 盲目搜索策略 w 启发式搜索策略 问题求解基本原理问题求解基本原理 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 19 搜索策略预备搜索策略预备 n盲目搜索：盲目搜索： 不考虑给定问题所具有的特定知识，系统按照事 先确定好的某种固定顺序固定顺序调用规则，或是随机地随机地 调用规则。 常用的常用的盲目盲目搜索算法搜索算法: : 深度优先搜索策略；深度优先搜索策略； 宽度优先搜索策略宽度优先搜索策略 2021/5/27 北京航空航天大学软件开发环境国家

20、重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 20 搜索策略预备搜索策略预备 启发式信息启发式信息： 与问题求解有关的信息和知识。 由于信息的信息的片面性片面性和不准确性不准确性，应用启发式信息不能百分之百地保 证找到问题的解，但能提高问题求解的可能性。 启发式信息启发式信息在问题求解过程中的在问题求解过程中的作用作用： 有助于有助于加速求解过程；加速求解过程； 有助于有助于找到找到“较优较优”解。解。 n 启发式搜索策略启发式搜索策略: : 考虑给定问题领域具有的特定知识（启发式信息启发式信息），系统 动态地规定动态地规定规则调用顺序，优先使用优先使用“较较”合适合适的规

21、则。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 21 搜索策略预备搜索策略预备 n 常用的基于常用的基于状态图状态图的的启发式启发式搜索策略搜索策略 : n 爬山搜索策略爬山搜索策略 (Hill Climbing) (Hill Climbing) n 大英博物馆搜索策略大英博物馆搜索策略 (British Museum) (British Museum) n 启发式图搜索策略启发式图搜索策略 ( ( A A ) ) n 最佳最佳启发式启发式图搜索策略图搜索策略 ( ( A A* * ) ) n 常用的基于常用的基于与或

22、图及博弈与或图及博弈的的启发式启发式搜索策略搜索策略： n 最佳最佳启发式启发式与或图搜索策略与或图搜索策略 ( ( AOAO* * ) ) n 极大极小搜索策略极大极小搜索策略 ( (MinimaxMinimax) ) n 剪枝搜索策略剪枝搜索策略 ( (Alpha-Beta PruningAlpha-Beta Pruning) ) 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 22 基于基于状态空间状态空间的的搜索技术：搜索技术： 有关搜索概念有关搜索概念 盲目搜索策略盲目搜索策略 启发式启发式搜索策略搜索策略 问题求

23、解基本原理 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 23 状态空间状态空间搜索搜索有关概念有关概念 n状态状态图图特点：特点：多条路径通向同一节点。例： E 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 24 状态空间状态空间搜索搜索有关概念有关概念 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 25 状态空间状态空间搜索有关概念搜索有关概念 n 节点深度节点深度： 根节点根

24、节点的深度深度为0，其它节点其它节点的深度深度规定为其父节 点的深度加 1，即dn+1 = dn + 1 。 n 标记节点标记节点 n n：用指针指针将后继节点连接连接到父节点 n 的操作 。 n 节点节点：对应状态图中有关状态状态的描述。 n扩展节点扩展节点n n：称生成生成节点 n 的所有后继节点后继节点并计算计算生成这些后继 节点所造成的花费花费的过程（ 即，计算各后继节点的优劣且将其 连接到节点 n 等操作造成的开销 ）叫做扩展节点扩展节点 n n 。 n 后继节点后继节点：称将规则作用于节点 n 生成生成的新节点为节点 n 的后后 继节点。继节点。 2021/5/27 北京航空航天大

25、学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 26 n 路径路径：对于一个节点序列（n0, n1, , nl, , nk），如若每一节点 ni-1都有一个后继节点 ni（i = 1, 2, , k），则称该节点序列为一条 从节点 n0 到节点 nk、长度为 k 的路径；路径还可表示为与节点序列 对应的规则序列 。 状态空间状态空间搜索有关概念搜索有关概念 n路径花费路径花费：设 C（ni，nj）为节点 ni 到 nj 这段路径（或弧线）的 花费。一条路径的花费等于连接这条路径各节点间所有弧线花费 值的总和。路径 n i nj t 的花费值C（ni，t）可递

26、归计算如下: C（ni，t）= C (ni，nj) + C（nj，t ) )。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 27 基于基于状态空间状态空间的的盲目盲目搜索算法搜索算法: : 宽宽度优先搜索策略度优先搜索策略 深深度优先搜索策略度优先搜索策略 问题求解基本原理 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 28 盲目搜索盲目搜索算法的算法的符号符号及及数据结构数据结构 s： 初始节点；n n：当前节点。 open： 已被生成已被生成但未

27、被扩展未被扩展的节点序列表； closed：已被生成已被生成且已被扩展已被扩展的节点序列表； mi = mj mk mlmi = mj mk ml：扩展 n 后所得的 n 的后继节点后继节点 其中， mk ：在OPEN表中出现过的待扩展节点待扩展节点， ml ：在CLOSED表中出现过的已扩展节点已扩展节点。 mj ：第一次生成的节点，mj OPEN 且 mj CLOSED表， 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 29 宽度宽度优先搜索算法优先搜索算法 open := S; closed := ; while o

28、pen do n := first ( open ); remove ( first ( open ) ); add ( n, closed )； if n = goal then exit ( success ); expand ( n ) - mi ; delete ( ( mi)( mi mk ( mi ml ) ); add ( open, mj) ; exit ( fail ); 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 30 宽度宽度优先搜索算法优先搜索算法 1、S, A, D 2、A, D, B, D 3

29、、D, B, A, E Open 表为表为队队 操操 作作： 先进先出！先进先出！ 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 31 G 节点节点扩展扩展 顺序顺序 宽度宽度优先搜索算法优先搜索算法 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 32 open := S; closed := ; d = 深度限制值深度限制值 while open do n := first ( open ); remove ( first ( open ) ); a

30、dd ( n, closed )； if n = goal then exit ( success ); if depth ( n ) d then continue; expand ( n ) - mi ; delete ( ( mi)( mi mk ( mi ml ) ); add ( mj, open ) ; exit ( fail ); 深度深度优先搜索算法优先搜索算法 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 33 深度深度优先搜索算法优先搜索算法 1、S 2、A, D 3、B, D, D Open表为表为栈

31、栈 操操 作作：后进先出！后进先出！ 4、C, E, D 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 34 节点节点扩展扩展 顺序顺序 深度深度优先搜索算法优先搜索算法 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 35 盲目盲目搜索搜索算法应用实例算法应用实例- - 8 8数码问题数码问题 描述描述状态状态： 矩阵矩阵(S(Sij ij) )，其中 ，其中 1 1i,ji,j3 3，S Sij ij 0,1,0,1,8;,8; 2021/5/27

32、北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 36 盲目搜索算法应用实例盲目搜索算法应用实例 - - n 合法走步规则：合法走步规则： 设设 (i0i0、j0)j0)为空格所在行列数值，为空格所在行列数值， S Si0j0 i0j0 = 0 = 0 R1: if j-1R1: if j-11 then S1 then Si0j0 i0j0:= S := Si0(j0-1) i0(j0-1), S , Si0(j0-1) i0(j0-1):=0 :=0 空格左移；空格左移； R2: if i-1R2: if i-11 then S1 then

33、Si0j0 i0j0:= S := S(i0-1)j0 (i0-1)j0, S , S(i0-1)j0 (i0-1)j0:=0 :=0 空格上移；空格上移； R3: if j+1R3: if j+13 then S3 then Si0j0 i0j0:= S := Si0(j0+1) i0(j0+1), S , Si0(j0+1) i0(j0+1):=0 :=0 空格右移；空格右移； R4: if i+1R4: if i+13 then S3 then Si0j0 i0j0:= S := S(i0+1)j0 (i0+1)j0, S , S(i0+1) (i0+1)j0:=0 j0:=0 空格下移

34、。空格下移。 8 8数码问题数码问题 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 37 宽度优先策略宽度优先策略求解求解8 8数码问题数码问题： 目标目标 R1 R2 R3 R2 R1 R2 R3 R2 R2 R3R2 R4 R1R3 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 38 深度优先策略深度优先策略求解求解8 8数码问题：数码问题： n 说明：说明： 设规则固定使用顺序：设规则固定使用顺序： R1- 左移、左移、R2-上移、上移、 R3-

35、 右移、右移、R4-下移；下移； 设节点深度限制值：设节点深度限制值：6 ； 合法的走步合法的走步 规则规则 重复节点重复节点 造成循环造成循环 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 39 问题求解基本原理 基于基于状态空间状态空间的的启发式启发式搜索算法搜索算法: : A A 算法；算法； A A* * 算法算法 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 40 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学

36、软件开发环境国家重点实验室 Slide 41 启发式启发式图搜索算法图搜索算法 n假设：假设： f (n) = g (n) + h (n) 任意节点任意节点 n 的的评价函数评价函数：指指迄今为止迄今为止已已找到找到的从初的从初 始节点始节点 s ，到达节点，到达节点 n，再从节点，再从节点 n 到达目标节点到达目标节点 t 的路径全程的最小费的路径全程的最小费 用，用，是对是对 f *(n ) 的一个估计。的一个估计。 h (n) ：迄今为止迄今为止从从节点节点 n 到目标节点到目标节点 t 最佳分段路径最佳分段路径将要花费将要花费的的未知未知估估 计费用计费用，是对是对 h* (n) 的一

37、个估计，的一个估计，可视为可视为启发式分量函数启发式分量函数，有，有h (n) 0。 g (n) ：迄今为止搜索到迄今为止搜索到的从的从初始节点初始节点 s 到当前节点到当前节点 n 最佳路径分段的最佳路径分段的 已知费用已知费用，是对是对g* (n) 的一个估计。的一个估计。 f *(n) = g* (n) + h* (n)：从初始节点从初始节点 s 出发，经过出发，经过最佳路径最佳路径上任意上任意 节点节点 n，到达目标节点，到达目标节点 t 的的最小最小费用。费用。 h* (n)：n t 最佳路径最佳路径的的分段费用分段费用。 g* (n)：sn 最佳路径最佳路径的的分段费用。分段费用。

38、 s：初始节点；初始节点；n：当前节点；当前节点；t：目标节点。目标节点。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 42 启发式启发式图搜索算法图搜索算法 - A 算算 法法 n 定义定义：按照按照 f (n) = g (n) + h (n) f (n) = g (n) + h (n) 估价函数值由小到大估价函数值由小到大 地排列待扩展节点顺序的图搜索算法，称为地排列待扩展节点顺序的图搜索算法，称为A A 算法。算法。 n A 算法流程。算法流程。 nA算法应用实例算法应用实例: n 普通有向图普通有向图 A 算法搜

39、索实例算法搜索实例； n 8数码问题数码问题A 算法搜索实例算法搜索实例。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 43 启发式图搜索算法启发式图搜索算法 - A - A算法算法 n算法中符号：算法中符号： s：初始节点；G：搜索图的节点集合； OPEN表： 已生成但尚未被扩展的节点序列表； CLOSED表： 已生成且已被扩展的节点序列表； n： 待扩展的当前节点； mi = mj mk ml：扩展 n 后生成的后继节点 其中， mj：第一次生成的节点，mj OPEN 且 mj CLOSED表， mk：在OPEN表中

40、出现过的待扩展节点， ml：在CLOSED表中出现过的已扩展节点。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 44 A算法算法 n 为目标为目标t ? 取当前节点取当前节点 n n := first ( OPEN ), 从从OPEN中删除中删除n, CLOSED:= CLOSEDn 初初 始始 化化 G:=G0S, OPEN:=(S) CLOSED := ( ), f (S) := g(S) + h(S) OPEN= 未发现目标未发现目标t Return ( Fail ) A yes No yes No B Exit

41、( Success ) 输出解径输出解径 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 45 扩展扩展节点节点n：生成：生成n的后继节点；计算后继节点的花费。的后继节点；计算后继节点的花费。 mi := Expand(n), 计算计算: f (n, mi) := g(n,mi) + h(mi) 比较花费，修改比较花费，修改连接标记连接标记 对于对于mj mi: OPEN:= OPEN mj , mj - n; 对于对于mk mi: if f (n, mk) n; 对于对于ml mi: if f (n, ml) n, OPE

42、N:= OPEN ml 将将OPEN表中节点按表中节点按f 值值 从小到大重新排序从小到大重新排序 AB 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 46 启发式最佳启发式最佳图搜索算法图搜索算法 - A*算法算法 n A*算法定义：算法定义： 若将若将A算法中评价函数算法中评价函数 f (n)的启发式分量函数的启发式分量函数 h（n）的值）的值 限制在限制在 h*（n）的下界范围内，亦即对所有节点）的下界范围内，亦即对所有节点 n，都满足，都满足 h（n） h*（n），则称此时的），则称此时的 A 算法为算法为 A*

43、算法。算法。 n A*算法作用：算法作用： 问题有解时，问题有解时， A A* *算法算法一定能够找到一定能够找到从初始节点从初始节点 s s 到目标节到目标节 点点 t t 的的最佳最佳解径。解径。 2021/5/27 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 47 n 信息度信息度定理：定理： 有两个有两个A*算法算法A1和和A2, 若若A2比比A1有较多的启发式信息（即对所有有较多的启发式信息（即对所有 非目标节点均有：非目标节点均有： h1（n） h2（n） h*（n），则在具有一条从），则在具有一条从 s 到到 t 的隐含状态图上，搜索结束时，由的隐含状态图上，搜索结束时，由A2扩展的每一个节点，也必扩展的每一个节点，也必 定由定由A1所扩展，即所扩展，即