搜索策略资料学习教案.pptx

《搜索策略资料学习教案.pptx》由会员分享，可在线阅读，更多相关《搜索策略资料学习教案.pptx（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1搜索搜索(su su)策略资料策略资料第一页，共67页。n n搜索分为盲目搜索和启发式搜索。n n盲目搜索是按照预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。n n启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着(cho zhe)最有希望的方向前进，加速问题的求解过程并找到最优解。w2第2页/共68页第二页，共67页。w w问题求解过程可以看作一个搜索过程。状态空间表示法是用来表示问题及其搜索过问题求解过程可以看作一个搜索过程。状态空间表示法是用来表示问题及其搜索过程的一种方法。它是人工智能中最基本的一种形式化方法。程的一种方法。它是人工智能中

2、最基本的一种形式化方法。w w状态空间用状态空间用“状态状态”和和“算符算符”来表示问题。来表示问题。w w状态状态w w状态用以描述问题求解过程中不同时刻的状况，是一个数据结构，一般用一组状态用以描述问题求解过程中不同时刻的状况，是一个数据结构，一般用一组变量的有序组合表示：变量的有序组合表示：w wSK=(Sk0,Sk1,)SK=(Sk0,Sk1,)w w当每一个分量的值确定时，就得到了一个具体的状态。当每一个分量的值确定时，就得到了一个具体的状态。w w算符算符w w引起状态中某些分量发生变化，从而使问题从一个状态变为另一个状态的操作引起状态中某些分量发生变化，从而使问题从一个状态变为另

3、一个状态的操作称为算符。在产生称为算符。在产生(chnshng)(chnshng)式系统中，一条产生式系统中，一条产生(chnshng)(chnshng)式规则就是一个算式规则就是一个算符。符。w w状态空间状态空间w w由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：三元组表示：w w(S,F,G)(S,F,G)w w其中其中S S是问题所有初始状态的集合；是问题所有初始状态的集合；F F是算符的集合；是算符的集合；GG是目标状态的集合。是目标状态的集合。w w状态空间的图示形式称为状

4、态空间图。状态空间的图示形式称为状态空间图。w3第3页/共68页第三页，共67页。设用设用SK=(Sk0,Sk1)SK=(Sk0,Sk1)表示问题的状态，表示问题的状态，SK0SK0表示金片表示金片A A所在的柱号，所在的柱号，Sk1Sk1表示金片表示金片B B所所在的柱号，全部可能的状态有九种：在的柱号，全部可能的状态有九种：S0=(1,1),S1=(1,2),S2=(1,3)S0=(1,1),S1=(1,2),S2=(1,3)S3=(2,1),S4=(2,2),S5=(2,3)S3=(2,1),S4=(2,2),S5=(2,3)S6=(3,1),S7=(3,2),S8=(3,3)S6=(3

5、,1),S7=(3,2),S8=(3,3)问题的初始状态集合为问题的初始状态集合为S=S0,S=S0,目标状态集合为目标状态集合为G=S4,S8G=S4,S8。算符分别用算符分别用A(i,j)A(i,j)及及B(i,j)B(i,j)。A(i,j)A(i,j)表示把表示把A A金片从第金片从第i i号柱移到第号柱移到第j j号柱。号柱。B(i,j)B(i,j)与之同理。算符共有与之同理。算符共有1212个。个。在状态空间图中，从初始节点在状态空间图中，从初始节点(1,1)(1,1)到目标节点到目标节点(2,2)(2,2)或或(3,3)(3,3)的任何的任何(rnh)(rnh)一条通路一条通路都是

6、问题的一个解。都是问题的一个解。其中最短的路径长度是其中最短的路径长度是3 3，它由它由3 3个算符组成。个算符组成。例如例如:A(1,3),B(1,2),A(3,2):A(1,3),B(1,2),A(3,2)w4第4页/共68页第四页，共67页。n n用状态空间方法表示问题，首先必须定义状态的描述形用状态空间方法表示问题，首先必须定义状态的描述形式，把问题的一切状态都表示出来。其次要定义一组算式，把问题的一切状态都表示出来。其次要定义一组算符。符。n n问题的求解过程是一个不断把算符作用于状态的过程。问题的求解过程是一个不断把算符作用于状态的过程。如果如果(rgu)(rgu)在使用某个算符后

