搜索
北京航空航天大学软件开发环境国家重点实验室Slide1人工智能(问题求解基本原理及搜索技术)北京航空航天大学软件开发环境国家重点实验室Slide2问题求解基本原理问题求解：在给定条件下，寻求一个能解决某类问题且能在有限步骤内完成的算法。问题求解特征：传统软件：①求解的问题是能够用数学精确描述的良结构的问题（如，解方程）；②计算机执行的繁杂的统计计算任务一般不能看成是人工智能活动。AI软件：①求解的是不可直接用数学模型描述的所谓不良结构问题（如，几何证明、求不定积分、逻辑演算等），通常需要采用弱方法进行搜索求解；②AI程序中符号的内涵不仅局限于数值计算和数据处理中的一般数据信息，应表现人类进行推理所需要的各种知识。北京航空航天大学软件开发环境国家重点实验室Slide3问题求解基本原理一、问题求解的基本方法二、搜索技术北京航空航天大学软件开发环境国家重点实验室Slide4问题求解基本原理问题求解方法：基于状态空间的问题求解方法基于问题空间的问题求解方法基于博弈搜索的问题求解方法北京航空航天大学软件开发环境国家重点实验室Slide5问题实例桌上固定了3根柱子，按1，2，3次序排例。有n个大小全不一样大的盘子d1，…，dn，按从小到大，小的在上的次序依次插在第一根柱子上，要把这n个盘子全部搬到第三根柱子上，每次只许搬一个，任何时候都不允许把大盘子放在小盘子上面，问该如何搬法。设n=3，该如何搬法？123123梵塔问题北京航空航天大学软件开发环境国家重点实验室Slide6基于状态空间的问题求解方法（1，1，1）→（1，1，2）（1，1，1）→（1，1，3）（1，1，2）→（1，3，2）。。。。。状态合法变换规则（满足约束条件）：状态定义-（i大,j中,k小）:设向量下标分别表示大盘、中盘、小盘；向量值分别表示盘子所在柱子的编号。状态描述-大盘在第i根柱子上；中号盘在第j根柱子上，小号盘在第k根柱子上。北京航空航天大学软件开发环境国家重点实验室Slide7基于问题空间的问题求解方法问题：如何将i柱子上的m个盘子搬到k柱子上?将i柱子上的m–1个盘子搬到j柱子上；将i柱子上的第m个盘子搬到k柱子上；将j柱子上的m–1个盘子搬到k柱子上。问题描述：问题（a,b,c):将b柱子上的a个盘子搬到c柱子上。问题分解合法规则：（3，1，3）--〉（2，1，2）(1，1，3）（2，2，3）。。。。。。北京航空航天大学软件开发环境国家重点实验室Slide8基于问题空间的问题求解方法北京航空航天大学软件开发环境国家重点实验室Slide9状态空间法有关概念状态空间法:从问题的初始状态出发，通过一系列的状态变换找到目标状态的问题求解方法。状态：描述问题中事物形状或状况的符号或数据结构。状态空间：所有状态的全体构成的集合；用四元组（S,S0,O,G)表示:S:非空状态子集，S0=初始状态（非空）。G:非空目标状态子集。O:操作算子集合，一个状态合法转换为另一个状态的描述规则问题求解过程：隐含求一个普通有向图，节点-状态，边–算子搜索空间：问题求解过程中到达过的所有状态（节点）的集合。北京航空航天大学软件开发环境国家重点实验室Slide10状态空间法有关概念状态空间、搜索空间及解径的关系：问题的解（解径）：初始状态到目标状态通路上的每一条规则（或状态）构成序列，称为解径。解不唯一。S0R1S2R2Sk…..RkG问题有解：从代表初始状态s节点出发，存在一条通向目标节点的路径。北京航空航天大学软件开发环境国家重点实验室Slide11问题空间法有关概念问题空间法：首先产生待证问题的所有子问题，而后通过解决所有子问题达到问题求解目的的方法。问题：描述问题及其子问题的符号或数据结构。问题空间：初始问题以及其所有子问题的全体构成的集合，用四元组（S,S0,F,G)表示:S:问题和子问题；S0:初始问题。G:具有平凡解的本原问题集合。F:操作算子集合，用于将问题分解成其若干个子问题的描述规则北京航空航天大学软件开发环境国家重点实验室Slide12问题空间法的有关概念（2）问题空间分解过程：隐含求一个与或图节点–问题，边-分解问题的算子。“与”节点：如果节点A有边通向一组节点{B1，B2，…..Bn}，问题A的解决有待于A的子问题组{B1,B2…..Bn}的全部解决，则称A为“与”节点。如图a所示。“或”节点：若节点Ａ有边通向一组节点{{Ｂ１},{Ｂ2}，…{Ｂn}}，问题Ａ的解决有待于子问题Ｂ１或Ｂ2或…或Ｂn中某一个子问题的解决，则称A为“或”节点。如图b所示。…...a:AB1B2Bn…...b:AB1B2Bn北京航空航天大学软件开发环境国家重点实验室Slide13问题空间法有关概念（2）问题的解（解图）：从代表初始问题的节点出发，搜索到一个完整的‘与或’子图，图中所有叶节点均满足问题求解的结束条件。例：（C,B,Z)-〉（M,…M)重写规则:R1:C(D,L)R2:C(B,M)R3:B(M,M)R4:Z(B,B,M)解图北京航空航天大学软件开发环境国家重点实验室Slide14小结–问题求解方法比较状态空间法问题空间法问题求解状态变换问题分解搜索过程隐含构建普通有向图隐含构建与或图节点状态问题边状态变换规则（算子）问题分解规则（算子）求解解径解图北京航空航天大学软件开发环境国家重点实验室Slide15问题求解基本原理一、问题求解的基本方法二、搜索技术（一）北京航空航天大学软件开发环境国家重点实验室Slide16搜索技术预备状态空间搜索有关概念盲目搜索策略启发式搜索策略问题求解基本原理北京航空航天大学软件开发环境国家重点实验室Slide17搜索策略预备盲目搜索：•不考虑给定问题所具有的特定知识，系统按照事先确定好的某种固定顺序调用规则，或是随机地调用规则。•常用的盲目搜索算法:深度优先搜索策略；宽度优先搜索策略北京航空航天大学软件开发环境国家重点实验室Slide18搜索策略预备启发式信息：•与问题求解有关的信息和知识。•由于信息的片面性和不准确性，应用启发式信息不能百分之百地保证找到问题的解，但能提高问题求解的可能性。启发式信息在问题求解过程中的作用：•有助于加速求解过程；•有助于找到“较优”解。启发式搜索策略:•考虑给定问题领域具有的特定知识（启发式信息），系统动态地规定规则调用顺序，优先使用“较”合适的规则。北京航空航天大学软件开发环境国家重点实验室Slide19搜索策略预备常用的基于状态图的启发式搜索策略:爬山搜索策略(HillClimbing)大英博物馆搜索策略(BritishMuseum)启发式图搜索策略(A)最佳启发式图搜索策略(A*)常用的基于与或图及博弈的启发式搜索策略：最佳启发式与或图搜索策略(AO*)极大极小搜索策略(Minimax)α－β剪枝搜索策略(Alpha-BetaPruning)北京航空航天大学软件开发环境国家重点实验室Slide20基于状态空间的搜索技术：有关搜索概念盲目搜索策略启发式搜索策略问题求解基本原理北京航空航天大学软件开发环境国家重点实验室Slide21状态空间搜索有关概念状态图特点：多条路径通向同一节点。例：E北京航空航天大学软件开发环境国家重点实验室Slide22状态空间搜索有关概念北京航空航天大学软件开发环境国家重点实验室Slide23状态空间搜索有关概念节点深度：根节点的深度为0，其它节点的深度规定为其父节点的深度加1，即dn+1=dn+1。标记节点n：用指针将后继节点连接到父节点n的操作。节点：对应状态图中有关状态的描述。扩展节点n：称生成节点n的所有后继节点并计算生成这些后继节点所造成的花费的过程（即，计算各后继节点的优劣且将其连接到节点n等操作造成的开销）叫做扩展节点n。后继节点：称将规则作用于节点n生成的新节点为节点n的后继节点。北京航空航天大学软件开发环境国家重点实验室Slide24路径：对于一个节点序列（n0,n1,…,nl,…,nk），如若每一节点ni-1都有一个后继节点ni（i=1,2,…,k），则称该节点序列为一条从节点n0到节点nk、长度为k的路径；路径还可表示为与节点序列对应的规则序列。状态空间搜索有关概念路径花费：设C（ni，nj）为节点ni到nj这段路径（或弧线）的花费。一条路径的花费等于连接这条路径各节点间所有弧线花费值的总和。路径ni→nj→t的花费值C（ni，t）可递归计算如下:C（ni，t）=C(ni，nj)+C（nj，t)。北京航空航天大学软件开发环境国家重点实验室Slide25基于状态空间的盲目搜索算法:宽度优先搜索策略深度优先搜索策略问题求解基本原理北京航空航天大学软件开发环境国家重点实验室Slide26盲目搜索算法的符号及数据结构s：初始节点；n：当前节点。open：已被生成但未被扩展的节点序列表；closed：已被生成且已被扩展的节点序列表；{mi}={mj}∪{mk}∪{ml}：扩展n后所得的n的后继节点其中，{mk}：在OPEN表中出现过的待扩展节点，{ml}：在CLOSED表中出现过的已扩展节点。{mj}：第一次生成的节点，mj∈OPEN且mj∈CLOSED表，北京航空航天大学软件开发环境国家重点实验室Slide27宽度优先搜索算法open:=[S];closed:=[];whileopen≠[]do{n:=first(open);remove(first(open));add(n,closed)；ifn=goalthenexit(success);expand(n)-{mi};delete((mi)(mi∈{mk}∨(mi∈{ml}));add(open,mj)};exit(fail);北京航空航天大学软件开发环境国家重点实验室Slide28宽度优先搜索算法1、S,A,D2、A,D,B,D3、D,B,A,E………Open表为队操作：先进先出！北京航空航天大学软件开发环境国家重点实验室Slide29G节点扩展顺序宽度优先搜索算法北京航空航天大学软件开发环境国家重点实验室Slide30open:=[S];closed:=[];d=深度限制值whileopen≠[]do{n:=first(open);remove(first(open));add(n,closed)；ifn=goalthenexit(success);ifdepth(n)dthencontinue;expand(n)-{mi};delete((mi)(mi∈{mk}∨(mi∈{ml}));add(mj,open)};exit(fail);深度优先搜索算法北京航空航天大学软件开发环境国家重点实验室Slide31深度优先搜索算法1、S2、A,D3、B,D,D………Open表为栈操作：后进先出！4、C,E,D北京航空航天大学软件开发环境国家重点实验室Slide32节点扩展顺序深度优先搜索算法北京航空航天大学软件开发环境国家重点实验室Slide33盲目搜索算法应用实例-8数码问题描述状态：矩阵(Sij)，其中1≤i,j≤3，Sij∈{0,1,…,8};北京航空航天大学软件开发环境国家重点实验室Slide34盲目搜索算法应用实例-合法走步规则：设(i0、j0)为空格所在行列数值，Si0j0=0R1:ifj-1≥1thenSi0j0:=Si0(j0-1),Si0(j0-1):=0空格左移；R2:ifi-1≥1thenSi0j0:=S(i0-1)j0,S(i0-1)j0:=0空格上移；R3:ifj+1≤3thenSi0j0:=Si0(j0+1),Si0(j0+1):=0空格右移；R4:ifi+1≤3thenSi0j0:=S(i0+1)j0,S(i0+1)j0:=0空格下移。8数码问题北京航空航天大学软件开发环境国家重点实验室Slide35宽度优先策略求解8数码问题：目标R1R2R3R2R1R2R3R2R2R3R2R4R1R3北京航空航天大学软件开发环境国家重点实验室Slid