人工智能一般搜索原理.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,*,搜索技术,问题提出,：有了知识表示方法之后，就需要有处理问题方法，也就是搜索技术。所谓搜索，就是寻找一条从初始问题到问题解路径,本章内容,：搜索技术有许各种，本章介绍一些早期、比较简单搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术,关键问题,：,怎样利用知识，尽可能有效地找到问题解(最正确解)。,第三章 普通搜索原理,10/1/,1,人工智能一般搜索原理,第1页,普通搜索原理,搜索策略可分为三大类,不可撤回方式、回朔方式、图搜索方式,不可撤回方式,：每一次搜索时，利用局部知识依据最优评价，选出下一状态，选定后不能撤回，只能继续,回朔方式,：在搜索过程中，有时会发觉所选路径不适合找到目标，这时允许退回去另选一条路径。,图搜索方式：,假如把问题求解过程用图来表示。节点代表问题状态，弧代表状态改变方向，则搜索就变成对图进行从初始节点开始，到目标节点路径搜索。,第三章 普通搜索原理,3.1,盲目搜索,10/1/,2,人工智能一般搜索原理,第2页,回溯搜索策略,例：皇后问题,第三章 普通搜索原理,3.1,盲目搜索,10/1/,3,人工智能一般搜索原理,第3页,(),皇后问题搜索过程（一）,第三章 普通搜索原理,3.1,盲目搜索,10/1/,4,人工智能一般搜索原理,第4页,Q,(),(1,1),皇后问题搜索过程（二）,第三章 普通搜索原理,3.1,盲目搜索,10/1/,5,人工智能一般搜索原理,第5页,Q,Q,(),(1,1),(1,1)(2,3),皇后问题搜索过程（三）,第三章 普通搜索原理,3.1,盲目搜索,10/1/,6,人工智能一般搜索原理,第6页,Q,(),(1,1),(1,1)(2,3),皇后问题搜索过程（四）,第三章 普通搜索原理,3.1,盲目搜索,10/1/,7,人工智能一般搜索原理,第7页,Q,Q,(),(1,1),(1,1)(2,3),(1,1)(2,4),皇后问题搜索过程（五）,第三章 普通搜索原理,3.1,盲目搜索,10/1/,8,人工智能一般搜索原理,第8页,Q,Q,Q,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),第三章 普通搜索原理,3.1,盲目搜索,皇后问题搜索过程（六）,10/1/,9,人工智能一般搜索原理,第9页,Q,Q,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),第三章 普通搜索原理,3.1,盲目搜索,皇后问题搜索过程（七）,10/1/,10,人工智能一般搜索原理,第10页,Q,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),第三章 普通搜索原理,3.1,盲目搜索,皇后问题搜索过程（八）,10/1/,11,人工智能一般搜索原理,第11页,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),第三章 普通搜索原理,3.1,盲目搜索,皇后问题搜索过程（九）,10/1/,12,人工智能一般搜索原理,第12页,Q,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),第三章 普通搜索原理,3.1,盲目搜索,皇后问题搜索过程（十）,10/1/,13,人工智能一般搜索原理,第13页,Q,Q,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),第三章 普通搜索原理,3.1,盲目搜索,皇后问题搜索过程（十一）,10/1/,14,人工智能一般搜索原理,第14页,Q,Q,Q,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),(1,2)(2,4)(3,1),第三章 普通搜索原理,3.1,盲目搜索,皇后问题搜索过程（十二）,10/1/,15,人工智能一般搜索原理,第15页,Q,Q,Q,Q,(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(1,2),(1,2)(2,4),(1,2)(2,4)(3,1),(1,2)(2,4)(3,1)(4,3),第三章 普通搜索原理,3.1,盲目搜索,皇后问题搜索过程（十三）,10/1/,16,人工智能一般搜索原理,第16页,递归思想,从前有座山,从前有座山,从前有座山,第三章 普通搜索原理,3.1,盲目搜索,10/1/,17,人工智能一般搜索原理,第17页,一个递归例子,int ListLenght(LIST*pList),if(pList=NULL)return 0;,else return ListLength(pList-next)+1;,第三章 普通搜索原理,3.1,盲目搜索,10/1/,18,人工智能一般搜索原理,第18页,回溯搜索算法说明,BACKTRACK（DATA）,DATA：当前状态。,返回值：从当前状态到目标状态路径,（以规则表形式表示）,或FAIL。,第三章 普通搜索原理,3.1,盲目搜索,10/1/,19,人工智能一般搜索原理,第19页,回溯搜索算法（一）,递归过程BACKTRACK(DATA),1,IF TERM(DATA)RETURN NIL;,2,IF DEADEND(DATA)RETURN FAIL;,3,RULES:=APPRULES(DATA);,第三章 普通搜索原理,3.1,盲目搜索,TERM:找目标,DEADEND:状态不正当,无法继续搜索,APPRULES:取可应用规则集,10/1/,20,人工智能一般搜索原理,第20页,回溯搜索算法（二）,4,LOOP:IF NULL(RULES)RETURN FAIL;,5,R:=FIRST(RULES);,6,RULES:=TAIL(RULES);,7,RDATA:=GEN(R,DATA);,8,PATH:=BACKTRACK(RDATA);,9,IF PATH=FAIL GO LOOP;,10,RETURN CONS(R,PATH);,第三章 普通搜索原理,3.1,盲目搜索,TAIL:删除头条规则,GEN:调用规则作用于当前状态,CONS:获取解路径规则表,10/1/,21,人工智能一般搜索原理,第21页,存在问题及处理方法,问题：,深度问题:假如深度太深,死循环问题:假如状态出现重复,处理方法：,对搜索深度加以限制,统计从初始状态到当前状态路径,第三章 普通搜索原理,3.1,盲目搜索,10/1/,22,人工智能一般搜索原理,第22页,增加约束后回溯搜索算法,BACKTRACK1（DATALIST）,DATALIST：从初始到当前状态表（逆向）,返回值：从当前状态到目标状态路径,（以规则表形式表示）,或FAIL。,第三章 普通搜索原理,3.1,盲目搜索,10/1/,23,人工智能一般搜索原理,第23页,增加约束后回溯搜索算法(一),1,DATA:=FIRST(DATALIST),2,IF MENBER(DATA,TAIL(DATALIST),RETURN FAIL;,3,IF TERM(DATA)RETURN NIL;,4,IF DEADEND(DATA)RETURN FAIL;,5,IF LENGTH(DATALIST)BOUND,RETURN FAIL;,第三章 普通搜索原理,3.1,盲目搜索,10/1/,24,人工智能一般搜索原理,第24页,增加约束后回溯搜索算法(二),6,RULES:=APPRULES(DATA);,7,LOOP:IF NULL(RULES)RETURN FAIL;,8,R:=FIRST(RULES);,9,RULES:=TAIL(RULES);,第三章 普通搜索原理,3.1,盲目搜索,10/1/,25,人工智能一般搜索原理,第25页,增加约束后回溯搜索算法(三),10,RDATA:=GEN(R,DATA);,11,RDATALIST:=CONS(RDATA,DATALIST);,12,PATH:=BACKTRCK1(RDATALIST),13,IF PATH=FAIL GO LOOP;,14,RETURN CONS(R,PATH);,第三章 普通搜索原理,3.1,盲目搜索,10/1/,26,人工智能一般搜索原理,第26页,一些深入问题,失败原因分析、多步回溯,Q,Q,第三章 普通搜索原理,3.1,盲目搜索,10/1/,27,人工智能一般搜索原理,第27页,一些深入问题（续）,回溯搜索中知识利用,基本思想：,尽可能选取划去对角线上位置数最少。,Q,Q,Q,Q,4 3 3 4,第三章 普通搜索原理,3.1,盲目搜索,10/1/,28,人工智能一般搜索原理,第28页,模式导向搜索,这个算法是将递归搜索应用到谓词演算通用搜索算法,要判断一个谓词表示式是某个断言集合逻辑结论,首先谓词表示式作为目标，使用合一来选择能与其后件匹配蕴涵式,并把得到置换利用于该蕴涵式前件,这个前件成了新目标称其为子目标,应用递归搜索解这个子目标,假如与事实相匹配，则搜索坚固,第三章 普通搜索原理,3.1,盲目搜索,10/1/,29,人工智能一般搜索原理,第29页,模式导向搜索算法描述一,Function pattern_search(current_goal),begin,if current_goal is in closed then return FAIL,else put current_goal into closed,while every rule and facts do,begin,case,current_goal 与事实合一,return SUCCESS,第三章 普通搜索原理,3.1,盲目搜索,10/1/,30,人工智能一般搜索原理,第30页,模式导向搜索算法描述二,current_goal 是合取式,begin,for every合取项item do,ret=pattern_search(item),if ret=FAIL then return FAIL,end,current_goal 与规则后件合一,begin,对前件q应用对应合一置换,ret=pattern_search(q),if ret=FAIL then return FAIL else SUCCESS,end,end,return FAIL,end,第三章 普通搜索原理,3.1,盲目搜索,10/1/,31,人工智能一般搜索原理,第31页,图搜索策略,图搜索策略就是在图中寻找从起始点到目标点路径方法,图搜索普通过程是结构搜索图过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展过程就是搜索过程,扩展节点方法不一样，就意味着搜索方法不一样，也就是搜索路径不一样。,第三章 普通搜索原理,3.1,盲目搜索,10/1/,32,人工智能一般搜索原理,第32页,图搜索策略图示,S0,Sg,第三章 普通搜索原理,3.1,盲目搜索,10/1/,33,人工智能一般搜索原理,第33页,节点扩展,扩展一个节点,生成出该节点全部后继节点，并给出它们之间代价值。这一过程称为“扩展一个节点”。,第三章 普通搜索原理,3.1,盲目搜索,10/1/,34,人工智能一般搜索原理,第34页,路径,路径,设一节点序列为(n,0,n,1,n,k,)，对于i=1k，若节点n,i-1,含有一个后继节点n,i,，则该序列称为从n,0,到n,k,路径。,路径代价值,一条路径代价值等于连接这条路径各节点间全部代价值总和。用C(n,i,n,j,),表示从n,i,到n,j,路径代价值。,第三章 普通搜索原理,3.1,盲目搜索,10/1/,35,人工智能一般搜索原理,第35页,节点深度,节点深度：,根节点深度=0,其它节点深度=父节点深度+1,0,1,2,3,第三章 普通搜索原理,3.1,盲目搜索,10/1/,36,人工智能一般搜索原理,第36页,图搜索普通过程,第三章 普通搜索原理,3.1,盲目搜索,成功,是,把第一个节点(n)从OPEN表移至CLOSED表,把n后继节点放入OPEN表末端，提供返回节点n指针,修改指针方向,把S放入OPEN表,重排OPEN表,是,否,否,OPEN为空？,n为目标节点？,失败,开始,10/1/,37,人工智能一般搜索原理,第37页,图搜索过程说明,我们在搜索过程中用到了OPEN,表和,CLOSED,表两个数据结构,OPEN,表中节点都是搜索树端节点，即至今还未被选作为扩展节点,CLOSED,表中节点或者是已被,扩展而不能生成后继节点那些端节点，或者是搜索树非端节点,重排,OPEN,表，实际上就是在选择搜索次序，也就是扩展节点次序。,第三章 普通搜索原理,3.1,盲目搜索,10/1/,38,人工智能一般搜索原理,第38页,节点类型说明,.,mj,.,mk,.,.,.,ml,第三章 普通搜索原理,3.1,盲目搜索,扩展节点OPEN表没有部分,扩展,节点在已在,close,表中部分,扩展节点已在OPEN表中部分,选定扩展节点,10/1/,39,人工智能一般搜索原理,第39页,第三章 普通搜索原理,3.1,盲目搜索,图搜索过程图示（一）,现要扩展它,10/1/,40,人工智能一般搜索原理,第40页,第三章 普通搜索原理,3.1,盲目搜索,图搜索过程图示（二）,修改父子关系,现要扩展它,10/1/,41,人工智能一般搜索原理,第41页,第三章 普通搜索原理,3.1,盲目搜索,图搜索过程图示（三）,修改父子关系,修改父子关系,10/1/,42,人工智能一般搜索原理,第42页,盲目搜索概述,盲目搜索也叫无信息搜索,盲目搜索实际上是对解空间遍历,盲目搜索包含有：,宽度优先搜索,：搜索以靠近起始节点程度依次扩展节点，在对下一层搜索前，必须搜索完本层全部节点。,深度优先搜索,：搜索首先扩展最新产生节点。,等代价搜索,：搜索沿最小代价节点进行扩展。,第三章 普通搜索原理,3.1,盲目搜索,10/1/,43,人工智能一般搜索原理,第43页,宽度优先搜索,成功,是,把第一个节点(n)从OPEN表移至CLOSED表,把n后继节点放入OPEN表末端，提供返回节点n指针,把S放入OPEN表,是,否,否,OPEN为空？,是否有任何后继节点为目标节点？,失败,开始,第三章 普通搜索原理,3.1,盲目搜索,10/1/,44,人工智能一般搜索原理,第44页,目标,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,5,6,7,3,1 2 3,8 4,7 6 5,8,2 3 4,1 8,7 6 5,4,第三章 普通搜索原理,3.1,盲目搜索,八数码难题宽度优先搜索树,按上下左右序走步,10/1/,45,人工智能一般搜索原理,第45页,宽度优先搜索性质,当问题有解时，一定能找到解,当问题为单位代价值，且问题有解时，一定能找到最优解,方法与问题无关，含有通用性,效率较低,属于图搜索方法,第三章 普通搜索原理,3.1,盲目搜索,10/1/,46,人工智能一般搜索原理,第46页,第三章 普通搜索原理,3.1,盲目搜索,深度优先搜索,成功,是,把第一个节点(n)从OPEN表移至CLOSED表,把n后继节点放入OPEN表前端，提供返回节点n指针,把S放入OPEN表,是,否,否,OPEN为空？,节点n深度是否等于深度界限？,失败,开始,是否有任何后继节点为目标节点？,是,否,S是否为目标节点？,否,成功,10/1/,47,人工智能一般搜索原理,第47页,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,1 2 3,8 4,7 6 5,目标,。,。,第三章 普通搜索原理,3.1,盲目搜索,八数码难题深度优先搜索树,10/1/,48,人工智能一般搜索原理,第48页,深度优先搜索性质,普通不能确保找到最优解,当深度限制不合理时，可能找不到解，能够将算法改为可变深度限制,最坏情况时，搜索空间等同于穷举,是一个通用与问题无关方法,第三章 普通搜索原理,3.1,盲目搜索,10/1/,49,人工智能一般搜索原理,第49页,第三章 普通搜索原理,3.1,盲目搜索,等代价搜索,成功,是,把含有最小g(i)值节点i从OPEN表移至CLOSED表,计算其后继节点jg(j)值。把其后继节点放入OPEN表,把S放入OPEN表,否,否,OPEN为空？,失败,开始,i是否为目标节点？,是,S是否为目标节点？,否,成功,是,令g(s)=0,10/1/,50,人工智能一般搜索原理,第50页,什么是启发式搜索,盲目搜索效率低，花费过多计算时间和空间，轻易产生组合爆炸。,利用知识来引导搜索，到达降低搜索范围，降低问题复杂度目标。,对搜索产生帮助信息称为启发信息,第三章 普通搜索原理,3.2,启发式搜索,10/1/,51,人工智能一般搜索原理,第51页,启发式信息对搜索方法影响,启发信息多少用启发信息强度来表示,不一样启发信息对搜索方法带来不一样影响：,强：降低搜索工作量，但可能造成找不到最优解,弱：普通造成工作量加大，极限情况下变为盲目搜索，但可能能够找到最优解,第三章 普通搜索原理,3.2,启发式搜索,10/1/,52,人工智能一般搜索原理,第52页,启发式搜索类型,启发信息按用途可分为3类：,用于决定要扩展下一个节点（,这个节点称为最有希望节点,），以免像在宽度优先或深度优先搜索中那样盲目地扩展,在扩展一个节点过程中，用于决定要生成哪些其后继节点,，,以免盲目地生成全部节点。,用于决定哪些节点应从搜索树中抛弃或修剪。,用来估算节点希望程度方法为估价函数,第三章 普通搜索原理,3.2,启发式搜索,10/1/,53,人工智能一般搜索原理,第53页,对启发式搜索认识,有些启发信息能够大大降低搜索工作量，但不能确保能够得到最小代价路径,我们往往希望取得路径代价和求该路径所需搜索代价综合为最小,因为计算综合代价很困难，所以，比较两种方法优劣，依赖使用经验,使用估价函数实际是对OPEN表进行排序，再按次序扩展节点，进行搜索,第三章 普通搜索原理,3.2,启发式搜索,10/1/,54,人工智能一般搜索原理,第54页,有序搜索,若按估价函数增序对OPEN表进行排序，这种搜索方法叫做有序搜索或最正确优先搜索,有序搜索有效性取决于估价函数选择，不然有可能失去一个最好解甚至全部解,假如没有适当选择，可考虑两个方面内容：,一个是时间和空间折中,确保有一个解,第三章 普通搜索原理,3.2,启发式搜索,10/1/,55,人工智能一般搜索原理,第55页,有序搜索框图,第三章 普通搜索原理,3.2,启发式搜索,成功,是,选取f值最小节点i，从OPEN表移至CLOSED表,扩展i，计算后继节点jf(j)，对OPEN表重排序，调整亲子关系,把S放入OPEN表，计算f(s),是,否,否,OPEN为空？,i是目标节点？,失败,开始,10/1/,56,人工智能一般搜索原理,第56页,估价函数：f(n)=d(n)+w(n),其中，d(n):节点深度,w(n):节点放错棋子数目,第三章 普通搜索原理,3.2,启发式搜索,八数码难题有序搜索树,2 8 3,1 6 4,7 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,1 2 3,8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,1 2 3,7 8 4,6 5,2 3,1 8 4,7 6 5,5,4,6,4,6,6,7,7,5,6,7,5,5,1 2 3,8 4,7 6 5,目标,5,估价函数值,10/1/,57,人工智能一般搜索原理,第57页,A,算法,A算法是一个有序搜索启发式搜索算法。它采取估算节点n两个代价：,从起始点s到n最小代价路径代价,从n到某个目标节点最小代价路径代价,估价函数形式：,f(n)=g(n)+h(n),其中：g(n)：是对g*(n)估价值,h(n)：是对h*(n)估价值,称为启发函数,第三章 普通搜索原理,3.2,启发式搜索,10/1/,58,人工智能一般搜索原理,第58页,A,算法,估价函数说明,g*(n)：从s到n最正确路径代价,h*(n)：从n到某个目标节点最正确路径代价,f*(n)=g*(n)+h*(n)：,从s经过n到某个目标节点最正确路径代价,g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)预计值,表明，估价函数f(n)是对从起始点s经过n到某个目标节点最正确路径代价预计值,第三章 普通搜索原理,3.2,启发式搜索,10/1/,59,人工智能一般搜索原理,第59页,A算法流程,1,OPEN:=(s),f(s):=g(s)+h(s);,2,LOOP:IF OPEN=()THEN EXIT(FAIL);,3,n:=FIRST(OPEN);,4,IF GOAL(n)THEN EXIT(SUCCESS);,5,REMOVE(n,OPEN),ADD(n,CLOSED);,6,EXPAND(n),mi,计算f(n,mi):=g(n,mi)+h(mi);,第三章 普通搜索原理,3.2,启发式搜索,10/1/,60,人工智能一般搜索原理,第60页,A算法流程（续）,ADD(mj,OPEN),标识mj到n指针；,IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),标识mk到n指针；,IF f(n,ml)a b,(,z)(x)(y),(P(x)Q(x)R(y),U(z),2,移动否定符,理论依据：(a b)=a b,(a b)=a b,(x)P(x)=(x)P(x),(x)P(x)=(x)P(x),(,z)(x)(y),(P(x)Q(x)R(y),U(z),第三章 普通搜索原理,3.3,消解原理,10/1/,76,人工智能一般搜索原理,第76页,化子句集例,（续1）,3,变量标准化,即：对于不一样约束，对应于不一样变量,(,x)A(x)(x)B(x)=,(,x)A(x)(y)B(y),4,量词左移,(,x)A(x)(y)B(y)=,(,x)(y)A(x)B(y),5,消存在量词(skolem化）,标准：对于一个受存在量词约束变量，假如他不受全程量词约束，则该变量用一个常量代替，假如他受全程量词约束，则该变量用一个函数代替。,(,z)(x)(y)(P(x)Q(x)R(y)U(z),=(x)(P(x)Q(x)R(,f(x),)U(,a,),第三章 普通搜索原理,3.3,消解原理,10/1/,77,人工智能一般搜索原理,第77页,化子句集例（续2）,6,化为合取范式,即(a,b)(cd)(ef),形式,(x)(P(x)Q(x)R(f(x)U(a),=(x)(P(x)Q(x)R(f(x)U(a),=(x)P(x)R(f(x)U(a),Q(x)R(f(x)U(a),7,隐去全程量词,P(x)R(f(x)U(a)Q(x)R(f(x)U(a),第三章 普通搜索原理,3.3,消解原理,10/1/,78,人工智能一般搜索原理,第78页,化子句集例,（续3）,8,表示为子句集,P(x)R(f(x)U(a),Q(x)R(f(x)U(a),9,变量标准化（变量换名）,P(x1)R(f(x1)U(a),Q(x2)R(f(x2)U(a),第三章 普通搜索原理,3.3,消解原理,10/1/,79,人工智能一般搜索原理,第79页,消解推理规则,L1、L2为任一原子公式，他们含有相同谓词符号，但普通变量名不一样,已知两子句L1,和,L,2,假如L1、L2含有最普通合一者,那么可得新子句(,),这个,新子句叫做消解式,第三章 普通搜索原理,3.3,消解原理,10/1/,80,人工智能一般搜索原理,第80页,命题逻辑消解推理举例,第三章 普通搜索原理,3.3,消解原理,假言推理：P PQ (PQ）,消解式,：Q,合并：PQ PQ,消解式,：QQ=Q,重言式：P Q PQ,消解式,：PP 或 QQ,空子句：P P,消解式,：NIL,三段论：PQ (PQ）QR (QR）,消解式,：PR (PQ）,10/1/,81,人工智能一般搜索原理,第81页,谓词逻辑消解推理举例,第三章 普通搜索原理,3.3,消解原理,B(x)B(x)C(x）,消解式,：C(x),P(x)Q(x）Qf(y),消解式,：Pf(y),置换,：f(y)/x,Px,f(y)Q(x)Rf(a),y Pf(f(a),zR(z,w）,消解式,：Qf(f(a)Rf(a),yRf(y),w,置换,：f(f(a)/x,f(y)/z,10/1/,82,人工智能一般搜索原理,第82页,消解反演求解过程,消解反演,是利用,消解原理进行命题证实。,给定公式集,S和目标公式L,证实,公式L步骤以下：,否定,L,，得,L,把,L,添加到,S,中去,把新产生集合,L,S化成子句集,应用消解原理力图推导出一个表示矛盾空子句,第三章 普通搜索原理,3.3,消解原理,10/1/,83,人工智能一般搜索原理,第83页,命题逻辑消解反演例子,设公理集：,P,(P,Q)R,(ST)Q,T,求证：R,子句集：,(1)P,(2)PQR,(3)SQ,(4)TQ,(5)T,(6)R（目标求反）,化子句集：,(P,Q)R,=(PQ)R,=PQR,(ST)Q,=(ST)Q,=(ST)Q,=(SQ)(TQ),=SQ,TQ,第三章 普通搜索原理,3.3,消解原理,10/1/,84,人工智能一般搜索原理,第84页,命题逻辑消解反演例子（续）,子句集：,(1)P,(2)PQR,(3)SQ,(4)TQ,(5)T,(6)R（目标求反）,归结：,(7),PQ (2,6),(8)Q (1,7),(9)T (4,8),(10)nil (5,9),第三章 普通搜索原理,3.3,消解原理,10/1/,85,人工智能一般搜索原理,第85页,谓词逻辑消解反演例子,例：,已知：If Fido goes wherever John goes and if John is at school,where is Fido?,(,x)AT(John,x)AT(Fido,x),AT(John,School),求证：(x)AT(Fido,x),子句集：,AT(John,y)AT(Fido,y),AT(John,School),AT(Fido,x)(x)AT(Fido,x)=(x)AT(Fido,x),第三章 普通搜索原理,3.3,消解原理,10/1/,86,人工智能一般搜索原理,第86页,AT(Fido,x),AT(John,y),AT(Fido,y),子句集：AT(John,y)AT(Fido,y),AT(John,School),AT(Fido,x),AT(John,x),x/y,AT(John,School),nil,School/x,AT(Fido,School),第三章 普通搜索原理,3.3,消解原理,谓词逻辑消解反演例子（续）,10/1/,87,人工智能一般搜索原理,第87页,基于消解原理问答系统,消解原理主要用来处理证实问题，但有时我们希望得到如x=?时，W(x)为真回答,消解原理是将结论否定作为前提进行归约，而为了回答下列问题，用由结论否定组成重言式作为前提进行归约，得到结论是问题回答而不是空语句。这个过程称为修改证实过程（或修改归约过程）。,下面以猴子摘香蕉问题为例来说明,第三章 普通搜索原理,3.3,消解原理,10/1/,88,人工智能一般搜索原理,第88页,用消解原了解猴子摘香蕉问题,为了把状态空间算符描述与谓词演算结合起来，将状态添到谓词上；,将算符看成是把一个状态映射成另一个状态函数；,问题简化成没有goto()规则；,第三章 普通搜索原理,3.3,消解原理,c,10/1/,89,人工智能一般搜索原理,第89页,猴子摘香蕉问题表示,问题能够描述以下,：,1,ONBOX(s0),2,(,x)(s)(ONBOX(s)AT(box,x,push(x,s),3,(s)(ONBOX(climbbox(s),4,(s)(ONBOX(s)AT(box,c,s)HB(grasp(s),5,(,x)(s)(AT(box,x,s)AT(box,x,climb(s),求解：(s)HB(s),第三章 普通搜索原理,3.3,消解原理,10/1/,90,人工智能一般搜索原理,第90页,猴子摘香蕉问题子句集,1,ON(s0),2,ON(s1)AT(box,x1,push(x1,s1),3,ON(climb(s2),4,ON(s3)AT(box,c,s3)HB(grasp(s3),5,AT(box,x4,s4)AT(box,x4,climb(s4),6,HB(s5),第三章 普通搜索原理,3.3,消解原理,10/1/,91,人工智能一般搜索原理,第91页,HB(s5),ON(s3)AT(box,c,s3)HB(grasp(s3),ON(s3)AT(box,c,s3),grasp(s3)/s5,ON(climb(s2),climb(s2)/s3,AT(box,c,climb(s2),ON(s0),ON(s1)AT(box,x1,push(x1,s1),s0/s1,AT(box,x1,push(x1,s0),AT(box,x4,s4)AT(box,x4,climb(s4),x4/x1,push(x4,s0)/s4,AT(box,x4,climb(push(x4,s0),NIL,c/x4,push(c,s0)/s2,HB(s5),HB(grasp(s3),HB(grasp(climb(s2),HB(grasp(climb(push(c,s0),第三章 普通搜索原理,3.3,消解原理,猴子摘香蕉问题（修正）消解树,10/1/,92,人工智能一般搜索原理,第92页,消解方法小结,求子句集，进行归结，方法简单,经过修改证实树方法，提取回答,方法通用,求解效率低，不宜引入启发信息,不宜了解推理过程,第三章 普通搜索原理,3.3,消解原理,10/1/,93,人工智能一般搜索原理,第93页,普通搜索原理,The End.,第三章 普通搜索原理,10/1/,94,人工智能一般搜索原理,第94页,