《人工智能课件-搜索技术.ppt》由会员分享，可在线阅读，更多相关《人工智能课件-搜索技术.ppt（113页珍藏版）》请在三一办公上搜索。
1、搜索策略,搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。,主要内容,状态空间的表示搜索的基本概念状态空间的搜索状态空间的一般搜索过程盲目搜索启发式搜索,概述,问题求解AI中每个研究领域都有其各自的特点和规律,但就求解问题的过程看,都可抽象为一个问题求解过程.问题求解过程实际上是一个搜索,广义地说,它包含了全部计算机科学1974年，Nilsson归纳出的AI研究的基本问题知识的模型化和表示常识性推理、演绎和问题解决启发式搜索人工智能系统和语言本章讨论的表示主要包括:状态空间表示问题空间表示,搜索的基本概念,搜索的含义状态空间法,适用情况：
2、不良结构或非结构化问题；难以获得求解所需的全部信息；更没有现成的算法可供求解使用。概念：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索,搜索的类型按是否使用启发式信息：盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。启发式搜索：在搜索中加入了与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。按问题的表示方式：状态空间搜索：用状态空间法来求解问题所进行的搜索 与或树搜索：用问题归约法来求解问题时所进行的搜索,什么是搜索根据问题的实际情况不断寻找可
3、利用的知识,构造出一条代价较少的推理路线,使问题得到圆满解决的过程称为搜索 包括两个方面：-找到从初始事实到问题最终答案的一条推理路径-找到的这条路径在时间和空间上复杂度最小搜索分两大类:盲目搜索:也称为无信息搜索，即只按预定的控制策略进行搜索,在搜索过程中获得的中间信息不用来改进控制策略启发式搜索:在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向进行,加速问题的求解过程并找到最优解,状态空间法,状态(State)：是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：Sk=Sk0,Sk1,当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作(Operat
4、or)也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。,状态空间(State space)用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：(S,F,G)其中，S为问题的所有初始状态的集合；F为操作的集合；G为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。,状态空间表示法,状态空间表示法是用来表示问题及其搜索过程的一种方法状态状态是描述问题求解过程中任一时刻状况的数据
5、结构.,A，B，C，D,（2,3,7,0,5,2,4,8,6）,状态空间表示法,一般一个搜索问题由四个部分组成：初始状态集合：定义了agent所处的环境；操作符集合：把一个问题从一个状态变换为另一个状态的动作；目标检测函数：agent用来确定一个状态是不是目标；路径费用函数：对每条路径赋予一定费用的函数。初始状态集合和操作符集合定义了问题的搜索空间,状态空间法求解问题的基本过程：首先为问题选择适当的“状态”及“操作”的形式化描述方法；然后从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止；此时，由初始状态到目标状态所使用的算符序列就是该问题的一个解。,八数码问
6、题,states 数字的位置，共有9！/2=181440actions 空格的上下左右移动goal test 给定的目标状态path cost 每一步消耗为1,二阶梵塔问题,二阶梵塔问题。设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。,解：设用Sk=(Sk0,Sk1)表示问题的状态，其中，Sk0表示金片A所在的钢针号，Sk1表示金片B所在的钢针号。全部可能的问题状态共有以下9种：S0=(1,1)S1=(1,2)S2=(1,
7、3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3),AB,AB,AB,1 2 3,1 2 3,1 2 3,二阶梵塔问题的初始状态和目标状态,问题的初始状态集合为S=S0 目标状态集合为G=S4,S5,初始状态S0和目标状态S4、S8如图所示,S0=(1,1),S4=(2,2),S8=(3,3),操作分别用A(i,j)和B(i,j)表示 A(i,j)表示把金片A从第i号钢针移到j号钢针上；B(i,j)表示把金片B从第i号钢针一到第j号钢针上。共有12种操作，它们分别是：A(1,2)A(1,3)A(2,1)A(2,3)A(3,1)A(3,2)B(1
8、,2)B(1,3)B(2,1)B(2,3)B(3,1)B(3,2)根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如下图所示。,(3,3)(1,3)(1,2)(2,2)二阶梵塔的状态空间图,从初始节点(1,1)到目标节点(2,2)及(3,3)的任何一条路径都是问题的一个解。其中，最短的路径长度是3，它由3个操作组成。例如，从(1,1)开始，通过使用操作A(1,3)、B(1,2)及A(3,2)，可到达(3,3)。,A(1,2),B(1,3),A(2,3),(1,1),(3,1),(3,2),(2,1),(2,3),A(1,3),B(1,2),A(3,2),例 修道士(Miss
9、ionaries)和野人(Cannibals)问题(简称M-C问题)设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：一是修道士和野人都会划船，但每次船上至多可载两个人；二是在河的任一岸，如果野人数目超过修道士数，修道士会被 野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。,解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态 S=(m,c,b)其中，m表示左岸的修道士人数，c表示左岸的野人
10、数，b表示左岸的船数。右岸的状态可由下式确定：右岸修道士数 m=3-m 右岸野人数 c=3-c 右岸船数 b=1-b 在这种表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有442=32种状态。,这32种状态并非全有意义，除去不合法状态和修道士被野人吃掉的状态，有意义的状态只有16种：S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)
11、S14=(0,1,0)S15=(0,0,0),操作是指用船把修道士或野人从河的左岸运到右岸，或从河的 右岸运到左岸。每个操作都应当满足如下条件：一是船至少有一个人（m或c）操作，离开岸边的m和c的减少 数目应该等于到达岸边的m和c的增加数目；二是每次操作船上人数不得超过2个；三是操作应保证不产生非法状态。,操作的表示：用符号Pij表示从左岸到右岸的运人操作 用符号Qij表示从右岸到左岸的操作其中：i表示船上的修道士人数 j表示船上的野人数操作集 本问题有10种操作可供选择：F=P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20,至此，该问题的状态空间(S,F,G)构
12、造完成，这就完成了对问题的状态空间表示。为了求解该问题，根据该状态空间的16种可能达到的合法状态和10种算符，构造状态转换图。,用状态空间表示,首先必须定义状态的描述形式,把问题的一切状态都表示出来,其次定义算符,完成状态的转换问题的求解过程就是一个把算符不断地作用于状态的过程.如果在使用某个算符后得到的状态就是目标状态,就得到了问题的解.这个解就是从初始状态到目标状态所用算符构成的序列.,算符的一次使用,就使问题由一种状态转变为另一种状态.可能有多个算符序列都可使问题从初始状态变到目标状态,这就得到了多个解.对任何一个状态,可使用的算符可能不止一个,这样由一个状态所生成的后继状态可能有多个.
13、如何选择下一步的操作,由搜索策略决定.,搜索策略,搜索的基本概念状态空间的盲目搜索状态空间的启发式搜索,状态空间的盲目搜索,一般图搜索过程广度优先和深度优先搜索代价树搜索,状态空间搜索的基本思想 先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。,算法的数据结构和符号约定
14、 Open表：用于存放刚生成的节点 Closed表：用于存放已经扩展或将要扩展的节点 S0：用表示问题的初始状态 G：表示搜索过程所得到的搜索图 M：表示当前扩展节点新生成的且不为自己先辈的子节点集。,如何度量问题求解的性能一般搜索策略可以通过下面四个准则来评价：完备性：如果存在一个解答，该策略是否保证能够找到？时间复杂性：需要多长时间可以找到解答？空间复杂性：执行搜索需要多少存储空间？最优性：如果存在不同的几个解答，该策略是否可以发现最高质量的解答？,如何度量问题求解的性能搜索策略反映了状态空间或问题空间扩展的方法，也决定了 状态或问题的访问顺序。在AI领域，状态空间图由初始状态和算子隐含地
15、表示，经常是无限的，它的复杂度根据下面三个值来表达：分支因子b：任何节点的后继的最大个数 最浅的目标节点的深度d 状态空间中任何路径的最大长度m,状态空间搜索过程要点求解一个能够满足目标条件的问题可以表达为搜索一个图以找到一个满足目标状态描述的节点问题。搜索过程的要点如下:起始节点:对应于初始状态描述后继节点:把适用于某个节点状态描述的一些算符用来推算该节点而得到的新节点,称为该节点的后继节点指针:从每个后继节点返回指向其父辈节点检查各后继节点看是否为目标节点.,状态空间搜索过程要点搜索过程扩展后继节点的次序如果搜索是以接近起始节点的程度(由节点之间连结弧线的数目来衡量)依次扩展节点,称为广(
16、宽)度优先搜索如果搜索时首先扩展最新产生的节点,称为深度优先搜索,状态空间搜索过程要点调整指针扩展一个节点生成出该节点的所有后继节点。弧的费用有一条弧连接ni和nj两个节点,用C(ni,nj)表示从ni到nj的费用(耗散值)。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。,状态空间的一般搜索过程主要数据结构OPEN表:存放刚生成的节点,是还未扩展的节点.一般是端节点.CLOSED表:存放将要扩展或已扩展的节点.或者是已被扩展但还没有在搜索树中生成后继节点的端节点,或者是非端节点,一般图搜索过程(1)把初始节点S0放入OP
17、EN表,并建立目前只包含S0的图,记为G(2)检查OPEN表是否为空,若为空则问题无解,退出(3)把OPEN表的第一个节点取出放入CLOSED表,记该节点为n(4)考察n是否为目标节点.如是,则问题得解,退出(5)扩展节点n,生成一组子节点.把其中不是节点n先辈的那些节点记作集合M,并把这些子节点作为节点n的子节点加入G中(6)针对M中子节点的不同情况,分别进行处理对于那些未曾在G中出现过的M成员设置一个指向父节点(即n)的指针,并把它们放入OPEN表对于那些先前已在G中出现过的M成员,确定是否需要修改它指向父节点的指针对于那些先前已在G中出现并且已经扩展了的M成员,确定是否需要修改其后继节点
18、指向父节点的指针(7)按某种搜索策略对OPEN表中的节点进行排序(8)转第(2)步,算法说明(1)上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。各种搜索策略的主要区别在于对Open表中节点的排列顺序不同。例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。,算法说明 对节点n扩展后，生成并记入M的子节点有以下三种情况：该子节点来从未被任何节点生成过，由n第一次生成；该子节点原来被其他节点生成过，但还没有被扩展，这一次又被n再次生成；该子节点原来被其他节点生成过，并且已经被扩展过，这一次又被n再次生成
19、。上三种情况是对一般图搜索算法而言。对于状态空间是树状结构不会出现后两种情况，这是因为每个节点经扩展后生成的子节点都是第一次出现的 节点，不必检查并修改指向父节点的指针。,在第(6)步针对M中子节点的不同情况进行处理时，如果发生当第种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点？一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。如果发生第种情况，除了需要确定该子节点指向父节点的指针外，还需要确定其后继节点指向父节点的指针。其依据也是由原始节点到该节点的路径上的代
20、价。,在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。,在搜索过程的第(4)步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第(6)步所形成的指向父节点的指针来确定。如果搜索过程终止在第(2)步，即没有达到目标，且Open表中已无可供扩展的节点，则失败结束。,例子,2,S,1,3,2,10,11,OPEN表中的节点修改指针,2,S,1,3,2,8,9,10,11,CLOSE表中的节点修改指针,2,S,1,3,2,8,9,10,
21、11,CLOSE表中的节点(8)的后裔(10)修改指针,这是一个通用的搜索过程,后面讨论的状态空间各种搜索策略都是其特例.各种搜索策略的主要区别就是对OPEN表中节点排序准则不同算法结束后，将生成一个图G，称为搜索图。同时由于每个节点都有一个指针指向父节点，这些指针指向的节点构成G的一个支撑树，称为搜索树。从目标节点开始，将指针指向的状态回串起来，即找到一条解路径.,盲目搜索,盲目 搜索策略只使用问题定义中的信息宽度优先搜索代价一致搜索深度优先搜索深度有限搜索迭代加深搜索,广度优先搜索,基本思想 从初始节点S0开始逐层向下扩展，在第n层节点还没有全部搜索完之前，不进入第n+1层节点的搜索。Op
22、en表中的节点总是按进入的先后排序，先进入的节点排在前面，后进入的节点排在后面。,广度优先搜索,搜索算法:把初始节点S0放入Open表中；如果Open表为空，则问题无解，失败退出；把Open表的第一个节点取出放入Closed表，并记该节点为n；考察节点n是否为目标节点。若是，则得到问题的解，成功退出；若节点n不可扩展，则转第(2)步；扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。,例 八数码难题。在33的方格棋盘上，分别放置了表有数字1、2、3、4、5、6、7、8的八张牌，初始状态S0，目标状态Sg，如下图所示。可以使用的操作有 空格左移，
23、空格上移，空格右移，空格下移即只允许把位于空格左、上、右、下方的牌移入空格。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径,31 8 47 6 5,1 2 38 47 6 5,S0 Sg,2 31 8 47 6 5,1,2,5,6,7,3,目标,8,4,广度优先搜索,Complete Yes(如果 b 是有限的)Time 1+b+b2+b3+bd+b(bd-1)=O(bd+1)Space O(bd+1)Optimal Yes(如果每步代价为1)分支因子b：任何节点的后继的最大个数 最浅的目标节点的深度d 状态空间中任何路径的最大长度m空间是大问题(和时间相比)特点缺点当目标节点距离初
24、始节点较远时会产生许多无用的节点,搜索效率低优点只要问题有解,则总可以得到解,而且是最短路径的解,深度优先搜索,基本思想 从初始节点S0开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。,深度优先搜索,算法描述(1)把初始节点S0放入Open表中；(2)如果Open表为空，则问题无解，失败退出；(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；(4)考察节点n是否为目标节点。若是
25、，则得到问题的解，成功退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置 指向父节点的指针，然后转第(2)步。,2 8 31 47 6 5,2 8 3 1 47 6 5,2 31 8 47 6 5,2 8 31 47 6 5,2 8 31 6 47 5,2 8 31 6 4 7 5,2 8 31 6 47 5,2 8 31 6 7 5 4,2 8 31 67 5 4,2 8 1 6 37 5 4,2 81 6 37 5 4,S0 1,2 3 4 5 6,八数码难题的深度优先搜索如右图,一种改进的深度优先算法是有界深度优先搜索算法
26、，深度限制为dm,八数码难题,深度优先搜索,Complete?No:当空间为无限深度时Time?O(bm):如果 m 比d大很多则比较严重Space?O(bm),线性空间Optimal?No 分支因子b：任何节点的后继的最大个数 最浅的目标节点的深度d 状态空间中任何路径的最大长度m特点缺点如果目标节点不在搜索所进入的分支上,而该分支又是一个无穷分支,则就得不到解.因此该算法是不完备的优点如果目标节点不在搜索所进入的分支上,则可以较快地得到解,有界深度优先搜索,定义搜索深度的界限dm,当搜索深度达到了深度界限,而尚未出现目标节点时,就换一个分支进行搜索搜索过程如下:(1)把初始节点S0放入OP
27、EN表,置S0的深度d(S0)=0(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)如果节点n的深度d(节点n)=dm,则转第(2)步(6)若节点n不可扩展,则转第(2)步(7)扩展节点n,将其子节点放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步,2 31 8 47 6 5,2,3,4,5,6,7,8,9,a,b,c,d,目标,迭代加深搜索,对于有界深度搜索策略，有下面几点需要说明：1）在有界深度搜索算法中，深度限制dm是一个很重要的参数。2
28、）深度限制dm不能太大。3）有界深度搜索的主要问题是深度限制值dm的选取。问题：但是对很多问题，我们并不知道该值到底为多少，直到该问题求解完成了，才可以确定出深度限制dm。,迭代加深搜索,改进方法-迭代加深搜索算法：先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限度内没有找到问题的解，则增大深度限制dm，继续搜索。迭代加深搜索是一种回避选择最优深度限制问题的策略，它是试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，等等，一直进行下去。问题：迭代加深搜索看起来会很浪费，因为很多节点都要扩展多次。,迭代加深搜索,迭代加深搜索,
29、迭代加深搜索,迭代加深搜索,迭代加深搜索,深度为d，分支因子为b的深度优先搜索生成的节点数为：NDLS=b0+b1+b2+bd-2+bd-1+bd 深度为d，分支因子为b的迭代加深搜索生成的节点数为NIDS=(d+1)b0+d b1+(d-1)b2+3bd-2+2bd-1+1bd 对于 b=10,d=5,NDLS=1+10+100+1,000+10,000+100,000=111,111NIDS=6+50+400+3,000+20,000+100,000=123,456增加=(123,456-111,111)/111,111=11%,迭代加深搜索,Complete?YesTime?(d+1)b
30、0+d b1+(d-1)b2+bd=O(bd)Space?O(bd)Optimal?Yes,如果每步代价为1 分支因子b：任何节点的后继的最大个数 最浅的目标节点的深度d 状态空间中任何路径的最大长度m,其他问题,避免重复状态：由于扩展已经遇到并扩展过的状态可能造成时间的浪费利用CLOSED表，如果当前节点与其中的某个节点相匹配的话，那么它可以被放弃而不去扩展，或者需要比较耗散值如果单步耗散为常数时，代价广度优先搜索找到的总是最优路径使用不完全信息的搜索：无传感问题：Agent了解它的每个行动的结果，但是没有传感器。从Agent可能到达的状态中搜索，而不是实际状态空间中搜索偶发性问题：环境是部
31、分可观察的，或者行动是不确定的。在每个行动后Agent能从感知器中得到新的信息。其解答往往表现为树的形式，对树的分支的选择取决于树上结点接收到的感知信息,代价树搜索,在代价树中，可以用g(n)表示从初始节点S0到节点n的代价，用c(n1,n2)表示从父节点n1到其子节点n2的代价。这样，对节点n2的代价有：g(n2)=g(n1)+c(n1,n2)。代价树搜索的目的是为了找到最佳解，即找到一条代价最小的解路径。,代价树的广度优先搜索算法：(1)把初始节点S0放入Open表中，置S0的代价g(S0)=0；(2)如果Open表为空，则问题无解，失败退出；(3)把Open表的第一个节点取出放入Clos
32、ed表，并记该节点为n；(4)考察节点n是否为目标。若是，则找到了问题的解，成功退出；(5)若节点n不可扩展，则转第(2)步；(6)扩展节点n，生成其子节点ni(i=1,2,)，将这些子节点放入Open表中，并为每一个子节点设置指向父节点的指针。按如下公式：g(ni)=g(n)+c(ni)i=1,2,.计算各子结点的代价，并根据各子结点的代价对Open表中的全部结点按由小到大的顺序排序。然后转第(2)步。,例 城市交通问题。设有5个城市，它们之间的交通线路如左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的广度优先搜索，求从A市出发到E市，费用最小的交通路线。,2 4 5,A,
33、C1,B1,D1,D2,E1,E2,B2,C2,E3,3 4,3 4 2 3,城市交通图 城市交通图的代价树,解：代价树如右图所示。其中，红线为最优解，其代价为8,主要内容,概述状态空间的搜索状态空间的一般搜索过程盲目搜索启发式搜索约束满足问题博弈,启发式搜索（1）,前面讨论的方法都是盲目的搜索方法,即都没有利用问题本身的特性信息,在决定要被扩展的节点时,都没有考虑该节点在解的路径上的可能性有多大,它是否有利于问题求解以及求出的解是否为最优启发式搜索要用到问题自身的某些特性信息,以指导搜索朝着最有希望的方向前进启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限
34、情况下变为盲目搜索，但可能可以找到最优解,启发式搜索（2）,启发性信息和估价函数用于指导搜索过程,且与具体问题有关的控制性信息称为为启发性信息用于评价节点重要性的函数称为估价函数.记为 f(x)=g(x)+h(x)g(x)为从初始节点S0到节点x已经实际付出的代价h(x)是从节点x到目标节点Sg的最优路径的估价代价,体现了问题的启发性信息,称为启发函数f(x)表示从初始节点经过节点x到达目标节点的最优路径的代价估价值,其作用是用来评估OPEN表中各节点的重要性,决定其次序,启发式搜索（3）,启发式就是要猜测：从节点n开始，找到最优解的可能性有多大？从起始节点开始，经过节点n，到达目标节点的最佳
35、路径的费用是多少？(存在一个约束)gh,最佳优先搜索（1）,思想:对每个节点使用估价函数,估计希望:扩展最有希望未扩展的节点主要包括:-贪婪最佳优先搜索-A*算法,最佳优先搜索（2）,贪婪最佳优先搜索(1),启发失函数 f(n)=h(n):从n到最近的目标节点代价的估计这里采用hSLD(n):从n到Bucharest的直线距离贪婪算法扩展看来与目标最近的节点,贪婪最佳优先搜索(2),贪婪最佳优先搜索(3),贪婪最佳优先搜索(4),贪婪最佳优先搜索(5),特性完备性:NO时间:O(bm),但是一个好的启发式可以得到很大的改进空间:O(bm),保存所有的节点在内存中最优:NO,A*算法(1),思想
36、:避免对已经扩展的路径进行再扩展评价函数为:f(x)=g(x)+h(x)把OPEN表中的节点按此函数的值从小到大进行排序g(x)是对g*(x)的估价,g(x)0h(x)是h*(x)的下界,即对所有的x,h(x)=h*(x)其中:g*(x)是从初始节点S0到节点x的最小代价 h*(x)是从节点x到目标节点的最小代价,若有多个目标节点,则为 其中最小的一个,n,S,g*(n),h*(n),g,A*算法（2）,f*(S)f*(S)=g*(S)+h*(S)=h*(S)从S无约束地到达目标的最佳路经上的耗散值;g(n)一般取实际走过的路径的费用和.g(n)g*(n)随着算法的执行，由于指针的变动，g(n
37、)会下降.h0没有启发式信息;,A*算法（3）,8数码问题h(n)=“不在位”的将牌数h(n)=将牌“不在位”的距离和,A*算法（4）,A*算法（5）,宽度优先:当问题为单位耗散值，且问题有解时，一定能找到最优解;f(n)=g(n)+h(n)g(n)h(n)=0 h*(n),A*算法例子(1),A*算法例子(2),A*算法例子(3),A*算法例子(4),A*算法例子(5),A*算法可纳性,对于可解状态图(即从初始节点到目标节点有路径存在)所说,如果一个搜索算法能在有限步内终止,并且能找到最优解,则称该搜索算法是可纳的.定理:A*算法是可纳的,即在有限步内终止,并且找到最优解证明思路对于有限图,
38、A*算法一定会在有限步内终止对应无限图,只要从初始节点到目标节点有路径存在,A*算法也必然终止A*算法一定终止在最优路径上,A*算法的最优性和单调性,最优性A*算法的搜索效率在很大程度上取决于h(x),在满足h(x)=h*(x)的前提下,h(x)的值越大越好.H(x)所携带的启发性信息越多,搜索时所扩展的节点数越少,搜索效率就越高单调性限制单调性限制是指h(x)满足如下两个条件h(Sg)=0设xj是节点xi 的任意子节点,则有 h(xi)-h(xj)=c(xi,xj)其中:Sg是目标节点,c(xi,xj)是节点xi到子节点xj的边代价A*算法的h(x)满足单调性限制时,可有下面的结论若A*算法
39、选择节点xn进行扩展,则g(xn)=g*(x)由A*算法所扩展的节点序列其f值是非递减的,启发式对性能的影响(1),8数码问题,两个启发式函数:h1(n):不在目标位的棋子数目h2(n):所有棋子到其目标位置的距离和(Manhattan距离),h1(S)=6h2(s)=4+0+3+3+1+0+2+1=14,启发式对性能的影响(2),典型情况下的搜索代价:d=14 IDS=3,473,941节点 A*(h1)=539节点 A*(h2)=113节点d=24 IDS 54,000,000,000节点 A*(h1)=39,135节点 A*(h2)=1,641节点,A*算法特性（1）,完备性:Yes,除
40、非有无限多的节点具有f C*的节点,A*算法特性（2）,但是对大多数搜索问题，搜索目标时的搜索空间的节点数仍然是答案深度的指数。在A*算法中计算时间不是主要的问题。由于A*算法把所有生成的节点保存在内存中，所以A*算法在耗尽计算时间之前一般早已经把空间耗尽了。为了克服空间问题，开发了一些新的算法，如迭代加深A*算法IDA*。启发式函数用做深度的限制，而不是选择扩展节点时的排序。IDA*算法和A*算法相比，主要优点是对于内存的需求。A*算法需要指数级数量的存贮空间，因为没有深度方面的限制。而IDA*算法只有当节点n的所有子节点n的f(n)小于限制值c时才扩展它，这样就可以节省大量的内存。,局部择
41、优搜索-瞎子爬山法（1）,搜索过程如下:(1)把初始节点S0放入OPEN表,计算f(S0)(2)如果OPEN表为空,则问题无解,退出(3)把OPEN表的第一个节点(记为节点n)取出,放入CLOSED表(4)考查节点n是否为目标节点.若是,则求得了问题的解,退出(5)若节点n不可扩展,则转第(2)步(6)扩展节点n,用估价函数f(x)计算每个子节点的估价值,并按估价值从小到大的顺序依次放入OPEN表的首部,并为每一个子节点都配置指向父节点的指针,转第(2)步,局部择优搜索-瞎子爬山法（2）,局部择优搜索-瞎子爬山法（3）,爬山法的三个问题：局部最大：高地：也称为平顶，在某一局部点周围f(x)为常
42、量。此时，搜索就无法确定要搜索的最佳方向，会产生随机走动，这使得搜索效率降低。山脊：山脊可能具有陡峭的斜面，所以搜索可以比较容易地到达山脊的顶部，但是山脊的顶部到山峰之间可能倾斜的很平缓。除非正好有合适的操作符直接沿着山脊的顶部移动，该搜索可能会在山脊的两面来回震荡，搜索的前进步伐会很小。在每种情况中，算法都会到达一个点，使得算法无法继续前进。如果出现这种情况，可以从另外一个点重新启动该算法。这称为随机重启爬山法。爬山法是否成功和状态空间“表面”的形状有很大的关系：如果只有很少的局部最大，随机重启爬山法将会很快地找到一个比较好的解答。如果该问题是NP完全的，则该算法不可能好于指数时间。这是因为
43、一定具有指数数量的局部最大值,局部择优搜索-瞎子爬山法（4）,爬山法从来不“下山”，即不会向值比当前结点低的方向搜索，它是不完备的，它可能会停留在局部极大值上。随机走到方法就是从后继集合中等概率随机地选取一个后继，它是完备的，但效率低下模拟退火算法结合了上述思想。“退火（Annealing）”是金属铸造的一个过程，它是指金属首先在高温下熔化，然后让它冷却下来直到它成为固态,局部择优搜索-瞎子爬山法（5）,如何在搜索中实现退火？在这个阶段，应该记住：需要模拟退火算法在函数f产生了没有比当前状态更好的下一个状态时，指出搜索的方向。这样，对所有可能的下一个合理状态计算E的值，并用下式计算p 的值 在闭区间0，1中随机得到一个数字，然后和p比较。如果p大，则选择它作为下一个转换状态。参数T在搜索程序中是逐渐降低的。这时由于T降低，p也降低，从而使得算法终止在一个稳定的状态。,局部择优搜索-瞎子爬山法（6）,局部择优搜索-瞎子爬山法（7）,遗传算法：是一种随机剪枝的搜索形式，它不是通过修改单一状态而是通过把两个父状态结合起来生成后继的GA从k个随机生成的状态开始（称为种群），通过遗传操作得到后代,局部择优搜索-瞎子爬山法（8）,
