第03章搜索推理技术ppt课件.ppt

《第03章搜索推理技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、三、搜索推理技术1.搜索的概念和种类2.图搜索策略3.盲目搜索4.启发式搜索概述搜索是人工智能的一个基本问题，是推理不可分割的一部分；搜索是求解问题的一种方法；为了利用搜索的方法求解问题，首先必须将被求解的问题用某种形式表示出来3.1.搜索的概念和种类搜索根据问题的实际情况，按照一定的策略或规则，从知识库中寻找可利用的知识，从而构造出一条使问题获得解决的推理路线的过程。含义从初始事实到问题答案的一条推理路线；找到的这条路线是时间和空间复杂度最小的求解路线。搜索的概念盲目搜索（无信息搜索）：在搜索过程中，只按照预定的搜索控制策略进行搜索，而没有任何中

2、间信息来改变这些控制策略。搜索带有盲目性，效率不高，如果遇到比较复杂的问题，其求解的效率可能就相当低。用于解决比较简单的问题。搜索的种类启发式搜索（有信息搜索）：在搜索求解过程中，根据问题本身的特性或搜索过程中产生的一些信息来不断地改变或调整搜索的方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。虽然启发式搜索由于考虑到问题本身的特性并利用这些特性，从而使搜索求解的效率更高，更易于求解复杂的问题，然而并不是对所有的问题都能方便地抽取问题的有关特性和信息，因此尽管启发式搜索好于盲目搜索，但盲目搜索也会在很多问题的求解中得到应用。搜索的

3、种类3.2.图搜索策略什么是状态空间图？使用图示的方式用状态空间图对一个问题进行描述的方法。状态空间图是一个有向图。当把一个待求解的问题表示为状态空间以后，就可以通过对状态空间的搜索，实现对问题的求解。如果从状态空间的角度来看，则对问题的求解就相当于在有向图上寻找一条从某一节点（初始状态节点）到另一节点（目标节点）的路径。3.2.图搜索策略（1）若要把表示问题的整个状态空间都存入计算机，往往需要占据巨大的存储空间，尤其对比较复杂的问题，这几乎是不能实现的。并且一般也无这种必要。因为对于一个具体的问题，其解往往只与状态空间的一部分相关，只要计算机生成

4、并存储与问题有关的解状态空间部分，即可将问题解决。如何来生成并存储与问题有关的部分状态空间？3.2.图搜索策略（2）求解的基本思想（1）将问题的初始状态（状态空间图中的初始节点）当作当前节点，选择一适当的算符作用于当前状态，生成一组后继状态（或后继节点）。（2）检查这组后继状态中有没有目标状态，如果有，则说明搜索成功，从初始状态到目标状态的一系列算符即是问题的解。（3）若没有，则按照某种控制策略从已生成的状态中再选择一个状态作为当前状态。（4）重复上述过程，直到目标状态出现或不再有可供操作的状态及算符时为止。3.2.图搜索策略（3）状态空间图是由节

5、点和分支构成的集合。节点数目有限的状态空间图被称为有限节点图。一个分支连接两个节点，其中有方向的分支称为有向分支，没有方向的称为无向分支。当存在从节点N1到节点N2的路径时，节点N1被称为节点N2的父节点；节点N2被称为节点N1的子节点。如果从N1到N2的路径只有一条的时候，而且两端的节点相同，则这种路径称为闭路。3.2.图搜索策略（4）3.2.图搜索策略（5）已扩展节点用适合的算符对某个节点进行操作生成一组后继节点，扩展过程实际上就是求后继节点的过程。所以，对状态空间图的某个节点，如果求出了它的后继节点，则此节点为已扩展的节点，而尚未求出它的后继

6、节点的节点称为未扩展节点。状态节点父节点未扩展OPEN表编号状态节点父节点扩展CLOSED表3.2.图搜索策略（6）状态空间的搜索算法如下：（1）建立一个只含有初始节点S的搜索图G,把S放入OPEN表中。（2）建立CLOSED表，且置为空表。（3）LOOP:若OPEN表是空表，则失败退出。（4）选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中，称此节点为节点n。（5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的。（6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成

7、员作为n的后继节点添入图G中。（7）对那些未曾在G中出现过的，M成员设置一个通向n的指针，把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。（8）按某一任意方式或按某个试探值，重排OPEN表。（9）GOLOOP3.2.图搜索策略（7）开始节点n是否为目标节点失败退出YN根据后入先出或先入先出的原则从Open表中选择一个节点，并置为n将n的子节点中未包含在Closed表中的节点加入Open表中Ope

8、n表是否空成功退出YN将初始节点加入Open表Closed表置空3.2.图搜索策略（8）各种搜索策略的主要区别第（8）步对