人工智能-一般搜索算法原理153

1、第三章 一般搜索原理盲目搜索启发式搜索归结原理10/13/20221人工智能讲义盲目搜索索图搜索策策略深度优先先搜索宽度优先先搜索等代价搜搜索2/11/20202人工智能能讲义一些基本本概念节点深度度：根节点深深度=0其它节点点深度=父节点点深度+101232/11/20203人工智能能讲义一些基本本概念（续1）路径设一节点点序列为为(n0, n1,nk)，对于于i=1,k，若若节点ni-1具有一个个后继节节点ni，则该序序列称为为从n0到nk的路径。路径的耗耗散值一条路径径的耗散散值等于于连接这这条路径径各节点点间所有有耗散值值的总和和。用C(ni, nj)表示从ni到nj的路径的的耗散值值

2、。2/11/20204人工智能能讲义一些基本本概念（续1）扩展一个个节点生成出该该节点的的所有后后继节点点，并给给出它们们之间的的耗散值值。这一一过程称称为“扩扩展一个个节点”。2/11/20205人工智能能讲义一般的图图搜索算算法（GRAPHSEARCH）1,G=G0 (G0=s),OPEN=(s);2,CLOSED=();3,LOOP:IFOPEN=()EXIT(FAIL);4,n=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED);5,IFGOAL(n)EXIT(SUCCESS);6,EXPAND(n)mi,G=ADD(mi, G);2/11/20206人工

3、智能能讲义一般的图图搜索算算法（续续）7,标标记和修修改指针针：ADD(mj, OPEN),并标记mj到n的指针；计算是否否要修改改mk、ml到n的指针；计算是否否要修改改ml到其后继继节点的的指针；8, 对OPEN中的节节点按某种原则则重新排序序；9,GOLOOP；2/11/20207人工智能能讲义深度优先先搜索在深度优优先搜索索中，首首先扩展展最新产产生的(最深的的)节点点，深度度 相等等的节点点可以任任意排列列。“最最晚产生生的节点点最先扩扩展”2/11/20208人工智能能讲义深度优先先搜索算算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN

4、=()EXIT (FAIL);3,n=FIRST(OPEN);4,IFGOAL(n) EXIT(SUCCESS);5,REMOVE(n,OPEN), ADD(n,CLOSED);6,IFDEPTH(n)DmGOLOOP;7,EXPAND(n)mi, G=ADD(mi,G);8,IF目目标在mi中THEN EXIT(SUCCESS);9,ADD(mj, OPEN),并并标记mj到n的指针;10,GOLOOP;2/11/20209人工智能能讲义23184765 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8

5、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 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123456789abcd1 2 3 8 47 6 5目标2/11/202010人工智能能讲义深度优先先搜索的的性质一般不能能保证找找到最优优解当深度限限制不合合理时，可能找找不到解解，可以以将算法法改为

6、可可变深度度限制最坏情况况时，搜搜索空间间等同于于穷举与回溯法法的差别别：图搜搜索是一个通通用的与与问题无无关的方方法2/11/202011人工智能能讲义宽度优先先搜索如果搜索索是以接接近起始始节点的的程度依依次扩展展节点的的，那么么这种搜搜索就叫叫做宽度度优先搜搜索。这这种搜索索使逐层层进行的的，在对对下一层层的任意意节点进进行搜索索之前，必须搜搜索完本本层的所所有节点点。“先先产生的的节点先先扩展”2/11/202012人工智能能讲义宽度优先先搜索算算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(

7、OPEN);4,IFGOAL(n)EXIT (SUCCESS);5,REMOVE(n,OPEN), ADD(n,CLOSED);6,EXPAND(n)mi, G=ADD(mi,G);7,IF目目标在mi中THEN EXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;2/11/202013人工智能能讲义23184765 2 31 8 47 6 52 8 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

8、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 5目标82 3 41 8 7 6 542/11/202014人工智能能讲义宽度优先先搜索的的性质当问题有有解时，一定能能找到解解当问题为为单位耗耗散值，且问题题有解时时，一定定能找到到最优解解方法与问问题无关关，具有有通用性性效率较低低属于图搜搜索方法法2/11/202015人工智能能讲义等代价搜搜索宽度优先先搜索可可被推广广用来解解决寻找找从起始始节点到到目标节节点具有有最小代代价路径径问题，这种推推广了的的宽度优

