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

《人工智能一般搜索原理.pptx》由会员分享，可在线阅读，更多相关《人工智能一般搜索原理.pptx（120页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、搜索技术搜索技术l问题提出问题提出：有了知识表示方法之后，就需要有解决问题的方法，也就是搜索技术。所谓搜索，就是寻找一条从初始问题到问题解的路径l本章内容本章内容：搜索技术有许多种，本章介绍一些早期的、比较简单的搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术l关键问题关键问题：如何利用知识，尽可能有效地找到问题的解(最佳解)。第三章第三章 一般搜索原理一般搜索原理 2024/3/111一般搜索原理一般搜索原理l搜索策略可分为三大类搜索策略可分为三大类不可撤回方式、回朔方式、图搜索方式l不可撤回方式不可撤回方式：每一次搜索时，利用局部知识根据最优评价，选出下一状态，选

2、定后不能撤回，只能继续l回朔方式回朔方式：在搜索过程中，有时会发现所选的路径不适合找到目标，这时允许退回去另选一条路径。l图搜索方式：图搜索方式：如果把问题求解过程用图来表示。节点代表问题的状态，弧代表状态变化的方向，则搜索就变成对图进行从初始节点开始，到目标节点路径的搜索。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/112回溯搜索策略回溯搜索策略l例：皇后问题第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/113()皇后问题搜索过程（一）皇后问题搜索过程（一）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲

3、目搜索2024/3/114Q()(1,1)皇后问题搜索过程（二）皇后问题搜索过程（二）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/115QQ()(1,1)(1,1)(2,3)皇后问题搜索过程（三）皇后问题搜索过程（三）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/116Q()(1,1)(1,1)(2,3)皇后问题搜索过程（四）皇后问题搜索过程（四）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/117QQ()(1,1)(1,1)(2,3)(1,1)(2,4)皇后问题搜索过程（五）皇后问题

