人工智能 一般搜索原理课件.ppt

1,2022/12/11,搜索技术,问题提出：有了知识表示方法之后，就需要有解决问题的方法，也就是搜索技术。所谓搜索，就是寻找一条从初始问题到问题解的路径本章内容：搜索技术有许多种，本章介绍一些早期的、比较简单的搜索原理：1，盲目搜索；2，启发式搜索；3，消解原理；4，通用问题求解技术关键问题：如何利用知识，尽可能有效地找到问题的解(最佳解)。,第三章 一般搜索原理,2,2022/12/11,一般搜索原理,搜索策略可分为三大类不可撤回方式、回朔方式、图搜索方式不可撤回方式：每一次搜索时，利用局部知识根据最优评价，选出下一状态，选定后不能撤回，只能继续回朔方式：在搜索过程中，有时会发现所选的路径不适合找到目标，这时允许退回去另选一条路径。图搜索方式：如果把问题求解过程用图来表示。节点代表问题的状态，弧代表状态变化的方向，则搜索就变成对图进行从初始节点开始，到目标节点路径的搜索。,第三章 一般搜索原理 3.1盲目搜索,3,2022/12/11,回溯搜索策略,例：皇后问题,第三章 一般搜索原理 3.1盲目搜索,4,2022/12/11,( ),皇后问题搜索过程（一）,第三章 一般搜索原理 3.1盲目搜索,5,2022/12/11,Q,皇后问题搜索过程（二）,第三章 一般搜索原理 3.1盲目搜索,6,2022/12/11,皇后问题搜索过程（三）,第三章 一般搜索原理 3.1盲目搜索,7,2022/12/11,Q,皇后问题搜索过程（四）,第三章 一般搜索原理 3.1盲目搜索,8,2022/12/11,皇后问题搜索过程（五）,第三章 一般搜索原理 3.1盲目搜索,9,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（六）,10,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（七）,11,2022/12/11,Q,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（八）,12,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（九）,13,2022/12/11,Q,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（十）,14,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（十一）,15,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（十二）,16,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,皇后问题搜索过程（十三）,17,2022/12/11,递归的思想,第三章 一般搜索原理 3.1盲目搜索,18,2022/12/11,一个递归的例子,int ListLenght(LIST *pList)if (pList = NULL) return 0;else return ListLength(pList-next)+1;,第三章 一般搜索原理 3.1盲目搜索,19,2022/12/11,回溯搜索算法说明,BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。,第三章 一般搜索原理 3.1盲目搜索,20,2022/12/11,回溯搜索算法（一）,递归过程BACKTRACK(DATA)1, IF TERM(DATA) RETURN NIL;2, IF DEADEND(DATA) RETURN FAIL;3, RULES:=APPRULES(DATA);,第三章 一般搜索原理 3.1盲目搜索,TERM: 找目标DEADEND: 状态不合法,无法继续搜索APPRULES: 取可应用规则集,21,2022/12/11,回溯搜索算法（二）,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: 获取解路径规则表,22,2022/12/11,存在问题及解决办法,问题：深度问题:如果深度太深死循环问题: 如果状态出现重复解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径,第三章 一般搜索原理 3.1盲目搜索,23,2022/12/11,增加约束后的回溯搜索算法,BACKTRACK1（DATALIST）DATALIST：从初始到当前的状态表（逆向）返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。,第三章 一般搜索原理 3.1盲目搜索,24,2022/12/11,增加约束后的回溯搜索算法(一),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盲目搜索,25,2022/12/11,增加约束后的回溯搜索算法(二),6, RULES:=APPRULES(DATA);7, LOOP: IF NULL(RULES) RETURN FAIL;8,R:=FIRST(RULES);9,RULES:=TAIL(RULES);,第三章 一般搜索原理 3.1盲目搜索,26,2022/12/11,增加约束后的回溯搜索算法(三),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盲目搜索,27,2022/12/11,一些深入的问题,失败原因分析、多步回溯,第三章 一般搜索原理 3.1盲目搜索,28,2022/12/11,一些深入问题（续）,回溯搜索中知识的利用基本思想：尽可能选取划去对角线上位置数最少的。,第三章 一般搜索原理 3.1盲目搜索,29,2022/12/11,模式导向搜索,这个算法是将递归搜索应用到谓词演算的通用搜索算法要判断一个谓词表达式是某个断言集合的逻辑结论首先谓词表达式作为目标，使用合一来选择能与其后件匹配的蕴涵式并把得到的置换运用于该蕴涵式的前件这个前件成了新的目标称其为子目标应用递归搜索解这个子目标如果与事实相匹配，则搜索结实,第三章 一般搜索原理 3.1盲目搜索,30,2022/12/11,模式导向搜索算法描述一,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盲目搜索,31,2022/12/11,模式导向搜索算法描述二,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 end end return FAIL end,第三章 一般搜索原理 3.1盲目搜索,32,2022/12/11,图搜索策略,图搜索策略就是在图中寻找从起始点到目标点的路径的方法图搜索的一般过程是构造搜索图的过程。令搜索图开始时只有起始点S0，然后逐步扩展节点，直到将目标点扩展到搜索图里为止。扩展的过程就是搜索的过程扩展节点的方法不同，就意味着搜索的方法不同，也就是搜索的路径不同。,第三章 一般搜索原理 3.1盲目搜索,33,2022/12/11,图搜索策略图示,S0,Sg,第三章 一般搜索原理 3.1盲目搜索,34,2022/12/11,节点扩展,扩展一个节点生成出该节点的所有后继节点，并给出它们之间的代价值。这一过程称为“扩展一个节点”。,第三章 一般搜索原理 3.1盲目搜索,35,2022/12/11,路径,路径设一节点序列为(n0, n1,nk)，对于i = 1k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的代价值一条路径的代价值等于连接这条路径各节点间所有代价值的总和。用C(ni, nj)表示从ni到nj的路径的代价值。,第三章 一般搜索原理 3.1盲目搜索,36,2022/12/11,节点深度,节点深度：根节点深度=0其它节点深度=父节点深度+1,0,1,2,3,第三章 一般搜索原理 3.1盲目搜索,37,2022/12/11,图搜索的一般过程,第三章 一般搜索原理 3.1盲目搜索,38,2022/12/11,图搜索过程说明,我们在搜索过程中用到了OPEN表和CLOSED表两个数据结构OPEN表中的节点都是搜索树的端节点，即至今尚未被选作为扩展的节点CLOSED表中的节点或者是已被扩展而不能生成后继节点的那些端节点，或者是搜索树的非端节点重排OPEN表，实际上就是在选择搜索顺序，也就是扩展的节点的顺序。,第三章 一般搜索原理 3.1盲目搜索,39,2022/12/11,节点类型说明,.,mj,第三章 一般搜索原理 3.1盲目搜索,扩展的节点OPEN表没有的部分,扩展的节点在已在close表中的部分,扩展的节点已在OPEN表中的部分,选定的扩展节点,40,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示（一）,现要扩展它,41,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示（二）,修改父子关系,现要扩展它,42,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,图搜索过程的图示（三）,修改父子关系,修改父子关系,43,2022/12/11,盲目搜索概述,盲目搜索也叫无信息搜索盲目搜索实际上是对解空间的遍历盲目搜索包括有：宽度优先搜索：搜索以接近起始节点的程度依次扩展节点，在对下一层搜索前，必须搜索完本层的所有节点。深度优先搜索：搜索首先扩展最新产生的节点。等代价搜索：搜索沿最小代价节点进行扩展。,第三章 一般搜索原理 3.1盲目搜索,44,2022/12/11,宽度优先搜索,第三章 一般搜索原理 3.1盲目搜索,45,2022/12/11,目标,2 31 8 47 6 5,1,2,5,6,7,3,8,4,第三章 一般搜索原理 3.1盲目搜索,八数码难题的宽度优先搜索树,按上下左右序走步,46,2022/12/11,宽度优先搜索的性质,当问题有解时，一定能找到解当问题为单位代价值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法,第三章 一般搜索原理 3.1盲目搜索,47,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,深度优先搜索,48,2022/12/11,2 31 8 47 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,。,第三章 一般搜索原理 3.1盲目搜索,八数码难题的深度优先搜索树,49,2022/12/11,深度优先搜索的性质,一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举是一个通用的与问题无关的方法,第三章 一般搜索原理 3.1盲目搜索,50,2022/12/11,第三章 一般搜索原理 3.1盲目搜索,等代价搜索,51,2022/12/11,什么是启发式搜索,盲目搜索的效率低，耗费过多的计算时间和空间，容易产生组合爆炸。利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。对搜索产生帮助的信息称为启发信息,第三章 一般搜索原理 3.2启发式搜索,52,2022/12/11,启发式信息对搜索方法的影响,启发信息的多少用启发信息强度来表示不同的启发信息对搜索方法带来不同的影响：强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解,第三章 一般搜索原理 3.2启发式搜索,53,2022/12/11,启发式搜索类型,启发信息按用途可分为3类：用于决定要扩展的下一个节点（这个节点称为最有希望的节点），以免像在宽度优先或深度优先搜索中那样盲目地扩展在扩展一个节点的过程中，用于决定要生成哪些其后继节点，以免盲目地生成所有节点。用于决定哪些节点应从搜索树中抛弃或修剪。用来估算节点希望程度的方法为估价函数,第三章 一般搜索原理 3.2启发式搜索,54,2022/12/11,对启发式搜索的认识,有些启发信息能够大大减少搜索工作量，但不能保证能够得到最小代价路径我们往往希望获得路径代价和求该路径所需的搜索代价的综合为最小由于计算综合代价很困难，因此，比较两种方法的优劣，依赖使用的经验使用估价函数实际是对OPEN表进行排序，再按顺序扩展节点，进行搜索,第三章 一般搜索原理 3.2启发式搜索,55,2022/12/11,有序搜索,若按估价函数的增序对OPEN表进行排序，这种搜索方法叫做有序搜索或最佳优先搜索有序搜索的有效性取决于估价函数的选择，否则有可能失去一个最好的解甚至全部的解如果没有合适的选择，可考虑两个方面的内容：一个是时间和空间的折中保证有一个解,第三章 一般搜索原理 3.2启发式搜索,56,2022/12/11,有序搜索框图,第三章 一般搜索原理 3.2启发式搜索,57,2022/12/11,估价函数：f(n)=d(n)+w(n) 其中， d(n):节点的深度 w(n):节点放错棋子数目,第三章 一般搜索原理 3.2启发式搜索,八数码难题的有序搜索树,估价函数值,58,2022/12/11,A算法,A算法是一种有序搜索的启发式搜索算法。它采用估算节点n的两个代价：从起始点s到n的最小代价路径的代价从n到某个目标节点的最小代价路径的代价估价函数的形式：f(n) = g(n) + h(n)其中：g(n)：是对g*(n)的估价值 h(n)：是对h*(n)的估价值,称为启发函数,第三章 一般搜索原理 3.2启发式搜索,59,2022/12/11,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启发式搜索,60,2022/12/11,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启发式搜索,61,2022/12/11,A算法流程（续）,ADD(mj, OPEN), 标记mj到n的指针；IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 标记mk到n的指针；IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml),标记ml到n的指针, ADD(ml, OPEN);7, OPEN中的节点按f值从小到大排序；8, GO LOOP；,第三章 一般搜索原理 3.2启发式搜索,62,2022/12/11,最佳图搜索算法A*（A*算法）,在A算法中，如果对于任意点n满足条件：h(n)h*(n)则A算法称为A*算法。,第三章 一般搜索原理 3.2启发式搜索,63,2022/12/11,A*算法估价函数举例,在问题求解过程中，不可能明确知道h*(n) ，可根据经验估计下界范围条件例如，8数码问题如取h(n) = “不在位”的牌数，可估计出至少要移动h(n) 步，才能达到目标，因此，有h(n) h*(n) 如取h (n) = 每个牌与目标位置的距离和，同样可估计出至少要移动h(n) 步，才能达到目标，因此，有h(n) h*(n),第三章 一般搜索原理 3.2启发式搜索,64,2022/12/11,博弈中的启发式搜索,博弈空间的极小极大搜索:假定对手具有相同的关于状态空间的知识,且用该知识以一致方式比赛.博弈中的对手分别称为MIN和MAX一种余一棋变体：博弈双方要交替地将一堆牌分成数量不同的两堆牌,最先无法分堆的棋手为失败,第三章 一般搜索原理 3.2启发式搜索,65,2022/12/11,穷举式的极小极大搜索,博弈过程可以用一个树来表示标记叶节点若MIN获胜标0, MAX获胜标1,标记MIN节点为其子节点值中的最大值标记MAX节点为其子节点值中的最小值这样向上传播,直至根节点,第三章 一般搜索原理 3.2启发式搜索,66,2022/12/11,第三章 一般搜索原理 3.2启发式搜索,一种余一棋变体树,4-3,4-2-1,5-1-1,7,5-2,2-2-1-1-1,3-2-1-1,6-1,4-1-1-1,2-2-2-1,3-1-1-1-1,2-1-1-1-1-1,3-2-2,0,0,1,1,0,1,1,1,1,1,1,0,0,3-3-1,0,MIN,MAX,MIN,MAX,MIN,MAX,67,2022/12/11,固定层深的极小极大搜索,这种策略称为n-层预判用于状态空间不可能全部展开的情形，比如国际象棋的状态数大约是10120n的值由可用的时间和空间资源而定由于叶节点不是博弈的最终状态,不能用胜利或失败来标记需用某个启发评估函数的值来标记这个向上传播的值不表示是否可以胜利,只表示经过n步可达到的最佳状态,也可能是完全误导性的大多数博弈都为设计启发提供了无限的想象空间,第三章 一般搜索原理 3.2启发式搜索,68,2022/12/11,第三章 一般搜索原理 3.2启发式搜索,一种九宫游戏的启发函数,启发值为对MAX来说存在的所有可能胜利路线,减去对MIN来说存在的所有可能胜利路线,X有6条,O有5条可能的胜利路线E(n)=6-5=1,X有4条,O有6条可能的胜利路线E(n)=4-6= -2,X有5条,O有4条可能的胜利路线E(n)=5-4=1,69,2022/12/11,第三章 一般搜索原理 3.2启发式搜索,-搜索,单纯的极小极大搜索需要对搜索空间进行两遍分析,效率低-搜索对极小极大搜索进行改进基本思想：不搜索预判深度的整个空间，对能判断不起作用的分支则去掉，不搜索以深度优先方式到达预判层，在不断剪枝的过程中，向上传播评估值值是与MAX节点关联的不减小值值是与MIN节点关联的不增大值,70,2022/12/11,第三章 一般搜索原理 3.2启发式搜索,-搜索举例,MIN,MAX,MIN,MAX,2,3,5,9,0,7,4,2,1,5,6,3,9,0,7,2,6,3,0,2,3,2,3,5,2,0,2, 3,71,2022/12/11,双向搜索,搜索可以是从初始状态开始向目标状态的正向搜索；搜索也可以是从目标状态开始向初始状态的逆向搜索再可能是同时从初始状态向目标状态的正向搜索和从目标状态向初始状态的逆向搜索，直至这两条路径在中途某处小结接为止，这种搜索策略称为双向搜索,第三章 一般搜索原理 3.2启发式搜索,72,2022/12/11,消解原理概述,消解原理又称为归结原理是一种重要的推理规则它来源于定理证明：F1 F2 Fn W用反证法证：F= F1 F2 Fn W为永假等价于证明：F对应的子句集S为不可满足的归结原理的基本思路是：寻找将S扩充后的子句集S1，它可满足性与S相同，且容易判断可满足性，从而知道S的可满足性，则定理得证,第三章 一般搜索原理 3.3 消解原理,73,2022/12/11,消解过程,原子公式和原子公式的否定称为文字文字的析取构成的公式称为子句若S中存在空子句， S为不可满足的将F化为对应的子句集S将S扩充为可满足性相同的子句集S1，这个扩充的过程就是归结的过程判断S1 是否存在空子句,第三章 一般搜索原理 3.3 消解原理,74,2022/12/11,消解过程举例,E2 E1 （前提） E2 E3 （前提） （消解式） E1 E3 （结论）,第三章 一般搜索原理 3.3 消解原理,75,2022/12/11,建立子句集,消去蕴涵符号： PQ取代PQ减少否定符号的管辖域对变量标准化消去存在量词化为前束形化为合取范式： 如：P(PQ）(PQ）消去全称量词获得子句集更换变量名,第三章 一般搜索原理 3.3 消解原理,76,2022/12/11,化子句集例,例：(z) (x)(y)(P(x) Q(x) R(y) U(z)1, 消蕴涵符理论根据：a b = 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 消解原理,77,2022/12/11,化子句集例（续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 消解原理,78,2022/12/11,化子句集例（续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 消解原理,79,2022/12/11,化子句集例（续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 消解原理,80,2022/12/11,消解推理规则,L1、 L2为任一原子公式，他们具有相同的谓词符号，但一般变量名不同已知两子句L1和 L2如果L1、 L2具有最一般合一者那么可得新子句() 这个新子句叫做消解式,第三章 一般搜索原理 3.3 消解原理,81,2022/12/11,命题逻辑的消解推理举例,第三章 一般搜索原理 3.3 消解原理,三段论： PQ (PQ） QR (QR）,消解式：PR (PQ）,82,2022/12/11,谓词逻辑的消解推理举例,第三章 一般搜索原理 3.3 消解原理,83,2022/12/11,消解反演求解过程,消解反演是利用消解原理进行命题证明。给定公式集S和目标公式L证明公式L的步骤如下： 否定L ，得L 把L 添加到S中去把新产生的集合L ,S化成子句集应用消解原理力图推导出一个表示矛盾的空子句,第三章 一般搜索原理 3.3 消解原理,84,2022/12/11,命题逻辑消解反演的例子,设公理集：P, (PQ) 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 消解原理,85,2022/12/11,命题逻辑消解反演的例子（续）,子句集：(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 消解原理,86,2022/12/11,谓词逻辑消解反演的例子,例：已知：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 消解原理,87,2022/12/11,第三章 一般搜索原理 3.3 消解原理,谓词逻辑消解反演的例子（续）,88,2022/12/11,基于消解原理的问答系统,消解原理主要用来解决证明的问题，但有时我们希望得到如x=?时，W(x)为真的回答消解原理是将结论的否定作为前提进行归约，而为了回答问题，用由结论的否定构成的重言式作为前提进行归约，得到的结论是问题的回答而不是空语句。这个过程称为修改证明过程（或修改归约过程）。下面以猴子摘香蕉问题为例来说明,第三章 一般搜索原理 3.3 消解原理,89,2022/12/11,用消解原理解猴子摘香蕉问题,为了把状态空间的算符描述与谓词演算结合起来，将状态添到谓词上；将算符看成是把一种状态映射成另一种状态的函数；问题简化成没有goto()规则；,第三章 一般搜索原理 3.3 消解原理,90,2022/12/11,猴子摘香蕉问题的表示,问题可以描述如下：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 消解原理,91,2022/12/11,猴子摘香蕉问题的子句集,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 消解原理,92,2022/12/11,第三章 一般搜索原理 3.3 消解原理,猴子摘香蕉问题的（修正）消解树,93,2022/12/11,消解方法小结,求子句集，进行归结，方法简单通过修改证明树的方法，提取回答方法通用求解效率低，不宜引入启发信息不宜理解推理过程,第三章 一般搜索原理 3.3 消解原理,94,2022/12/11,一般搜索原理,The End.,第三章 一般搜索原理,