《人工智能 问题求解基本原理及搜索技术.pptx》由会员分享，可在线阅读，更多相关《人工智能 问题求解基本原理及搜索技术.pptx（75页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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 柱子上的 a 个盘
6、子搬到 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.R Rk k G G
9、n问题有解问题有解：从代表从代表初始状态初始状态 s s 节点出发，节点出发，存在一条通向存在一条通向目标节点目标节点的路径。的路径。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 11问题空间法问题空间法有关概念有关概念n问题空间法问题空间法：首首先先产产生生待待证证问问题题的的所所有有子子问问题题，而而后后通通过过解解决决所所有有子子问问题题达达到到问问题求解目的的方法。题求解目的的方法。n 问题问题：描述问题及其子问题的符号或数据结构描述问题及其子问题的符号或数据结构。n 问题空间问题空间：初始问题以及其所有子问题的全体构成的集合，用初始
10、问题以及其所有子问题的全体构成的集合，用四元四元组组（S,SS,S0 0,F,G),F,G)表示表示:w S:S:问题和子问题；问题和子问题；S S0 0:初始问题。初始问题。w G:G:具有具有平凡解平凡解的的本原问题本原问题集合。集合。w F:F:操作算子集合，用于将问题分解成其若干个子问题的描述规则操作算子集合，用于将问题分解成其若干个子问题的描述规则北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 12问题空间法问题空间法的有关概念（的有关概念（2 2）n问题空间分解过程问题空间分解过程：隐含求一个隐含求一个与或图与或图w 节点节点 问题
11、，问题，边边 -分解问题的算子。分解问题的算子。w “与与”节点：节点：如果节点 A 有边通向一组节点 B1，B2，.Bn，问题 A 的解决有待于 A 的子问题组 B1,B2.Bn 的全部解决全部解决，则称 A 为“与”节点。如图 a 所示。w “或或”节点：节点：若节点有边通向一组节点,2，n，问题的解决有待于子问题或2或或n中某一个某一个子问题的解决子问题的解决，则称 A 为“或”节点。如图 b 所示。.a:AB1B2Bn.b:AB1B2Bn北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 13问题空间法问题空间法有关概念（有关概念（2 2）
12、n问题的解（解图）问题的解（解图）：从代表从代表初始问题初始问题的节点出发，搜索到一个完的节点出发，搜索到一个完整的整的与或与或 子图子图，图中所有叶节点均满足问题求解的结束条件。，图中所有叶节点均满足问题求解的结束条件。例：例：（C,B,Z)-（M,M)重写规则:R1:C (D,L)R2:C (B,M)R3:B (M,M)R4:Z (B,B,M)解图解图北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 14小结小结 问题求解方法比较问题求解方法比较 状态空间法状态空间法 问题空间法问题空间法问题求解问题求解 状态变换 问题分解搜索过程搜索过程隐
13、含构建普通有向图普通有向图隐含构建与或图与或图 节点节点 状态 问题 边边状态变换规则（算子）问题分解规则（算子）求解求解 解径 解图北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 15问题求解基本原理问题求解基本原理一、问一、问 题题 求求 解解 的的 基基 本本 方方 法法二、搜二、搜 索索 技技 术术 （一）（一）北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 16n搜索技术预备搜索技术预备n状态空间搜索状态空间搜索w 有关概念w 盲目搜索策略w 启发式搜索策略问题求解基本原理问题求解基本
14、原理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 17搜索策略预备搜索策略预备n盲目搜索：盲目搜索：不考虑给定问题所具有的特定知识，系统按照事先确定好的某种固定顺序固定顺序调用规则，或是随机地随机地调用规则。常用的常用的盲目盲目搜索算法搜索算法:深度优先搜索策略；深度优先搜索策略；宽度优先搜索策略宽度优先搜索策略北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 18搜索策略预备搜索策略预备启发式信息启发式信息：与问题求解有关的信息和知识。由于信息的信息的片面性片面性和不准确性不准确性，应用启发式
15、信息不能百分之百地保证找到问题的解，但能提高问题求解的可能性。启发式信息启发式信息在问题求解过程中的在问题求解过程中的作用作用：有助于有助于加速求解过程；加速求解过程；有助于有助于找到找到“较优较优”解。解。n 启发式搜索策略启发式搜索策略:考虑给定问题领域具有的特定知识（启发式信息启发式信息），系统动态地规定动态地规定规则调用顺序，优先使用优先使用“较较”合适合适的规则。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 19搜索策略预备搜索策略预备n 常用的基于常用的基于状态图状态图的的启发式启发式搜索策略搜索策略:n 爬山搜索策略爬山搜索策略
16、(Hill Climbing)(Hill Climbing)n 大英博物馆搜索策略大英博物馆搜索策略(British Museum)(British Museum)n 启发式图搜索策略启发式图搜索策略(A A)n 最佳最佳启发式启发式图搜索策略图搜索策略(A A*)n 常用的基于常用的基于与或图及博弈与或图及博弈的的启发式启发式搜索策略搜索策略：n 最佳最佳启发式启发式与或图搜索策略与或图搜索策略(AOAO*)n 极大极小搜索策略极大极小搜索策略(MinimaxMinimax)n 剪枝搜索策略剪枝搜索策略(Alpha-Beta PruningAlpha-Beta Pruning)北京航空航天大
17、学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 20基于基于状态空间状态空间的的搜索技术：搜索技术：有关搜索概念有关搜索概念 盲目搜索策略盲目搜索策略 启发式启发式搜索策略搜索策略问题求解基本原理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 21状态空间状态空间搜索搜索有关概念有关概念 n状态状态图图特点：特点：多条路径通向同一节点。例：E北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 22状态空间状态空间搜索搜索有关概念有关概念北京航空航天大学软件开发环境
18、国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 23状态空间状态空间搜索有关概念搜索有关概念n 节点深度节点深度：根节点根节点的深度深度为0，其它节点其它节点的深度深度规定为其父节 点的深度加 1，即dn+1=dn +1。n 标记节点标记节点 n n：用指针指针将后继节点连接连接到父节点 n 的操作。n 节点节点：对应状态图中有关状态状态的描述。n扩展节点扩展节点n n：称生成生成节点 n 的所有后继节点后继节点并计算计算生成这些后继节点所造成的花费花费的过程（即，计算各后继节点的优劣且将其连接到节点 n 等操作造成的开销）叫做扩展节点扩展节点 n n。n 后继节点后继节
19、点：称将规则作用于节点 n 生成生成的新节点为节点 n 的后后继节点。继节点。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 24n 路径路径：对于一个节点序列（n0,n1,nl,nk），如若每一节点 ni-1都有一个后继节点 ni（i=1,2,k），则称该节点序列为一条从节点 n0 到节点 nk、长度为 k 的路径；路径还可表示为与节点序列对应的规则序列。状态空间状态空间搜索有关概念搜索有关概念n路径花费路径花费：设 C（ni，nj）为节点 ni 到 nj 这段路径（或弧线）的花费。一条路径的花费等于连接这条路径各节点间所有弧线花费值的总和。
20、路径 ni nj t 的花费值C（ni，t）可递归计算如下:C（ni，t）=C(ni，nj)+C（nj，t)。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 25基于基于状态空间状态空间的的盲目盲目搜索算法搜索算法:宽宽度优先搜索策略度优先搜索策略深深度优先搜索策略度优先搜索策略问题求解基本原理北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 26盲目搜索盲目搜索算法的算法的符号符号及及数据结构数据结构 s：初始节点；n n：当前节点。open：已被生成已被生成但未被扩展未被扩展的节点序列表；cl
21、osed：已被生成已被生成且已被扩展已被扩展的节点序列表；mi=mj mk mlmi=mj mk 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
22、,closed)；if n=goal then exit(success);expand(n)-mi;delete(mi)(mi mk (mi ml );add(open,mj);exit(fail);北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 28宽度宽度优先搜索算法优先搜索算法 1、S,A,D2、A,D,B,D3、D,B,A,EOpen 表为表为队队 操操 作作：先进先出！先进先出！北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 29G节点节点扩展扩展顺序顺序宽度宽度优先搜索算法优先搜索
23、算法 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 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 );add(mj,open);exit(fail);深度深度优先搜索算法优先搜索算法北京航空航天大学软件开发环境国家重点实
24、验室北京航空航天大学软件开发环境国家重点实验室 Slide 31深度深度优先搜索算法优先搜索算法 1、S2、A,D3、B,D,DOpen表为表为栈栈 操操 作作：后进先出！后进先出！4、C,E,D北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 32节点节点扩展扩展顺序顺序深度深度优先搜索算法优先搜索算法 北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 33盲目盲目搜索搜索算法应用实例算法应用实例-8 8数码问题数码问题描述描述状态状态：矩阵矩阵(S(Sijij)，其中，其中 1 1i,ji,j3
25、 3，S Sijij0,1,0,1,8;,8;北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 34盲目搜索算法应用实例盲目搜索算法应用实例-n 合法走步规则：合法走步规则：设设(i0i0、j0)j0)为空格所在行列数值，为空格所在行列数值，SSi0j0i0j0=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 Si0j0i0
26、j0:=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 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数码问题数码问题北京航空航天大学软件开发环境国家重点实验室北京航空
27、航天大学软件开发环境国家重点实验室 Slide 35宽度优先策略宽度优先策略求解求解8 8数码问题数码问题：目标目标R1R2R3R2R1R2R3R2R2R3R2R4R1R3北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 36深度优先策略深度优先策略求解求解8 8数码问题：数码问题：n 说明：说明：设规则固定使用顺序：设规则固定使用顺序：R1-左移、左移、R2-上移、上移、R3-右移、右移、R4-下移；下移；设节点深度限制值：设节点深度限制值：6；合法的走步合法的走步规则规则重复节点重复节点 造成循环造成循环北京航空航天大学软件开发环境国家重点实
28、验室北京航空航天大学软件开发环境国家重点实验室 Slide 37问题求解基本原理基于基于状态空间状态空间的的启发式启发式搜索算法搜索算法:A A 算法；算法；A A*算法算法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 38北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 39启发式启发式图搜索算法图搜索算法n假设：假设：f(n)=g(n)+h(n)任意节点任意节点 n 的的评价函数评价函数：指指迄今为止迄今为止已已找到找到的从初的从初始节点始节点 s，到达节点，到达节点 n，再从节点，再从节点
29、 n 到达目标节点到达目标节点 t 的路径全程的最小费用，的路径全程的最小费用，是对是对 f*(n)的一个估计。的一个估计。h(n)：迄今为止迄今为止从从节点节点 n 到目标节点到目标节点 t 最佳分段路径最佳分段路径将要花费将要花费的的未知未知估估计费用计费用，是对是对 h*(n)的一个估计，的一个估计，可视为可视为启发式分量函数启发式分量函数，有，有h(n)0。g(n)：迄今为止搜索到迄今为止搜索到的从的从初始节点初始节点 s 到当前节点到当前节点 n 最佳路径分段的最佳路径分段的已知费用已知费用，是对是对g*(n)的一个估计。的一个估计。f*(n)=g*(n)+h*(n)：从初始节点从初
30、始节点 s 出发，经过出发，经过最佳路径最佳路径上任意上任意节点节点 n，到达目标节点，到达目标节点 t 的的最小最小费用。费用。h*(n)：n t 最佳路径最佳路径的的分段费用分段费用。g*(n)：sn 最佳路径最佳路径的的分段费用。分段费用。s：初始节点；初始节点；n：当前节点；当前节点；t：目标节点。目标节点。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 40启发式启发式图搜索算法图搜索算法-A 算算 法法 n 定义定义：按照按照 f(n)=g(n)+h(n)f(n)=g(n)+h(n)估价函数值由小到大估价函数值由小到大地排列待扩展节
31、点顺序的图搜索算法，称为地排列待扩展节点顺序的图搜索算法，称为A A 算法。算法。n A 算法流程。算法流程。nA算法应用实例算法应用实例:n 普通有向图普通有向图 A 算法搜索实例算法搜索实例；n 8数码问题数码问题A 算法搜索实例算法搜索实例。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 41启发式图搜索算法启发式图搜索算法-A-A算法算法n算法中符号：算法中符号：s：初始节点；G：搜索图的节点集合；OPEN表：已生成但尚未被扩展的节点序列表；CLOSED表：已生成且已被扩展的节点序列表；n：待扩展的当前节点；mi=mj mk ml：扩展
32、 n 后生成的后继节点其中，mj：第一次生成的节点，mj OPEN 且 mj CLOSED表，mk：在OPEN表中出现过的待扩展节点，ml：在CLOSED表中出现过的已扩展节点。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 42A算法算法n 为目标为目标t?取当前节点取当前节点 nn:=first(OPEN),从从OPEN中删除中删除n,CLOSED:=CLOSEDn初初 始始 化化 G:=G0S,OPEN:=(S)CLOSED:=(),f(S):=g(S)+h(S)OPEN=未发现目标未发现目标tReturn(Fail)AyesNoyesN
33、oBExit(Success)输出解径输出解径北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 43扩展扩展节点节点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,OPEN:=OPEN ml将将OPEN表中节点按表中节点按f 值值从小到大重新排序
34、从小到大重新排序AB北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 44启发式最佳启发式最佳图搜索算法图搜索算法-A*算法算法n A*算法定义：算法定义：若若将将A算算法法中中评评价价函函数数 f(n)的的启启发发式式分分量量函函数数 h（n）的的值值限限制制在在 h*（n）的的下下界界范范围围内内，亦亦即即对对所所有有节节点点 n，都都满满足足h（n）h*（n），则称此时的），则称此时的 A 算法为算法为 A*算法。算法。n A*算法作用：算法作用：问题有解时，问题有解时，A*A*算法算法一定能够找到一定能够找到从初始节点从初始节点 s s
35、到目标节到目标节点点 t t 的的最佳最佳解径。解径。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 45n 信息度信息度定理：定理：有两个有两个A*算法算法A1和和A2,若若A2比比A1有较多的启发式信息（即对所有有较多的启发式信息（即对所有非目标节点均有：非目标节点均有：h1（n）h2（n）h*（n），则在具有一条从），则在具有一条从 s 到到 t 的隐含状态图上，搜索结束时，由的隐含状态图上，搜索结束时，由A2扩展的每一个节点，也必扩展的每一个节点，也必定由定由A1所扩展，即所扩展，即A1扩展的节点数至少和扩展的节点数至少和A2一样多。一
36、样多。启发式最佳启发式最佳图搜索算法图搜索算法-A*算法算法n A*算法应用验证算法应用验证:n 8数码问题数码问题A*算法搜索实例。算法搜索实例。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 468数码问题数码问题搜索策略比较：搜索策略比较：宽度优先宽度优先 A算法算法 A*算法算法北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 47小结小结n启发式搜索策略启发式搜索策略n g:n 考虑当前路径考虑当前路径已经花费的费用已经花费的费用，及时抛弃已经经过的花费太大，及时抛弃已经经过的花费太大且
37、距目标仍远的路径且距目标仍远的路径;n h:n 估计当前路径上节点到目标节点估计当前路径上节点到目标节点还需要的费用还需要的费用，引导搜索向最，引导搜索向最有希望的路径前进。有希望的路径前进。w A A 算法算法：定义估计函数：定义估计函数：f=g+hf=g+h；u A A*算法算法：定义估计函数：定义估计函数：f=g+hf=g+h；满足满足h（n）h*（n）。）。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 48作业作业:利用宽度优先法或深度优先法，程序利用宽度优先法或深度优先法，程序实现实现 High-way map High-way m
38、ap 问题求解，只考问题求解，只考虑节点的连接和变换虑节点的连接和变换,不考虑边的权不考虑边的权值值;求出有向图的一条解径求出有向图的一条解径,给出求解给出求解过程（过程（OpenOpen，ClosedClosed内容）。内容）。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 49作业作业:设设 h=0;f=g=h=0;f=g=边的标记值，边的标记值，程序求解程序求解 High-way map High-way map 问题，求出最短解径，问题，求出最短解径，给出求解过程（给出求解过程（OpenOpen，ClosedClosed内容）。内容）。
39、北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 50n给定两个油桶给定两个油桶,一个可装一个可装 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)
40、(2,y)要求定义合法的装油规则，利用盲目搜索策略画出要求定义合法的装油规则，利用盲目搜索策略画出状态图。状态图。作业作业:北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 51演讲完毕，谢谢观看！北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 52About Teaching Plan基本要求：人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支，是目前迅速发展的一门新兴学科，新思想新方法层出不穷。其基本思想是利用机器来模仿和执行人脑的功能，如判断、推理、证明、识别、感知、理解、设计、思
41、考、规划、学习和问题求解等思维活动。对于培养学生计算机技术的应用能力，开阔思路和视野，有重要意义。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 53About Teaching Plan因此，要求学生掌握知识表示知识表示和问题求解问题求解的几种常用方法，尤其是不确定性推理不确定性推理；掌握机器学习机器学习基本概念，了解几种机器学习方法机器学习方法尤其是神经网络学习方法；神经网络学习方法；掌握专家系统的概念，了解专家系统设计方法专家系统设计方法，掌握一些智能控制方法智能控制方法，了解国内外人工智能研究尤其是机器人的最新进展；最新进展；具有一定的
42、人工智能编程设计能力人工智能编程设计能力（利用Lisp或Prolog语言）。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 54About Teaching Plan课程内容以及学时分配课程内容以及学时分配人工智能引论(1)人工智能概念及与计算机的关系，研究途径、内容和应用领域概况介绍，其他最新材料其他最新材料。符号主义、连接主义、行为主义三大流派人工智能数学基础(1)知识表示方法（2）状态空间法、问题归约法，谓词逻辑法、产生式表示法（动物识别系统）；CLIPS语言；语义网络法、框架法（这是结构化表示）；剧本、过程、Petri网、面向对象的表示
43、。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 55About Teaching Plan搜索技术和策略（3-4）状态空间法，盲目搜索和启发式搜索，A*算法；海伯伦理论、消解原理和策略；与或形推理和搜索策略；其他求解技术。不确定推理技术（3-4）主观Bayes理论；可信度方法和证据理论；系统组织技术；非单调推理；Rete快速算法；模糊推理技术；基于语义网络和框架不确定推理；专家系统（2）专家系统概念、结构和知识获取；黑板模型、知识组织、管理及系统建造和开发工具；专家系统举例及编程。人工智能程序设计人工智能程序设计（1）人工智能语言基本机制：L
44、ISP和PROLOG。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 56About Teaching Plan模式识别导论（3）模式识别专题：概率模式识别。模式识别专题：结构模式识别机器学习（1）：机械,解释经验,事例,归纳,概念,类比学习等；统计,结构,模糊模式识别。专题讲座（3次）1)神经网络基本理论和应用(史奎凡课程：安排于人工智能理论与应用课程内)；2)智能体（Agent）；3)自然语言处理；4)智能控制和机器人科学智能控制的结构理论和研究领域，智能控制系统及应用示例；机器人规划、机器视觉和自然语言理解等。北京航空航天大学软件开发环境
45、国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 57About Teaching Plan实践：1)搜索技术和策略2)不确定推理技术3)专家系统：动物识别系统4)模式识别技术5)调研：搜索技术和策略、不确定推理技术、统计模式识别、机器学习等四个领域进展报告。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 58Chapter One:Brief Introduction to Artificial Intelligence1.What is AI?人工智能（人工智能（Artificial Intelligence,AI）是当
46、前科学技发展的一门前是当前科学技发展的一门前沿学科，同时也是一门新思想，新观念，新理论，新技术不断出沿学科，同时也是一门新思想，新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。现的新兴学科以及正在发展的学科。它是在它是在计算机科学，控制论，信息论，神经心理学，哲学，语言学计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基础发展起来的，因此又可把它看作是一门等多种学科研究的基础发展起来的，因此又可把它看作是一门综综合性的边缘学科合性的边缘学科。它的出现及所取得的成就引起了人们的高度重视它的出现及所取得的成就引起了人们的高度重视,并取得了很高的评并取得了很高的评价。
47、有的人把它与空间技术，原子能技术一起并誉为价。有的人把它与空间技术，原子能技术一起并誉为20世纪的三世纪的三大科学技术成就。大科学技术成就。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 59Intelligence智能是知识与智力的总合。智能是知识与智力的总合。知识知识智能行为的基础；智能行为的基础；智力智力获取知识并运用知识求解问题的能力。获取知识并运用知识求解问题的能力。智能具有以下特征：智能具有以下特征：(1)具有感知能力具有感知能力指人们通过视觉、听觉、触觉、味觉、嗅觉等感指人们通过视觉、听觉、触觉、味觉、嗅觉等感觉器官感知外部世界的
48、能力；觉器官感知外部世界的能力；(2)具有记忆与思维的能力具有记忆与思维的能力这是人脑最重要的功能，亦是人之所以有这是人脑最重要的功能，亦是人之所以有智能的根本原因；智能的根本原因；(3)具有学习能力及自适应能力；具有学习能力及自适应能力；(4)具有行为能力。具有行为能力。Artificial Intelligence人工智能人工智能计算机科学的一个分支，是智能计算机系统，即人类智慧计算机科学的一个分支，是智能计算机系统，即人类智慧在机器上的模拟，或者说是人们使机器具有类似于人的智慧（在机器上的模拟，或者说是人们使机器具有类似于人的智慧（对语言对语言能理解、能学习、能推理）。能理解、能学习、能
49、推理）。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 602.Brief History of AI(1)孕育（孕育（1956年前）年前）古希腊的古希腊的Aristotle（亚里士多德）（前亚里士多德）（前384-322），给出了形式逻辑的），给出了形式逻辑的基本规律。基本规律。英国的哲学家、自然科学家英国的哲学家、自然科学家Bacon（培根）（培根）（1561-1626），系统地给），系统地给 出了归纳法。出了归纳法。“知识就是力量知识就是力量”德国数学家、哲学家德国数学家、哲学家Leibnitz（布莱尼茨）（布莱尼茨）（1646-1716
50、）。提出了关于）。提出了关于数理逻辑的思想，把形式逻辑符号化，从而能对人的思维进行运算和数理逻辑的思想，把形式逻辑符号化，从而能对人的思维进行运算和推理。做出了能做四则运算的手摇计算机推理。做出了能做四则运算的手摇计算机英国数学家、逻辑学家英国数学家、逻辑学家Boole（布尔）（布尔）（1815-1864）实现了布莱尼茨）实现了布莱尼茨 的思维符号化和数学化的思想，提出了一种崭新的代数系统的思维符号化和数学化的思想，提出了一种崭新的代数系统布尔布尔代数。代数。北京航空航天大学软件开发环境国家重点实验室北京航空航天大学软件开发环境国家重点实验室 Slide 61美籍奥地利数理逻辑学家美籍奥地利数