人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
第五章 状态空间搜索策略
搜索是人工智能的一个基本问题，是推理不可分割的一部分。搜索是求解问题的一种方法，是根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。搜索包含两层含义：一层含义是要找到从初始事实到问题最终答案的一条推理路线；另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。搜索可分为盲目搜索和启发式搜索两种。 1．1 盲目搜索策略 1．状态空间图的搜索策略
为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来。一般情况下，不同的知识表示对应着不同的求解方法。状态空间表示法是一种用“状态”和“算符”表示问题的方法。状态空间可由一个三元组表示(S0，F，Sg)。
利用搜索方法求解问题的基本思想是：首先将问题的初始状态(即状态空间图中的初始节点)当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态(或称后继节点)，然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。
算法5．1 状态空间图的一般搜索算法
①建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中。 ②建立CLOSED表，且置为空表。
③判断OPEN表是否为空表，若为空，则问题无解，退出。
④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，
1 / 6
人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
将此节点记为节点n。
⑤考察节点n是否为目标节点，若是，则问题有解，并成功退出。问题的解即可从图G中沿着指针从n到S0的这条路径得到。
⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记作集合M，将M中的这些节点作为n的后继节点加入图G中。
⑦对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M中的节点，设置一个指向父节点(即节点n)的指针，并把这些节点加入OPEN表中；对于已在G中出现过的M中的那些节点，确定是否需要修改指向父节点(n节点)的指针；对于那些先前已在G中出现并且已在COLSED表中的M中的节点，确定是否需要修改通向它们后继节点的指针。
⑧按某一任意方式或按某种策略重排OPEN表中节点的顺序。 ⑨转第③步。 2．宽度优先搜索策略
宽度优先搜索是一种盲目搜索策略。其基本思想是，从初始节点开始，逐层对节点进行依次扩展，并考察它是否为目标节点，在对下层节点进行扩展(或搜索)之前，必须完成对当前层的所有节点的扩展(或搜索)。在搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在后面(即将扩展得到的后继节点放于OPEN表的末端)。
宽度优先搜索的盲目性较大，搜索效率低，这是它的缺点。但宽度优先搜索策略是完备的，即只要问题有解，用宽度优先搜索总可以找到它的解。 3．深度优先搜索
深度优先搜索也是一种盲目搜索策略，其基本思想是：首先扩展最新产生的(即最深的)节点，即从初始节点S0开始，在其后继节点中选择一个节点，对其进行考察，若它不是目标节点，则对该节点进行扩展，并再从它的后继节点中选择
2 / 6
人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
一个节点进行考察。依此类推，一直搜索下去，当到达某个既非目标节点又无法继续扩展的节点时，才选择其兄弟节点进行考察。
深度优先搜索与宽度优先搜索的区别就在于：在对节点n进行扩展时，其后继节点在OPEN表中的存放位置。宽度优先搜索是将后继节点放入OPEN表的末端，而深度优先搜索则是将后继节点放入OPEN表的前端。 4．有界深度优先搜索
对于许多问题，其状态空间搜索树的深度可能为无限深。为了避免搜索过程沿着无穷的路径搜索下去，往往对一个节点扩展的最大深度进行限制。任何节点如果达到了深度界限，就把它作为没有后继节点进行处理，即对另一个分支进行搜索。
在有界深度优先搜索算法中，深度界限的选择很重要。选择过大，可能会影响搜索的效率；选择的过小，有可能求不到解。有界深度优先搜索策略是不完备的。
5．代价树的宽度优先搜索
前面的搜索算法没有考虑搜索的代价问题，即假设状态空间图中各节点之间的有向边的代价是相同的。在实际问题求解中，往往是将一个状态变换成另一个状态时所付出的操作代价(或费用)是不一样的，即状态空间图中各有向边的代价是不一样的。把有向边上标有代价的搜索树称为代价搜索树，简称代价树。 代价树宽度优先搜索的基本思想是：每次从OPEN表中选择一个代价最小的节点，移入COLSED表。因此，每当对一节点扩展之后，就要计算它的所有后继节点的代价，并将它们与OPEN表中已有的待扩展的节点按代价的大小从小到大依次排序。而从OPEN表选择被扩展节点时即选择排在最前面的节点(代价最小)。代价树的宽度优先搜索算法是一个完备算法。 6．代价树的深度优先搜索
代价树的深度优先搜索和宽度优先搜索的区别是：宽度优先搜索法每次从
3 / 6
人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
