张仰森全套配套课件人工智能教程第2版 第5章.ppt

《张仰森全套配套课件人工智能教程第2版 第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章状态空间搜索策略5.1搜索的概念及种类5.1.1搜索的概念现实世界中的大多数问题都是非结构化问题，一般不存在现成的求解方法来求解这样的问题，而只能利用已有的知识一步一步的摸索着前进。在这一过程中，所要解决的问题是如何寻找可利用的知识，即如何确定推理路线，才能使在付出尽量少的代价的前提下把问题圆满解决。如果存在多条路线可实现对问题的求解，那就又存在着这样的问题，即如何从这多条求解路线中，选出一条使它的求解代价最小，以提高求解程序的运行效率。像这样根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程，就称为搜索。所以搜索包含两

2、层含义，一层含义是要找到从初始事实到问题最终答案的一条推理路线，另一层含义是找到的这条路线是时间和空间复杂度最小的求解路线。5.1搜索的概念及种类5.1.2搜索的种类搜索分为盲目搜索和启发式搜索两种。盲目搜索又称无信息搜索，也就是说，在搜索过程中，只按预先规定的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略。由于这种搜索其控制策略都是预定的，不管什么问题都采用这样的控制策略——即问题本身的特性对搜索控制策略没有任何影响，这就使得这样的搜索带有盲目性，效率不高。如果碰到比较复杂的问题，其求解的效率可能就相当低，所以盲目搜索只用于解决比较简单的问题。启发式搜索又称有信息搜索，它是指

3、在搜索求解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。虽然启发式搜索由于考虑到问题本身的特性并利用这些特性，从而使搜索求解的效率更高，更易于求解复杂的问题，然而并不是对所有的问题都能方便地抽取出问题的相关特性和信息，因此尽管启发式搜索好于盲目搜索，但盲目搜索也会在很多问题的求解中得到应用。5.2盲目搜索策略5.2.1状态空间图的搜索策略在第二章中我们已经指出，可以用状态空间对一个问题进行表示，而且这一表示也可以使用图示的方式，这种图示的方式称作状态空间图。当把一个待求解的问题表示为状态空间以后

4、，就可以通过对状态空间的搜索，实现对问题的求解。搜索法求解问题的基本思想就是：首先将问题的初始状态（即状态空间图中的初始节点）当作当前状态，选择一适当的算符作用于当前状态，生成一组后继状态（或称后继节点），然后检查这组后继状态中有没有目标状态。如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解；若没有，则按照某种控制策略从已生成的状态中再选一个状态作为当前状态，重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。5.2盲目搜索策略下面给出状态空间图的一般搜索策略。这里先说明一下已扩展节点和未扩展节点的概念。所谓扩展就是用合适的算符对某个节点进行操作生成一组后

5、继节点，扩展过程实际上就是求后继节点的过程。所以，对状态空间图中的某个节点，如果求出了它的后继节点，则此节点为已扩展的节点，而尚未求出它的后继节点的节点称为未扩展节点。将未扩展的节点存于一个名为OPEN的表中，而将已扩展的节点存于一个名为CLOSED的表中。OPEN表的数据结构及CLOSED表的数据结构分别如表5.1和表5.2所示。状态节点父节点编号状态节点父节点表5.1OPEN表结构表5.2CLOSED表结构5.2盲目搜索策略状态空间图的搜索算法如下：算法5.1状态空间图的一般搜索算法(1)建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中。(2)建立CLOSED表，且置为空表

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

7、要修改指向父节点（n节点）的指针；对于那些先前已在G中出现并且已在COLSED表中的那些M中的节点，确定是否需要修改通向它们后继节点的指针。(8)按某一任意方式或按某种策略重排OPEN表中节点的顺序。(9)转第（3）步。图5.1状态空间的搜索过程框图开始初始化：把S0放入OPEN表，CLOSED表置空OPEN为空表？失败,退出出把OPEN表中的第一个节点（n）移至CLOSED表中n为目标节点吗？成功，退出若n的后继未曾在