9、优先搜索索算法叫叫做等代价搜搜索算法法。2/11/202016人工智能能讲义等代价搜搜索算法法算法1,G=G0(G0=s), OPEN=(s),CLOSED=(),g(s)=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,从从OPEN表中中选择一一个节点点i,使使其g(i)为为最小。如果有有几个节节点都合合格，那那么就要要选择一一个目标标节点作作为i(要是有有目标节节点的话话)；否否则，就就从中选选一个作作为节点点I;REMOVE(i,OPEN), ADD(i,CLOSED);4,IFGOAL(i)EXIT (SUCCESS);5,EXPAND(i) j, G=ADD(j, G)

10、;6,对对每个后后继节点点j,计计算g(j)=g(i)+c(i,j)且且ADD(OPEN,j),并标记j到i的指针;7,GOLOOP;2/11/202017人工智能能讲义启发式图图搜索利用知识识来引导导搜索，达到减减少搜索索范围，降低问问题复杂杂度的目目的。启发信息息的强度度强：降低低搜索工工作量，但可能能导致找找不到最最优优解解弱：一般般导致工工作量加加大，极极限情况况下变为为盲盲目搜索索，但可可能可以以找到最最优解2/11/202018人工智能能讲义希望：引入启发发知识，在保证证找到最最佳解的的情况下下，尽可可能减少少搜索范范围，提提高搜索索效率。2/11/202019人工智能能讲义基本思

11、想想定义一个个评价函函数f，对当前前的搜索索状态进进行评估估，找出出一个最最有希望望的节点点来扩展展。2/11/202020人工智能能讲义1，启发发式搜索索算法A（A算算法）评价函数数的格式式：f(n) =g(n)+ h(n)f(n)：评价价函数h(n)：启发发函数2/11/202021人工智能能讲义符号的意意义g*(n)：从从s到n的最短短路径的的耗散值值h*(n)：从从n到g的最短短路径的的耗散值值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路路径的耗耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估估计值2/11/202022人工智能能讲义A算法1

12、,OPEN=(s),f(s)=g(s)+h(s);2,LOOP:IFOPEN=()EXIT(FAIL);3,n=FIRST(OPEN);4,IFGOAL(n) EXIT(SUCCESS);5,REMOVE(n,OPEN), ADD(n,CLOSED);6,EXPAND(n)Mi,计算f(n, mi)=g(n, mi)+h(mi);2/11/202023人工智能能讲义A算法（续）ADD(mj, OPEN),标标记mj到n的的指针；IFf(n, mk)f(mk)f(mk)=f(n, mk),标记mk到n的指针；IFf(n, ml)f*(s)。2/11/202031人工智能能讲义A*算法法的性质质（

13、续2）引理2.2：A*结束前，OPEN表中必存存在f(n)f*(s)。2/11/202032人工智能能讲义A*算法法的性质质（续3）定理2：对无限图图，若从从初始节节点s到到目标节节点t有有路径存存在，则则A*一一定成功功结束。2/11/202033人工智能能讲义A*算法法的性质质（续4）推论2.1：OPEN表上任任一具有有f(n) h1(n)，则在在具有一一条从s到t的的路径的的隐含图图上，搜搜索结束束时，由由A2所所扩展的的每一个个节点，也必定定由A1所扩展展，即A1扩展展的节点点数至少少和A2一样多多。简写：如如果h2(n)h1(n),则则A1扩展的的节点数数A2扩展的节节点数2/11/

14、202037人工智能能讲义A*算法法的改进进问题的提提出：因A算法法第6步步对ml类节点点可能要要重新放放回到OPEN表中，因此可可能会导导致多次次重复扩扩展同一一个节点点，导致致搜索效效率下降降。2/11/202038人工智能能讲义s(10)A(1)B(5)C(8)G 目标631118一个例子子：OPEN表CLOSED表s(10)s(10)A(7) B(8)C(9)A(7) s(10)B(8) C(9)G(14)A(5) C(9)G(14)C(9) G(12)B(7) G(12)A(4) G(12)G(11)A(7)B(8)s(10)A(5) B(8)s(10)C(9) A(5)B(8) s