7、得到的新状态是目标状态，在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成的序列。态所用算符构成的序列。n n算符的一次使用，就使问题由一种状态转变为另一种状算符的一次使用，就使问题由一种状态转变为另一种状态。使用算符最少的解或者总代价最少的解称为最优解。态。使用算符最少的解或者总代价最少的解称为最优解。n n对任何一个状态，可使用的算符可能不止一个。这样由对任何一个状态，可使用的算符可能不止一个。这样由一个状态所生成的后继状态就可能有多个。此时首先对一个状态所生成的后继状态就可能有多个。此时首

8、先对哪一个状态进行操作，就取决于搜索策略。哪一个状态进行操作，就取决于搜索策略。w5第5页/共68页第五页，共67页。n n与或树是用于表示问题及其求解过程的又一种形式化方法，通与或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较复杂问题的求解。常用于表示比较复杂问题的求解。n n对于一个复杂问题，直接求解往往比较困难。此时可通过下述对于一个复杂问题，直接求解往往比较困难。此时可通过下述方法进行简化：方法进行简化：n n分解分解(fnji)(fnji)n n把一个复杂问题分解把一个复杂问题分解(fnji)(fnji)为若干个较为简单的子问为若干个较为简单的子问题，每个子问题又可

9、继续分解题，每个子问题又可继续分解(fnji)(fnji)。重复此过程，直到不。重复此过程，直到不需要或者不能再分解需要或者不能再分解(fnji)(fnji)为止。如此形成为止。如此形成“与与”树。树。n n等价变换等价变换n n利用同构或同态的等价变换，把原问题变换为若干个较利用同构或同态的等价变换，把原问题变换为若干个较为容易求解的新问题。如此形成为容易求解的新问题。如此形成“或或”树。树。w6第6页/共68页第六页，共67页。w7第7页/共68页第七页，共67页。n n本原问题本原问题n n不能再分解或变换，而且直接不能再分解或变换，而且直接(zhji)(zhji)可解的子问可解的子问题

10、。题。n n端节点与终止节点端节点与终止节点n n在与在与/或树中，没有子节点的节点统称为端节点；本或树中，没有子节点的节点统称为端节点；本原问题所对应的节点称为终止节点。原问题所对应的节点称为终止节点。n n可解节点可解节点n n在与在与/或树中，满足下列条件之一者，称为可解节点：或树中，满足下列条件之一者，称为可解节点：n n它是一个终止节点；它是一个终止节点；n n它是一个它是一个“或或”节点，且其子节点中至少有一个是节点，且其子节点中至少有一个是可解节点；可解节点；n n它是一个它是一个“与与”节点，且其子节点全部是可解节点。节点，且其子节点全部是可解节点。n n不可解节点不可解节点n

11、 n关于可解节点的三个条件全部不满足的节点关于可解节点的三个条件全部不满足的节点w8第8页/共68页第八页，共67页。n n解树解树n n由可解节点由可解节点(ji din)(ji din)所构成，并且由这些可解节所构成，并且由这些可解节点点(ji din)(ji din)可推出初始节点可推出初始节点(ji din)(ji din)为可解节点为可解节点(ji din)(ji din)的子树称为解树。的子树称为解树。w9第9页/共68页第九页，共67页。w10第10页/共68页第十页，共67页。w11盲目搜索的特点：搜索按规定的路线进行，不使用与问题有关的启发性信息；适用于其状态(zhungti

12、)空间图是树状结构的一类问题。启发式搜索要使用与问题有关的启发性信息，并以这些启发性信息指导搜索过程，可以高效地求解结构复杂的问题。第11页/共68页第十一页，共67页。n n广度优先搜索按照广度优先搜索按照“先扩展先扩展(kuzhn)(kuzhn)出的节点先被考察出的节点先被考察”的原则进行搜索；的原则进行搜索；n n深度优先搜索按照深度优先搜索按照“后扩展后扩展(kuzhn)(kuzhn)出的节点先被考察出的节点先被考察”的原则进行搜索；的原则进行搜索；n n有界深度优先搜索的原则与深度优先搜索相同，但是它有界深度优先搜索的原则与深度优先搜索相同，但是它规定了深度限界，使搜索不得无限制地向

