第五章 搜索策略资料

第五章搜索策略•5.1概述•5.2状态空间搜索•5.3与或树搜索2•搜索分为盲目搜索和启发式搜索。–盲目搜索是按照预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。–启发式搜索是在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。3问题求解过程可以看作一个搜索过程。状态空间表示法是用来表示问题及其搜索过程的一种方法。它是人工智能中最基本的一种形式化方法。状态空间用“状态”和“算符”来表示问题。–状态状态用以描述问题求解过程中不同时刻的状况，是一个数据结构，一般用一组变量的有序组合表示：SK=(Sk0,Sk1,…)当每一个分量的值确定时，就得到了一个具体的状态。–算符引起状态中某些分量发生变化，从而使问题从一个状态变为另一个状态的操作称为算符。在产生式系统中，一条产生式规则就是一个算符。–状态空间由问题的全部状态及一切可用算符所构成的集合称为问题的状态空间，一般用一个三元组表示：(S,F,G)其中S是问题所有初始状态的集合；F是算符的集合；G是目标状态的集合。状态空间的图示形式称为状态空间图。4设用SK=(Sk0,Sk1)表示问题的状态，SK0表示金片A所在的柱号，Sk1表示金片B所在的柱号，全部可能的状态有九种：S0=(1,1),S1=(1,2),S2=(1,3)S3=(2,1),S4=(2,2),S5=(2,3)S6=(3,1),S7=(3,2),S8=(3,3)问题的初始状态集合为S={S0},目标状态集合为G={S4,S8}。算符分别用A(i,j)及B(i,j)。A(i,j)表示把A金片从第i号柱移到第j号柱。B(i,j)与之同理。算符共有12个。在状态空间图中，从初始节点(1,1)到目标节点(2,2)或(3,3)的任何一条通路都是问题的一个解。其中最短的路径长度是3，它由3个算符组成。例如:A(1,3),B(1,2),A(3,2)51,12,13,12,33,23,31,31,22,2A(1,3)B(1,2)A(3,2)•用状态空间方法表示问题，首先必须定义状态的描述形式，把问题的一切状态都表示出来。其次要定义一组算符。•问题的求解过程是一个不断把算符作用于状态的过程。如果在使用某个算符后得到的新状态是目标状态，就得到了问题的一个解。这个解是从初始状态到目标状态所用算符构成的序列。•算符的一次使用，就使问题由一种状态转变为另一种状态。使用算符最少的解或者总代价最少的解称为最优解。•对任何一个状态，可使用的算符可能不止一个。这样由一个状态所生成的后继状态就可能有多个。此时首先对哪一个状态进行操作，就取决于搜索策略。6•与或树是用于表示问题及其求解过程的又一种形式化方法，通常用于表示比较复杂问题的求解。•对于一个复杂问题，直接求解往往比较困难。此时可通过下述方法进行简化：–分解把一个复杂问题分解为若干个较为简单的子问题，每个子问题又可继续分解。重复此过程，直到不需要或者不能再分解为止。如此形成“与”树。–等价变换利用同构或同态的等价变换，把原问题变换为若干个较为容易求解的新问题。如此形成“或”树。7PP1P2P3与树PP1P2P3或树P31PP1P2P3与或树P11P12P32P338•本原问题–不能再分解或变换，而且直接可解的子问题。•端节点与终止节点–在与/或树中，没有子节点的节点统称为端节点；本原问题所对应的节点称为终止节点。•可解节点–在与/或树中，满足下列条件之一者，称为可解节点：•它是一个终止节点；•它是一个“或”节点，且其子节点中至少有一个是可解节点；•它是一个“与”节点，且其子节点全部是可解节点。•不可解节点–关于可解节点的三个条件全部不满足的节点9•解树由可解节点所构成，并且由这些可解节点可推出初始节点为可解节点的子树称为解树。10解树PtttPttt(1,1,1)=(3,3,3)(1,1,1)=(1,2,2)(1,2,2)=(3,2,2)(3,2,2)=(3,3,3)(1,1,1)=(1,1,3)(1,1,3)=(1,2,3)(1,2,3)=(1,2,2)(3,2,2)=(3,2,1)(3,2,1)=(3,3,1)(3,3,1)=(3,3,3)11状态空间搜索策略盲目搜索启发式搜索广度优先搜索深度优先搜索有界深度优先搜索代价树的广度优先搜索代价树的深度优先搜索局部择优搜索全局择优搜索A*算法12盲目搜索的特点：搜索按规定的路线进行，不使用与问题有关的启发性信息；适用于其状态空间图是树状结构的一类问题。启发式搜索要使用与问题有关的启发性信息，并以这些启发性信息指导搜索过程，可以高效地求解结构复杂的问题。•广度优先搜索按照“先扩展出的节点先被考察”的原则进行搜索；•深度优先搜索按照“后扩展出的节点先被考察”的原则进行搜索；•有界深度优先搜索的原则与深度优先搜索相同，但是它规定了深度限界，使搜索不得无限制地向纵深方向发展；•代价树的广度优先搜索按照“哪个节点到根节点的代价小就先考察哪个节点”的原则进行搜索；•代价树的深度优先搜索按照“当前节点的哪个子节点到其父节点的代价小就先考察哪个子节点”的原则进行搜索；•局部择优搜索按照“当前节点的哪个子节点到目标节点的估计代价小就先考察哪个子节点”的原则进行搜索；•全局择优搜索按照“哪个节点到目标节点的估计代价小就先考察哪个节点”的原则进行搜索；13•OPEN表和CLOSE表–OPEN表用于存放刚生成的节点。对于不同的搜索策略，节点在OPEN表中的排列顺序是不同的。–CLOSE表用于存放将要扩展或者已经扩展的节点。OPEN表CLOSE表14状态节点父节点编号状态节点父节点1.把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；2.检查OPEN表是否为空，若为空则问题无解，退出；3.把OPEN表的第一个节点取出放入CLOSE表，并计该节点为n；4.考察节点n是否为目标节点。若是，则求得了问题的解，退出；5.扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；6.针对M中子节点的不同情况，分别进行如下处理：1.对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；2.对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；3.对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；7.按某种搜索策略对OPEN表中的节点进行排序；8.转第2步。151.上述是一个通用过程，各种搜索策略的主要区别是对OPEN表中节点排序的准则不同。2.一个节点经一个算符操作后一般只生成一个子节点。但适用于一个节点的算符可能有多个，此时就会生成一组子节点。这些子节点中可能有些是当前扩展节点的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。3.一个新生成的节点，它可能是第一次被生成的节点，也可能是先前已作为其它节点的后继节点被生成过，当前又作为另一个节点的后继节点被再次生成。此时，它究竟应作为哪个节点的不后继节点？一般由原始节点到该节点的代价来决定，代价小的相应节点就作为父节点。4.在搜索过程中，一旦某个被考察的节点是目标节点就得到了一个解。该解是由从初始节点到该目标节点路径上的算符构成。5.如果在搜索中一直找不到目标节点，而且OPEN表中不再有可供扩展的节点，则搜索失败。16•基本思想：从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前，不对第n＋1层的节点进行扩展。•OPEN表中节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。171.把初始节点S0放入OPEN表。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展，则转第2步。6.扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2步。182831476528314765832147652837146583214765283714658321476581324765283746152837146523184765231847651238476512384765283147652318476523418765281437652814376528314576283145762831647528316476283641752831647528316754S0Sg1234567891011121314151617181192021222324252619•优点：只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。•缺点：广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。20•基本思想：从初始节点S0开始，在其子节点中选择一个节点进行考察。若不是目标节点，则再在该子节点的子节点中选择一个节点进行考察，一直如此向下搜索。当达到某个子节点，且该子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。•深度优先搜索与广度优先搜索的唯一区别是：广度优先搜索是将节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点n的子节点放入到OPEN表的首部。211.把初始节点S0放入OPEN表。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n不可扩展，则转第2步。6.扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。222831476528314765283167542318476528314765281637542816375428316475283164762831647528316754S01234...523•在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到解。但是，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。所以深度优先搜索是不完备的，即使问题有解，它也不一定能求得解。•用深度优先求得的解，不一定是路径最短的解。24基本思想：–对深度优先搜索引入搜索深度的界限（设为dm），当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。搜索过程：1.把初始节点S0放入OPEN表中，置S0的深度d(S0)=0。2.如果OPEN表为空，则问题无解，退出。3.把OPEN表的第一个节点（记为节点n）取出放入CLOSE表。4.考察节点n是否为目标节点。若是，则求得了问题的解，退出。5.若节点n的深度d(节点n)=dm，则转第2步。6.若节点n不可扩展，则转第2步。7.扩展节点n，将其子节点放入OPEN表的首部，并为每一个子节点都配置指向父节点的指针，然后转第2步。25•如果问题有解，且其路径长度≤dm，则上述搜索过程一定能求得解。但是，若解的路径长度dm,则上述搜索过程就得不到解。这说明在有界深度优先搜索中，深度界限的选择是很重要的。•要恰当地给出dm的值是比较困难的。即使能求出解，它也不一定是最优解。261.先任意设定一个较小的数作为dm，然后进行上述的有界深度优先搜索，当搜索达到了指定的深度界限dm仍未发现目标节点，并且CLOSE表中仍有待扩展节点时，就将这些节点送回OPEN表，同时增大深度界限dm，继续向下搜索。如此不断地增大dm，只要问题有解，就一定可以找到它。但此时找到的解不一定是最优解。2.为了找到最优解，可增设一个表R，每找到远程目标节点Sg后，就把它放入到R的前面，并令dm等于该目标节点所对应的路径长度，然后继续搜索。由于后求得的