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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第,1,章 搜索问题,一个在图中寻找路径方法。,人工智能之盲目搜索培训课件,第1页,2,8,3,1,4,7,6,5,8,1,3,2,4,7,6,5,八数码魔方,1.1,搜索问题知识表示方法,初始节点,S,0,目标节点,S,g,人工智能之盲目搜索培训课件,第2页,状态空间表示,状态（,State,）基本概念,状态,(state),是为描述某类不一样事物间差异而引入一组最少变量,q,0,，,q,1,，,，,q,n,有序集合，其矢量形式以下：,Q=q,0,q,1,q,n,T,(1),式中每个元素,q,i,(i=0,1,，,，,n),为集合分量，称为状态变量。给定每个分量一组值就得到一个详细状态，如,Q,k,=q,0k,q,1k,，,q,nk,T,(2),人工智能之盲目搜索培训课件,第3页,比如，八数码魔方中，全部初始节点,S,0,组成初始节点状态集合,Q,；全部目标节点,S,g,组成目标节点状态集合,Q,。,当,Q,中每个分量取定一个值时，就得到一个详细状态集合，如例子中 就是,Q,0,，,而 就是,Q,k,。,2,8,3,1,4,7,6,5,8,1,3,2,4,7,6,5,人工智能之盲目搜索培训课件,第4页,问题求解技术主要是两个方面：,问题表示,求解方法,人工智能之盲目搜索培训课件,第5页,问题状态空间,(state space),是一个表示该问题全部可能状态及其关系图，它包含三种说明集合，即全部可能问题初始状态集合,S,、算符集合,F,以及目标状态集合,G,。所以，可把状态空间记为三元状态,(S,，,F,，,G),。,人工智能之盲目搜索培训课件,第6页,算符,：使问题从一个状态改变为另一个状态伎俩称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。,人工智能之盲目搜索培训课件,第7页,比如，例子中八数码魔方问题就能够用三元状态空间表示为,（,S,0,，,F,，,S,g,）,其中，,S,0,代表初始状态，,S,g,代表目标状态，而,F,就是全部能将初始状态改变为目标状态算符集合。,人工智能之盲目搜索培训课件,第8页,举例：,0,1,2,x,0,1,2,y,迷宫问题,人工智能之盲目搜索培训课件,第9页,整个迷宫问题知识表示是如书上第,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),人工智能之盲目搜索培训课件,第10页,与图相关术语,状态空间图,由节点,(,不一定是有限节点,),及连接节点分枝集合组成。,有限节点图,节点数目有限图称为有限节点图。,有向图,一对节点用分枝线连接起来，从一个节点指向另一个节点。这种图叫做有向图。始节点叫父节点或双亲节点，终节点叫子节点。,人工智能之盲目搜索培训课件,第11页,扩展求解父节点全部子节点，叫做扩展,。,路径在一系列节点,n,1,n,2,n,m,中，从,n,1,开始，,n,i,总有分枝连接,n,i+1,，称从,n,1,到,n,m,之间分枝集合是路径。路径中不包含两个及以上相同分枝，假如,n,1,和,n,m,是同一个节点，则称这种路径为闭路。不组成闭路称为树。,在用状态空间图来表示问题时，对问题求解就是求出从初始节点到目标节点路径。,人工智能之盲目搜索培训课件,第12页,1.2,图搜索策略,1.,图搜索定义,一个计算机在状态图中寻找路径方法。,人工智能之盲目搜索培训课件,第13页,2.CLOSED,表引入,编号,节点号,父节点号,CLOSED,表,(,统计扩展过节点,),人工智能之盲目搜索培训课件,第14页,OPEN,表引入,节点号,父节点号,OPEN,表,(,统计待扩展节点,),人工智能之盲目搜索培训课件,第15页,举例：八数码魔方例子中,人工智能之盲目搜索培训课件,第16页,OPEN,表改变过程,节点号,父节点号,S,0,空,A,S,0,B,S,0,C,S,0,D,S,0,E,A,F,A,人工智能之盲目搜索培训课件,第17页,CLOSED,表改变过程,编号,节点号,父节点号,0,S,0,空,1,A,S,0,2,B,S,0,人工智能之盲目搜索培训课件,第18页,图搜索普通过程,(1),建立一个只含有起始节点,S,搜索图,G,，把,S,放到一个叫做,OPEN,表未扩展节点表中。,(2),建立一个叫做,CLOSED,已扩展节点表，其初始为空表。,(3)LOOP,：若,OPEN,表是空表，则失溃退出。,(4),选择,OPEN,表上第一个节点，把它从,OPEN,表移出并放进,CLOSED,表中。称此节点为节点,n,。,(5),若,n,为一目标节点，则有解并成功退出，此解是追踪图,G,中沿着指针从,n,到,S,这条路径而得到,(,指针将在第,7,步中设置,),。,人工智能之盲目搜索培训课件,第19页,图搜索普通过程,(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)GO LOOP,。,人工智能之盲目搜索培训课件,第20页,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,n,为目标节点吗？,把,n,后继节点放入,OPEN,表末端，提供返回节点,n,指针,修改指针方向,重排,OPEN,表,失败,成功,图搜索普通过程框图,是,是,否,否,人工智能之盲目搜索培训课件,第21页,1.3,无信息图搜索过程,深度优先搜索（纵向搜索）,宽度优先搜索（横向搜索）,均一代价搜索,人工智能之盲目搜索培训课件,第22页,1.,深度优先搜索,定义,首先扩展最新产生,(,即最深,),节点,。,深度相等节点能够任意排列。这种盲目,(,无信息,),搜索叫做,深度优先,搜索,或,纵向搜索。,特点,扩展最深节点结果使得搜索沿着状态空间某条单一路径从起始节点向下进行下去；只有当搜索抵达一个没有后代状态时，它才考虑另一条替换路径。,人工智能之盲目搜索培训课件,第23页,为了预防搜索过程沿着无益路径扩展下去，往往给出一个节点扩展最大深度,深度界限。,深度优先,搜索算法是一个“后进先出”算法,。,人工智能之盲目搜索培训课件,第24页,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,扩展,n,，把其后代放入,OPEN,表前头,失败,成功,深度优先,搜索算法框图,是,否,是,否,是否有后继节点,为目标节点？,S,是否为目标节点？,成功,是,否,人工智能之盲目搜索培训课件,第25页,八数码魔方,深度优先,搜索树,人工智能之盲目搜索培训课件,第26页,2.,宽度优先搜索,定义,以靠近起始节点程度逐层扩展节点搜索方法,(breadth-first search),，这种盲目,(,无信息,),搜索叫做宽度优先搜索或横向搜索。,特点,一个高代价搜索，但若有解存在，则必能找到它,。,人工智能之盲目搜索培训课件,第27页,算法,这种搜索是逐层进行；在对下一层任一节点进行搜索之前，必须搜索完本层全部节点。,宽度优先,搜索算法是一个“先进先出”算法,。,人工智能之盲目搜索培训课件,第28页,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,扩展,n,，把,n,后继节点放入,OPEN,表末端，提供返回节点,n,指针,失败,宽度优先搜索,算法框图,是,否,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,n,为目标节点吗？,成功,是,否,人工智能之盲目搜索培训课件,第29页,举例：,八数码魔方,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,（目标状态）,（初始状态,）,人工智能之盲目搜索培训课件,第30页,1,2,3,8,4,5,6,7,1,2,3,8,4,1,2,3,8,4,5,6,7,4,1,2,3,8,5,6,7,1,2,3,8,4,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,6,7,8,9,10,11,12,13,1,2,3,8,4,5,6,7,5,6,7,5,6,7,1,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,2,3,4,5,八数码魔方,宽度优先搜索,树,1,3,4,5,6,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,23,24,25,26,27,1,2,3,6,7,8,22,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,14,15,16,17,18,19,20,21,1,2,3,8,4,5,6,7,4,28,29,30,31,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,1,2,3,8,4,5,6,7,32,1,3,4,5,6,1,2,3,6,7,8,38,1,2,3,8,4,5,6,7,39,扩展,26,个节点，,共生成,46,个节点之后，才得到目标,人工智能之盲目搜索培训课件,第31页,3.,均一代价搜索,是横向搜索一个推广，不是沿着等长度路径断层进行扩展，而是沿着均一代价路径断层进行扩展。,搜索树中每条连接弧线上相关代价,表示时间、距离等花费。,若全部连接弧线含有相等代价，则简化为横向搜索算法。,人工智能之盲目搜索培训课件,第32页,均一代价搜索中几个记号：,起始节点记为,S,；,从节点,i,到它后继节点,j,连接弧线代价记为,c(i,，,j),；,从起始节点,S,到任一节点,i,路径代价记为,g(i),。,人工智能之盲目搜索培训课件,第33页,开始,把,S,放入,OPEN,表,OPEN,表为空表？,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,扩展,n,，把,n,后继节点放入,OPEN,表末端，提供返回节点,n,指针,失败,均一代价搜索算法框图,是,否,把第一个节点,(n),从,OPEN,表移至,CLOSED,表,n,为目标节点吗？,成功,是,否,按,g(i),值由小到大次序重排,OPEN,表,人工智能之盲目搜索培训课件,第34页,均一代价搜索法思绪：,1,、从,A,点开始依次展开得到,AB,（,7,）、,AC,（,3,）、,AD,（,10,）、,AE,（,15,）四个新结点，把第一层结点,A,标识为已展开，而且每个新结点要统计下其距离（括号中数字）；,2,、把未展开过,AB,、,AC,、,AD,、,AE,四个结点中距离最小一个展开，即展开,AC,（,3,）结点，得到,ACB,（,8,）、,ACD,（,16,）、,ACE,（,13,）三个结点，并把结点,AC,标识为已展开；,3,、再从未展开全部结点中找出距离最小一个展开，即展开,AB,（,7,）结点，得到,ABC,（,12,）、,ABD,（,20,）、,ABE,（,19,）三个结点，并把结点,AB,标识为已展开；,4,、再次从未展开全部结点中找出距离最小一个展开，即展开,ACB,（,8,）结点,；,5,、每次展开全部未展开结点中距离最小那个结点，直到展开新结点中出现目标情况（结点含有,5,个字母）时，即得到了结果。,人工智能之盲目搜索培训课件,第35页,算法分析：,由上可见，均一代价搜索法并没有象横向搜索一样展开全部结点，只是依据代价最小标准，每次展开距离,A,点最近那个结点，重复下去即可最终得到答案。即使中途有时也展开了一些并不是答案结点，但这种展开并不是大规模，不是全部展开，因而耗时要比横向搜索小得多。,人工智能之盲目搜索培训课件,第36页,迷宫问题以下，,F,是入口，,B,是出口，试采取均一代价搜索算法进行求解。,举例：迷宫问题,0,1,2,3,x,1,2,3,y,F,G,H,E,C,A,D,B,2,2,2,4,1,1,1,1,人工智能之盲目搜索培训课件,第37页,注：每个节点小括号内数值表示走到该节点所需付出代价。,F(0),G(1),H(3),E(2),C(3),A(6,4),D(5),B(6),1,2,3,4,5,6,7,8,搜索到路径为黄线所表示,人工智能之盲目搜索培训课件,第38页,