13、纵深方向发展；规定了深度限界，使搜索不得无限制地向纵深方向发展；n n代价树的广度优先搜索按照代价树的广度优先搜索按照“哪个节点到根节点的代价哪个节点到根节点的代价小就先考察哪个节点小就先考察哪个节点”的原则进行搜索；的原则进行搜索；n n代价树的深度优先搜索按照代价树的深度优先搜索按照“当前节点的哪个子节点到当前节点的哪个子节点到其父节点的代价小就先考察哪个子节点其父节点的代价小就先考察哪个子节点”的原则进行搜的原则进行搜索；索；n n局部择优搜索按照局部择优搜索按照“当前节点的哪个子节点到目标节点当前节点的哪个子节点到目标节点的估计代价小就先考察哪个子节点的估计代价小就先考察哪个子节点”的

14、原则进行搜索；的原则进行搜索；n n全局择优搜索按照全局择优搜索按照“哪个节点到目标节点的估计代价小哪个节点到目标节点的估计代价小就先考察哪个节点就先考察哪个节点”的原则进行搜索；的原则进行搜索；w12第12页/共68页第十二页，共67页。n nOPENOPEN表和表和CLOSECLOSE表表n nOPENOPEN表用于存放刚生成的节点。对于不同的搜索策略，表用于存放刚生成的节点。对于不同的搜索策略，节点在节点在OPENOPEN表中的排列顺序是不同的。表中的排列顺序是不同的。n nCLOSECLOSE表用于存放将要扩展表用于存放将要扩展(kuzhn)(kuzhn)或者已经扩展或者已经扩展(ku

15、zhn)(kuzhn)的节点。的节点。n n OPEN OPEN表表CLOSECLOSE表表w13状态节点父节点编号 状态节点 父节点第13页/共68页第十三页，共67页。1.1.把初始节点把初始节点S0S0放入放入OPENOPEN表，并建立目前只包含表，并建立目前只包含S0S0的图，记为的图，记为GG；2.2.检查检查OPENOPEN表是否为空，若为空则问题无解，退出；表是否为空，若为空则问题无解，退出；3.3.把把OPENOPEN表的第一个节点取出放入表的第一个节点取出放入CLOSECLOSE表，并计该节点为表，并计该节点为n n；4.4.考察节点考察节点n n是否为目标节点。若是，则求得

16、了问题的解，退出；是否为目标节点。若是，则求得了问题的解，退出；5.5.扩展节点扩展节点n n，生成一组子节点。把其中不是节点，生成一组子节点。把其中不是节点n n先辈的那些子节先辈的那些子节点记做集合点记做集合MM，并把这些子节点作为节点，并把这些子节点作为节点n n的子节点加入的子节点加入GG中；中；6.6.针对针对MM中子节点的不同情况，分别进行如下处理：中子节点的不同情况，分别进行如下处理：7.7.对于那些未曾在对于那些未曾在GG中出现过的中出现过的MM成员设置一个指向父节点（即节点成员设置一个指向父节点（即节点n n）的指针，并把它们放入）的指针，并把它们放入OPENOPEN表；表；

17、8.8.对于那些先前已经在对于那些先前已经在GG中出现过的中出现过的MM成员，确定是否需要成员，确定是否需要(xyo)(xyo)修改它指向父节点的指针；修改它指向父节点的指针；9.9.对于那些先前已在对于那些先前已在GG中出现并且已经扩展了的中出现并且已经扩展了的MM成员，确定是否需成员，确定是否需要要(xyo)(xyo)修改其后继节点指向父节点的指针；修改其后继节点指向父节点的指针；10.10.按某种搜索策略对按某种搜索策略对OPENOPEN表中的节点进行排序；表中的节点进行排序；11.11.转第转第2 2步。步。w14第14页/共68页第十四页，共67页。1.1.上述是一个通用过程，各种搜

18、索策略的主要区别是对上述是一个通用过程，各种搜索策略的主要区别是对OPENOPEN表中表中节点排序的准则不同。节点排序的准则不同。2.2.一个节点经一个算符操作后一般只生成一个子节点。但适用于一一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符可能有多个，此时就会生成一组子节点。这些子节个节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。把这些先辈节点作为当前扩展节点的子节点。3.3.一个新生成的节点，它可能是第一次被生成

19、的节点，也可能是先一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的后继节点被生成过，当前又作为另一个节点前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节点被再次生成。此时，它究竟的后继节点被再次生成。此时，它究竟(jijng)(jijng)应作为哪个节应作为哪个节点的不后继节点？一般由原始节点到该节点的代价来决定，代价点的不后继节点？一般由原始节点到该节点的代价来决定，代价小的相应节点就作为父节点。小的相应节点就作为父节点。4.4.在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是