4、搜索过程（五）第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/118QQQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（六）皇后问题搜索过程（六）2024/3/119QQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（七）皇后问题搜索过程（七）2024/3/1110Q()(1,1)(1,1)(2,3)(1,1)(2,4

5、)(1,1)(2,4)(3.2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（八）皇后问题搜索过程（八）2024/3/1111()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（九）皇后问题搜索过程（九）2024/3/1112Q()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索皇后问题搜索过程（十）皇后问题搜索过程（十）2024

6、/3/1113QQ()(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盲目搜索盲目搜索皇后问题搜索过程（十一）皇后问题搜索过程（十一）2024/3/1114QQQ()(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盲目搜索盲目搜索皇后问题搜索过程（十二）皇后问题搜索过程（十二）2024/3/1115QQQQ()(1,1)(1,1)(2,3)

7、(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盲目搜索盲目搜索皇后问题搜索过程（十三）皇后问题搜索过程（十三）2024/3/1116递归的思想递归的思想从前有座山 从前有座山 从前有座山第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1117一个递归的例子一个递归的例子int ListLenght(LIST*pList)if(pList=NULL)return 0;else return ListLengt

8、h(pList-next)+1;第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1118回溯搜索算法说明回溯搜索算法说明BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1119回溯搜索算法（一）回溯搜索算法（一）递归过程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:取可应用规则集2024/3/1120回溯搜索算法（二）回溯搜索算法（二）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:获取解路径规则表2024/3/1121存在问题及解决办法存在问题及解决办法l问题：深度问题:如果深度太深死循环问题:如果状态出现重复l解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1122增加约束后的回溯搜索算法增加约束后的回溯搜索算法BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。第三章第三章 一般搜索原理一般搜索原理 3.13

11、.1盲目搜索盲目搜索2024/3/1123增加约束后的回溯搜索算法增加约束后的回溯搜索算法(一一)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盲目搜索盲目搜索2024/3/1124增加约束后的回溯搜索算法增加约束后的回溯搜索算法(二二)6,RULES:=APPRULES

12、(DATA);7,LOOP:IF NULL(RULES)RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1125增加约束后的回溯搜索算法增加约束后的回溯搜索算法(三三)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盲目搜索盲目搜索2024/3/1126一些深入的问题一些深入的问题l失败原因分析、多步回溯QQ第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1127一些深入问题（续）一些深入问题（续）l回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。QQQQ4 3 3 4第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1128模式导向搜索模式导向搜索l这个算法是将递归搜索应用到谓词演算的通用搜索算法l要判断一个谓词表达式是某个断言集合的逻辑结论l首先谓词表达式作为目标，使用合一来选择能与其后件匹配的蕴

14、涵式l并把得到的置换运用于该蕴涵式的前件l这个前件成了新的目标称其为子目标l应用递归搜索解这个子目标l如果与事实相匹配，则搜索结实 第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1129模式导向搜索算法描述一模式导向搜索算法描述一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 cur

15、rent_goal 与事实合一return SUCCESS 第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1130模式导向搜索算法描述二模式导向搜索算法描述二 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 SUCCE

16、SS end end return FAIL end第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1131图搜索策略图搜索策略l图搜索策略就是在图中寻找从起始点到目标点的路径的方法l图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展的过程就是搜索的过程l扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的路径不同。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1132图搜索策略图示图搜索策略图示S0Sg第三章第三章 一般搜索原理一般搜索原理 3.13

17、.1盲目搜索盲目搜索2024/3/1133节点扩展节点扩展l扩展一个节点生成出该节点的所有后继节点，并给出它们之间的代价值。这一过程称为“扩展一个节点”。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1134路径路径l路径设一节点序列为(n0,n1,nk)，对于i=1k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。l路径的代价值一条路径的代价值等于连接这条路径各节点间所有代价值的总和。用C(ni,nj)表示从ni到nj的路径的代价值。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1135节点深度节点

18、深度l节点深度：根节点深度=0其它节点深度=父节点深度+10123第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1136图搜索的一般过程图搜索的一般过程第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向把S放入OPEN表重排OPEN表是否否OPEN为空？n为目标节点？失败开始2024/3/1137图搜索过程说明图搜索过程说明l我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构lOPEN表中的节点都是搜索树的端节

19、点，即至今尚未被选作为扩展的节点lCLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点l重排OPEN表，实际上就是在选择搜索顺序，也就是扩展的节点的顺序。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1138节点类型说明节点类型说明.mj.mk.ml第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索扩展的节点OPEN表没有的部分扩展的节点在已在close表中的部分扩展的节点已在OPEN表中的部分选定的扩展节点2024/3/1139第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索图搜索

20、过程的图示（一）图搜索过程的图示（一）现要扩展它2024/3/1140第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索图搜索过程的图示（二）图搜索过程的图示（二）修改父子关系现要扩展它2024/3/1141第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索图搜索过程的图示（三）图搜索过程的图示（三）修改父子关系修改父子关系2024/3/1142盲目搜索概述盲目搜索概述l盲目搜索也叫无信息搜索l盲目搜索实际上是对解空间的遍历l盲目搜索包括有：宽度优先搜索宽度优先搜索：搜索以接近起始节点的程度依次扩展节点，在对下一层搜索前，必须搜索完本层的所有节点。深度优先搜

21、索深度优先搜索：搜索首先扩展最新产生的节点。等代价搜索等代价搜索：搜索沿最小代价节点进行扩展。第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1143宽度优先搜索宽度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的末端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？是否有任何后继节点为目标节点？失败开始第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1144目标2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8

22、 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 51256731 2 3 8 47 6 582 3 41 8 7 6 54第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索八数码难题的宽度优先搜索树八数码难题的宽度优先搜索树按上下左右序走步2024/3/1145宽度优先搜索的性质宽度优先搜索的性质l当问题有解时，一定能找到解l当问题为单位

23、代价值，且问题有解时，一定能找到最优解l方法与问题无关，具有通用性l效率较低l属于图搜索方法第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1146第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索深度优先搜索深度优先搜索成功是把第一个节点(n)从OPEN表移至CLOSED表把n的后继节点放入OPEN表的前端，提供返回节点n的指针把S放入OPEN表是否否OPEN为空？节点n的深度是否等于深度界限？失败开始是否有任何后继节点为目标节点？是否S是否为目标节点？否成功2024/3/11472 31 8 47 6 5 2 31 8 47 6 52 8

24、 31 47 6 52 31 8 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盲目搜索盲目搜索八数码难题的深度优先搜索树八数码难题的深度优先搜索树2024/3/1148深度优先搜索的性质深度优先搜索的性质l一般不能保证找到

25、最优解l当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制l最坏情况时，搜索空间等同于穷举l是一个通用的与问题无关的方法第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索2024/3/1149第三章第三章 一般搜索原理一般搜索原理 3.13.1盲目搜索盲目搜索等代价搜索等代价搜索成功是把具有最小g(i)值的节点i从OPEN表移至CLOSED表计算其后继节点j的g(j)值。把其后继节点放入OPEN表把S放入OPEN表否否OPEN为空？失败开始 i是否为目标节点？是S是否为目标节点？否成功是令g(s)=02024/3/1150什么是启发式搜索什么是启发式搜索l盲目搜索的

26、效率低，耗费过多的计算时间和空间，容易产生组合爆炸。l利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。l对搜索产生帮助的信息称为启发信息第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索2024/3/1151启发式信息对搜索方法的影响启发式信息对搜索方法的影响l启发信息的多少用启发信息强度来表示l不同的启发信息对搜索方法带来不同的影响：强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索2024/3/1152启发式搜索类型启发式搜索

27、类型l启发信息按用途可分为3类：用于决定要扩展的下一个节点（这个节点称为最有希这个节点称为最有希望的节点望的节点），以免像在宽度优先或深度优先搜索中那样盲目地扩展在扩展一个节点的过程中，用于决定要生成哪些其后继节点，以免盲目地生成所有节点。用于决定哪些节点应从搜索树中抛弃或修剪。l用来估算节点希望程度的方法为估价函数第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索2024/3/1153对启发式搜索的认识对启发式搜索的认识l有些启发信息能够大大减少搜索工作量，但不能保证能够得到最小代价路径l我们往往希望获得路径代价和求该路径所需的搜索代价的综合为最小l由于计算综合代价很困

28、难，因此，比较两种方法的优劣，依赖使用的经验l使用估价函数实际是对OPEN表进行排序，再按顺序扩展节点，进行搜索第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索2024/3/1154有序搜索有序搜索l若按估价函数的增序对OPEN表进行排序，这种搜索方法叫做有序搜索或最佳优先搜索l有序搜索的有效性取决于估价函数的选择，否则有可能失去一个最好的解甚至全部的解l如果没有合适的选择，可考虑两个方面的内容：一个是时间和空间的折中保证有一个解第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索2024/3/1155有序搜索框图有序搜索框图第三章第三章 一般搜索原

29、理一般搜索原理 3.23.2启发式搜索启发式搜索成功是选取f值最小的节点i，从OPEN表移至CLOSED表扩展i，计算后继节点j的f(j)，对OPEN表重排序，调整亲子关系把S放入OPEN表，计算f(s)是否否OPEN为空？i是目标节点？失败开始2024/3/1156估价函数：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

30、6 51 2 38 47 6 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 51 2 37 8 4 6 5 2 31 8 47 6 554646677567551 2 3 8 47 6 5目标5估价函数值2024/3/1157A算法算法lA算法是一种有序搜索的启发式搜索算法。它采用估算节点n的两个代价：从起始点s到n的最小代价路径的代价从n到某个目标节点的最小代价路径的代价l估价函数的形式：f(n)=g(n)+h(n)其中：g(n)：是对g*(n)的估价值 h(n)：是对h*(n)的估价值,称为启发函数

31、第三章第三章 一般搜索原理一般搜索原理 3.23.2启发式搜索启发式搜索2024/3/1158A算法算法估价函数的说明估价函数的说明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启发式搜索启发式搜索2024/3/1159A算法流程算法流程1,OPEN:=(s),f(s)

32、:=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.23.2启发式搜索启发式搜索2024/3/1160A算法流程（续）算法流程（续）ADD(mj,OPEN),标记mj到n的指针；IF f(n,mk)f(mk)THEN f(mk):=f(n,mk),标记mk到n的指针；IF f(n,

33、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 3.3 消解原理消解原理2024/3/1176化子句集例化子句集例（续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 消解原理消解原理2024/3/1177化子句集例（续化子句集例（续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

35、)第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理2024/3/1178化子句集例化子句集例（续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 消解原理消解原理2024/3/1179消解推理规则消解推理规则lL1、L2为任一原子公式，他们具有相同的谓词符号，但一般变量名不同l已知两子句L1和 L2l如果L1、L2具有最一般合一者l那么可得新子句()l这个新子句叫做消解式第三章第三章 一般搜索原

36、理一般搜索原理 3.3 3.3 消解原理消解原理2024/3/1180命题逻辑的消解推理举例命题逻辑的消解推理举例第三章第三章 一般搜索原理一般搜索原理 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）2024/3/1181谓词逻辑的消解推理举例谓词逻辑的消解推理举例第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理B(x)B(x)C(x）消解式：C(x)P(x)Q(x）Qf(y)

37、消解式：Pf(y)置换：f(y)/xPx,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)/z2024/3/1182消解反演求解过程消解反演求解过程l消解反演是利用消解原理进行命题证明。l给定公式集S和目标公式Ll证明公式L的步骤如下：否定L，得L 把L 添加到S中去把新产生的集合L,S化成子句集应用消解原理力图推导出一个表示矛盾的空子句 第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理2024/3/1183命题逻辑消解反演的例子命题逻辑消解反演的例子设公理集：P,(PQ)

38、R,(ST)Q,T求证：R子句集：(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R（目标求反）化子句集：(PQ)R=(PQ)R=PQR(ST)Q=(ST)Q=(ST)Q=(SQ)(TQ)=SQ,TQ第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理2024/3/1184命题逻辑消解反演的例子（续）命题逻辑消解反演的例子（续）子句集：(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 消解原理消解原理2

39、024/3/1185谓词逻辑消解反演的例子谓词逻辑消解反演的例子l例：已知：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 消解原理消解原理2024/3/1186AT(Fido,x)AT(J

40、ohn,y)AT(Fido,y)子句集：AT(John,y)AT(Fido,y)AT(John,School)AT(Fido,x)AT(John,x)x/yAT(John,School)nilSchool/xAT(Fido,School)第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理谓词逻辑消解反演的例子（续）谓词逻辑消解反演的例子（续）2024/3/1187基于消解原理的问答系统基于消解原理的问答系统l消解原理主要用来解决证明的问题，但有时我们希望得到如x=?时，W(x)为真的回答l消解原理是将结论的否定作为前提进行归约，而为了回答问题，用由结论的否定构成的重言式作

41、为前提进行归约，得到的结论是问题的回答而不是空语句。这个过程称为修改证明过程（或修改归约过程）。l下面以猴子摘香蕉问题为例来说明第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理2024/3/1188用消解原理解猴子摘香蕉问题用消解原理解猴子摘香蕉问题l为了把状态空间的算符描述与谓词演算结合起来，将状态添到谓词上；l将算符看成是把一种状态映射成另一种状态的函数；l问题简化成没有goto()规则；第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理c2024/3/1189猴子摘香蕉问题的表示猴子摘香蕉问题的表示问题可以描述如下：1,ONBOX(s0)2,

42、(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 3.3 消解原理消解原理2024/3/1190猴子摘香蕉问题的子句集猴子摘香蕉问题的子句集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

43、,x4,s4)AT(box,x4,climb(s4)6,HB(s5)第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理2024/3/1191HB(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)/s

44、4AT(box,x4,climb(push(x4,s0)NILc/x4,push(c,s0)/s2HB(s5)HB(grasp(s3)HB(grasp(climb(s2)HB(grasp(climb(push(c,s0)第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理猴子摘香蕉问题的（修正）消解树猴子摘香蕉问题的（修正）消解树2024/3/1192消解方法小结消解方法小结l求子句集，进行归结，方法简单l通过修改证明树的方法，提取回答l方法通用l求解效率低，不宜引入启发信息l不宜理解推理过程第三章第三章 一般搜索原理一般搜索原理 3.3 3.3 消解原理消解原理2024/

45、3/1193一般搜索原理一般搜索原理The End.第三章第三章 一般搜索原理一般搜索原理2024/3/1194演讲完毕，谢谢观看！附录资料：人工智能简介About Teaching Plan基本要求：人工智能是计算机科学中涉及研究、设计和应用智能机器的一个分支，是目前迅速发展的一门新兴学科，新思想新方法层出不穷。其基本思想是利用机器来模仿和执行人脑的功能，如判断、推理、证明、识别、感知、理解、设计、思考、规划、学习和问题求解等思维活动。对于培养学生计算机技术的应用能力，开阔思路和视野，有重要意义。About Teaching Plan因此，要求学生掌握知识表示知识表示和问题求解问题求解的几种

46、常用方法，尤其是不确定性推理不确定性推理；掌握机器学习机器学习基本概念，了解几种机器学习方法机器学习方法尤其是神经网络学习方法；神经网络学习方法；掌握专家系统的概念，了解专家系统设计方法专家系统设计方法，掌握一些智能控制方法智能控制方法，了解国内外人工智能研究尤其是机器人的最新进展；最新进展；具有一定的人工智能编程设计能力人工智能编程设计能力（利用Lisp或Prolog语言）。About Teaching Plan课程内容以及学时分配课程内容以及学时分配人工智能引论(1)人工智能概念及与计算机的关系，研究途径、内容和应用领域概况介绍，其他最新材料其他最新材料。符号主义、连接主义、行为主义三大流

47、派人工智能数学基础(1)知识表示方法（2）状态空间法、问题归约法，谓词逻辑法、产生式表示法（动物识别系统）；CLIPS语言；语义网络法、框架法（这是结构化表示）；剧本、过程、Petri网、面向对象的表示。About Teaching Plan搜索技术和策略（3-4）状态空间法，盲目搜索和启发式搜索，A*算法；海伯伦理论、消解原理和策略；与或形推理和搜索策略；其他求解技术。不确定推理技术（3-4）主观Bayes理论；可信度方法和证据理论；系统组织技术；非单调推理；Rete快速算法；模糊推理技术；基于语义网络和框架不确定推理；专家系统（2）专家系统概念、结构和知识获取；黑板模型、知识组织、管理及系

48、统建造和开发工具；专家系统举例及编程。人工智能程序设计人工智能程序设计（1）人工智能语言基本机制：LISP和PROLOG。About Teaching Plan模式识别导论（3）模式识别专题：概率模式识别。模式识别专题：结构模式识别机器学习（1）：机械,解释经验,事例,归纳,概念,类比学习等；统计,结构,模糊模式识别。专题讲座（3次）1)神经网络基本理论和应用(史奎凡课程：安排于人工智能理论与应用课程内)；2)智能体（Agent）；3)自然语言处理；4)智能控制和机器人科学智能控制的结构理论和研究领域，智能控制系统及应用示例；机器人规划、机器视觉和自然语言理解等。About Teaching

49、Plan实践：1)搜索技术和策略2)不确定推理技术3)专家系统：动物识别系统4)模式识别技术5)调研：搜索技术和策略、不确定推理技术、统计模式识别、机器学习等四个领域进展报告。Chapter One:Brief Introduction to Artificial Intelligence1.What is AI?人工智能（人工智能（Artificial Intelligence,AI）是当前科学技发展的一门前是当前科学技发展的一门前沿学科，同时也是一门新思想，新观念，新理论，新技术不断出沿学科，同时也是一门新思想，新观念，新理论，新技术不断出现的新兴学科以及正在发展的学科。现的新兴学科以及正

50、在发展的学科。它是在它是在计算机科学，控制论，信息论，神经心理学，哲学，语言学计算机科学，控制论，信息论，神经心理学，哲学，语言学等多种学科研究的基础发展起来的，因此又可把它看作是一门等多种学科研究的基础发展起来的，因此又可把它看作是一门综综合性的边缘学科合性的边缘学科。它的出现及所取得的成就引起了人们的高度重视它的出现及所取得的成就引起了人们的高度重视,并取得了很高的评并取得了很高的评价。有的人把它与空间技术，原子能技术一起并誉为价。有的人把它与空间技术，原子能技术一起并誉为20世纪的三世纪的三大科学技术成就。大科学技术成就。Intelligence智能是知识与智力的总合。智能是知识与智力的