15、(10)A(5)B(7)C(9) s(10)A(4) B(7)C(9)s(10)2/11/202039人工智能能讲义出现多次次扩展节节点的原原因在前面的的扩展中中，并没没有找到到从初始始节点到到当前节节点的最最短路径径，如节节点A。2/11/202040人工智能能讲义解决的途途径对h加以以限制能否对h增加适适当的限限制，使使得第一一次扩展展一个节节点时，就找到到了从s到该节节点的最最短路径径。对算法加加以改进进能否对算算法加以以改进，避免或或减少节节点的多多次扩展展。2/11/202041人工智能能讲义改进的条条件可采纳性性不变不多扩展展节点不增加算算法的复复杂性2/11/202042人工智能

16、能讲义对h加以以限制定义：一一个启发发函数h，如果果对所有有节点ni和nj，其其中nj是ni的子节节点，满满足h(ni)- h(nj) c(ni,nj)h(t) =0则称h是是单调的的。h(ni)ninjh(nj)c(ni,nj)2/11/202043人工智能能讲义h单调的的性质定理5：若h(n)是单单调的，则A*扩展了了节点n之后，就已经经找到了了到达节节点n的的最佳路路径。即：当A*选n扩展时时，有g(n)=g*(n)。2/11/202044人工智能能讲义h单调的的性质（续）定理6：若h(n)是单单调的，则由A*所扩扩展的节节点序列列其f值值是非递递减的。2/11/202045人工智能能讲

17、义h单调的的例子8数码问问题：h为“不不在位”的将牌牌数1h(ni)- h(nj) =0(nj为ni的后继节节点)-1h(t) =0c(ni,nj)=1满足单调调的条件件。2/11/202046人工智能能讲义对算法加加以改进进一些结论论：OPEN表上任任一具有有f(n) f*(s)的节点点定会被被扩展。A*选作作扩展的的任一节节点，定定有f(n)f*(s)。2/11/202047人工智能能讲义改进的出出发点OPEN =( )f*(s)f值小于f*(s)的节点f值大于等等于f*(s)的节点fm：到目前为为止已扩扩展节点点的最大大f值，用fm代代替f*(s)2/11/202048人工智能能讲义修正

18、过程程A1,OPEN=(s),f(s)=g(s)+h(s), fm=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,NEST=ni|f(ni)5)n2(4)n3(4)n0(3)n0(3-4)2/11/202062人工智能能讲义n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1-2)2/11/202063人工智能能讲义n0n1n2n3n4n5n6n7n8红色代价价：5蓝色代价：6n0(4)n4(1)n5(1-2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4-5)2/11/20

19、2064人工智能能讲义n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/11/202065人工智能能讲义目标目标初始节点点n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/11/202066人工智能能讲义目标目标初始节点点n0n1n2n3n4n5n6n7n8初始节点点可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2/11/202067人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形H

20、erbrand定理理归结原理理归结过程程的策略略控制2/11/202068人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/202069人工智能能讲义概述归结原理理由J.A.Robinson由1965年年提出。与演绎法法完全不不同，新新的逻辑辑演算算算法。一阶逻辑辑中，至至今为止止的最有有效的半半可判定定的算法法。即，一阶逻逻辑中任任意恒真真公式，使用归归结原理理，总可可以在有有限步内内给以判判定。语义网络络、框架架表示、产生式式规则等等等都是是以推理理方法为为前提的的。即，有了规规则已知知条件，顺藤摸摸瓜找到到结果。 而归归

21、结方法法是自动动推理、自动推推导证明明用的。（“数数学定理理机器证证明”）本课程只只讨论一一阶谓词词逻辑描描述下的的归结推推理方法法，不涉涉及高阶阶谓词逻逻辑问题题。2/11/202070人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/202071人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/202072人工智能能讲义命题逻辑辑的归结结法基本单元元：简单单命题（陈述句句）例： 命题：A1、A2、A3和B求证：A1A2A3成立，则B成立，即：A1A2A3

