状态空间搜索策略

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

1、第三章状态空间搜索策略3.1搜索的概念及种类3.2盲目搜索策略3.3启发式搜索策略例1走迷宫是人们熟悉的一种游戏，如图就是一个迷宫。如果我们把该迷宫的每一个格子以及入口和出口都作为节点，把通道作为边，则该迷宫可以由一个有向图表示。我们通过例子引入状态空间搜索的概念。迷宫的有向图表示走迷宫其实就是从该有向图的初始节点(入口)出发，寻找目标节点(出口)的问题，或者是寻找通向目标节点(出口)的路径的问题。例2在一个3×3的方格棋盘上放置着1,2,3,4,5,6,7,8八个数码，每个数码占一格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在的问题是：对于指定的

2、初始棋局和目标棋局(如图)，给出数码的移动序列。该问题称为八数码难题或重排九宫问题。2831476581324765初始棋局目标棋局状态空间（图）是一类问题的抽象表示，有许多智力问题(如Hanoi塔问题、旅行商问题、八皇后问题、农夫过河问题等)和实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在状态空间(图)中寻找目标或路径的问题。因此，研究状态空间搜索具有普遍意义。3.1搜索的概念及种类现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步地摸索着前进。搜索：是一种求解问题的方法，是寻找从问题初始事实到最终答案

3、的推理路线的一种过程。搜索包含两层含义：一是根据问题的实际情况，按照一定的策略，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线；另一是找到的这条路线是时空复杂度最小的求解路线。3.1.1搜索的概念盲目搜索：又称无信息搜索。即在搜索过程中，只按预先规定的搜索控制策略进行搜索。问题本身的特性对搜索控制策略没有任何影响，搜索带有盲目性，效率不高，只用于解决比较简单的问题。启发式搜索：又称有信息搜索。指在搜索求解过程中，根据问题本身的特性来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。搜索求解的效率高，易于求解复杂的问题，但抽取出问题的相

4、关特性和信息难。3.1.2搜索的种类搜索分为盲目搜索和启发式搜索两种。状态空间表示法：是一种用状态和算符表示问题的方法。当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。状态空间图：状态空间的图示表示问题形式。状态空间图是一个有向图，节点表示状态，有向边（弧）表示算符。3.2盲目搜索策略3.2.1状态空间图的搜索策略状态空间图对问题的求解就相当于在有向图上寻找一条从某一节点(初始状态节点)到另一节点(目标状态节点)的路径。搜索法求解问题的基本思想：首先将问题的初始状态(初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(后继节点)，然

5、后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。节点扩展概念扩展：就是用合适的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求后继节点的过程。已扩展节点：对状态空间图中的某个节点，如果求出了它的后继节点，则此节点为已扩展的节点。未扩展节点：对状态空间图中的某个节点，如果尚未求出它的后继节点，则此节点称为未扩展节点。在对状态空间图搜索求解时，将未扩展的节点存于一个名为OPEN的表中，而将已扩展

6、的节点存于一个名为CLOSED的表中。状态空间图的一般搜索策略：搜索的目的是为了寻找初始节点到目标节点的路径，所以在搜索过程中就得随时记录搜索轨迹。我们用一个称为CLOSED表的动态数据结构来专门记录考查过的节点（已扩展的节点）。CLOSED表中存储的是一棵不断成长的搜索树。另一方面，还得不断地把待考查的节点（未扩展的节点）组织在一起，并做某种排列，以便控制搜索的方向和顺序。我们采用一个称为OPEN表的动态数据结构，来专门登记当前待考查的节点。(1)建立一个只含有初始节点S0的搜索图G，把S0放人OPEN表中。(2)建立CLOSED表，且置为空表。(3)判断OPEN表是否为空表，若为空，则问

7、题无解，退出。(4)若OPEN表非空，选择OPEN表中的第一个节点，把它从OPEN表移出，并放人CLOSED表中，将此节点记为节点n。(5)考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从图G中沿着指针从n到S0的这条路径得到。(6)扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中。(7)对那些未曾在G中出现过的M中的节点，设置一个