20、由从初始节点到该目标节点路径上的算符构成。解。该解是由从初始节点到该目标节点路径上的算符构成。5.5.如果在搜索中一直找不到目标节点，而且如果在搜索中一直找不到目标节点，而且OPENOPEN表中不再有可供表中不再有可供扩展的节点，则搜索失败。扩展的节点，则搜索失败。w15第15页/共68页第十五页，共67页。n n基本思想(sxing)：n n从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前，不对第n1层的节点进行扩展。n nOPEN表中节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。w16第16页/共68页第十六页，共

21、67页。1.1.把初始节点把初始节点S0S0放入放入OPENOPEN表。表。2.2.如果如果OPENOPEN表为空，则问题无解，退出。表为空，则问题无解，退出。3.3.把把OPENOPEN表的第一个节点（记为节点表的第一个节点（记为节点n n）取）取出放入出放入CLOSECLOSE表。表。4.4.考察节点考察节点n n是否为目标节点。若是，则求得是否为目标节点。若是，则求得了问题的解，退出。了问题的解，退出。5.5.若节点若节点n n不可扩展，则转第不可扩展，则转第2 2步。步。6.6.扩展节点扩展节点n n，将其子节点放入，将其子节点放入OPENOPEN表的尾表的尾部，并为每一个子节点都配置

22、指向部，并为每一个子节点都配置指向(zh(zh xin)xin)父节点的指针，然后转第父节点的指针，然后转第2 2步。步。w17第17页/共68页第十七页，共67页。w18第18页/共68页第十八页，共67页。n n优点：n n只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。n n缺点：n n广度优先搜索盲目性较大，当目标节点(ji din)距初始节点(ji din)较远时将会产生许多无用节点(ji din)，搜索效率低。w19第19页/共68页第十九页，共67页。n n基本思想：基本思想：n n从初始节点从初始节点S0S0开始，在其子节点中选择一个节点开始，在其子节点中选

23、择一个节点进行考察。若不是目标节点，则再在该子节点的子节进行考察。若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，一直如此向下点中选择一个节点进行考察，一直如此向下(xin xi)(xin xi)搜索。当达到某个子节点，且该子节点既不是目标节搜索。当达到某个子节点，且该子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。点，又不能继续扩展时，才选择其兄弟节点进行考察。n n深度优先搜索与广度优先搜索的唯一区别是：广度优深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点先搜索是将节点n n的子节点放入到的子节点放入到OPENOPEN表的尾部，而表的尾部，而深

24、度优先搜索是把节点深度优先搜索是把节点n n的子节点放入到的子节点放入到OPENOPEN表的首表的首部。部。w20第20页/共68页第二十页，共67页。1.1.把初始节点把初始节点S0S0放入放入OPENOPEN表。表。2.2.如果如果OPENOPEN表为空，则问题无解，退出。表为空，则问题无解，退出。3.3.把把OPENOPEN表的第一个节点（记为节点表的第一个节点（记为节点n n）取出放入）取出放入CLOSECLOSE表。表。4.4.考察节点考察节点n n是否为目标是否为目标(mbio)(mbio)节点。若是，则求节点。若是，则求得了问题的解，退出。得了问题的解，退出。5.5.若节点若节点

25、n n不可扩展，则转第不可扩展，则转第2 2步。步。6.6.扩展节点扩展节点n n，将其子节点放入，将其子节点放入OPENOPEN表的首部，并表的首部，并为每一个子节点都配置指向父节点的指针，然后为每一个子节点都配置指向父节点的指针，然后转第转第2 2步。步。w21第21页/共68页第二十一页，共67页。w22第22页/共68页第二十二页，共67页。n n在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果直向下搜索。如果(rgu)(rgu)目标节点恰好在此分支上，则可较快地目标节点恰好在此分支上，则可较快地得到解。但

26、是，如果得到解。但是，如果(rgu)(rgu)目标节点不在此分支上，而该分支又目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。备的，即使问题有解，它也不一定能求得解。n n用深度优先求得的解，不一定是路径最短的解。用深度优先求得的解，不一定是路径最短的解。w23第23页/共68页第二十三页，共67页。w w基本思想：基本思想：w w对深度优先搜索引入搜索深度的界限（设为对深度优先搜索引入搜索深度的界限（设为dmdm），当搜），当搜索深度达到了深度界限，而尚未出

