状态空间的搜索策略

1、状态空间的搜索策略一般说来，搜索策略讨论对于具有树状结构图的问题状态空间更加方便。因此，对于非树状结构 图的问题，例如网状结构等，往往需要化为树状结构图，以便更好地应用搜索策略进行讨论。（1）广度优先搜索先进先岀，生成的节点插入open表的后面。基本方法：从根节点so开始，向下逐层逐个地对节点进行扩展与穷尽搜索，并逐层逐个地考察 所搜索节点是否满足目标节点sg的条件。若到达冃标节点sg,则搜索成功，搜索过程可以终 止。注意：在广度优先搜索法的过程屮，同一层的节点搜索次序可以任意；但在第n层的节点 没有全部扩展并考察z前，不应对第n+1层的节点进行扩展和考察。特点：显然，宽度优先搜索法是一种遵循

2、规则的盲日性搜索，它遍访了目标节点前的每一层次每 一个节点，即检查了日标节点前的全部的状态空间点，只要问题有解，它就能最终找到解，且最 先得到的将是最小深度的解。可见，宽度优先搜索法很可靠。但是，当冃标节点距离初始节点较 远时将会产生许多无用的中间节点。因此，速度慢，效率低，尤其对于庞大的状态空间实用价 值差。（2）深度优先搜索后进先出，生成的节点插入open表的前面。基本方法：从根节点so开始，始终沿着纵深方向搜索，总是在其后继子节点中选择一节点来考 察。若到达目标节点sg,则搜索成功；若不是目标节点，则再在该节点的后继子节点中选一考 察，一直如此向下搜索，直到搜索找到甘标节点才停下来。若到

3、达某个子节点时，发现该节点既 不是冃标节点又不能继续扩展，就选择其兄弟节点再进行考察。依此类推，直到找到冃标节点或 全部节点考察完毕，搜索过程才可以终止或结束。特点：方式灵活，规则易于实现，对于有限状态空间并有解时，必能找到解。例如，当搜索到某 个分支时，若目标节点恰好在此分支上，则可较快地得到解。故在一定条件下，可实现较高求解 效率。但是，在深度优先搜索中，一旦搜索进入某个分支，就将沿着该分支一直向下搜索。这时, 如果冃标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。可见，深度优先 搜索算法不完备，风险大，易于掉入陷阱。因此，要使深度优先搜索算法可用，必须加以改造。（3）有界

4、深度优先后进先出，设置节点深度dm,在步骤4后需考察节点深度，如达到 深度转步骤7基本思想：设定一个搜索深度的界限dm ,当搜索深度达到dm ,而尚未出现目标节点时，可 回朔换一个分支进行搜索，直到dm的深度内所有分支节点搜索完毕。如果问题有解，且其路径长度v=dm,则搜索过程一定能求得解。dm的选择：（dm自适应）先任意给定一个较小的数作为dm,进行有界深度的优先搜索，当 深度达dm时仍未发现目标节点，11 close表屮仍有待扩展节点时，将这些节点送回open 表，同时增大深度界限dm,继续向下搜索。只要有解，一定可以找到。为找到最优解，可增设一个表（r）,每找到一个冃标节点sg后，就把它

5、放入到r的前面，并 令dm等于该冃标节点所对应的路径长度，然后继续搜索。由于最后求得的解的路径长度不会 超过先求得的解的路径长度，所以最后求得的解一定是最优解。（4）代价树的广度优先搜索边上标有代价（或费用）的称为代价树。c (x1, x2)表示父节点"到子节点x2的代价。初始节点so到节点x的代价用g (x)表示，g (x2) =g (x1) + c (x1, x2)扩展的m集合，添加到open表尾部，然后对整个open表中的节点计算其代价，由小到大排 序。w五间旳交通间路bb. ajt出火地.u是目 的坨. mmttt间的sub费用(代价)如田中數手所示.水从ajwe旳瑕小路费用

6、文通踣銭。从初始予点a开妬.把与它宜按相邻的莎魂作 为它的子予点0暂一个书点巳作为条术的jl取先* 节人时 敢不炖k作为 达个¥虫的子节点0hb中檢施越莎点外. 其它p点都可魁嬰在代价 打中出现决.为区别之用下标i. 2. 3. 楊出(5) 代价树的深度优先搜索从刚扩展的子节点中选一个代价最小的节点送入close表进行考察。(6) 启发式搜索启发信息：在智能搜索中，人们常把搜索中岀现的诸如问题的状态条件、性质、发展动态、解的 过程特性、结构特性等规律，问题求解的技巧性规则等，都称z为搜索的启发信息。所谓启发式搜索(heuristic search)策略，即利用与问题解有关的启发信息来作引导的搜索策 略。估价函数：f (x) =g (x) 4-h (x)g (x):从so到节点x已经实际付出的代价。指出了搜索的横向趋势、完备性好、但效率差。h (x):是从节点x到目标节点sg的最优路径的估计代价称为启发函数f (x):从so经过节点x到达日标节点sg的最优路径的代价估计值，作用是估价open表中 各节点的重要性，决定open表的次序。人工智能问题求解屮，往往需要的是设法找