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

1、人工智能一般搜索算法原理1532022/7/15人工智能一般搜索算法原理153盲目搜索图搜索策略深度优先搜索宽度优先搜索等代价搜索2022/7/152人工智能一般搜索算法原理153一些基本概念节点深度：根节点深度=0其它节点深度=父节点深度+101232022/7/153人工智能一般搜索算法原理153一些基本概念（续1）路径设一节点序列为(n0, n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。2022/7/154人工智能一

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

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

4、PEN=( ) EXIT (FAIL);3, n=FIRST(OPEN);4, IF GOAL(n) EXIT (SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, IF DEPTH(n)Dm GO LOOP;7, EXPAND(n) mi, G=ADD(mi, G);8, IF 目标在mi中 THEN EXIT(SUCCESS);9, ADD(mj, OPEN), 并标记mj到n的指针;10, GO LOOP;2022/7/159人工智能一般搜索算法原理1532 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8

5、 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 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目标2022/7/1510人工智能一般搜索算法原理153深度优先搜索的性质一

6、般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法2022/7/1511人工智能一般搜索算法原理153宽度优先搜索如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索使逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”2022/7/1512人工智能一般搜索算法原理153宽度优先搜索算法1, G=G0(G0=s), OPEN=(s), CLOSED=( );2, LOOP: IF OPEN=( ) EXIT (

7、FAIL);3, n=FIRST(OPEN);4, IF GOAL(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, GO LOOP;2022/7/1513人工智能一般搜索算法原理1532 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 31 6 47 52 8 3

8、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 5目标82 3 41 8 7 6 542022/7/1514人工智能一般搜索算法原理153宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法2022/7/1515人工智能一般搜索算法原理153等代价搜索宽度优先搜索可被推广用来解决寻找从

9、起始节点到目标节点具有最小代价路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。2022/7/1516人工智能一般搜索算法原理153等代价搜索算法算法1,G=G0(G0=s), OPEN=(s), CLOSED=( ),g(s)=0;2, LOOP: IF OPEN=( ) EXIT (FAIL);3, 从OPEN表中选择一个节点i,使其g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为i(要是有目标节点的话)；否则，就从中选一个作为节点I; REMOVE(i, OPEN), ADD(i, CLOSED);4, IF GOAL(i) EXIT (SUCCESS);5,

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

11、搜索算法原理153基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。2022/7/1520人工智能一般搜索算法原理1531，启发式搜索算法A（A算法）评价函数的格式：f(n) = g(n) + h(n)f(n)：评价函数h(n)：启发函数2022/7/1521人工智能一般搜索算法原理153符号的意义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)的估计值2022/7/1522人工智能一般搜索算法原理

12、153A算法1, OPEN=(s), f(s)=g(s)+h(s);2, LOOP: IF OPEN=( ) EXIT(FAIL);3, n=FIRST(OPEN);4, IF GOAL(n) EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) Mi, 计算f(n, mi)=g(n, mi)+h(mi);2022/7/1523人工智能一般搜索算法原理153A算法（续）ADD(mj, OPEN), 标记mj到n的指针；IF f(n, mk)f(mk) f(mk)=f(n, mk), 标记mk到n的指针；IF f(n, ml)

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

14、扩展的节点数A2扩展的节点数2022/7/1537人工智能一般搜索算法原理153A*算法的改进问题的提出：因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。2022/7/1538人工智能一般搜索算法原理153s(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

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

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

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

18、s)2022/7/1548人工智能一般搜索算法原理153修正过程A1, OPEN=(s), f(s)=g(s)+h(s), fm=0;2, LOOP: IF OPEN=( ) EXIT(FAIL);3, NEST=ni|f(ni)5)n2(4)n3(4)n0(3)n0(3-4)2022/7/1562人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1-2)2022/7/1563人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8红色代价：5蓝色代价：6n0(4)n4(1

19、)n5(1-2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4-5)2022/7/1564人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022/7/1565人工智能一般搜索算法原理153目标目标初始节点n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022/7/1566人工智能一般搜索算法原理153目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点可解n0(5)n4(1)n

20、5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022/7/1567人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制2022/7/1568人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制2022/7/1569人工智能一般搜索算法原理153概述归结原理由J.A.Robinson由1965年提出。与演绎法完全不同，新的逻辑演算算法。一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。 语义网络