27、现目标节点时，就换索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。一个分支进行搜索。w w搜索过程：搜索过程：w w把初始节点把初始节点S0S0放入放入OPENOPEN表中，置表中，置S0S0的深度的深度d(S0)=0d(S0)=0。w w如果如果OPENOPEN表为空，则问题无解，退出。表为空，则问题无解，退出。w w把把OPENOPEN表的第一个节点（记为节点表的第一个节点（记为节点n n）取出放入）取出放入CLOSECLOSE表。表。w w考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。w w若节点若节点

28、n n的深度的深度d(d(节点节点n)=dmn)=dm，则转第，则转第2 2步。步。w w若节点若节点n n不可扩展，则转第不可扩展，则转第2 2步。步。w w扩展节点扩展节点n n，将其子节点放入，将其子节点放入OPENOPEN表的首部，并为每一表的首部，并为每一个子节点都配置个子节点都配置(pizh)(pizh)指向父节点的指针，然后转第指向父节点的指针，然后转第2 2步。步。w24第24页/共68页第二十四页，共67页。n n如果问题有解，且其路径长度dm，则上述搜索过程(guchng)一定能求得解。但是，若解的路径长度dm,则上述搜索过程(guchng)就得不到解。这说明在有界深度优先

29、搜索中，深度界限的选择是很重要的。n n要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。w25第25页/共68页第二十五页，共67页。1.1.先任意设定一个较小的数作为先任意设定一个较小的数作为dmdm，然后进行上述的有界，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限深度优先搜索，当搜索达到了指定的深度界限dmdm仍未发仍未发现目标节点，并且现目标节点，并且CLOSECLOSE表中仍有待扩展节点时，就将表中仍有待扩展节点时，就将这些节点送回这些节点送回OPENOPEN表，同时增大深度界限表，同时增大深度界限dmdm，继续向，继续向下搜索。如此下搜索。如此(rc

30、)(rc)不断地增大不断地增大dmdm，只要问题有解，就，只要问题有解，就一定可以找到它。但此时找到的解不一定是最优解。一定可以找到它。但此时找到的解不一定是最优解。2.2.为了找到最优解，可增设一个表为了找到最优解，可增设一个表R R，每找到远程目标节点，每找到远程目标节点SgSg后，就把它放入到后，就把它放入到R R的前面，并令的前面，并令dmdm等于该目标节点等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的解的所对应的路径长度，然后继续搜索。由于后求得的解的路径长度不会超过先求得的解的路径长度，所以后求得路径长度不会超过先求得的解的路径长度，所以后求得的解一定是最优解。的解一定

31、是最优解。w26第26页/共68页第二十六页，共67页。设深度设深度(shnd)(shnd)界限界限dmdm4 4w27第27页/共68页第二十七页，共67页。n n盲目搜索具有较大的盲目性，产生的盲目搜索具有较大的盲目性，产生的无用节点较多，搜索空间较大，效率无用节点较多，搜索空间较大，效率不高。不高。n n启发式搜索要用到问题启发式搜索要用到问题(wnt)(wnt)自身的自身的某些特性信息，以指导搜索朝着最有某些特性信息，以指导搜索朝着最有希望的方向前进。由于这种搜索针对希望的方向前进。由于这种搜索针对性较强，因而原则上只需要搜索问题性较强，因而原则上只需要搜索问题(wnt)(wnt)的部

32、分状态空间，效率较高。的部分状态空间，效率较高。w28第28页/共68页第二十八页，共67页。n n可用于指导搜索过程，且与具体问题求解有关的控制性信息称为可用于指导搜索过程，且与具体问题求解有关的控制性信息称为(chn wi)(chn wi)启发性信息。启发性信息。n n用于估价节点重要性的函数称为用于估价节点重要性的函数称为(chn wi)(chn wi)估价函数。其一般估价函数。其一般形式为：形式为：n nf(x)=g(x)+h(x)f(x)=g(x)+h(x)n n其中其中g(x)g(x)为从初始节点为从初始节点S0S0到节点到节点x x已经实际付出的代价；已经实际付出的代价；h(x)

