人工智能搜索策略ppt课件.ppt

第1-2章 搜索策略,基本概念状态空间的搜索策略 A算法与/或图的搜索策略其它搜索策略搜索的完备性和效率,第1-2章 搜索策略,基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率,基本概念,推理什么是推理：依据一定的规则（策略）从已知的事实推出新事实（结论）的过程称为推理。,基本概念,推理推理方式及其分类 演绎推理、归纳推理、默认推理 确定推理、不确定推理 单调推理、非单调推理 启发式推理、非启发式推理 ,基本概念 - 搜索,什么叫搜索：根据问题的实际情况不断寻找可用的知识，从而构造一条代价较小的推理线路，使问题得到解的过程称为搜索。盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。启发式搜索：在搜索过程中加入了与问题有关的启发性信息，用以指导搜索朝最有利的方向前进，加速求解过程并得到最优解。,基本概念 - 状态空间表示法,状态：描述某一类事物中各不同事物之间的差异而引入的一组变量或多维数组。 Sk=(Sk0,Sk1,Skn)算符(算子) ：引起状态中某些分量发生变化，从而使问题从一个状态改变到另一个状态的操作，以F指示。状态空间：以SP指示，表示问题的全部可能的状态及其相互关系，状态和算符的集合。一般用三元式表示： SP = ( S0 , F , Sg ),基本概念 - 状态空间表示法,状态空间以SP指示，也可表示为一个二元组： SP = （S, F）S-在问题求解（即搜索）过程中所有可达的合法状态构成的集合；F-操作算子的集合，操作算子的执行导致状态的变迁。 所以，状态空间又可描述为一个有向图，其节点指示状态，节点间的有向弧表示状态变迁，弧上的标签则指示导致状态变迁的操作算子。状态可通过定义某种数据结构来描述，用于记载问题求解（即搜索）过程中某一时刻问题现状的快照。,状态空间表示法举例：八数码游戏,问题：一个33棋盘，有八张牌1，2， 8及一个空格，空格周围的牌可以向空格移动。求解：给定一个初始状态S0 、一个目标状态Sg ，求从S0到Sg的走步序列。,S0状态 Sg状态,解： 综合数据库（状态及状态空间描述） 定义：矩阵（Sij）表示任何状态，其中： Sij0,1, 8 1i,j3 Sij 互不相同状态空间：9！=362,880 种状态,状态空间表示法举例：八数码游戏, 规则集（算符F）设：空格移动代替数码移动。至多有四种移动的可能：上、下、左、右。定义： Sij为矩阵第i行j列的数码; 其中：i0,j0表示空格所在的位置，则Si0j0=0 （0代表空格）空格左移规则： if j0-11 then j0j0-1; Si0j00解释：如果当前空格不在第一列，则空格左移一位，新的空格位置赋值为0。同理：右移规则：if j0+13 then j0j0+1; Si0j00 上移规则：if i0-11 then i0i0-1; Si0j00 下移规则：if i0+13 then i0i0+1; Si0j00,状态空间表示法举例：八数码游戏, 控制策略需要解决的问题： 在当前可用的规则中如何选择其中之一来实现状态的转换 实时判断是否到达目标状态,状态空间表示法举例：八数码游戏,随机产生的八数码排列转换成目标共有两种可能，而且这两种不可能同时成立，也就是奇数排列和偶数排列。,状态空间表示法举例：八数码游戏,某初始状态 奇数排列 偶数排列,计算公式 （），其中（）就是一个数的前面比这个数小的数的个数，判断为奇数或偶数,设N个传教士带领N个野人划船渡河，且为安全起见，渡河需遵从二个约束： 1）船上人数不得超过载重限量，设为K个人； 2）为预防野人攻击，任何时刻（包括两岸、船上）野人数目不得超过传教士。,状态空间表示法举例：传教士和野人问题,状态空间表示法举例：传教士和野人问题,为便于理解状态空间表示方法，我们简化该问题到一个特例：N=3，K=2；并以变量m和c分别指示传教士和野人在左岸或船上的实际人数，变量b指示船是否在左岸（值1指示船在左岸，否则为0）。从而上述约束条件转变为m + c = c。 考虑到在这个渡河问题中，左岸的状态描述（m、c和b）可以决定右岸的状态，所以整个问题状态就可以左岸的状态来描述，以简化问题的表示。,设初始状态下传教士、野人和船都在左岸，目标状态下这三者均在右岸，问题状态以三元组（m,c,b）表示，则问题求解任务可描述为： (3，3，1） （0，0，0） 在这个简单问题中，状态空间可能的状态总数为442 = 32 ，但由于要遵守安全约束，只有20个状态是合法的。下面是几个不合法状态的例子： (1，0，1）， （1，2，1）， （2，3，1） 鉴于存在不合法状态，还会导致某些合法状态不可达，例如状态（0，0，1），（0，3，0）。结果，这个问题总共只有16个可达的合法状态。,状态空间表示法举例：传教士和野人问题,渡河问题中的操作算子可以定义2类：L(m,c)、R(m,c)，分别指示从左岸到右岸的划船操作和从右岸回到左岸的划船操作。由于m和c取值的可能组合只有5个：10，20，11，01，02，故而总共有10个操作算子。 渡河问题状态空间的有向图,状态空间表示法举例：传教士和野人问题,状态空间表示法举例：传教士和野人问题,基本概念 - 与/或树表示法,与/或树又称问题归约。问题归约是人们求解问题常用的策略，就是把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。只有当这些子问题全部解决时，问题才算解决，问题的解答就由子问题的解答联合构成。,基本概念 - 与/或树表示法,与/或图：应用问题归约策略得到的状态空间图。与节点：用园弧将几条节点间关联弧连接在一起去指示问题分解为若干子问题，只有这些子问题全部解决才会导致问题的解决。 或节点：问题（子问题）也可能激活多条重写规则（等价变换）；显然，只要有一条激活的重写规则能导致最终的解答成功即可。,基本概念 - 与/或树表示法,本原问题：不可或不需再通过变换，可以直接得到问题的解的子问题。 端节点与终止节点：没有子节点的节点称为端节点（叶节点）。本原问题对应的节点称为终止节点。,基本概念 - 与/或树表示法,可解节点： 终止节点是可解节点。 如果非终止节点有“或”子节点，当且仅当其子节点至少有一个能解，则该非终止节点是可解节点。 如果非终止节点有“与”子节点，当且仅当其子节点都能解，则该非终止节点是可解节点。,基本概念 - 与/或树表示法,不可解节点： 没有后裔的非终止节点是不可解节点（该节点是叶节点但不是本原问题）。 如果非终止节点有“或”子节点，当且仅当所有子节点都不能解，则该非终止节是不可解节点。 如果非终止节点有“与”子节点，至少有一个子节点不能解，则该非终止节点是不可解节点。解树：由可解节点构成，并且由这些可解节点可推出初始节点为可解节点的子树。,基本概念 - 与/或树表示法,与或图是一个超图，节点间通过连接符连接。K-连接符：,解图：,基本概念 - 与/或树表示法,解图的耗散值计算：设K_连接符的耗散值为K，G的耗散值为K(n,N) 若n 是N的一个元素，则K(n,N)=0 若n有一个到解图中后继节点集n1, n2 ni的外向连接符，设该连接符的耗散值为Cn，则 K(n,N) Cn+ K(n1,N)+ K(n2,N)+ + K(ni,N),基本概念 - 与/或树表示法,左图耗散值 K(n0,N) 1+ K(n1,N) 1+1+ K(n3,N) 1+1+2+ K(n5,N)+ K(n6,N) 1+1+2+2+ K(n7,N)+ K(n8,N)+2+ K(n7,N)+ K(n8,N) 1+ 1+ 2+ 2+ 0+ 0+ 2+ 0+ 0 8,右图耗散值 K(n0,N) 2+ K(n4,N) + K(n5,N) 2+ 1+K(n5N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+K(n7,N) +K(n8,N) + 2+K(n7,N) +K(n8,N) 2+ 1+ 2+ 0+ 0+ 2+ 0+ 0 7,与/或树表示法举例：梵塔问题,（1 1 1） （3 3 3）,（1 2 2） （3 2 2）,（3 2 2） （3 3 3）,（1 1 1） （1 2 2）,（1 1 1） （1 1 3）,（3 2 2） （3 2 1）,（3 2 1） （3 3 1）,（3 3 1） （3 3 3）,（1 2 3） （1 2 2）,（1 1 3） （1 2 3）,( c b a ),与/或树表示法举例：符号积分问题,符号积分是求不定积分原函数的问题，通过应用各种代数和三角变换以及不定积分性质（如函数和积分、分部积分等）可以把复杂的积分问题逐步归约为若干个本原积分问题（可利用积分表直接求出原函数）。六十年代开发的SAINT系统。就是一个应用问题归约的符号积分系统。,与/或树表示法举例：符号积分问题,作为一个例子，观察： ( sin3x + x4/(x2 + 1) ) dx=sin3xdx + (x4/(x2 + 1)dx=-(1 - cos2x)dcosx + (x2 - 1 + 1/(1 + x2)dx= (-dcosx + cos2xdcosx) + (x2dx - dx + (1/(1 + x2)dx ) = -cosx + cos3x/3 + x3/3 - x + arctgx 该积分问题首先分解为二个独立的子问题，然后分别变换这二个积分子问题，并分解变换结果为若干本原积分问题，分别求解这些本原问题后再联合成最终解答。,第1-2章 搜索策略,基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率,第1-2章 搜索策略,基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率,状态空间的搜索策略,状态空间的搜索以SE指示，可表示为一个五元组：SE = (S,F,E,S0,Sg)E -搜索引擎；S0 -问题的初始状态， S0 S;Sg -问题的目标状态集， Sg S。状态空间搜索的基本思想就是通过搜索引擎寻找一个操作算子的调用序列，使问题从初始状态变迁到目标状态之一，而变迁过程中的状态序列或相应的操作算子调用序列称为从初始状态到目标状态的 解答路径。搜索引擎可以设计为任意实现搜索算法的控制系统。,状态空间的搜索策略,通常，状态空间的解答路径有多条，但最短的只有1条或少数几条。上述渡河问题就有无数条解答路径（因为划船操作可逆），但只有4条是最短的，都包含11个操作算子的调用。由于一个状态可以有多个可供选择的操作算子，导致了多个待搜索的解答路径。除了少数像渡河这样的简单问题外，描述状态空间的一般图都很大，无法直观地画出，只能将其视为隐含图，在搜索解答路径的过程中只画出搜索时直接涉及到的节点和弧线，构成所谓的 搜索图。,状态空间的搜索策略,八数码问题的搜索图。对于八数码游戏，可能的棋盘布局（问题状态）总共9!=362880个，由于棋盘的对称性，实际只有这个总数的一半。显然，我们无法直观地画出整个状态空间的一般图，但搜索图则小得多，可以图示。状态空间、搜索图和解答路径之间的关系 ,状态空间的搜索策略,尽管状态空间可以很大（例如国际象棋），但只要确保搜索空间足够小，就能在合理的时间范围内搜索到问题解答。搜索空间的压缩程度主要取决于搜索引擎采用的搜索算法。换言之，当问题有解时，使用不同的搜索策略，找到解答路径时，搜索图的大小是有区别的。,一些基本概念,节点深度：根节点深度=0其它节点深度=父节点深度+1,0,1,2,3,一些基本概念（续1）,路径设一节点序列为(n0, n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。,一些基本概念（续1）,扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,状态空间的一般搜索过程,一般图搜索算法为建立该算法，令： s -指示初始状态节点；G -指示搜索图；OPEN -作为存放待扩展节点的表；CLOSED -作为存放已被扩展节点的表；MOVE-FIRST(OPEN) -指示取OPEN表首的节点作为当前要被扩展的节点n，同时将节点n移至CLOSE表；SNS -子节点集合；,状态空间的一般搜索过程,该算法的一般过程如下：1） G := s； / 即算法开始时搜索图只包括初始状态节点； 2 ） OPEN := (s), CLOSED := ()； / 即此时仅有作为待扩展节点，而CLOSE表为空； 3）若OPEN是空表，则算法以失败结束； / 因为此时未搜索到解答（目标状态），又无法继续搜索； 4） n := MOVE-FIRST(OPEN)； 5）若n是目标状态节点，则搜索成功结束，并给出解答路径； 6）扩展节点n，将非节点n祖先的子节点置于子节点集合SNS中，并插入搜索图G中；,状态空间的一般搜索过程,7） 标记和修改指针： 把SNS中的子节点分为三类：（1）全新节点，（2）已出现于OPEN表的节点，（3）已出现于CLOSED表的节点； / 后二类子节点实际上意味着具有新老二个父节点； 加第1类子节点于OPEN表，并建立从子节点到父节点n的指针； 比较第2类子节点经由新、老父节点到达初始状态节点s的路径代价，若经由新父节点的代价较小， 则移动子节点指向老父节点的指针，改为指向新父节点n； 对于第3类子节点作与第2类同样的处理，并把这些子节点从CLOSED表中移出，重新加入OPEN表；8） 按某种原则重新排序OPEN表中的节点；9） 返回语句3）；,Back算法A,状态空间的一般搜索过程,状态空间的一般搜索过程,讨论：1 OPEN中的节点是尚未扩充的节点2 CLOSED的节点是已经扩充过的节点 3 G中的每个节点都唯一地指向一个父节点4 mi mj mk ml其中： mi是当前被扩充的全部节点 mj是新扩充的节点 mk是已经在OPEN中的节点 ml是已经在CLOSED中的节点5 n是当前被选中的节点，它是OPEN表中排列在最前面的一个节点。6 该算法对于连通图及树都适用。,例：,n=1,S,2,3,4,5,6,当前节点,ml节点,讨论： 空心节点是已经在OPEN中的节点，如：1，4，5 实心节点是已经在CLOSED中的节点，如：S，2，3 扩充节点2后，对其原来搜索路径进行修改，由原来指向节点3改为指向节点1 对后继节点4的搜索路径进行修改，由原来指向节点6改为指向节点2,表示图本身的连接关系,搜索路径,修改后的搜索图如下：,n=1,S,2,3,4,5,6,下面给出两种对OPEN表中节点按照某种规则排列的算法： 深度优先算法 宽度优先算法,状态空间的一般搜索过程,一般图搜索算法中，提高搜索效率的关键在于优化OPEN表中节点的排序方式，若每次排在表首的节点都在最终搜索到的解答路径上，则算法不会扩展任何多余的节点就可快速结束搜索。所以排序方式成为研究搜索算法的焦点，并由此形成了多种搜索策略。一种简单的排序策略就是按预先确定的顺序或随机地排序新加入到OPEN表中的节点，常用的方式是深度优先和宽度优先。,状态空间的一般搜索过程,广（宽）度优先搜索,宽度优先-扩展当前节点后生成的子节点总是置于OPEN表的后端（未部），即OPEN表作为排队表使用，先进先出，使搜索优先向横广方向发展。,先进先出排序策略使宽度优先法能确保搜索到最短的解答路径。,2 31 8 47 6 5,1,2,5,6,7,3,目标,8,4,宽度优先搜索的性质,当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法,深度优先搜索,深度优先-扩展当前节点后生成的子节点总是置于OPEN表的前端（首部），即OPEN表作为栈表使用，后进先出，使搜索优先向纵深方向发展。,当一个问题有多个解答或多条解答路径，且只须找到其中一个时，深度优先法十分适用。例如8数码游戏，若不限定从初始布局转变到目标布局所需移动的棋牌个数（即移动步数），则存在多条解答路径，应用深度优先法可随机地找到其中一条。,深度优先搜索,不过有些问题的状态空间搜索或许会无限延伸，而又存在较短的解答路径，则可以对搜索深度加以限制，以求提高搜索效率并确保寻找到较短的解答路径。,有界深度优先如果当前节点的深度不超过限定的界限，则扩展当前节点后生成的子节点总是置于OPEN表的前端（首部） ，后进先出，使搜索优先向纵深方向发展。,2 31 8 47 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,深度优先搜索的性质,一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法,状态空间搜索,上述二种搜索方法可直接应用一般图搜索算法实现，且只要问题有解就一定能搜索到解答。由于不需要设计特别的节点排序方法，从而简单易行，适合于许多复杂度不高的问题求解任务。 这两种搜索方法的共同缺点是节点排序的盲目性，由于不采用领域专门知识去指导排序，往往会在白白搜索了大量无关的状态节点后才碰到解答，所以也称为盲目搜索。,状态空间搜索,只要引入与应用领域相关的启发式知识来指导OPEN表中节点的排序，使最有希望出现在较短解答路径上的节点优先考察，就能显著提高搜索的有效性。用启发式知识指导排序可划分为二种方式: 局部排序-这是对上述深度优先法的改进，仅对新扩展出来的子节点排序，使这些节点中最有希望者能优先取出考察和扩展。如：代价树深度优先。 全局排序-对OPEN表中的所有节点排序，使最有希望的节点排在表首。如：代价树广度优先。,代价树的广度优先搜索,代价树广度优先-对OPEN表中的所有节点按代价大小排序，使最有希望的节点排在表首，又称为分枝界限法。是一种全局排序方法。,代价树：边上标有代价（费用）的树。代价：若用g(x)表示从初始节点S0到节点x的代价，用c(x1,x2)表示从父节点x1到子节点x2的代价，则有： g(x2) = g(x1) + c(x1,x2)最有希望的节点：代价最小的节点。,代价树的广度优先搜索,例：巡回推销员问题，从A出发并返回。,A,B,C,D,E,75,100,125,125,75,50,100,50,125,100,A-E-D-B-C-A : 375,代价树的深度优先搜索,代价树深度优先-这是对上述深度优先法的改进，仅对新扩展出来的子节点按代价大小排序，使这些节点中最有希望者能优先取出考察和扩展。是一种局部排序方法。,启发式搜索,搜索是一种试探性的查寻过程，引入启发式知识可以减少搜索的盲目性，增加试探的准确性，为此就称应用启发式知识的搜索是启发式搜索。 启发式知识对于搜索的指导作用可归纳为三方面： 选择下一个要被扩展的节点，排序OPEN表中的待扩展节点是一种常用的方法。在扩展一个节点时，仅仅有选择性地生成部分有用的节点，而非所有可能的子节点。修剪掉某些估计不可能导致成功的子节点。 本节只讨论如何应用第一方面的启发式知识于一般图搜索。,启发式搜索,启发式信息用于解决OPEN表中节点的排列次序问题，方法是利用一个评(估)价函数计算OPEN表中节点的评价函数值，按照函数值从大到小（或从小到大）排列所有节点。 一种有效的方法就是设计体现启发式知识的所谓评价函数来计算每个节点的得分，以便用于排列它们在OPEN表中的位置。 应用这种评价函数来实现启发式搜索的典型是算法A，其将评价函数f设计为：,启发式搜索 -算法A,算法A，其将评价函数f设计为： f(n) = g(n) + h(n) n-搜索图中的某个当前被扩展的节点； f(n)-从初始状态节点s0, 经由节点n到达目标状节点sg，估计的最小路径代价； g(n)-从s0到x ,估计的最小路径代价； h(n)-从n到sg,估计的最小路径代价； 通常我们可以用至今已发现的自s0到n的最短路径作为g(n)值，但h(n)则要依赖于启发式知识来加以估算，故h(n)称为启发式函数。,s0,启发式搜索 -算法A,启发式函数举例：移动将牌游戏其中，B-黑色 W-白色 规则：每跨过1张牌费用为1，最多可跨多2张牌。要求把所有的B都移到所有W的右边。,启发式搜索 -算法A,算法A的设计与前述一般图算法类同，主要的不同是在算法第（6）步中增加了子节点函数f的计算，在第（7）步中依赖于f值确定子节点指向父节点指针的修改，并在第（8）步中按f值从小到大排序OPEN表中的节点。算法A第（6）和第（7）步的修改如下：,启发式搜索 -算法A,(6) 扩展节点n,将非节点n祖先的子节点置于子节点集合SNS中， 并插入搜索图G中，对于SNS中每个子节点ni,计算f(n,ni) = g(n,ni) + h(ni);(7) 标记和修改指针把SNS中的子节点分为三类（同一般图搜索算法）；加第1类子节点于OPEN表（同一般图搜索算法）；比较第2类子节点ni经由新、老父节点的评价函数值f(n,ni)、f(ni);若f(n,ni) f(ni)点,则令f(ni) = f(n,ni),并移动子节点指向老父节点的指针，改为指向新父节点。对第3类子节点作与第2类同样的处理，并把这些子节点从CLOSED表中移出，重新加入OPEN表。,算法A,1, OPEN:=(s), f(s):=g(s)+h(s);2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) mi, 计算f(n, mi):=g(n, mi)+h(mi);,算法A（续）,ADD(mj, OPEN), 标记mj到n的指针；IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 标记mk到n的指针；IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml),标记ml到n的指针, ADD(ml, OPEN);7, OPEN中的节点按f值从小到大排序；8, GO LOOP；,.,.,.,.,.,mj,mk,ml,n,a,b,结点类型, ,启发式搜索 -算法A,以八数码游戏为例，观察算法A的应用。令 f(n) = d(n) + w(n) d(n)是当前被考察和扩展的节点n在搜索图中的节点深度，作为对g(n)的量度； 启发式函数h(n)则设计为w(n),其值是节点n与目标状态节点ng相比较，错位的棋牌个数。 当前要解决的八数码问题，初始状态节点的评价函数值f(n) = 0 + 4 = 4, 则应用算法A搜索解答路径十分快捷，除了个别走步判断失误外（节点d的选用和扩展）其它的走步选择全部正确。给出的搜索图以字母标识每个节点，字母后的括号中给出评价函数f的值；OPEN和CLOSED表中的节点变化如表所示。,2 8 31 6 47 5,s(4),A(6),B(4),C(6),D(5),E(5),F(6),G(6),H(7),I(5),J(7),K(5),L(5),M(7),目标,1,2,3,4,5,6,启发式搜索 -算法A,OPEN CLOSE0 sbac sdeaci sbeacikj sbdlacikjm sbdenacikjm sbdelqacikjmo sbdeln成功结束,启发式搜索 - A*算法(最佳图搜索算法),定义几个函数 g*(n)=k(s,n)：从初始节点s到节点n的最小代价路径的实际代价值。 h*(n)=min k(n,ti)：从节点n到目标节点集 ti 中所有节点最小代价路径的实际代价值中的最小值。 f*(n)= g*(n) + h*(n) ：从初始节点s约束通过节点n的最小代价路径的代价值。,启发式搜索 - A*算法(最佳图搜索算法), 评价函数：f(n)= g(n) + h(n) 其中： f, g, h分别是f*, g*, h*的估计值。通常约定： f(n) 按照升序排列。 将评价函数f与f *相比较，实际上，f(n)、g(n)和h(n)分别是f*(n)、g*(n)和h*(n)的近似值。 在理想的情况下，设计评价函数f时可以让 g(n) = g*(n), h(n) = h*(n),则应用该评价函数的算法A就能在搜索过程中,每次都正确地选择下一个从OPEN表中取出加以扩展的节点，从而不会扩展任何无关的节点，就可顺利地获取解答路径。,启发式搜索 - A*算法(最佳图搜索算法),然而g*(n)和h*(n)在最短解答路径找到前是未知的，故而几乎不可能设计出这种理想的评价函数；而且对于复杂的应用领域，即便是要设计接近于f*的f往往也是困难的。 一般来讲，g(n)的值容易从迄今已生成的搜索树中计算出来，不必专门定义计算公式。 例如就以节点深度d(n)作为g(n),并有g(n)g*(n)。 然而h(n)的设计依赖于启发式知识的应用，所以如何挖掘贴切的启发式知识是设计评价函数乃至算法A的关键。 前述八数码游戏例使用的启发式函数w(n)就不够贴切，从而在搜索过程中错误地选用了节点d加以扩展（见图） 。,启发式搜索 - A*算法(最佳图搜索算法),其实我们可以设计更接近于h*(n)的h(n)，如p(n),其值是节点n与目标状态节点相比较，每个错位棋牌在假设不受阻拦的情况下，移动到目标状态相应位置所需走步（移动次数）的总和。显然p(n)比w(n)更接近于h*(n)，因为p(n)不仅考虑了错位因素，还考虑了错位的距离（移动次数）。,启发式搜索 - A*算法(最佳图搜索算法),OPEN CLOSE0 sbac seacdi sblacdim sbenacdim sbdeqacdimo sbdel成功结束,启发式搜索 - A*算法(最佳图搜索算法),评价函数：f(n)= g(n) + h(n) 其中： f, g, h分别是f*, g*, h*的估计值。 综述： (1) g(n)比较容易得到，由上述定义，得： g(n) g*(n) (2) 关键设计启发函数h(n)。 (3)当h0 且g(n)=d(n)时， f(n)= d(n) 即 宽度优先策略， d(n)：节点深度,启发式搜索 - A*算法,A*算法(最佳图搜索算法) 定义： 对于算法A，如果有h(n) h*(n) ，即h(n) 在h*(n) 的下界范围内，则该算法称为A*算法。 性质,启发式搜索 - A*算法性质,1.算法可采纳性： （证明略） 给定任意图，设存在从初始节点s到目标节点t的路径。如果算法能够结束在从s到t的最佳解路径上，则称该算法是可采纳的。定理1.1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。为了证明无限图问题，有2个引理：,启发式搜索 - A*算法性质,1.算法可采纳性： （证明略）引理1.1 ：对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)f*(s)。引理1.2：A*结束前，OPEN表中必存在f(n)f*(s)。,启发式搜索 - A*算法性质,1.算法可采纳性： （证明略）定理1.2：对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。推论1.1：OPEN表上任一具有f(n)f*(s)的节点n，最终都将被A*选作扩展的节点。,启发式搜索 - A*算法性质,1.算法可采纳性（定理1-3）： A*算法是可纳的，即给定任意图，设存在从初始节点s到目标节点t的路径，则它能在有限步内终止并找到最优解。（证明略）推论1.2：A*选作扩展的任一节点n，有f(n)f*(s)。,启发式搜索 - A*算法性质,对于八数码游戏，从当前被扩展节点n到目标状态节点的最短路径-棋牌移动的最少次数必定不少于错位棋牌的个数w(n) （因为有些棋牌可能需移动多于一次才能到达目标状态的相应位置）， 即w(n) h*(n) 也必定不会少于错位棋牌不受阻挡情况下移动到目标状态相应位置的移动次数总和p(n) （因为有些棋牌的移动可能受阻挡），即p(n) h*(n) 从而采用w(n)和p(n)作为评价函数时，算法A都是可纳的。,启发式搜索 - A*算法性质,思考1: 传教士和野人问题(m,c,b) 1) h(n)=0； 2) h(n)=m+c 3) h(n)=m+c-2b哪个是A*算法？思考2: 只有A*算法才能找到最优解？ 对于八数码游戏，令h(n)= p(n) + 3 s(n) ,其中s(n)为所有棋子得分总和，计算方法：中心方格棋子得1分，非中心方格棋子后继棋子与目标顺序不同得2分，否则0分。,例:一个简化的罗马尼亚道路图,启发式搜索 - A*算法性质,2.算法最优性（启发式函数的强弱及其影响 ） 用h(n)接近h* (n)的程度去衡量启发式函数的强弱。当h(n) h* (n)且两者差距较大时，h(n)过弱，从而导致OPEN表中节点排序的误差较大，易于产生较大的搜索图；反之，当h(n) h* (n),则h(n)过强，使算法A失去可采纳性，从而不能确保找到最短解答路径。 设计接近、又总是 h* (n)的h(n)成为应用A*算法搜索问题解答的关键，以压缩搜索图，提高搜索效率。,启发式搜索 - A*算法性质,算法最优性： （启发式函数的强弱及其影响 ）定理1-4： 给定两个A*算法A1、A2，如果A2的启发信息比A1多，则在任何存在从节点s到目标节点t 路径的图上，搜索结束时由A2扩充的每一个节点必定被A1扩充。（ A1扩充的节点数至少与A2 扩充的节点数一样多)。 （证明略）,启发式搜索 - A*算法性质,算法最优性： （启发式函数的强弱及其影响 ） 可以证明，对于解决同一问题的两个算法A1和A2，若有h1(n) h2(n) h* (n)，则t(A1) t(A2) 其中，h1、h2分别是算法A1、A2 的启发式函数，t指示相应算法达到目标状态时搜索图含的节点总数。,启发式搜索 - A*算法性质,算法最优性： （启发式函数的强弱及其影响 ）再以八数码游戏为例，正因为w(n) p(n) h* (n),所以采用p(n)扩展出的节点总数不会比采用w(n)时多。更明显的例子是采用宽度优先法解决八数码问题，其相当于h(n)0，则搜索树会变得比采用w(n)时庞大得多。,启发式搜索 - A*算法性质,算法最优性： （启发式函数的强弱及其影响 ） 三种算法的搜索代价,其中IDS为深度搜索,h1采用的启发式函数为w(n), h2采用的启发式函数为p(n),d为解的长度.随机产生1200个八数码问题统计: d=12 IDS = 3,644,035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes,启发式搜索 - A*算法性质,3.h(x)的单调性限制：单调性定义：给定一个启发函数h，如果对于所有节点ni 、 nj （ nj是ni的子节点）满足 h(ni) h(nj) c(ni, nj) 且 h(t) 0 ，则称h 满足单调性限制。上式可以写成 h(ni) c(ni, nj) h(nj) 可以理解为三角形边长和不等式。,单调性限制的作用是：避免重复计算某些节点的f值（主要针对连通图而言）以便减少搜索代价。,启发式搜索 - A*算法性质,h(x)的单调性限制：结论1（定理1-5） 如果h(n)满足单调性限制条件，则A*算法扩充了节点n之后，就已经找到了到达节点n的最佳路径，即：如果A*选中节点n，在单调性限制条件下，有 g(n) g*(n) 结论2（定理1-6） 如果h 满足单调性限制，则由A*扩充的节点序列的f 值是非递减的。,启发式搜索 - A*算法的改进,问题的提出： 因A算法第6步对ml类（第3类）节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。,一个例子：,s(10),s(10),A(7) B(8) C(9),A(7) s(10),B(8) C(9) G(14),A(5) C(9) G(14),C(9) G(12),B(7) G(12),A(4) G(12),G(11),B(8) s(10),A(5) B(8) s(10),C(9) A(5) s(10),B(7) C(9) s(10),A(4) B(7) C(9) s(10),出现多次扩展节点的原因,在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。,解决的途径,对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。要求满足单调性限制对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。,改进的条件,可采纳性不变不多扩展节点不增加算法的复杂性,对算法加以改进,一些结论：推论1.1 ： OPEN表上任以具有f(n) f*(s)的节点定会被扩展。推论1.2： A*选作扩展的任一节点，定有f(n)f*(s)。,基本思想：按照节点的f值从小到大排序 OPEN表中的节点，以 f*(s)为界将OPEN表的节点划分为两个部分。f f*(s)的节点，称为NEST。,改进的出发点,OPEN = ( ),f*(s),f值小于f*(s)的节点,f值大于等于f*(s)的节点,fm：到目前为止已扩展节点的最大f值，用fm代替f*(s),修正过程A,1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0;2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, NEST:=ni|f(ni)fmIF NEST ( ) THEN n:=NEST中g最小的节点 ELSE n:=FIRST(OPEN), fm:=f(n);4, , 8: 同过程A。,前面的例子：,OPEN表,CLOSED表,fm,s(0+10),s(0+10),10,A(6+1) B(3+5) C(1+8),s(0+10) C(1+8),10,A(6+1) B(2+5),s(0+10) C(1+8) B(2+5),10,A(3+1),s(0+10)C(1+8)B(2+5)A(3+1),10,G(11+0),h的单调化方法,如果令：f(n) = max f(n的父节点), g(n)+h(n) 则容易证明，这样处理后的h是单调的。,第1-2章 搜索策略,基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率,第1-2章 搜索策略,基本概念状态空间的搜索策略与/或树的搜索策略搜索的完备性和效率,可以把 与/或图（树）视为对一般图的扩展；或反之，把一般图视为与/或图的特例，即一般图不允许节点间具有“与”关系，所以又可把一般图称为或图。与一般图类似，与/或图也有根节点，用于指示初始状态。由于同父子节点间可以存在“与”关系，父、子节点间不能简单地以弧线关联，需要引入超连接概念。同样原因，在典型的与/或图中，解答路径往往不复存在，代之以广义的解路径-解图。,与/或树的一般搜索过程,与/或树的一般搜索过程,与/或树的一般搜索过程,解图的生成-自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如此反复进行，直到所有外向连接都指向终节点为止。解图是遵从问题归约策略而搜索到的，解图中不存在节点或节点组之间的“或”关系；换言之，解图纯粹是一种“与”图。另外，正因为与或图中存在“或”关系，所以往往会搜索到多个解图，本例中就有4个。,与/或树的一般搜索过程,初始节点S0对应原始问题的描述。用可适用的分解或等价变换算符求得S0的后继节点集合。从每个后裔设置指向父辈节点的指针（用于标示可解或不可解，并指出一个到终叶节点的解图），删去没有意义的节点。继续扩展节点和设置指针的过程，直至S0被标示为可解或不可解为止。,与/或树的一般搜索过程,基本思想：把新生成的子节点放入OPEN表的尾部。算法：1）把初始节点S0放入OPEN表。2）把OPEN表中首节点（记为n）取出放入CLOSE表。3）如果节点n可扩