21、、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。 而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。 2022/7/1570人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制2022/7/1571人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制2022/7/1572人工智能一般搜索算法原理153命题逻辑的归结法基本单元：简单命题（陈述句）例： 命题：

22、 A1、A2、A3 和 B求证： A1A2A3成立，则B成立，即：A1A2A3 B反证法：证明A1A2A3B 是矛盾式 （永假式） 2022/7/1573人工智能一般搜索算法原理153命题逻辑的归结法建立子句集合取范式：命题、命题和的与， 如：P（ PQ）（ PQ）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：P（ PQ）（ PQ） 子句集 S：S = P, PQ, PQ 2022/7/1574人工智能一般搜索算法原理153命题逻辑的归结法归结式消除互补对，求新子句得到归结式。如子句：C1= C1L, C2 = C2 归结式：R(C1, C2) = C1 C2注意：C1C2 R(

23、C1, C2) ， 反之不一定成立。 假言推理: 由合适公式W1和W1 W2产生合适公式W2 ,如何用归结法证明?2022/7/1575人工智能一般搜索算法原理153命题逻辑的归结法归结过程 对结论作否定,并加入前提中将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句 ，S是不可满足的（矛盾），原命题成立。 （证明完毕）谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。 2022/7/1576人工智能一般搜索算法原理153命题逻辑的归结法例 证明先将化为合取范式 建立子句集 S=对S做归结 P NIL2022/7/1577人工智能一般搜索算法原理

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

25、ixi为存在量词或全称量词, M(x1, , xn) 为合取范式(由一些子句的合取组成)。2022/7/1580人工智能一般搜索算法原理153子句形( Skolem 标准形) 量词消去原则：消去存在量词“”，略去全程量词“”。注意：左边有全称量词的存在量词，消去时该变量改写成为全称量词的函数(Skloem函数)；如没有，改写成为常量。 例子：见人工智能及其应用P752022/7/1581人工智能一般搜索算法原理153子句形( Skolem 标准形) 定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。 SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKO

26、LEM标准形同G并不等值。 2022/7/1582人工智能一般搜索算法原理153子句形( 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)2022/7/1583人工智能一般搜索算法原理153子句形子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取： G SKOLEM标准形 消去存在变量 以“，”取代“”，并表示为集合形式 。2022/7/1584人工智能一般搜索算法原理153子句形 G是不可满足的 S是不可满足的G与S不等

27、价，但在不可满足的意义下是一致的。 定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的 S是不可满足的。 注意：G真不一定S真，而S真必有G真。即： S = G2022/7/1585人工智能一般搜索算法原理153子句形G = G1 G2 G3 Gn 的子句形G的子句集可以分解成几个单独处理。 有 SG = S1 U S2 U S3 U U Sn则SG 与 S1 U S2 U S3 U U Sn在不可满足的意义上是一致的。即SG 不可满足 S1 U S2 U S3 U U Sn不可满足2022/7/1586人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Herbrand

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

29、（或永假）的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。” 2022/7/1590人工智能一般搜索算法原理153Herbrand定理Herbrand的思想定义：公式G永真：对于G的所有解释，G都为真。思想：寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且算法在有限步内停止。 2022/7/1591人工智能一般搜索算法原理153Herbrand定理H域H解释语义树结论：Herbrand定理2022/7/1592人工智能一般搜索算法原理153Herbrand定理H域H解释语义树结论：Herbrand定理2022/7/1593人工智能一般

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