22、B反证法：证明A1A2A3B是矛盾式式（永假式式）2/11/202073人工智能能讲义命题逻辑辑的归结结法建立子句句集合取范式式：命题题、命题题和的与与，如如：P（PQ）（ PQ）子句集S：合取范式式形式下下的子命命题（元元素）的的集合例：命题题公式：P（PQ）（ PQ）子句集S：S =P, PQ,PQ2/11/202074人工智能能讲义命题逻辑辑的归结结法归结式消除互补补对，求求新子句句得到归结结式。如子句：C1= C1L,C2= C2归结式：R(C1, C2) =C1C2注意：C1C2 R(C1, C2)，反之不一定成立。假言推理理:由合适公公式W1和W1W2产生合适适公式W2,如何用归归

23、结法证证明?2/11/202075人工智能能讲义命题逻辑辑的归结结法归结过程程对结论作作否定,并加入入前提中中将命题写写成合取取范式求出子句句集对子句集集使用归归结推理理规则归结式作作为新子子句参加加归结归结式为为空子句句，S是不不可满足足的（矛矛盾），原命题题成立。（证明完完毕）谓词的归归结：除除了有量量词和函函数以外外，其余余和命题题归结过过程一样样。2/11/202076人工智能能讲义命题逻辑辑的归结结法例证明先将化为合取取范式建立子句句集S=对S做归归结PNIL2/11/202077人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略

24、控制2/11/202078人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/202079人工智能能讲义子句形引用Herbrand定理，以以说明归归结原理理的意义义及一个个原理形形成的根根基与背背景SKOLEM标准形前束范式式：把所有有的量词词都提到到前面去去，然后后消掉所所有量词词。定义：说公式式A是一个前前束范式式，如果果A中的一切切量词都都位于该该公式的的最左边边（不含含否定词词），且且这些量量词的辖辖域都延延伸到公公式的末末端。即即(Q1x1)(Qnxn)M(x1, ,xn),其中Qixi为存在量词词或全称称量词,M(x

25、1, ,xn)为合取范范式(由一些子子句的合合取组成成)。2/11/202080人工智能能讲义子句形(Skolem标准形)量词消去去原则：消去存在在量词“”，略去全程程量词“”。注意：左边有全全称量词词的存在在量词，消去时时该变量量改写成成为全称称量词的的函数(Skloem函数)；如没有有，改写写成为常常量。例子：见见人工智能能及其应应用P752/11/202081人工智能能讲义子句形(Skolem标准形)定理：谓词逻辑辑的任意意公式都都可以化化为与之之等价的的前束范范式，但但其前束束范式不不唯一。SKOLEM标准形定定义：消去量词词后的谓谓词公式式。注意：谓词公公式G的SKOLEM标准形同G

