状态空间的搜索策略

《状态空间的搜索策略》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

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

4、先搜索算法不完备，风险大，易于掉入陷阱。因此，要使深度优先搜索算法可用，必须加以改造。（3）有界深度优先——后进先出，设置节点深度dm,在步骤4后需考察节点深度，如达到深度转步骤7基本思想：设定一个搜索深度的界限dm,当搜索深度达到dm,而尚未出现目标节点时，可回朔换一个分支进行搜索，直到dm的深度内所有分支节点搜索完毕。如果问题有解，且其路径长度v=dm,则搜索过程一定能求得解。dm的选择：（dm自适应）先任意给定一个较小的数作为dm,进行有界深度的优先搜索，当深度达dm时仍未发现目标节点，11CLOSE表屮仍有待扩展节点时，将这些节点送回OPEN表，

5、同时增大深度界限dm,继续向下搜索。只要有解，一定可以找到。为找到最优解，可增设一个表（R）,每找到一个冃标节点Sg后，就把它放入到R的前面，并令dm等于该冃标节点所对应的路径长度，然后继续搜索。由于最后求得的解的路径长度不会超过先求得的解的路径长度，所以最后求得的解一定是最优解。（4）代价树的广度优先搜索边上标有代价（或费用）的称为代价树。c(x1,x2)表示父节点"到子节点x2的代价。初始节点sO到节点x的代价用g(x)表示，g(x2)=g(x1)+c(x1,x2)扩展的M集合，添加到OPEN表尾部，然后对整个OPEN表中的节点计算其代价，由小到大排

6、序。w五间旳交通间路BB.AJt出火地.U是目的坨.MMtTt间的SUB费用(代价)如田中數手所示.水从AJWE旳瑕小路费用文通踣銭。①从初始予点A开妬.把与它宜按相邻的莎魂作为它的子予点0暂一个书点巳作为条〒术的JL取先节人时敢不炖k作为达个¥虫的子节点0HB中檢施越莎点外.其它P点都可魁嬰在代价打中出现■决.为区别之・用下标I.2.3・..・楊出(5)代价树的深度优先搜索从刚扩展的子节点中选一个代价最小的节点送入CLOSE表进行考察。(6)启发式搜索启发信息：在智能搜索中，人们常把搜索中岀现的诸如问题的状态条件、性质、发展动态、解的过程特性、结构特

7、性等规律，问题求解的技巧性规则等，都称Z为搜索的启发信息。所谓启发式搜索(HeuristicSearch)策略，即利用与问题解有关的启发信息来作引导的搜索策略。估价函数：f(x)=g(x)4-h(x)g(x):从SO到节点x已经实际付出的代价。指出了搜索的横向趋势、完备性好、但效率差。h(x):是从节点x到目标节点Sg的最优路径的估计代价称为启发函数f(x):从SO经过节点x到达日标节点Sg的最优路径的代价估计值，作用是估价OPEN表中各节点的重要性，决定OPEN表的次序。人工智能问题求解屮，往往需要的是设法找到一个好的启发函数。局部择优搜索深度优先搜索

8、方法的一种改进。节点扩展成子节点时，按f(x)对子节点进行估算，选择最小者作为下