33、h(x)是是从节点从节点x x到目标节点到目标节点SgSg的最优路径的估计代价，它体现了问题的的最优路径的估计代价，它体现了问题的启发性信息，其形式要根据问题的特性确定。例如它可以是节点启发性信息，其形式要根据问题的特性确定。例如它可以是节点x x到目标节点的距离，或者节点到目标节点的距离，或者节点x x处于最优路径上的概率等等。处于最优路径上的概率等等。h(x)h(x)称为称为(chn wi)(chn wi)启发函数。启发函数。n ng(x)g(x)指出了搜索的横向趋势。它有利于搜索的完备性，但影响搜指出了搜索的横向趋势。它有利于搜索的完备性，但影响搜索的效率。如果我们只关心到达目标节点的路

34、径，并且希望有较索的效率。如果我们只关心到达目标节点的路径，并且希望有较高的搜索效率，则高的搜索效率，则g(x)g(x)可以忽略，但此时会影响搜索的完备性。可以忽略，但此时会影响搜索的完备性。w29第29页/共68页第二十九页，共67页。设有如下结构的移动牌游戏：设有如下结构的移动牌游戏：该游戏规则：该游戏规则：当一个牌移入相邻当一个牌移入相邻(xin ln)(xin ln)的空位置时，费用为一个单位。的空位置时，费用为一个单位。一个牌至多可跳过两个牌进入空位置，其费用等于跳过的牌数加一个牌至多可跳过两个牌进入空位置，其费用等于跳过的牌数加1 1。要求把所有的要求把所有的B B都移至都移至WW