26、并不等值值。2/11/202082人工智能能讲义子句形(Skolem标准形)例:G=(x)(y)(z)(u)P(x,y,z,u)Skolem标准形为为：(y)(z)P(a,y,z,f(y,z)其中，x=a(常量)，u=f(y.z)2/11/202083人工智能能讲义子句形子句与子子句集文字：不不含任何何连接词词的谓词词公式。子句：一一些文字字的析取取（谓词词的和）。子句集S的求取：G SKOLEM标准形 消去去存在变变量 以“，”取代“”，并表示为为集合形形式。2/11/202084人工智能能讲义子句形G是不可可满足的的S是不可可满足的的G与S不等价，但在不不可满足足的意义义下是一一致的。定理

27、：若G是给给定的公公式，而而S是相相应的子子句集，则G是是不可满满足的S是不可可满足的的。 注意：G真不一一定S真真，而S真必有有G真。即：S=G2/11/202085人工智能能讲义子句形G =G1 G2 G3 Gn的子句形形G的子句集集可以分分解成几几个单独独处理。 有SG= S1U S2U S3U USn则SG与S1U S2U S3U USn在不可满满足的意意义上是是一致的的。即SG不可满足足S1U S2U S3U USn不可满足足2/11/202086人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/202087人工智能

28、能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/202088人工智能能讲义Herbrand定理问题：一阶逻辑辑公式的的永真性性（永假假性）的的判定是是否能在在有限步步内完成成？2/11/202089人工智能能讲义Herbrand定理1936年图灵(Turing)和邱吉(Church)互相独立立地证明明了：“没有一一般的方方法使得得在有限限步内判判定一阶阶逻辑的的公式是是否是永永真（或或永假）。但是是如果公公式本身身是永真真（或永永假）的的，那么么就能在在有限步步内判定定它是永永真（或或永假）。对于于非永真真（或永永假）的的公式就就不

29、一定定能在有有限步内内得到结结论。判判定的过过程将可可能是不不停止的的。”2/11/202090人工智能能讲义Herbrand定理Herbrand的思思想定义：公式G永永真：对对于G的的所有解解释，G都为真真。思想：寻找一个个已给的的公式是是真的解解释。然然而，如如果所给给定的公公式的确确是永假假的，就就没有这这样的解解释存在在，并且且算法在在有限步步内停止止。2/11/202091人工智能能讲义Herbrand定理H域H解释语义树结论：Herbrand定理理2/11/202092人工智能能讲义Herbrand定理H域H解释语义树结论：Herbrand定理理2/11/202093人工智能能讲义

30、Herbrand定理理（H域）基本方法法：因为量词是任任意的，所讨论论的个体体变量域域D是任意的的，所以以解释的的个数是是无限、不可数数的。简化讨论论域。建建立一个个比较简简单、特特殊的域域，使得得只要在在这个论论域上，该公式式是不可可满足的的。此域称为为H域：H0为G中所所出现的的常量的的集合，若G中中没有常常量，就就任取常常量，H0=a。规定为为H域例题请参参考教科科书P272/11/202094人工智能能讲义H域举例例例1S=P(a),P(x)P(f(x)依定义有有H0=aH1=aUf(a)=a,f(a)H2=a,f(a)Uf(a),f(f(a)=a,f(a),f(f(a)H= a,f(

31、a),f(f(a)，2/11/202095人工智能能讲义Herbrand定理理（H域）几个基本本概念f（t1, t2, tn）：f为子句集集S中的所有有函数变变量。t1, t2, tn为S的H域的元素素。通过过它们来来讨论永永真性。原子集A：谓词套上上H域的元素素组成的的集合。如A =所有形如如P(t1, t2, tn)的元素即把H中的东西西填到S的谓词里里去。S中的谓词词是有限限的，H是可数的的，因此此，A也是可数数的。一旦原子子集内真真值确定定好（规规定好），则S在H上的真值值可确定定。成为为可数问问题。2/11/202096人工智能能讲义原子集举举例例1S=P(a),P(x)P(f(x)

32、H= a,f(a),f(f(a)，S的原子集集为A=P(a),P(f(a),P(f(f(a),2/11/202097人工智能能讲义Herbrand定理理（H域）没有变量量出现的的原子、文字、子句和和子句集集，分别称作作基原子子、基文文字、基基子句和和基子句句集。它们在讨讨论子句句集S的的不可满满足性时时占有重重要置。2/11/202098人工智能能讲义Herbrand定理H域H解释语义树结论：Herbrand定理理2/11/202099人工智能能讲义Herbrand定理H域H解释语义树结论：Herbrand定理理2/11/2020100人工智能能讲义Herbrand定理理（H解释）解释I*：取

33、一个值得得到一个个结论I映射S中到所有有常量符符号到它它们本身身。(即原子集集)令f是n元函数，I是f下的一个个指派，即H中的元素素到f的一个映映射（函函数值）。简单地说说(P29)，A中的各元元素真假假组合都都是H的解释。（或真真或假只只取一个个）问题：对于所有有的解释释，全是是假才可可判定。因为所所有解释释代表了了所有的的情况，如可穷穷举，问问题便可可解决。2/11/2020101人工智能能讲义H解释-举例例1S=P(a),P(x)P(f(x)S的H域H= a,f(a),f(f(a)，S的原子集集为A=P(a),P(f(a),P(f(f(a),S的H解释：I1*=P(a),P(f(a),P

34、(f(f(a),S|I1*=TI2*=P(a),P(f(a),P(f(f(a),S|I2*=FI3*=P(a),P(f(a),P(f(f(a),S|I3*=F我们关心心的是：对论域域上的任任一解释释I，若有S|I=T,如何求得得一个相相应的H解释I*,使得S|I*=T成立。2/11/2020102人工智能能讲义Herbrand定理理（H解释）如下三个个定理保保证了归归结法的的正确性性：定理1：设I是S的论域D上的解释释，存在在对应于于I的H解释I*，使得若有有S|I= T，必有S|I*= T。定理2：子句集S是不可满满足的，当且仅仅当所有有的S的H解释下为为假。定理3：子句集S是不可满满足的，

35、当且仅仅当对每每一个解解释I下，至少少有S的某个子子句的某某个基例为假。2/11/2020103人工智能能讲义Herbrand定理理（H解释）基例S中某子句句中所有有变元符符号均以以S的H域中的元元素代入入时，所所得的基基子句C称为C的一个基基例。若一个子子句为假假，则此此解释为为假。一般来说说，D是无穷不不可列的的，因此此，子句句集S也是无穷穷不可列列的。但但S确定后H是无穷可可列的。不过在在H上证明S的不可满满足性仍仍然是不不可能的的。解决问题题的方法法：语义树2/11/2020104人工智能能讲义Herbrand定理H域H解释语义树结论：Herbrand定理理2/11/2020105人工

36、智能能讲义Herbrand定理H域H解释语义树结论：Herbrand定理理2/11/2020106人工智能能讲义Herbrand定理理（语义树树）构成方法法原子集中中所有元元素逐层层添加的的一棵二二叉树。将元素素的是与与非分别别标记在在两侧的的分枝上上（可不不完全画画完）。(P34)特点一般情况况H是可数集集，S的语义树树是无限限树。2/11/2020107人工智能能讲义Herbrand定理理（语义树）意义S HA 语义树可以理解解语义树树为H域的图形形解释。目的：把把每个解解释都摊摊开。语语义树中中包含原原子集的的全部元元素，因因此，语义树是是完全的的。每一个直直到叶子子节点的的分支对对应S

37、的一个解解释。可可以通过过对语义义树每一一个分支支来计算算S的真值。如果每每个基例例都为假假，则可可认为是是不可满满足的。2/11/2020108人工智能能讲义语义树-举例例1设设子子句集S的原子子集A=P,Q,R语义树：N0N11N12N21N22N23N24N31N32N33N34N35N36N37N38P QQR R PI(N)表示从根根节点到到节点N分枝上所所标记的的所有文文字的并并集。如如I(N34)=P,Q,R2/11/2020109人工智能能讲义Herbrand定理理（语义树树）几个概念念失败结点点：当（由上上）延伸伸到点N时，I(N)已表明了了S的某子句句的某基基例假。但N以前

38、尚不不能判断断这事实实。就称称N为失败结结点。完全语义义树：如果对语语义树的的所有叶叶结点N来说，I(N)包含了S的原子集集A=A1,A2,中的所有有元素Ai或Ai，I=1n。封闭语义义树：如果S的完全语语义树的的每个分分枝上都都有一个个失败结结点，就就称它是是一棵封封闭语义义树。2/11/2020110人工智能能讲义封闭语义义树-举例例子子句集S=P(x)Q(x),P(f(y),Q(f(y)H=a,f(a),f(f(a),A=P(a),Q(a),P(f(a),Q(f(a),语义树：N0N11N12N21N22N23N24N31N32N33N34N35N36N37N38P(a)Q(a)P(f(

39、a)N41N42N43N44N45N46N47N48N49N410N411N413N415N412N414N416这是一个个无限树树，然而而它是否否是一个个封闭树树？Q(f(a)I(N41)=P(a),Q(a),P(f(a),Q(f(a),它使S的子句Q(f(y)的基例Q(f(a)为假，而N41的父辈不能能使子句句的基例例为假2/11/2020111人工智能能讲义封闭语义义树-举例例子子句集S=P(x)Q(x),P(f(y),Q(f(y)H=a,f(a),f(f(a),A=P(a),Q(a),P(f(a),Q(f(a),封闭语义义树：N0N11N12N21N22N23N24N31N32N36N

40、37N38P(a)Q(a)P(f(a)N41N42N49N410N413N414Q(f(a)2/11/2020112人工智能能讲义Herbrand定理H域H解释语义树结论：Herbrand定理理2/11/2020113人工智能能讲义Herbrand定理H域H解释语义树结论：Herbrand定理理2/11/2020114人工智能能讲义Herbrand定理理（结论）Herbrand定理理：子句集S是不可满满足的，当且仅仅当对应应于S的完全语语义数是是棵有限限封闭树树。子句集S是不可满满足的，当且仅仅当存在在不可满满足的S的有限基基例集。2/11/2020115人工智能能讲义Herbrand定理理（

41、结论）定理的意意义Herbrand定理已将将证明问问题转化化成了命命题逻辑辑问题。由此定理理保证，可以放放心的用用机器来来实现自自动推理理了。（归结原原理）注意Herbrand定理给出出了一阶阶逻辑的的半可判判定算法法，即仅仅当被证证明定理理是成立立时，使使用该算算法可以以在有限限步得证证。而当当被证定定理并不不成立时时，使用用该算法法得不出出任何结结论。但是2/11/2020116人工智能能讲义例S=P(x,g(x),y,h(x,y),z,k(x,y,z),P(u,v,e(v),w,f(v,w),x)有H0=a,S0=P(a,g(a),a,h(a,a),a,k(a,a,a),P(a,a,e(

42、a),a,f(a,a),a)H1=a,g(a),h(a,a),k(a,a,a),e(a),f(a,a)共6个元素S1：63+ 64= 1512个元素H2：元素个数数有63数量级（由于变变量最多多的函数数是k(x,y,z),三个变量量都都可能取取值于H1的六个元元素）S2：元素个数数有(63)4数量级建立S3，S4，直到S5才是不可可满足。然而S5元素个数数已达（ 1064）4=10256Herbrand定理理（结论）仍存在的的问题：基例集序序列元素素的数目目随子句句基的元元素数目目成指数数地增加加。因此，Herbrand定理是30年代提出出的，始始终没有有显著的的成绩。直至1965年Robin

43、son提出了归结原理理。2/11/2020117人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/2020118人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/2020119人工智能能讲义归结原理理归结原理理正确性性的根本本在于，找到矛矛盾可以以肯定不不真。方法：和命题逻逻辑一样样。但由于有有函数，所以要要考虑合一和置换。(定义与与例题参参考教科科书P41)2/11/2020120人工智能能讲义归结原理理置换和合合一的注注意事项项：谓词的一一致性，P()与Q

44、()，不可以常量的一一致性，P(a, )与P(b,.)，不可以常量与变变量，P(a, .)与P(x, )，可以变量与函函数，P(a, x, .)与P(x, f(x), )，不可以；但P(a, x, )与P(x, f(y), )，可以是不能同同时消去去两个互互补对，PQ与PQ的空，不不可以先进行内内部简化化（置换换、合并并）2/11/2020121人工智能能讲义归结原理理归结的过过程(P48)写出谓词词关系公公式用反演法法写出谓谓词表达达试SKOLEM标准形子句集S对S中可归结结的子句句做归结结 归结式仍仍放入S中，反复复归结过过程得到空子子句得证2/11/2020122人工智能能讲义归结原理理

45、归结法的的实质：归结法是是仅有一一条推理理规则的的推理方方法。归结的过过程是一一个语义义树倒塌塌的过程程。(P51)归结法的的问题子句中有有等号或或不等号号时，完完备性不不成立。Herbrand定理的不不实用性性引出了了可实用用的归结结法。2/11/2020123人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/2020124人工智能能讲义归结原理理概述命题逻辑辑的归结结法子句形Herbrand定理理归结原理理归结过程程的策略略控制2/11/2020125人工智能能讲义归结过程程的控制制策略要解决的的问题：归结方法法的知识识爆

46、炸。控制策略略的目的的归结点尽尽量少控制策略略的原则则给出控制制策略，以使仅仅对选择择合适的的子句间间方可做做归结。避免多多余的、不必要要的归结结式出现现。或者者说，少少做些归归结仍能能导出空空子句。2/11/2020126人工智能能讲义归结过程程的控制制策略盲目归结结例S=PQ,PQ,PQ,PQ是不可可满足。证明从S0=S开始始，依次次构造Si=C1,C2的归结式式|C1S0S1Si-1,C2Si-1 ,i=1,2,直直至得到到空子句句。具体体过程如如下：S0(1)PQ(2)PQ(3)PQ(4)PQS1(5)Q(1)(2)(6)P(1)(3)(7)QQ(1)(4)(8)PP(1)(4)(9)

47、Q Q(2)(3)(10)PP(2)(3)(11)P(2)(4)(12)Q(3)(4)2/11/2020127人工智能能讲义归结过程程的控制制策略(盲目归归结)S2(13)P(1)(7)(14)PQ(1)(8)(15)PQ(1)(9)(16)PQ(1)(10)(17)Q(1)(11)(18)P(1)(12)(19)Q(2)(6)(20)PQ(3)(4)(21)PQ(2)(8)(22)PQ(2)(9)(23)PQ(2)(10)(24)P(2)(12)(25)P(3)(5)(26)PQ(3)(7)(27) PQ(3)(8)(28) PQ(3)(9)(29) PQ(3)(10)(30)Q(3)(11

48、)(31)P(4)(5)(32)Q(4)(6)(33)PQ(4)(7)(34)PQ(4)(8)(35)PQ(4)(9)(36)PQ(4)(10)(37)Q(5)(7)(38)Q(5)(9)(39) (5)(12)产生过多多不必要要的归结结式。一一类是重重言式（7）-（10）由它们们又产生生了（13）-（16），（20）-（23），(26)-(29),(33)-(39)。另一类类是重复复的，如如P,Q,P,Q.2/11/2020128人工智能能讲义归结过程程的控制制策略删除策略略设有两个个子句C和D，若有置换换使得C D成立，便便说子句句C把子句D归类。例C=P(X)D=P(a)Q(a)取=a/

49、x,便有C =P(a)P(a),Q(a)。删除策略略：若对对s使用归结结推理过过程中，当归结结式Cj是重言式式或Cj被S中子句或或归结式式Ci(iQR解释I=P,Q,R2/11/2020131人工智能能讲义归结过程程的控制制策略线性归结结策略首先从子子句集S中选取取一个称称为顶子子句的子子句C0开始做归归结，其其次是归归结过程程中所得得到的归归结式Ci立即同另另一个子子句Bi进行归结结得归结结式Ci+1。而Bi属于S或或是已出出现的归归结式Cj(j完备采用支撑撑集完备语义归结结完备线性归结结完备单元归结结=完备输入归结结=完备2/11/2020135人工智能能讲义谓词逻辑辑的归结结方法对于子句

50、句C1L1和C2L2，如果L1与L2可合一，且s是其合一一者，则则(C1C2)s是其归结结式。例：P(x)Q(y),P(f(z)R(z)=Q(y)R(z)2/11/2020136人工智能能讲义归结举例例设公理集集：(x)(R(x)L(x)(x)(D(x)L(x)(x)(D(x)I(x)求证：(x)(I(x)R(x)化子句集集：(x)(R(x)L(x)=(x)(R(x)L(x)=R(x)L(x)(1)2/11/2020137人工智能能讲义(x)(D(x)L(x)=(x)(D(x)L(x)=D(x)L(x)(2)(x)(D(x)I(x)=D(A)I(A)=D(A)(3)I(A)(4)2/11/20

51、20138人工智能能讲义目标求反反：(x)(I(x)R(x)=(x)(I(x)R(x)=(x)(I(x)R(x)=I(x)R(x)(5)换名后得得字句集集：R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)2/11/2020139人工智能能讲义例题得归归结树R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)I(A)I(x5)R(x5)R(A) A/x5R(x1)L(x1)L(A) A/x1D(x2)L(x2)D(A) A/x2D(A)nil2/11/2020140人工智能能讲义归结反演演求解-提取回答答的过程程先进行归归结，证证明结论论的正确确性；用重言式式代替结结论求反反得到的的子句；按照证明明过程，进行归归结；最后，在在原来为为空的地地方，得得到的就就是提取取的回答答。修改后的的证明树树称为修改证明明树2/11/2020141人工智能能讲义归结反演演求解-举例“如果无无论John到到哪里去去，Fido也也就去那那里，那那么如果果John在学学校，Fido在哪里里？”已知：(x)AT(John,x)AT(Fido, x)AT(John,School)求证：(x)AT(Fido, x)如果我们们首先证证明公式式(x)AT(Fi