1、12023-2-1搜索技术搜索技术l 问题提出问题提出：有了知识表示方法之后，就需要有解决问题的方法，也就是搜索技术。所谓搜索，就是寻找一条从初始问题到问题解的路径l 本章内容本章内容：搜索技术有许多种，本章介绍一些早期的、比较简单的搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术l 关键问题关键问题：如何利用知识，尽可能有效地找到问题的解(最佳解)。第三章第三章 一般搜索原理一般搜索原理 22023-2-1一般搜索原理一般搜索原理l 搜索策略可分为三大类搜索策略可分为三大类不可撤回方式、回朔方式、图搜索方式l 不可撤回方式不可撤回方式：每一次搜索时，利用局部知识根据
2、最优评价，选出下一状态，选定后不能撤回，只能继续l 回朔方式回朔方式：在搜索过程中，有时会发现所选的路径不适合找到目标，这时允许退回去另选一条路径。l 图搜索方式：图搜索方式：如果把问题求解过程用图来表示。节点代表问题的状态，弧代表状态变化的方向，则搜索就变成对图进行从初始节点开始，到目标节点路径的搜索。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索32023-2-1回溯搜索策略回溯搜索策略l例：皇后问题QQQQ第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索42023-2-1()皇后问题搜索过程（一）皇后问题搜索过程（一）第三章第三章 一般搜索原理一
3、般搜索原理 3.13.1盲目搜索盲目搜索52023-2-1Q()(1,1)皇后问题搜索过程（二）皇后问题搜索过程（二）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索62023-2-1QQ()(1,1)(1,1)(2,3)皇后问题搜索过程（三）皇后问题搜索过程（三）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索72023-2-1Q()(1,1)(1,1)(2,3)皇后问题搜索过程（四）皇后问题搜索过程（四）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索82023-2-1QQ()(1,1)(1,1)(2,3)(1,1)(2,4)皇后
4、问题搜索过程（五）皇后问题搜索过程（五）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索92023-2-1QQQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（六）皇后问题搜索过程（六）102023-2-1QQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（七）皇后问题搜索过程（七）112023-2-1Q()(1,1)(1,1)(2,
5、3)(1,1)(2,4)(1,1)(2,4)(3.2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（八）皇后问题搜索过程（八）122023-2-1()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（九）皇后问题搜索过程（九）132023-2-1Q()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（十）皇后问题搜索
6、过程（十）142023-2-1QQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)(1,2)(2,4)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（十一）皇后问题搜索过程（十一）152023-2-1QQQ()(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.13.1盲目搜索盲目搜索皇后问题搜索过程（十二）皇后问题搜索过程（十二）162023-2-1QQQQ()(1,1)(1,1
7、)(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.13.1盲目搜索盲目搜索皇后问题搜索过程（十三）皇后问题搜索过程（十三）172023-2-1递归的思想递归的思想从前有座山 从前有座山 从前有座山第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索182023-2-1一个递归的例子一个递归的例子int ListLenght(LIST*pList)if(pList=NULL)return 0;else return ListL
8、ength(pList-next)+1;第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索192023-2-1回溯搜索算法说明回溯搜索算法说明BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索202023-2-1回溯搜索算法（一）回溯搜索算法（一）递归过程BACKTRACK(DATA)1,IF TERM(DATA)RETURN NIL;2,IF DEADEND(DATA)RETURN FAIL;3,RULES:=APPRULES(DATA);
9、第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索TERM:找目标DEADEND:状态不合法,无法继续搜索APPRULES:取可应用规则集212023-2-1回溯搜索算法（二）回溯搜索算法（二）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.13.1盲目搜索
10、盲目搜索TAIL:删除头条规则GEN:调用规则作用于当前状态CONS:获取解路径规则表222023-2-1存在问题及解决办法存在问题及解决办法l问题：深度问题:如果深度太深死循环问题:如果状态出现重复l解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索232023-2-1增加约束后的回溯搜索算法增加约束后的回溯搜索算法BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章第三章 一般搜索原理一般搜索原理 3.13.
11、1盲目搜索盲目搜索242023-2-1增加约束后的回溯搜索算法增加约束后的回溯搜索算法(一一)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.13.1盲目搜索盲目搜索252023-2-1增加约束后的回溯搜索算法增加约束后的回溯搜索算法(二二)6,RULES:=APPRULES(DA
12、TA);7,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索262023-2-1增加约束后的回溯搜索算法增加约束后的回溯搜索算法(三三)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);第三章第三章 一般搜索原理一般搜索原理
13、 3.13.1盲目搜索盲目搜索272023-2-1一些深入的问题一些深入的问题l失败原因分析、多步回溯QQ第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索282023-2-1一些深入问题（续）一些深入问题（续）l回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。QQQQ4 3 3 4第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索292023-2-1模式导向搜索模式导向搜索l 这个算法是将递归搜索应用到谓词演算的通用搜索算法l 要判断一个谓词表达式是某个断言集合的逻辑结论l 首先谓词表达式作为目标，使用合一来选择能与其后件匹配的蕴涵式l
14、并把得到的置换运用于该蕴涵式的前件l 这个前件成了新的目标称其为子目标l 应用递归搜索解这个子目标l 如果与事实相匹配，则搜索结实第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索302023-2-1模式导向搜索算法描述一模式导向搜索算法描述一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 curre
15、nt_goal 与事实合一return SUCCESS 第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索312023-2-1模式导向搜索算法描述二模式导向搜索算法描述二 current_goal 是合取式 beginfor 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
16、end end return FAIL end第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索322023-2-1图搜索策略图搜索策略l图搜索策略就是在图中寻找从起始点到目标点的路径的方法l图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展的过程就是搜索的过程l扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的路径不同。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索332023-2-1图搜索策略图示图搜索策略图示S0Sg第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜
17、索盲目搜索342023-2-1节点扩展节点扩展l扩展一个节点生成出该节点的所有后继节点，并给出它们之间的代价值。这一过程称为“扩展一个节点”。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索352023-2-1路径路径l路径设一节点序列为(n0,n1,nk)，对于i=1k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。l路径的代价值一条路径的代价值等于连接这条路径各节点间所有代价值的总和。用C(ni,nj)表示从ni到nj的路径的代价值。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索362023-2-1节点深度节点深度l节点深度：
18、根节点深度=0其它节点深度=父节点深度+10123第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索372023-2-1图搜索的一般过程图搜索的一般过程第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向把S放入OPEN表重排OPEN表是否否OPEN为空？n为目标节点？失败开始382023-2-1图搜索过程说明图搜索过程说明l 我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构l OPEN表中的节点都是搜索树的端节点，即至今尚未被
19、选作为扩展的节点l CLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点l 重排OPEN表，实际上就是在选择搜索顺序，也就是扩展的节点的顺序。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索392023-2-1节点类型说明节点类型说明.mj.mk.ml第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索扩展的节点OPEN表没有的部分扩展的节点在已在close表中的部分扩展的节点已在OPEN表中的部分选定的扩展节点402023-2-1第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索图搜索过程的图示（一）
20、图搜索过程的图示（一）现要扩展它412023-2-1第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索图搜索过程的图示（二）图搜索过程的图示（二）修改父子关系现要扩展它422023-2-1第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索图搜索过程的图示（三）图搜索过程的图示（三）修改父子关系修改父子关系432023-2-1盲目搜索概述盲目搜索概述l盲目搜索也叫无信息搜索l盲目搜索实际上是对解空间的遍历l盲目搜索包括有：宽度优先搜索宽度优先搜索：搜索以接近起始节点的程度依次扩展节点，在对下一层搜索前，必须搜索完本层的所有节点。深度优先搜索深度优先搜索：搜索首
21、先扩展最新产生的节点。等代价搜索等代价搜索：搜索沿最小代价节点进行扩展。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索442023-2-1宽度优先搜索宽度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？是否有任何后继节点为目标节点？失败开始第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索452023-2-1目标2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8
22、 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 582 3 41 8 7 6 54第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索八数码难题的宽度优先搜索树八数码难题的宽度优先搜索树按上下左右序走步462023-2-1宽度优先搜索的性质宽度优先搜索的性质l当问题有解时，一定能找到解l当问题为单位代价值，且问题有解时，一定能
23、找到最优解l方法与问题无关，具有通用性l效率较低l属于图搜索方法第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索472023-2-1第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索深度优先搜索深度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的前端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？节点n的深度是否等于深度界限？失败开始是否有任何后继节点为目标节点？是否S是否为目标节点？否成功482023-2-12 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8
24、 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 5123456789abcd1 2 3 8 47 6 5目标。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索八数码难题的深度优先搜索树八数码难题的深度优先搜索树492023-2-1深度优先搜索的性质深度优先搜索的性质l一般不能保证找到最优解l当深度限制不合理时，可能找
25、不到解，可以将算法改为可变深度限制l最坏情况时，搜索空间等同于穷举l是一个通用的与问题无关的方法第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索502023-2-1第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索等代价搜索等代价搜索成功是把具有最小g(i)值的节点i从OPEN表移至CLOSED表计算其后继节点j的g(j)值。把其后继节点放入OPEN表把S放入OPEN表否否OPEN为空？失败开始 i是否为目标节点？是S是否为目标节点？否成功是令g(s)=0512023-2-1什么是启发式搜索什么是启发式搜索l盲目搜索的效率低，耗费过多的计算时间和空间，容易
26、产生组合爆炸。l利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。l对搜索产生帮助的信息称为启发信息第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索522023-2-1启发式信息对搜索方法的影响启发式信息对搜索方法的影响l启发信息的多少用启发信息强度来表示l不同的启发信息对搜索方法带来不同的影响：强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索532023-2-1启发式搜索类型启发式搜索类型l启发信息按用途可分为3类：用于决定要
27、扩展的下一个节点（这个节点称为最有希这个节点称为最有希望的节点望的节点），以免像在宽度优先或深度优先搜索中那样盲目地扩展在扩展一个节点的过程中，用于决定要生成哪些其后继节点，以免盲目地生成所有节点。用于决定哪些节点应从搜索树中抛弃或修剪。l用来估算节点希望程度的方法为估价函数第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索542023-2-1对启发式搜索的认识对启发式搜索的认识l有些启发信息能够大大减少搜索工作量，但不能保证能够得到最小代价路径l我们往往希望获得路径代价和求该路径所需的搜索代价的综合为最小l由于计算综合代价很困难，因此，比较两种方法的优劣，依赖使用的经验
28、l使用估价函数实际是对OPEN表进行排序，再按顺序扩展节点，进行搜索第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索552023-2-1有序搜索有序搜索l 若按估价函数的增序对OPEN表进行排序，这种搜索方法叫做有序搜索或最佳优先搜索l 有序搜索的有效性取决于估价函数的选择，否则有可能失去一个最好的解甚至全部的解l 如果没有合适的选择，可考虑两个方面的内容：一个是时间和空间的折中保证有一个解第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索562023-2-1有序搜索框图有序搜索框图第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发
29、式搜索成功是选取f值最小的节点i，从OPEN表移至CLOSED表扩展i，计算后继节点j的f(j)，对OPEN表重排序，调整亲子关系把S放入OPEN表，计算f(s)是否否OPEN为空？i是目标节点？失败开始572023-2-1估价函数：f(n)=d(n)+w(n)其中，d(n):节点的深度 w(n):节点放错棋子数目第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索八数码难题的有序搜索树八数码难题的有序搜索树2 8 31 6 47 52 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 51 2 38 47 6 52 8 3
30、1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 51 2 37 8 4 6 5 2 31 8 47 6 554646677567551 2 3 8 47 6 5目标5估价函数值582023-2-1A算法算法lA算法是一种有序搜索的启发式搜索算法。它采用估算节点n的两个代价：从起始点s到n的最小代价路径的代价从n到某个目标节点的最小代价路径的代价l估价函数的形式：f(n)=g(n)+h(n)其中：g(n)：是对g*(n)的估价值 h(n)：是对h*(n)的估价值,称为启发函数第三章第三章 一般搜索原理一般搜索原理 3.2
31、3.2启发式搜索启发式搜索592023-2-1A算法算法估价函数的说明估价函数的说明lg*(n)：从s到n的最佳路径的代价lh*(n)：从n到某个目标节点的最佳路径的代价lf*(n)=g*(n)+h*(n)：从s经过n到某个目标节点的最佳路径的代价lg(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值l表明，估价函数f(n)是对从起始点s经过n到某个目标节点的最佳路径的代价的估计值第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索602023-2-1A算法流程算法流程1,OPEN:=(s),f(s):=g(s)+h(s);2,LOOP:IF OPE
32、N=()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.23.2启发式搜索启发式搜索612023-2-1A算法流程（续）算法流程（续）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(
33、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 3.3 消解原理消解原理772023-2-1化子句集例化子句集例（续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化）原则：对于一个受存在量词约束的变量，如果他不受全程量词约束，则该变量用一个常量代替，
34、如果他受全程量词约束，则该变量用一个函数代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a)第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理782023-2-1化子句集例（续化子句集例（续2）6,化为合取范式即(ab)(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 3.3
35、 消解原理消解原理792023-2-1化子句集例化子句集例（续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 3.3 消解原理消解原理802023-2-1消解推理规则消解推理规则lL1、L2为任一原子公式，他们具有相同的谓词符号，但一般变量名不同l已知两子句L1和 L2l如果L1、L2具有最一般合一者l那么可得新子句()l这个新子句叫做消解式第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理812023
36、-2-1命题逻辑的消解推理举例命题逻辑的消解推理举例第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理假言推理：P PQ (PQ）消解式：Q合并：PQ PQ 消解式：QQ=Q 重言式：P Q PQ 消解式：PP 或 QQ 空子句：P P 消解式：NIL 三段论：PQ (PQ）QR (QR）消解式：PR (PQ）822023-2-1谓词逻辑的消解推理举例谓词逻辑的消解推理举例第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理B(x)B(x)C(x）消解式：C(x)P(x)Q(x）Qf(y)消解式：Pf(y)置换：f(y)/xPx,f(y)Q(x)Rf(
37、a),y Pf(f(a),zR(z,w）消解式：Qf(f(a)Rf(a),yRf(y),w 置换：f(f(a)/x,f(y)/z832023-2-1消解反演求解过程消解反演求解过程l消解反演是利用消解原理进行命题证明。l给定公式集S和目标公式Ll证明公式L的步骤如下：否定L，得L 把L 添加到S中去把新产生的集合L,S化成子句集应用消解原理力图推导出一个表示矛盾的空子句 第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理842023-2-1命题逻辑消解反演的例子命题逻辑消解反演的例子设公理集：P,(PQ)R,(ST)Q,T求证：R子句集：(1)P(2)PQR(3)SQ(4
38、)TQ(5)T(6)R（目标求反）化子句集：(PQ)R=(PQ)R=PQR(ST)Q=(ST)Q=(ST)Q=(SQ)(TQ)=SQ,TQ第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理852023-2-1命题逻辑消解反演的例子（续）命题逻辑消解反演的例子（续）子句集：(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 3.3 消解原理消解原理862023-2-1谓词逻辑消解反演的例子谓词逻辑消解反演的例子l例：已
39、知：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 3.3 消解原理消解原理872023-2-1AT(Fido,x)AT(John,y)AT(Fido,y)子句集：AT(John,y)AT(Fido
40、,y)AT(John,School)AT(Fido,x)AT(John,x)x/yAT(John,School)nilSchool/xAT(Fido,School)第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理谓词逻辑消解反演的例子（续）谓词逻辑消解反演的例子（续）882023-2-1基于消解原理的问答系统基于消解原理的问答系统l消解原理主要用来解决证明的问题，但有时我们希望得到如x=?时，W(x)为真的回答l消解原理是将结论的否定作为前提进行归约，而为了回答问题，用由结论的否定构成的重言式作为前提进行归约，得到的结论是问题的回答而不是空语句。这个过程称为修改证明过程
41、（或修改归约过程）。l下面以猴子摘香蕉问题为例来说明第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理892023-2-1用消解原理解猴子摘香蕉问题用消解原理解猴子摘香蕉问题l 为了把状态空间的算符描述与谓词演算结合起来，将状态添到谓词上；l 将算符看成是把一种状态映射成另一种状态的函数；l 问题简化成没有goto()规则；第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理c902023-2-1猴子摘香蕉问题的表示猴子摘香蕉问题的表示问题可以描述如下：1,ONBOX(s0)2,(x)(s)(ONBOX(s)AT(box,x,push(x,s)3,(s
42、)(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 3.3 消解原理消解原理912023-2-1猴子摘香蕉问题的子句集猴子摘香蕉问题的子句集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)第三章第
43、三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理922023-2-1HB(s5)ON(s3)AT(box,c,s3)HB(grasp(s3)ON(s3)AT(box,c,s3)grasp(s3)/s5ON(climb(s2)climb(s2)/s3 AT(box,c,climb(s2)ON(s0)ON(s1)AT(box,x1,push(x1,s1)s0/s1AT(box,x1,push(x1,s0)AT(box,x4,s4)AT(box,x4,climb(s4)x4/x1,push(x4,s0)/s4AT(box,x4,climb(push(x4,s0)NILc/x4,pus
44、h(c,s0)/s2HB(s5)HB(grasp(s3)HB(grasp(climb(s2)HB(grasp(climb(push(c,s0)第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理猴子摘香蕉问题的（修正）消解树猴子摘香蕉问题的（修正）消解树932023-2-1消解方法小结消解方法小结l求子句集，进行归结，方法简单l通过修改证明树的方法，提取回答l方法通用l求解效率低，不宜引入启发信息l不宜理解推理过程第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理942023-2-1一般搜索原理一般搜索原理The End.第三章第三章 一般搜索原理一般搜索原理
