人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
第五章 状态空间搜索策略
搜索是人工智能的一个基本问题,是推理不可分割的一部分。搜索是求解问题的一种方法,是根据问题的实际情况,按照一定的策略或规则,从知识库中寻找可利用的知识,从而构造出一条使问题获得解决的推理路线的过程。搜索包含两层含义:一层含义是要找到从初始事实到问题最终答案的一条推理路线;另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。搜索可分为盲目搜索和启发式搜索两种。 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
人工智能[第五章状态空间搜索策略]山东大学期末考试知识点复习
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)