人工智能之盲目搜索培训课件.ppt

《人工智能之盲目搜索培训课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第1章搜索问题——一种在图中寻找路径的方法。2831476581324765八数码魔方1.1搜索问题－知识的表示方法初始节点S0目标节点Sg状态空间表示状态（State）的基本概念状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：Q=[q0,q1,…,qn]T(1)式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=[q0k,q1k,…，qnk]T(2)例如，八数码魔方中，所有初始节点S0构成初始节点状态集合Q；所有目标节点Sg构成目标节点状态集合Q。当Q中每个分

2、量取定一个值时，就得到一个具体的状态集合，如例子中的就是Q0，而就是Qk。2831476581324765问题求解技术主要是两个方面：问题的表示求解的方法问题的状态空间(statespace)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、算符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。例如，例子中的八数码魔方问题就可以用三元状态空间表示为（S0，F，Sg）其中，S0代表初始状态，Sg代表目标状态

3、，而F就是所有能将初始状态变化为目标状态的算符集合。举例：012x012y迷宫问题整个迷宫问题的知识表示是如书上第10页的图2.3，这是一种状态图知识表示法。问题是：机器人位于迷宫入口(0，0)处，如何到达迷宫的出口(2，2)。解：问题空间的初始状态是节点(0,0),而目标状态是节点(2,2)。从图2.3可见，从(0,0)到(2,2)需经过(U，R，R，U)算符集合的操作，因此本问题的解用三元状态集合表示为：{(0,0),(U,R,R,U),(2,2)}与图有关的术语状态空间图——由节点(不一定是有限的节点)及连接节点的分枝的集合构成。有限节点图——节点数目有限的图称为有限节点图。有向图——

4、一对节点用分枝线连接起来，从一个节点指向另一个节点。这种图叫做有向图。始节点叫父节点或双亲节点，终节点叫子节点。扩展——求解父节点的所有子节点，叫做扩展。路径——在一系列节点n1,n2,,nm中，从n1开始，ni总有分枝连接ni+1，称从n1到nm之间的分枝集合是路径。路径中不包含两个及以上相同的分枝，如果n1和nm是同一个节点，则称这种路径为闭路。不构成闭路的称为树。在用状态空间图来表示问题时，对问题的求解就是求出从初始节点到目标节点的路径。§1.2图搜索策略1.图搜索的定义——一种计算机在状态图中寻找路径的方法。2.CLOSED表的引入编号节点号父节点号CLOSED表(记录扩展过的节

5、点)OPEN表的引入节点号父节点号OPEN表(记录待扩展的节点)举例：八数码魔方例子中OPEN表变化过程节点号父节点号S0空AS0BS0CS0DS0EAFACLOSED表变化过程编号节点号父节点号0S0空1AS02BS0图搜索的一般过程(1)建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN表的未扩展节点表中。(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。(3)LOOP：若OPEN表是空表，则失败退出。(4)选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着

6、指针从n到S这条路径而得到的(指针将在第7步中设置)。图搜索的一般过程(6)扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点添入图G中。(7)对那些未曾在G中出现过的(既未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN或CLOSED表上的每一个M成员，确定是否需要更改通到n的指针方向。对已在CLOSED表上的每个M成员，确定是否需要更改图G中通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排OPEN表。(9)GOLOOP。开始把S放入OPEN表OPEN表为空表？

7、把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图搜索一般过程的框图是是否否1.3无信息图搜索过程深度优先搜索（纵向搜索）宽度优先搜索（横向搜索）均一代价搜索1.深度优先搜索定义首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索或纵向搜索。特点扩展最深的