31、022/7/1595人工智能一般搜索算法原理153Herbrand定理（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上的真值可确定。成为可数问题。 2022/7/1596人工智能一般搜索算法原理153原子集举例例1 S=P(a), P(x)P(f(x) H= a,f(a),f(f(a)，

32、 S的原子集为 A=P(a),P(f(a),P(f(f(a), 2022/7/1597人工智能一般搜索算法原理153Herbrand定理（H域）没有变量出现的原子、文字、子句和子句集，分别称作基原子、基文字、基子句和基子句集。它们在讨论子句集S的不可满足性时占有重要置。2022/7/1598人工智能一般搜索算法原理153Herbrand定理H域H解释语义树结论：Herbrand定理2022/7/1599人工智能一般搜索算法原理153Herbrand定理H域H解释语义树结论：Herbrand定理2022/7/15100人工智能一般搜索算法原理153Herbrand定理（H解释）解释I*：取一个值

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

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

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

36、结论：Herbrand定理2022/7/15106人工智能一般搜索算法原理153Herbrand定理（语义树）构成方法原子集中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上（可不完全画完） 。(P34)特点一般情况H是可数集，S的语义树是无限树。 2022/7/15107人工智能一般搜索算法原理153Herbrand定理（语义树）意义S H A 语义树可以理解语义树为H域的图形解释。 目的：把每个解释都摊开。语义树中包含原子集的全部元素，因此，语义树是完全的。每一个直到叶子节点的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。如果每个基例都为假，则可认为是不

37、可满足的。2022/7/15108人工智能一般搜索算法原理153语义树-举例例1 设子句集S的原子集 A=P,Q,R 语义树： N0 N11N12N21N22N23N24N31N32N33N34N35N36N37N38P QQR R PI(N)表示从根节点到节点N分枝上所标记的所有文字的并集。如 I(N34)=P, Q, R2022/7/15109人工智能一般搜索算法原理153Herbrand定理（语义树）几个概念失败结点： 当（由上）延伸到点N时，I(N)已表明了S的某子句的某基例假。但N以前尚不能判断这事实。就称N为失败结点。完全语义树： 如果对语义树的所有叶结点N来说， I(N)包含了S

38、的原子集 A=A1,A2,中的所有元素Ai或 Ai，I=1 n。封闭语义树：如果S的完全语义树的每个分枝上都有一个失败结点，就称它是一棵封闭语义树。2022/7/15110人工智能一般搜索算法原理153封闭语义树-举例例 子句集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), 语义树： N0 N11N12N21N22N23N24N31N32N33N34N35N36N37N38P(a)Q(a)P(f(a)N41N42N43N44N45N46N47N48N49N410N411N413N415N412N414N

39、416这是一个无限树，然而它是否是一个封闭树？Q(f(a)I(N41)=P(a),Q(a),P(f(a),Q(f(a),它使S的子句Q(f(y)的基例Q(f(a)为假，而N41的父辈不能使子句的基例为假2022/7/15111人工智能一般搜索算法原理153封闭语义树-举例例 子句集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), 封闭语义树： N0 N11N12N21N22N23N24N31N32N36N37N38P(a)Q(a)P(f(a)N41N42N49N410N413N414Q(f(a)2022/

40、7/15112人工智能一般搜索算法原理153Herbrand定理H域H解释语义树结论：Herbrand定理2022/7/15113人工智能一般搜索算法原理153Herbrand定理H域H解释语义树结论：Herbrand定理2022/7/15114人工智能一般搜索算法原理153Herbrand定理（结论）Herbrand定理：子句集S是不可满足的，当且仅当对应于S的完全语义数是棵有限封闭树。 子句集S是不可满足的，当且仅当存在不可满足的S的有限基例集。 2022/7/15115人工智能一般搜索算法原理153Herbrand定理（结论）定理的意义Herbrand定理已将证明问题转化成了命题逻辑问题

41、。由此定理保证，可以放心的用机器来实现自动推理了。（归结原理）注意Herbrand定理给出了一阶逻辑的半可判定算法，即仅当被证明定理是成立时，使用该算法可以在有限步得证。而当被证定理并不成立时，使用该算法得不出任何结论。但是 2022/7/15116人工智能一般搜索算法原理153例 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(a),a,f(a,a),a) H1=a,g(a),h(a,a),k(a,a,a),e(a),f(a,a) 共6个

42、元素 S1： 63 + 64 = 1512个元素 H2 ： 元素个数有 63 数量级（由于变量最多的函数是k(x,y,z),三个变 量都可能取值于H1的六个元素） S2 ：元素个数有 (63) 4 数量级建立S3 ， S4 ，直到S5才是不可满足。然而 S5元素个数已达（ 10 64）4=10256Herbrand定理（结论）仍存在的问题：基例集序列元素的数目随子句基的元素数目成指数地增加。因此，Herbrand定理是30年代提出的，始终没有显著的成绩。 直至1965年Robinson提出了归结原理。2022/7/15117人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Her

43、brand定理归结原理归结过程的策略控制2022/7/15118人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制2022/7/15119人工智能一般搜索算法原理153归结原理归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。 (定义与例题参考教科书P41)2022/7/15120人工智能一般搜索算法原理153归结原理置换和合一的注意事项：谓词的一致性，P()与Q()， 不可以常量的一致性，P(a, )与P(b,.)， 不可以 常量与变量，P(a, .)与P(x, )， 可以变量

44、与函数，P(a, x, .)与P(x, f(x), )，不可以；但P(a, x, )与P(x, f(y), )，可以是不能同时消去两个互补对，PQ与PQ的空，不可以先进行内部简化（置换、合并） 2022/7/15121人工智能一般搜索算法原理153归结原理归结的过程(P48)写出谓词关系公式 用反演法写出谓词表达试 SKOLEM标准形 子句集S 对S中可归结的子句做归结 归结式仍放入S中，反复归结过程 得到空子句 得证2022/7/15122人工智能一般搜索算法原理153归结原理归结法的实质：归结法是仅有一条推理规则的推理方法。 归结的过程是一个语义树倒塌的过程。 (P51)归结法的问题子句中

45、有等号或不等号时，完备性不成立。 Herbrand定理的不实用性引出了可实用的归结法。2022/7/15123人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制2022/7/15124人工智能一般搜索算法原理153归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制2022/7/15125人工智能一般搜索算法原理153归结过程的控制策略要解决的问题：归结方法的知识爆炸。控制策略的目的归结点尽量少控制策略的原则给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结

46、仍能导出空子句。2022/7/15126人工智能一般搜索算法原理153归结过程的控制策略盲目归结 例 S=PQ, PQ,PQ, PQ是不可满足。 证明从S0=S开始，依次构造 Si=C1,C2的归结式|C1S0S1 Si-1,C2 Si-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)Q Q (2)(3) (10)PP (2)(3) (11)P (2)(4) (12)Q (3)(4)2022/7/15127人工智能一般搜索

47、算法原理153归结过程的控制策略(盲目归结)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) (31)P (4)(5) (32)Q

48、(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.2022/7/15128人工智能一般搜索算法原理153归结过程的控制策略删除策略 设有两个子句C和D，若有置换使得 C D成立，便说子句C把子句D归类。例 C=P(X) D=P(a)Q(a) 取=a/x,便有C

49、=P(a) P(a),Q(a)。删除策略：若对s使用归结推理过程中，当归结式Cj是重言式或Cj被S中子句或归结式Ci(iQR 解释I=P, Q, R 2022/7/15131人工智能一般搜索算法原理153归结过程的控制策略线性归结策略 首先从子句集S中选取一个称为顶子句的子句C0开始做归结，其次是归结过程中所得到的归结式Ci立即同另一个子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(j完备采用支撑集完备语义归结完备线性归结 完备单元归结=完备输入归结 =完备2022/7/15135人工智能一般搜索算法原理153谓词逻辑的归结方法对于子句C1L1和C2L2，如果L1与L2可

50、合一，且s是其合一者，则(C1C2)s是其归结式。例： P(x)Q(y), P(f(z)R(z) = Q(y)R(z)2022/7/15136人工智能一般搜索算法原理153归结举例设公理集：(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)2022/7/15137人工智能一般搜索算法原理153 (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)

51、 (4)2022/7/15138人工智能一般搜索算法原理153目标求反： (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)2022/7/15139人工智能一般搜索算法原理153例题得归结树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/x5 R(x1)L(x1) L(A) A/x1 D(x2)L(x2) D(A) A/x2 D(A) nil2022/7/15140

52、人工智能一般搜索算法原理153归结反演求解-提取回答的过程先进行归结，证明结论的正确性；用重言式代替结论求反得到的子句；按照证明过程，进行归结；最后，在原来为空的地方，得到的就是提取的回答。修改后的证明树称为修改证明树2022/7/15141人工智能一般搜索算法原理153归结反演求解-举例“如果无论John到哪里去，Fido也就去那里，那么如果John在学校，Fido在哪里？”已知：(x)AT(John, x) AT(Fido, x) AT(John, School)求证：(x)AT(Fido, x)如果我们首先证明公式 (x)AT(Fido, x) 在逻辑上遵循前提公式集，然后寻求一个存在x的例，那么就能解决“Fido在哪里”的问题。2022/7/15142人工智能一般搜索算法原理153归结反演求解-基于归结的