1、北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 1人人 工工 智智 能能(问题求解问题求解基本原理及基本原理及搜索技术搜索技术)北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 2问题求解基本原理n问题求解：问题求解：在给定条件下，寻求一个能解决某类某类问题问题且能在有限步骤内完成的算法。n 问题求解特征：问题求解特征：w 传统软件传统软件：求解的问题是能够用数学精确描述的良结构良结构的问题的问题（如，解方程）；计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。w AI软件软件：求解的是不
2、可直接用数学模型描述的所谓不良不良结构问题结构问题（如，几何证明、求不定积分、逻辑演算等），通常需要采用弱方法进行搜索求解；AI程序程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息，应表现人类进行推理所需要的各种知识知识。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 3问题求解基本原理一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法二、搜二、搜 索索 技技 术术北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 4问题求解基本原理n问题求解方法：问题求解方法：w基于基于状态
3、空间状态空间的问题求解方法的问题求解方法w基于基于问题空间问题空间的问题求解方法的问题求解方法 w基于博弈搜索的问题求解方法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 5问题实例问题实例 桌上固定了桌上固定了 3 根柱子，按根柱子，按 1，2，3 次序排例。有次序排例。有 n n 个大小全不一样大个大小全不一样大的盘子的盘子d1，dn，按从小到大，小的在上的次序依次插在第一根柱子上，按从小到大，小的在上的次序依次插在第一根柱子上，要把这要把这 n n 个盘子全部搬到第三根柱子上，每次只许搬一个，任何时候都不个盘子全部搬到第三根柱子上，每次只
4、许搬一个，任何时候都不允许把大盘子放在小盘子上面，问该允许把大盘子放在小盘子上面，问该如何搬法。如何搬法。设设 n=3，该该如何搬法如何搬法？1 2 3 1 2 3梵塔问题北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 6基于基于状态空间状态空间的问题求解方法的问题求解方法（1，1，1）（1，1，2）（1，1，1）（1，1，3）（1，1，2）（1，3，2）。状态状态合法合法变换规则（满足约束条件）：变换规则（满足约束条件）：状态定义状态定义 -（i i大大,j,j中中,k,k小小 ）:设向量下标分别表示大盘、中盘、小盘；向量值分别表示盘子所在柱
5、子的编号。状态描述状态描述 -大盘在第 i 根柱子上；中号盘在第 j 根柱子上，小号盘在第 k 根柱子上。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 7基于基于问题空间问题空间的问题求解方法的问题求解方法n问题：问题：如何将如何将 i i 柱子上的柱子上的 m m 个盘子搬到个盘子搬到 k k 柱子上柱子上?w 将 i 柱子上的 m 1 个盘子搬到 j 柱子上；w 将 i 柱子上的 第 m 个盘子搬到 k 柱子上；w 将 j 柱子上的 m 1 个盘子搬到 k 柱子上。n 问题描述：问题描述：问题（问题（a,b,c):a,b,c):将 b 柱
6、子上的 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）。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 8 基于基于问题空间问题空间的问题求解方法的问题求解方法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 9状态空间法状态空间法有关概念有关概念n 状态空间法状态空间法:从问题的从问题的初始状态初始状态出发，通过一系列的出发，通过一系列的状态变换状态变换找到找到目标状态目标
7、状态的的问题求解方法。问题求解方法。n 状态状态：描述问题中事物形状或状况的符号或数据结构。描述问题中事物形状或状况的符号或数据结构。n 状态空间状态空间：所有状态的全体构成的集合；用所有状态的全体构成的集合；用四元组四元组（S,SS,S0 0,O,G),O,G)表示表示:S:S:非空状态子集，非空状态子集，S S0 0=初始状态（非空）。初始状态（非空）。G:G:非空目标状态子集。非空目标状态子集。O:O:操作算子集操作算子集合合，一个状态，一个状态合法合法转换为转换为另一个状态的另一个状态的描述描述规则规则n 问题求解过程问题求解过程：隐含隐含求一个求一个普通有向图普通有向图，节点节点 -
8、状态，状态，边边 算子算子 n 状态变换规则状态变换规则：一个状态向另一个状态一个状态向另一个状态合法转换合法转换的描述规则。的描述规则。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 10状态空间法状态空间法有关概念有关概念状态空间、搜索空间及解径的关系：状态空间、搜索空间及解径的关系：n 问题的解（解径）问题的解（解径）：初始状态初始状态到到目标状态目标状态通路上的每一条通路上的每一条规则规则（或（或 状态）构成状态）构成序列，称为序列，称为解径解径。解不唯一。解不唯一。S S0 0 R R1 1 S S2 2 R R2 2 S Sk k.
9、R Rk k G Gn问题有解问题有解：从代表从代表初始状态初始状态 s s 节点出发，节点出发，存在一条通向存在一条通向目标节点目标节点的路径的路径n 搜索空间搜索空间：问题求解过程中问题求解过程中到达到达过的所有状态（节点）的集合。过的所有状态（节点）的集合。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 11问题空间法问题空间法有关概念有关概念n问题空间法问题空间法：首先产生待证问题的首先产生待证问题的所有所有子问题，而后通过解决所有子问题达到子问题，而后通过解决所有子问题达到问题求解目的的方法。问题求解目的的方法。n 问题问题：描述问题
10、及其子问题的符号或数据结构描述问题及其子问题的符号或数据结构。n 问题空间问题空间：初始问题以及其所有子问题的全体构成的集合，用初始问题以及其所有子问题的全体构成的集合，用四元四元组组（S,SS,S0 0,F,G),F,G)表示表示:w S:S:问题和子问题；问题和子问题；S S0 0:初始问题初始问题。w G:G:具有具有平凡解平凡解的的本原问题本原问题集合。集合。w F:F:操作算子集合，用于将问题分解成其若干个子问题的描述规则操作算子集合，用于将问题分解成其若干个子问题的描述规则n 问题分解规则问题分解规则：将一个问题（子将一个问题（子问题问题）分解成其若干个子问题。）分解成其若干个子问
11、题。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 12问题空间法问题空间法的有关概念（的有关概念（2 2）n问题空间分解过程问题空间分解过程：隐含求一个隐含求一个与或图与或图w 节点节点 问题，问题，边边 -分解问题的算子。分解问题的算子。w “与与”节点节点：如果节点 A 有边通向一组节点 B1，B2，.Bn，问题 A 的解决有待于 A 的子问题组 B1,B2.Bn 的全部解决全部解决，则称 A 为“与”节点。如图 a 所示。w “或或”节点节点：若节点有边通向一组节点,2，n，问题的解决有待于子问题或2或或n中某一个子问某一个子问题的解决
12、题的解决，则称 A 为“或”节点。如图 b 所示。.a:AB1B2Bn.b:AB1B2Bn北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 13问题空间法问题空间法有关概念（有关概念（2 2）n问题的解（解图）问题的解（解图）：从代表从代表初始问题初始问题的节点出发，搜索到一个完的节点出发，搜索到一个完整的整的与或与或 子图子图，图中所有叶节点均满足问题求解的结束条件。，图中所有叶节点均满足问题求解的结束条件。例：例：（C,B,Z)-（M,M)重写规则:R1:C (D,L)R2:C (B,M)R3:B (M,M)R4:Z (B,B,M)解图解图北
13、京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 14小结小结 问题求解方法比较问题求解方法比较 状态空间法状态空间法 问题空间法问题空间法问题求解问题求解 状态变换 问题分解搜索过程搜索过程隐含构建普通有向图普通有向图隐含构建与或图与或图 节点节点 状态 问题 边边状态变换规则（算子）问题分解规则（算子）求解求解 解径 解图北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 15问题求解基本原理问题求解基本原理一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法二、搜二、搜 索索 技技 术术
14、（一）（一）北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 16n搜索技术预备搜索技术预备n状态空间搜索状态空间搜索w 有关概念w 盲目搜索策略w 启发式搜索策略问题求解基本原理问题求解基本原理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 17搜索策略预备搜索策略预备n盲目搜索：盲目搜索：不考虑给定问题所具有的特定知识，系统按照事先确定好的某种固定顺序固定顺序调用规则，或是随机地随机地调用规则。常用的常用的盲目盲目搜索算法搜索算法:深度优先搜索策略；深度优先搜索策略；宽度优先搜索策略宽度优先搜
15、索策略北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 18搜索策略预备搜索策略预备启发式信息启发式信息：与问题求解有关的信息和知识。由于信息的信息的片面性片面性和不准确性不准确性，应用启发式信息不能百分之百地保证找到问题的解，但能提高问题求解的可能性。启发式信息启发式信息在问题求解过程中的在问题求解过程中的作用作用：有助于有助于加速求解过程；加速求解过程；有助于有助于找到找到“较优较优”解。解。n 启发式搜索策略启发式搜索策略:考虑给定问题领域具有的特定知识（启发式信息启发式信息），系统动态地规定动态地规定规则调用顺序，优先使用优先使用“较较”
16、合适合适的规则。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 19搜索策略预备搜索策略预备n 常用的基于常用的基于状态图状态图的的启发式启发式搜索策略搜索策略:n 爬山搜索策略爬山搜索策略 (Hill Climbing)(Hill Climbing)n 大英博物馆搜索策略大英博物馆搜索策略 (British Museum)(British Museum)n 启发式图搜索策略启发式图搜索策略 (A A)n 最佳最佳启发式启发式图搜索策略图搜索策略 (A A*)n 常用的基于常用的基于与或图及博弈与或图及博弈的的启发式启发式搜索策略搜索策略：n
17、最佳最佳启发式启发式与或图搜索策略与或图搜索策略 (AOAO*)n 极大极小搜索策略极大极小搜索策略 (MinimaxMinimax)n 剪枝搜索策略剪枝搜索策略 (Alpha-Beta PruningAlpha-Beta Pruning)北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 20基于基于状态空间状态空间的的搜索技术：搜索技术：有关搜索概念有关搜索概念 盲目搜索策略盲目搜索策略 启发式启发式搜索策略搜索策略问题求解基本原理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 21状态空间状态
18、空间搜索搜索有关概念有关概念 n状态状态图图特点：特点：多条路径通向同一节点。例：E北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 22状态状态空间空间搜索搜索有关概念有关概念状态图搜索及生成过程状态图搜索及生成过程:从从S S节点开始，不断节点开始，不断搜索规搜索规则，则，动态动态生成生成节点节点;扩展扩展局部图；最终求得局部图；最终求得 S-G 的的可达路径可达路径。隐含隐含生成有重复节生成有重复节点的点的树树搜索过程搜索过程 特殊的特殊的图搜索图搜索北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Sl
19、ide 23状态空间状态空间搜索有关概念搜索有关概念n 节点深度节点深度：根节点根节点的深度深度为0，其它节点其它节点的深度深度规定为其父节 点的深度加 1，即dn+1=dn +1。n 标记节点标记节点 n n：用指针指针将后继节点连接连接到父节点 n 的操作。n 节点节点：对应状态图中有关状态状态的描述。n扩展节点扩展节点n n：称生成生成节点 n 的所有后继节点后继节点并计算计算生成这些后继节点所造成的花费花费的过程（即，计算各后继节点的优劣且将其连接到节点 n 等操作造成的开销）叫做扩展节点扩展节点 n n。n 后继节点后继节点：称将规则作用于节点 n 生成生成的新节点为节点 n 的后后
20、继节点。继节点。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 24n 路径路径：对于一个节点序列（n0,n1,nl,nk），如若每一节点 ni-1都有一个后继节点 ni（i=1,2,k），则称该节点序列为一条从节点 n0 到节点 nk、长度为 k 的路径；路径还可表示为与节点序列对应的规则序列。状态空间状态空间搜索有关概念搜索有关概念n路径花费路径花费：设 C（ni，nj）为节点 ni 到 nj 这段路径（或弧线）的花费。一条路径的花费等于连接这条路径各节点间所有弧线花费值的总和。路径 ni nj t 的花费值C（ni，t）可递归计算如下:C
21、（ni，t）=C(ni，nj)+C（nj，t)。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 25基于基于状态空间状态空间的的盲目盲目搜索算法搜索算法:宽宽度优先搜索策略度优先搜索策略深深度优先搜索策略度优先搜索策略问题求解基本原理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 26盲目搜索盲目搜索算法的算法的符号符号及及数据结构数据结构 s：初始节点；n n：当前节点。open：已被生成已被生成但未被扩展未被扩展的节点序列表；closed：已被生成已被生成且已被扩展已被扩展的节点序列表；mi
22、=mi=mjmj mkmk ml ml：扩展 n 后所得的 n 的后继节点后继节点 其中，mk：在OPEN表中出现过的待扩展节点待扩展节点，ml：在CLOSED表中出现过的已扩展节点已扩展节点。mj：第一次生成的节点，mj OPEN 且 mj CLOSED表，北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 27宽度宽度优先搜索算法优先搜索算法 open:=S;closed:=;while open do n:=first(open);remove(first(open);add(n,closed)；if n=goal then exit(suc
23、cess);expand(n)-mi;delete(mi)(mi mk (mi ml );append(open,mj);exit(fail);北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 28宽度宽度优先搜索算法优先搜索算法 1、S,A,D2、A,D,B,D3、D,B,A,EOpen 表为表为队队 操操 作作：先进先出！先进先出！北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 29G节点节点扩展扩展顺序顺序宽度宽度优先搜索算法优先搜索算法 北京航空航天大学软件开发环境国家重点实验室北京航空航
24、天大学软件开发环境国家重点实验室 Slide 30 open:=S;closed:=;d=深度限制值深度限制值while open do n:=first(open);remove(first(open);add(n,closed)；if n=goal then exit(success);if depth(n)d then continue;expand(n)-mi;delete(mi)(mi mk (mi ml );Insert(mj,open);exit(fail);深度深度优先搜索算法优先搜索算法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Sl
25、ide 31深度深度优先搜索算法优先搜索算法 1、S2、A,D3、B,D,DOpen表为表为栈栈 操操 作作：后进先出！后进先出！4、C,E,D北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 32节点节点扩展扩展顺序顺序深度深度优先搜索算法优先搜索算法 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 33盲目盲目搜索搜索算法应用实例算法应用实例-8 8数码问题数码问题描述描述状态状态：矩阵矩阵(S Sijij)，其中其中 1 1i,ji,j3 3，S Sijij0,1,0,1,8;,8;北京航空
26、航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 34盲目搜索算法应用实例盲目搜索算法应用实例 -n 合法走步规则：合法走步规则：设设(i0i0、j0)j0)为空格所在行列数值，为空格所在行列数值，S Si0j0i0j0=0=0R1:if j-1R1:if j-11 then S1 then Si0j0i0j0:=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 Si0j0i0j0:=S:=S(i0-1)j0(i0-1)j0,
27、S,S(i0-1)j0(i0-1)j0:=0:=0 空格上移；空格上移；R3:if j+1R3:if j+13 then S3 then Si0j0i0j0:=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 Si0j0i0j0:=S:=S(i0+1)j0(i0+1)j0,S,S(i0+1)(i0+1)j0:=0 j0:=0 空格下移。空格下移。8 8数码问题数码问题北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 3
28、5宽度优先策略宽度优先策略求解求解8 8数码问题数码问题：目标目标R1R2R3R2R1R2R3R2R2R3R2R4R1R3北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 36深度优先策略深度优先策略求解求解8 8数码问题：数码问题：n 说明：说明：设规则固定使用顺序：设规则固定使用顺序：R1-左移、左移、R2-上移、上移、R3-右移、右移、R4-下移；下移；设节点深度限制值：设节点深度限制值：6；合法的走步合法的走步规则规则重复节点重复节点 造成循环造成循环北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 S
29、lide 371 1、利用宽度优先法或深度优先法，、利用宽度优先法或深度优先法，程序实现程序实现 High-way map High-way map 问题求解，问题求解，只考虑节点的连接和变换只考虑节点的连接和变换,不考虑边不考虑边的权值的权值;求出有向图的一条解径求出有向图的一条解径,给出给出求解过程（即，给出求解过程（即，给出OpenOpen，ClosedClosed表表中的内容）。中的内容）。作业作业:2 2、利用宽度优先法或深度优先法，、利用宽度优先法或深度优先法，程序实现程序实现 8 8数码问题。数码问题。-隐含生成有向图隐含生成有向图北京航空航天大学软件开发环境国家重点实验室北京航
30、空航天大学软件开发环境国家重点实验室 Slide 38n给定两个油桶给定两个油桶,一个可装一个可装 4 4 公斤油公斤油,一个可装一个可装 3 3 公斤油公斤油,油桶上无任何度量标记。问：怎样才能使油桶上无任何度量标记。问：怎样才能使 4 4 公斤油桶公斤油桶里恰好只装里恰好只装 2 2 公斤油？公斤油？设状态定义设状态定义：(x,y)(x,y)，其中，其中，x x：4 4 公斤油桶中实际装油公斤数；公斤油桶中实际装油公斤数；y y：3 3 公斤油桶中实际装油公斤数。公斤油桶中实际装油公斤数。问题表示：问题表示：(0,0)-(0,0)-(2,y)(2,y)要求定义合法的装油规则，利用盲目搜索策
31、略画出状态要求定义合法的装油规则，利用盲目搜索策略画出状态图。图。作业作业:北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 39问题求解基本原理基于基于状态空间状态空间的的启发式启发式搜索算法搜索算法:A A 算法；算法；A A*算法算法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 40启发式图搜索策略启发式图搜索策略A算法算法、A*算法算法 核心思想核心思想：1、盲目搜索盲目搜索：根据节点连接情况，寻找s-t的解径（不一定最佳）；2、启发式搜索启发式搜索：根据节点连接及其花费情况，较快地寻找
32、 s-t 的最 佳（花费最小）的解径；3、求解思路求解思路：图搜索中，s-t 的路径总可以表示成 s-n n-t；若对图中每一个 n,都设置一个f(n),唯一地唯一地表示s-n-t路径的花费，即，在 n 与 f(n)=（s-n-t 路径的花费）之间建立一对一的映射；每当从当前局部局部搜索树搜索树中选择扩展叶节点 n 时，以f(n)=s-n-t路径花费最少为衡量标准；以此保证每次选择、扩展节点 n 都在当前局部最小花费的路径上进行。4 4、需解决的问题需解决的问题：如何为图中如何为图中节点节点 n n 定义定义标志全程路径标志全程路径 s-n-t 的花花 费费评价函数值评价函数值 f f（n n
33、）？）？如何保证节点 n 的 f(n)的唯一性唯一性。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 41启发式启发式图搜索算法图搜索算法n假设：假设：f(n)=g(n)+h(n)任意节点任意节点 n 的的评价函数评价函数：指指迄今为止迄今为止已已找到找到的从初的从初始节点始节点 s，到达节点到达节点 n，再从节点再从节点 n 到达目标节点到达目标节点 t 的路径全程的最小费的路径全程的最小费用，用，是对是对 f*(n)的一个估计。的一个估计。h(n)：迄今为止迄今为止从从节点节点 n 到目标节点到目标节点 t 最佳分段路径最佳分段路径将要花费
34、将要花费的的未知未知估估计费用计费用，是对是对 h*(n)的一个估计，的一个估计，可视为可视为启发式分量函数启发式分量函数，有，有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 最佳路径最佳路径的的分
35、段费用。分段费用。s：初始节点；初始节点；n：当前节点；当前节点；t：目标节点。目标节点。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 42启发式启发式图搜索算法图搜索算法-A 算算 法法 n 定义定义：按照按照 f(n)=g(n)+h(n)f(n)=g(n)+h(n)估价函数值由小到大估价函数值由小到大地排列待扩展节点顺序的图搜索算法，称为地排列待扩展节点顺序的图搜索算法，称为A A 算法。算法。n A 算法流程算法流程。nA算法应用实例算法应用实例:n 普通有向图普通有向图 A 算法搜索实例算法搜索实例；n 8数码问题数码问题A 算法搜索
36、实例算法搜索实例。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 43启发式图搜索算法启发式图搜索算法 -A-A算法算法n算法中符号：算法中符号：s：初始节点；G：搜索图的节点集合；OPEN表：已生成但尚未被扩展的节点序列表；CLOSED表：已生成且已被扩展的节点序列表；n：待扩展的当前节点；mi=mj mk ml：扩展 n 后生成的后继节点其中，mj：第一次生成的节点，mj OPEN 且 mj CLOSED表，mk：在OPEN表中出现过的待扩展节点，ml：在CLOSED表中出现过的已扩展节点。北京航空航天大学软件开发环境国家重点实验室北京航空
37、航天大学软件开发环境国家重点实验室 Slide 44A算法算法n 为目标为目标t?取当前节点取当前节点 nn:=first(OPEN),从从OPEN中删除中删除n,CLOSED:=CLOSEDn初初 始始 化化 G:=G0S,OPEN:=(S)CLOSED:=(),f(S):=g(S)+h(S)OPEN=未发现目标未发现目标tReturn(Fail)AyesNoyesNoBExit(Success)输出解径输出解径北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 45扩展扩展节点节点n：生成生成n的后继节点；计算后继节点的花费。的后继节点；计算后
38、继节点的花费。mi:=Expand(n),(mi)计算计算: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,OPEN:=OPEN ml将将OPEN表中节点按表中节点按f 值值从小到大重新排序从小到大重新排序AB北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 46搜索算法应用实例搜索算法应用实例 -8-8数码问题数码问题状态状态描述描述：矩阵矩阵(S Sijij
39、)，其中其中 1 1i,ji,j3 3，S Sijij0,1,0,1,8,8北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 47搜索算法应用实例搜索算法应用实例 -8-8数码问题数码问题n合法走步规则：合法走步规则：设设i0,j0i0,j0为空格所在行列数值，为空格所在行列数值，S Si0j0i0j0=0=0R1:if j0-1R1:if j0-11 then S1 then Si0j0i0j0:=S:=Si0(j0-1)i0(j0-1),S,Si0(j0-1)i0(j0-1):=0:=0 空格左移；空格左移；R2:if i0-1R2:if i
40、0-11 then S1 then Si0j0i0j0:=S:=S(i0-1)j0(i0-1)j0,S,S(i0-1)j0(i0-1)j0:=0:=0 空格上移；空格上移；R3:if j0+1R3:if j0+13 then S3 then Si0j0i0j0:=S:=Si0(j0+1)i0(j0+1),S,Si0(j0+1)i0(j0+1):=0:=0 空格右移；空格右移；R4:if i0+1R4:if i0+13 then S3 then Si0j0i0j0:=S:=S(i0+1)j0(i0+1)j0,S,S(i0+1)(i0+1)j0:=0 j0:=0 空格下移。空格下移。北京航空航天大
41、学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 48搜索算法应用实例搜索算法应用实例 -8-8数码问题数码问题ng(n)g(n):搜索树中节点 n 所在层的深度，每层为单位花费单位花费h(s)=w(s)=4 n h(n)=W(n)h(n)=W(n)：相对于目标节点而言，节点 n 中“不在位不在位”的将牌个数之和的将牌个数之和”(二者差异二者差异)启发式分量函数启发式分量函数。f(n)=g(n)+h(n)f(n)=g(n)+h(n)：节点节点 n n 的层次深度一定，n 与目标节点之间的差异差异越小，即 h(n)越小，则 f(n)越小，优先扩展。北京航空航天大
42、学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 49搜索算法应用实例搜索算法应用实例 -8-8数码问题数码问题目标目标S(4)C(6)A(6)D(5)F(6)G(6)L(5)g(s)=d0=0g(A,B,C)=d1=1g(D,E,F)=d2=2g(G,H,I,J)=d3=3g(K)=d4=4g(L,M)=d5=5括号中为括号中为 f f 值值北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 50启发式最佳启发式最佳图搜索算法图搜索算法-A*算法算法n A*算法定义：算法定义：若将若将A算法中评价函数算法中评价函
43、数 f(n)的启发式分量函数的启发式分量函数 h（n）的值的值限制在限制在 h*（n）的下界范围内，亦即对所有节点的下界范围内，亦即对所有节点 n，都满足，都满足h（n）h*（n），），则称此时的则称此时的 A 算法为算法为 A*算法。算法。n A*算法作用：算法作用：问题有解时，问题有解时，A A*算法算法一定能够找到一定能够找到从初始节点从初始节点 s s 到目标节到目标节点点 t t 的的最佳最佳解径。解径。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 51n 信息度信息度定理：定理：有两个有两个A*算法算法A1和和A2,若若A2比比A
44、1有较多的启发式信息（即对所有有较多的启发式信息（即对所有非目标节点均有：非目标节点均有：h1（n）h2（n）h*（n），则在具有一条从），则在具有一条从 s 到到 t 的隐含状态图上，搜索结束时，由的隐含状态图上，搜索结束时，由A2扩展的每一个节点，也必扩展的每一个节点，也必定由定由A1所扩展，即所扩展，即A1扩展的节点数至少和扩展的节点数至少和A2一样多。一样多。启发式最佳启发式最佳图搜索算法图搜索算法-A*算法算法n A*算法应用验证算法应用验证:n 8数码问题数码问题A*算法搜索实例。算法搜索实例。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 S
45、lide 52 A A*算法应用实例算法应用实例 -8-8数码问题数码问题状态状态描述描述：矩阵矩阵(S Sijij)，其中其中 1 1i,ji,j3 3，S Sijij0,1,0,1,8,8北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 53 A A*算法应用实例算法应用实例 -8-8数码问题数码问题n合法走步规则：合法走步规则：设设i0,j0i0,j0为空格所在行列数值，为空格所在行列数值，S Si0j0i0j0=0=0R1:if j0-1R1:if j0-11 then S1 then Si0j0i0j0:=S:=Si0(j0-1)i0(
46、j0-1),S,Si0(j0-1)i0(j0-1):=0:=0 空格左移；空格左移；R2:if i0-1R2:if i0-11 then S1 then Si0j0i0j0:=S:=S(i0-1)j0(i0-1)j0,S,S(i0-1)j0(i0-1)j0:=0:=0 空格上移；空格上移；R3:if j0+1R3:if j0+13 then S3 then Si0j0i0j0:=S:=Si0(j0+1)i0(j0+1),S,Si0(j0+1)i0(j0+1):=0:=0 空格右移；空格右移；R4:if i0+1R4:if i0+13 then S3 then Si0j0i0j0:=S:=S(i
47、0+1)j0(i0+1)j0,S,S(i0+1)(i0+1)j0:=0 j0:=0 空格下移。空格下移。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 54A A*算法应用实例算法应用实例 -8-8数码问题数码问题ng(n)g(n):搜索树中节点n所在层的深度，每层为单位花费。单位花费。n h(n)=P(n)h(n)=P(n)：节点 n 中各将牌与目标节点中对应将牌对应将牌相比归位的归位的距离之和（不考虑夹在其间的将牌）。距离之和（不考虑夹在其间的将牌）。-启发式分量函数启发式分量函数 f(nf(n)=)=g(n)+h(ng(n)+h(n)：节
48、点节点 n n 的层次深度一定，节点 n 与目标节点之间对应将牌的距离之和距离之和越小小，即 h(n)值越小，f(n)越小，优先扩展h(s)=P(s)=5北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 55A A*算法应用实例算法应用实例 -8-8数码问题数码问题n启发式函数比较启发式函数比较:w h(nh(n)=)=P(nP(n):):指出了本节点中各将牌归位的步数之和，指出了本节点中各将牌归位的步数之和，但未具体给出若考虑夹在其间的将牌，应如何移动将牌、但未具体给出若考虑夹在其间的将牌，应如何移动将牌、搜索最小解径的指导信息，因此有搜索最小
49、解径的指导信息，因此有 P(n)h(nP(n)h(n)*。u 对于任一节点对于任一节点n，至少要移动，至少要移动 P(n)步才能达到目标。实际的步才能达到目标。实际的走步数要经过一定程度的搜索。走步数要经过一定程度的搜索。h(n)=W(n):指出了本节点与目标节点的指出了本节点与目标节点的差异差异,但未具体给但未具体给出如何移动将牌、搜索最小解径的指导信息：出如何移动将牌、搜索最小解径的指导信息：W(n)h(n)*w 对于任一节点对于任一节点n，至少要移动，至少要移动 W(n)步才能达到目标。实际步才能达到目标。实际的走步数要经过一定程度的搜索。的走步数要经过一定程度的搜索。两算法均为两算法均
50、为A*算法算法 W(n)P(n)h*(n)北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 56A A*算法应用实例算法应用实例 -8-8数码问题数码问题g(s)=d0=0g(A,B,C)=d1=1g(D,E,F)=d2=2g(G,H,I,J)=d3=3g(K)=d4=4g(L,M)=d5=5北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 578数码问题数码问题搜索策略比较：搜索策略比较：宽度优先宽度优先 A算法算法 A*算法算法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环