35、的右边，请设计估价函数中的的右边，请设计估价函数中的h(x)h(x)。解：根据要求可知，解：根据要求可知，WW左边的左边的B B越少越接近目标，因此可用越少越接近目标，因此可用WW左边左边B B的个数作的个数作为为h(x),h(x),即即h(x)=3(h(x)=3(每个每个WW左边左边B B个数的总和个数的总和)这里乘以系数这里乘以系数3 3是为了扩大是为了扩大h(x)h(x)在在f(x)f(x)中的比重。中的比重。w30BBBWWWE第30页/共68页第三十页，共67页。n n基本思想：基本思想：n n当一个节点被扩展以后，按当一个节点被扩展以后，按f(x)f(x)对每一个子节点计对每一个子

36、节点计算估价值，并选择最小者作为下一个要考察的节点。算估价值，并选择最小者作为下一个要考察的节点。n n搜索过程：搜索过程：n n把初始节点把初始节点S0S0放入放入OPENOPEN表，令表，令g(S0)=0g(S0)=0。n n如果如果OPENOPEN表为空，则问题无解，退出。表为空，则问题无解，退出。n n把把OPENOPEN表的第一个节点（记为节点表的第一个节点（记为节点n n）取出放入）取出放入CLOSECLOSE表。表。n n考察节点考察节点n n是否为目标节点。若是，则求得了问题的是否为目标节点。若是，则求得了问题的解，退出。解，退出。n n若节点若节点n n不可不可(bk)(bk

37、)扩展，则转第扩展，则转第2 2步。步。n n扩展节点扩展节点n n，用估价函数，用估价函数f(x)f(x)计算每个子节点的估价值，计算每个子节点的估价值，并按估价值从小到大的顺序放到并按估价值从小到大的顺序放到OPENOPEN表中的首部，表中的首部，并为每一个子节点都配置指向父节点的指针，然后转并为每一个子节点都配置指向父节点的指针，然后转第第2 2步。步。n n深度优先搜索、代价树的深度优先搜索以及局部择优深度优先搜索、代价树的深度优先搜索以及局部择优搜索都是以子节点作为考察范围的。但是前二者可以搜索都是以子节点作为考察范围的。但是前二者可以看作局部择优搜索的特例。看作局部择优搜索的特例。

38、w31第31页/共68页第三十一页，共67页。n n基本思想：基本思想：n n在代价树的广度优先搜索中，每次都是从在代价树的广度优先搜索中，每次都是从OPENOPEN表的表的全体节点中选择一个代价最小的节点送入全体节点中选择一个代价最小的节点送入CLOSECLOSE表进行表进行考察。而代价树的深度考察。而代价树的深度(shnd)(shnd)优先搜索是从刚扩展出优先搜索是从刚扩展出的子节点中选一个代价最小的节点送入的子节点中选一个代价最小的节点送入CLOSECLOSE表进行考表进行考察。察。n n搜索过程：搜索过程：n n把初始节点把初始节点S0S0放入放入OPENOPEN表，令表，令g(S0)

39、=0g(S0)=0。n n如果如果OPENOPEN表为空，则问题无解，退出。表为空，则问题无解，退出。n n把把OPENOPEN表的第一个节点（记为节点表的第一个节点（记为节点n n）取出放入）取出放入CLOSECLOSE表。表。n n考察节点考察节点n n是否为目标节点。若是，则求得了问题的解，是否为目标节点。若是，则求得了问题的解，退出。退出。n n若节点若节点n n不可扩展，则转第不可扩展，则转第2 2步。步。n n扩展节点扩展节点n n，将其子节点按代价从小到大的顺序放到，将其子节点按代价从小到大的顺序放到OPENOPEN表中的首部，并为每一个子节点都配置指向父节表中的首部，并为每一个

40、子节点都配置指向父节点的指针，然后转第点的指针，然后转第2 2步。步。n n代价树的深度代价树的深度(shnd)(shnd)有限搜索是不完备的。有限搜索是不完备的。w32第32页/共68页第三十二页，共67页。w33基本思想：每当要选择一个节点进行考察时，局部择优搜索只是从刚生成的子节点中进行选择，选择的范围比较狭窄。全局择优搜索每次总是(zn sh)从OPEN表的全体节点中选择一个估价值最小的节点。搜索过程：把初始节点S0放入OPEN表，计算f(S0)。如果OPEN表为空，则问题无解，退出。把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问

41、题的解，退出。若节点n不可扩展，则转第2步。扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每一个子节点都配置指向父节点的指针。把这些子节点都送入OPEN表中，然后对OPEN表中的全部节点按估价值从小至大的顺序进行排序，然后转第2步。广度优先搜索、代价树的广度优先搜索以及全局择优搜索都是以当前所有节点作为考察范围的。但是前二者可以看作全局择优搜索的特例。第33页/共68页第三十三页，共67页。设估价函数为设估价函数为f(x)=d(x)+h(x)f(x)=d(x)+h(x)其中，其中，d(x)d(x)表示节点表示节点x x的深度，的深度，h(x)h(x)表示节点表示节点x x的格局与目

42、标的格局与目标(mbio)(mbio)节点节点格局不相同的牌数。格局不相同的牌数。w34第34页/共68页第三十四页，共67页。n n边上标有代价边上标有代价(或费用或费用)的树称为代价树。的树称为代价树。n n用用g(x)g(x)表示从初始节点表示从初始节点S0S0到节点到节点x x的代价，用的代价，用c(x1,x2)c(x1,x2)表表示从父节点示从父节点x1x1到子节点到子节点x2x2的代价则有：的代价则有：n ng(x2)=g(x1)+c(x1,x2)g(x2)=g(x1)+c(x1,x2)n n基本思想：基本思想：n n每次从每次从OPENOPEN表中选择节点往表中选择节点往CLOS

43、ECLOSE表传送时，表传送时，总是选择其代价最小的节点。也就是说，总是选择其代价最小的节点。也就是说，OPENOPEN表中的表中的节点在任一时刻都是按其代价从小到大排序节点在任一时刻都是按其代价从小到大排序(pi x)(pi x)的。的。代价小的节点排在前面，代价大的节点排在后面，而不代价小的节点排在前面，代价大的节点排在后面，而不管节点在代价树中处于什么位置。管节点在代价树中处于什么位置。n n如果问题有解，代价树的广度优先搜索一定可以求得解，如果问题有解，代价树的广度优先搜索一定可以求得解，并且求出的是最优解。并且求出的是最优解。w35第35页/共68页第三十五页，共67页。1.1.把初

44、始节点把初始节点S0S0放入放入OPENOPEN表，令表，令g(S0)=0g(S0)=0。2.2.如果如果OPENOPEN表为空，则问题无解，退出。表为空，则问题无解，退出。3.3.把把OPENOPEN表的第一个表的第一个(y)(y)节点（记为节点节点（记为节点n n）取出）取出放入放入CLOSECLOSE表。表。4.4.考察节点考察节点n n是否为目标节点。若是，则求得了问题是否为目标节点。若是，则求得了问题的解，退出。的解，退出。5.5.若节点若节点n n不可扩展，则转第不可扩展，则转第2 2步。步。6.6.扩展节点扩展节点n n，将其子节点放入，将其子节点放入OPENOPEN表中，并为每

45、一表中，并为每一个个(y)(y)子节点都配置指向父节点的指针。计算各子节点都配置指向父节点的指针。计算各子节点的代价，并按各节点的代价对子节点的代价，并按各节点的代价对OPENOPEN表中的表中的全部节点进行排序全部节点进行排序(按从小到大的顺序按从小到大的顺序)，然后转第，然后转第2 2步。步。w36第36页/共68页第三十六页，共67页。w37第37页/共68页第三十七页，共67页。n n如果使一般搜索过程如果使一般搜索过程(guchng)(guchng)满足如下限制，则它就称为满足如下限制，则它就称为A*A*算算法：法：n n1 1、把、把OPENOPEN表中的节点按估价函数表中的节点按

46、估价函数n nf(x)=g(x)+h(x)f(x)=g(x)+h(x)n n的值从小至大进行排序（一般搜索过程的值从小至大进行排序（一般搜索过程(guchng)(guchng)的第的第7 7步）。步）。n n2 2、g(x)g(x)是对是对g*(x)g*(x)的估计，的估计，g(x)0g(x)0。n n3 3、h(x)h(x)是是h*(x)h*(x)的下界，即对所有的的下界，即对所有的x x均有：均有：n nh(x)h*(x)h(x)h*(x)n n其中，其中，g*(x)g*(x)是从初始节点是从初始节点S0S0到节点到节点x x的最小代价；的最小代价；h*(x)h*(x)是从节点是从节点x

47、x到目标节点的最小代价，若有多个目标节点，则为其中最小的到目标节点的最小代价，若有多个目标节点，则为其中最小的一个。一个。w38第38页/共68页第三十八页，共67页。n n在在A*A*算法中，算法中，g(x)g(x)实际上就是从初始节点实际上就是从初始节点S0S0到节点到节点x x的路径的路径代价，恒有代价，恒有g(x)g*(x)g(x)g*(x)。而且在算法执行过程中随着更多搜。而且在算法执行过程中随着更多搜索信息的获得，索信息的获得，g(x)g(x)的值呈下降的趋势的值呈下降的趋势(qsh)(qsh)。n n例如：例如：n nH(x)H(x)的确定依赖于具体问题领域的启发性信息，其中的确

48、定依赖于具体问题领域的启发性信息，其中h(x)h*(x)h(x)h*(x)的限制十分重要，它保证的限制十分重要，它保证A*A*算法能找到最优解。算法能找到最优解。w39第39页/共68页第三十九页，共67页。n n可纳性可纳性n n对于可解状态空间图对于可解状态空间图(即从初始节点到目标节点有路径存在即从初始节点到目标节点有路径存在)来说，来说，如果一个搜索算法能在有限步那终止，并且如果一个搜索算法能在有限步那终止，并且(bngqi)(bngqi)能找到最优解，能找到最优解，则称该搜索算法是可纳的。则称该搜索算法是可纳的。n nA*A*算法是可纳的。算法是可纳的。n nA*A*算法的最优性算法

49、的最优性n nA*A*算法的搜索效率在很大程度上取决于算法的搜索效率在很大程度上取决于h(x)h(x)，在满足，在满足h(x)h*(x)h(x)h*(x)的前提下，的前提下，h(x)h(x)的值越大越好。的值越大越好。h(x)h(x)的值越大，表明它携带的启发性的值越大，表明它携带的启发性信息越多，搜索时扩展的节点数越少，搜索的效率越高。信息越多，搜索时扩展的节点数越少，搜索的效率越高。n nh(x)h(x)的单调性限制的单调性限制n n在在A*A*算法中，每当要扩展一个节点时都要先检查其子节点是否算法中，每当要扩展一个节点时都要先检查其子节点是否已在已在OPENOPEN表或表或CLOSECL

50、OSE表中，有时还要调整指向父节点的指针，这表中，有时还要调整指向父节点的指针，这就增加了搜索的代价。如果对启发函数就增加了搜索的代价。如果对启发函数h(x)h(x)加上单调性限制，就可减加上单调性限制，就可减少检查及调整的工作量，从而减少搜索代价。少检查及调整的工作量，从而减少搜索代价。w40第40页/共68页第四十页，共67页。n n所谓单调所谓单调(dndio)(dndio)性限制是指性限制是指h(x)h(x)满足如下两个条件：满足如下两个条件：n n1 1、h(Sg)=0;h(Sg)=0;n n2 2、设、设xjxj是节点是节点xixi的任意子节点，则有的任意子节点，则有n nh(xi