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

第三章一般搜索原理盲目搜索启发式搜索归结原理10/29/20231人工智能讲义盲目搜索图搜索策略深度优先搜索宽度优先搜索等代价搜索10/29/20232人工智能讲义一些基本概念节点深度： 根节点深度=0 其它节点深度=父节点深度+1012310/29/20233人工智能讲义一些基本概念（续1）路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。10/29/20234人工智能讲义一些基本概念（续1）扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。10/29/20235人工智能讲义一般的图搜索算法（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);10/29/20236人工智能讲义一般的图搜索算法（续）7,标记和修改指针： ADD(mj,OPEN),并标记mj到n的指针； 计算是否要修改mk、ml到n的指针； 计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；10/29/20237人工智能讲义深度优先搜索在深度优先搜索中，首先扩展最新产生的(最深的)节点，深度相等的节点可以任意排列。“最晚产生的节点最先扩展”10/29/20238人工智能讲义深度优先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPEN=()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}中THENEXIT(SUCCESS);9,ADD(mj,OPEN),并标记mj到n的指针;10,GOLOOP;10/29/20239人工智能讲义231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目标10/29/202310人工智能讲义深度优先搜索的性质一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法10/29/202311人工智能讲义宽度优先搜索如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索使逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”10/29/202312人工智能讲义宽度优先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();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},G=ADD(mi,G);7,IF目标在{mi}中THENEXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GOLOOP;10/29/202313人工智能讲义23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标823418765410/29/202314人工智能讲义宽度优先搜索的性质当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法10/29/202315人工智能讲义等代价搜索宽度优先搜索可被推广用来解决寻找从起始节点到目标节点具有最小代价路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。10/29/202316人工智能讲义等代价搜索算法算法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);6,对每个后继节点j,计算g(j)=g(i)+c(i,j)且ADD(OPEN,j),并标记j到i的指针;7,GOLOOP;10/29/202317人工智能讲义启发式图搜索利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解10/29/202318人工智能讲义希望：引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。10/29/202319人工智能讲义基本思想定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。10/29/202320人工智能讲义1，启发式搜索算法A（A算法）评价函数的格式： f(n)=g(n)+h(n) f(n)：评价函数 h(n)：启发函数10/29/202321人工智能讲义符号的意义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)的估计值10/29/202322人工智能讲义A算法1,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);

10/29/202323人工智能讲义A算法（续）

ADD(mj,OPEN),标记mj到n的指针； IFf(n,mk)<f(mk)f(mk)=f(n,mk),

标记mk到n的指针； IFf(n,ml)<f(ml,)f(ml)=f(n,ml), 标记ml到n的指针, ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GOLOOP；10/29/202324人工智能讲义一个A算法的例子定义评价函数： f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值 h(n)为当前节点“不在位”的将牌数

283164751238476510/29/202325人工智能讲义h计算举例 h(n)=42

831

64751234576810/29/202326人工智能讲义2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456定义评价函数： f(n)=g(n)+h(n) g(n)为从初始节点到当前节点的耗散值 h(n)为当前节点“不在位”的将牌数10/29/202327人工智能讲义最佳图搜索算法A*（A*算法）在A算法中，如果满足条件： h(n)≤h*(n) 则A算法称为A*算法。10/29/202328人工智能讲义A*条件举例8数码问题h(n)=“不在位”的将牌数h(n)=将牌“不在位”的距离和2

831

647512345768将牌1：1将牌2：1将牌6：1将牌8：210/29/202329人工智能讲义A*算法的性质定理1： 对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。10/29/202330人工智能讲义A*算法的性质（续1）引理2.1： 对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。10/29/202331人工智能讲义A*算法的性质（续2）引理2.2： A*结束前，OPEN表中必存在f(n)≤f*(s)。10/29/202332人工智能讲义A*算法的性质（续3）定理2： 对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。10/29/202333人工智能讲义A*算法的性质（续4）推论2.1： OPEN表上任一具有f(n)<f*(s)的节点n，最终都将被A*选作扩展的节点。10/29/202334人工智能讲义A*算法的性质（续5）定理3(可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。10/29/202335人工智能讲义A*算法的性质（续6）推论3.1： A*选作扩展的任一节点n，有f(n)≤f*(s)。10/29/202336人工智能讲义A*算法的性质（续7）定理4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)>h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)>h1(n),则A1扩展的节点数≥A2扩展的节点数10/29/202337人工智能讲义A*算法的改进问题的提出： 因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。10/29/202338人工智能讲义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(10)A(5)B(7)C(9)s(10)A(4)B(7)C(9)s(10)10/29/202339人工智能讲义出现多次扩展节点的原因在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。10/29/202340人工智能讲义解决的途径对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。10/29/202341人工智能讲义改进的条件可采纳性不变不多扩展节点不增加算法的复杂性10/29/202342人工智能讲义对h加以限制定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足 h(ni)-h(nj)≤c(ni,nj) h(t)=0 则称h是单调的。h(ni)ninjh(nj)c(ni,nj)10/29/202343人工智能讲义h单调的性质定理5： 若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。 即：当A*选n扩展时，有g(n)=g*(n)。10/29/202344人工智能讲义h单调的性质（续）定理6： 若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。10/29/202345人工智能讲义h单调的例子8数码问题：h为“不在位”的将牌数1 h(ni)-h(nj)=0 (nj为ni的后继节点)-1 h(t)=0 c(ni,nj)=1满足单调的条件。 10/29/202346人工智能讲义对算法加以改进一些结论：OPEN表上任一具有f(n)<f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)≤f*(s)。10/29/202347人工智能讲义改进的出发点OPEN=(…………)f*(s)f值小于f*(s)的节点f值大于等于f*(s)的节点fm：到目前为止已扩展节点的最大f值，用fm代替f*(s)10/29/202348人工智能讲义修正过程A1,OPEN=(s),f(s)=g(s)+h(s),fm=0;2,LOOP:IFOPEN=()EXIT(FAIL);3,NEST={ni|f(ni)<fm} IFNEST≠()n=NEST中g最小的节点 ELSEn=FIRST(OPEN), fm=f(n);4,…,8:同过程A。10/29/202349人工智能讲义s(10)A(1)B(5)C(8)G目标631118前面的例子：OPEN表CLOSED表fms(0+10)s(0+10)10A(6+1)B(3+5)C(1+8)s(0+10)C(1+8)10A(6+1)B(2+5)s(0+10)C(1+8)B(2+5)10A(3+1)s(0+10)C(1+8)B(2+5)A(3+1)10G(11+0)10/29/202350人工智能讲义例子：传教士与野人问题

设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡河过去？

10/29/202351人工智能讲义问题表示：需要考虑两岸的修道士人数和野人人数，船的位置。用三元式表示状态：

S=(m,c,b)

其中，m表示左岸修道士人数，c表示左岸野人人数，b表示左岸船的数目。解：确定估价函数。

f(n)=g(n)＋h(n)=d(n)＋m＋c－2b

其中，d(n)为节点深度。h(n)＜h*(n)，满足A*算法的限制条件。10/29/202352人工智能讲义(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7传教士和野人问题的A*搜索图(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)10/29/202353人工智能讲义4.5AO*算法搜索与或图的A*算法节点评价方法

A*算法中，对节点n的评价，实际上是对“初始节点--节点n--目标节点”这一条路径的评价AO*算法中，由于与节点的存在，解对应的不是一条路径，而是一个子图，因此对节点的评价，实际是对局部解图的评价10/29/202354人工智能讲义

A(6)

B

C

D(3)(4)(5)f(A)=min{(B)+(C)+2,(D)+1}

G

H

E

F(4)(4)(5)(7)(10)(9)(6)(11)与或图节点扩展与评价10/29/202355人工智能讲义算法的两个阶段第一阶段：自上而下的图生成过程

对于每一个已经扩展过的节点，都对应一个指针，指向该节点后继节点中，代价值小的那条边。图生成过程，就是从初始节点出发，按照该指针向下搜索，一直到找到一个未扩展的节点为止。然后扩展该节点。第二阶段：自下而上的代价值计算过程

设n为最新被扩展的节点，计算节点n对应的最小代价值，并标记一个指针指向对应最小代价的边。对于n的父节点，进行同样的计算。重复这一过程，直到初始节点s为止。这时，从s出发，选择那些指针所指向的边得到的局部图，为当前代价值最小的局部图。10/29/202356人工智能讲义具体步骤Step1建立一个仅由初始节点s构成的搜索图G，计算h(s)Step2在以下两过程间循环，直到s标记为可解或不可解，或其代价值大于阈值：

2.1选择节点进行扩展

2.2根据扩展情况修改节点的可解性与代价值

10/29/202357人工智能讲义Step2.1选择节点进行扩展：1根据指针找出待扩展的局部解图G′。

2选择G′中的一个非终节点n作为当前节点。

3扩展节点n，如不能扩展，则标记为不可解，否则生成子节点集，如子节点为非终节点，计算其代价值，若为终节点，标注其可解。将所有子节点添加到G中。4建立含n的单一节点集合S，S:＝{n}10/29/202358人工智能讲义Step2.2修改节点的可解性与代价值

重复以下步骤，直到S为空：

1从S中挑选一个子孙节点都不在S中的节点m2计算始于m的每条连接线的代价，取其中最小值为m对应的代价，并在对应于最小代价的连接线上加指针。3如果连接于最小代价连接线上的所有节点都可解，则标注m可解。4如果m的可解性或代价值发生改变，则把m的所有祖先节点添加到S中。10/29/202359人工智能讲义AO*算法举例目标目标初始节点n0n1n2n3n4n5n6n7n8h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2

h(n7)=0h(n8)=0连接线的代价=后继节点个数10/29/202360人工智能讲义n0n1n2n3n4n5n6n7n8n0(3)n1(2)n4(1)n5(1)红色代价：4蓝色代价：310/29/202361人工智能讲义n0n1n2n3n4n5n6n7n8n4(1)n5(1)红色代价：4蓝色代价：6n1(2->5)n2(4)n3(4)n0(3)n0(3->4)10/29/202362人工智能讲义n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1->2)10/29/202363人工智能讲义n0n1n2n3n4n5n6n7n8红色代价：5蓝色代价：6n0(4)n4(1)n5(1->2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4->5)10/29/202364人工智能讲义n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)10/29/202365人工智能讲义目标目标初始节点n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)10/29/202366人工智能讲义目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)10/29/202367人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/202368人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/202369人工智能讲义概述归结原理由J.A.Robinson由1965年提出。与演绎法完全不同，新的逻辑演算算法。一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。

10/29/202370人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/202371人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/202372人工智能讲义命题逻辑的归结法基本单元：简单命题（陈述句）例：

命题：A1、A2、A3和B求证：A1ΛA2ΛA3成立，则B成立，即：A1ΛA2ΛA3→B反证法：证明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

10/29/202373人工智能讲义命题逻辑的归结法建立子句集合取范式：命题、命题和的与，如： PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

10/29/202374人工智能讲义命题逻辑的归结法归结式消除互补对，求新子句→得到归结式。如子句：C1=C1′∨L,C2=C2′∨

归结式：R(C1,C2)=C1′∨

C2′

注意：C1ΛC2→R(C1,C2)，反之不一定成立。假言推理:由合适公式W1和W1

→W2产生合适公式W2,如何用归结法证明?10/29/202375人工智能讲义命题逻辑的归结法归结过程

对结论作否定,并加入前提中将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句□，S是不可满足的（矛盾），原命题成立。（证明完毕）谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。10/29/202376人工智能讲义命题逻辑的归结法例证明先将化为合取范式建立子句集S=对S做归结PNIL10/29/202377人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/202378人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/202379人工智能讲义子句形引用Herbrand定理，以说明归结原理的意义及一个原理形成的根基与背景SKOLEM标准形前束范式：把所有的量词都提到前面去，然后消掉所有量词。

定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。即(Q1x1)…(Qnxn)M(x1,…,xn),其中Qixi为存在量词或全称量词,M(x1,…,xn)为合取范式(由一些子句的合取组成)。10/29/202380人工智能讲义子句形(Skolem标准形)

量词消去原则： 消去存在量词“

”，略去全程量词“

”。

注意：左边有全称量词的存在量词，消去时该变量改写成为全称量词的函数(Skloem函数)；如没有，改写成为常量。

例子：见《人工智能及其应用》P7510/29/202381人工智能讲义子句形(Skolem标准形)

定理： 谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义： 消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。10/29/202382人工智能讲义子句形(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)

10/29/202383人工智能讲义子句形子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：G→SKOLEM标准形 →消去存在变量 →以“，”取代“Λ”，并表示为集合形式。10/29/202384人工智能讲义子句形

G是不可满足的<=>S是不可满足的G与S不等价，但在不可满足的意义下是一致的。

定理： 若G是给定的公式，而S是相应的子句集，则G是不可满足的<=>S是不可满足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G10/29/202385人工智能讲义子句形G=G1ΛG2ΛG3Λ…ΛGn的子句形G的子句集可以分解成几个单独处理。

有SG=S1US2US3U…USn 则SG

与S1US2US3U…USn在不可满足的意义上是一致的。 即SG不可满足<=>S1US2US3U…USn不可满足

10/29/202386人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/202387人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/202388人工智能讲义Herbrand定理问题： 一阶逻辑公式的永真性（永假性）的判定是否能在有限步内完成？10/29/202389人工智能讲义Herbrand定理1936年图灵(Turing)和邱吉(Church)互相独立地证明了：“没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（或永假）的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。”10/29/202390人工智能讲义Herbrand定理Herbrand的思想定义： 公式G永真：对于G的所有解释，G都为真。思想：

寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且算法在有限步内停止。10/29/202391人工智能讲义Herbrand定理H域H解释语义树结论：Herbrand定理10/29/202392人工智能讲义Herbrand定理H域H解释语义树结论：Herbrand定理10/29/202393人工智能讲义Herbrand定理（H域）基本方法：因为量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限、不可数的。简化讨论域。建立一个比较简单、特殊的域，使得只要在这个论域上，该公式是不可满足的。此域称为H域：H0为G中所出现的常量的集合，若G中没有常量，就任取常量，H0={a}。

规定为H域

※

例题请参考教科书P2710/29/202394人工智能讲义H域举例例1S={P(a),～P(x)∨P(f(x))}依定义有 H0={a} H1={a}U{f(a)}={a,f(a)} H2={a,f(a)}U{f(a),f(f(a))}={a,f(a),f(f(a))} … H∞={a,f(a),f(f(a))，…}10/29/202395人工智能讲义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上的真值可确定。成为可数问题。10/29/202396人工智能讲义原子集举例例1S={P(a),～P(x)∨P(f(x))}H∞={a,f(a),f(f(a))，…}S的原子集为A={P(a),P(f(a)),P(f(f(a))),…}10/29/202397人工智能讲义Herbrand定理（H域）没有变量出现的原子、文字、子句和子句集，分别称作基原子、基文字、基子句和基子句集。它们在讨论子句集S的不可满足性时占有重要置。10/29/202398人工智能讲义Herbrand定理H域H解释语义树结论：Herbrand定理10/29/202399人工智能讲义Herbrand定理H域H解释语义树结论：Herbrand定理10/29/2023100人工智能讲义Herbrand定理（H解释）解释I*：取一个值得到一个结论I映射S中到所有常量符号到它们本身。(即原子集)令f是n元函数，I是f下的一个指派，即H中的元素到f的一个映射（函数值）。简单地说(P29)，A中的各元素真假组合都是H的解释。（或真或假只取一个）问题：对于所有的解释，全是假才可判定。因为所有解释代表了所有的情况，如可穷举，问题便可解决。

10/29/2023101人工智能讲义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(f(f(a))),…} S|I1*=T

I2*={～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成立。10/29/2023102人工智能讲义Herbrand定理（H解释）如下三个定理保证了归结法的正确性：定理1：

设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I=T，必有S|I*=T。定理2： 子句集S是不可满足的，当且仅当所有的S的H解释下为假。定理3： 子句集S是不可满足的，当且仅当对每一个解释I下，至少有S的某个子句的某个基例为假。10/29/2023103人工智能讲义Herbrand定理（H解释）基例S中某子句中所有变元符号均以S的H域中的元素代入时，所得的基子句C’称为C的一个基例。若一个子句为假，则此解释为假。一般来说，D是无穷不可列的，因此，子句集S也是无穷不可列的。但S确定后H是无穷可列的。不过在H上证明S的不可满足性仍然是不可能的。解决问题的方法：语义树10/29/2023104人工智能讲义Herbrand定理H域H解释语义树结论：Herbrand定理10/29/2023105人工智能讲义Herbrand定理H域H解释语义树结论：Herbrand定理10/29/2023106人工智能讲义Herbrand定理（语义树）构成方法原子集中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上（可不完全画完）。(P34)特点一般情况H是可数集，S的语义树是无限树。10/29/2023107人工智能讲义Herbrand定理（语义树）意义SHA语义树可以理解语义树为H域的图形解释。目的：把每个解释都摊开。语义树中包含原子集的全部元素，因此，语义树是完全的。每一个直到叶子节点的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。如果每个基例都为假，则可认为是不可满足的。10/29/2023108人工智能讲义语义树-举例例1设子句集S的原子集A={P,Q,R}

语义树：

N0

N11N12N21N22N23N24N31N32N33N34N35N36N37N38P～QQR～R～PI(N)表示从根节点到节点N分枝上所标记的所有文字的并集。如I(N34)={P,～Q,～R}10/29/2023109人工智能讲义Herbrand定理（语义树）几个概念失败结点： 当（由上）延伸到点N时，I(N)已表明了S的某子句的某基例假。但N以前尚不能判断这事实。就称N为失败结点。完全语义树：如果对语义树的所有叶结点N来说，I(N)包含了S的原子集A={A1,A2,…}中的所有元素Ai或～Ai，I=1…n。封闭语义树： 如果S的完全语义树的每个分枝上都有一个失败结点，就称它是一棵封闭语义树。10/29/2023110人工智能讲义封闭语义树-举例例子句集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))N41N42N43N44N45N46N47N48N49N410N411N413N415N412N414N416这是一个无限树，然而它是否是一个封闭树？Q(f(a))ΧΧΧΧΧΧΧΧΧΧI(N41)={P(a),Q(a),P(f(a)),Q(f(a))},它使S的子句～Q(f(y))的基例～Q(f(a))为假，而N41的父辈不能使子句的基例为假10/29/2023111人工智能讲义封闭语义树-举例例子句集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))ΧΧΧΧΧΧΧΧΧΧ10/29/2023112人工智能讲义Herbrand定理H域H解释语义树结论：Herbrand定理10/29/2023113人工智能讲义Herbrand定理H域H解释语义树结论：Herbrand定理10/29/2023114人工智能讲义Herbrand定理（结论）Herbrand定理：子句集S是不可满足的，当且仅当对应于S的完全语义数是棵有限封闭树。

子句集S是不可满足的，当且仅当存在不可满足的S的有限基例集。

10/29/2023115人工智能讲义Herbrand定理（结论）定理的意义Herbrand定理已将证明问题转化成了命题逻辑问题。由此定理保证，可以放心的用机器来实现自动推理了。（归结原理）注意Herbrand定理给出了一阶逻辑的半可判定算法，即仅当被证明定理是成立时，使用该算法可以在有限步得证。而当被证定理并不成立时，使用该算法得不出任何结论。但是

10/29/2023116人工智能讲义例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个元素S1´：

63+64=1512个元素

H2：元素个数有63数量级（由于变量最多的函数是k(x,y,z),三个变量都可能取值于H1的六个元素）S2´：元素个数有(63)

4数量级建立S3´，S4´，直到S5´才是不可满足。然而

S5´元素个数已达（1064）4=10256Herbrand定理（结论）仍存在的问题：基例集序列元素的数目随子句基的元素数目成指数地增加。因此，Herbrand定理是30年代提出的，始终没有显著的成绩。

直至1965年Robinson提出了归结原理。10/29/2023117人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/2023118人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/2023119人工智能讲义归结原理归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。(定义与例题参考教科书P41)10/29/2023120人工智能讲义归结原理置换和合一的注意事项：谓词的一致性，P()与Q()，不可以常量的一致性，P(a,…)与P(b,….)，不可以 常量与变量，P(a,….)与P(x,…)，可以变量与函数，P(a,x,….)与P(x,f(x),…)，不可以；但P(a,x,…)与P(x,f(y),…)，可以是不能同时消去两个互补对，P∨Q与～P∨～Q的空，不可以先进行内部简化（置换、合并）10/29/2023121人工智能讲义归结原理归结的过程(P48)写出谓词关系公式→用反演法写出谓词表达试→SKOLEM标准形→子句集S→对S中可归结的子句做归结→归结式仍放入S中，反复归结过程→得到空子句

▯得证10/29/2023122人工智能讲义归结原理归结法的实质：归结法是仅有一条推理规则的推理方法。归结的过程是一个语义树倒塌的过程。(P51)归结法的问题子句中有等号或不等号时，完备性不成立。※Herbrand定理的不实用性引出了可实用的归结法。10/29/2023123人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/2023124人工智能讲义归结原理概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制10/29/2023125人工智能讲义归结过程的控制策略要解决的问题：归结方法的知识爆炸。控制策略的目的归结点尽量少控制策略的原则给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。10/29/2023126人工智能讲义归结过程的控制策略盲目归结

例S={P∨Q,

～P∨Q,P∨～Q,～P∨～Q}是不可满足。证明从S0=S开始，依次构造Si={C1,C2的归结式|C1∈S0∪S1∪…∪Si-1,C2∈Si-1},i=1,2,…,直至得到空子句。具体过程如下：S0(1)

P∨Q(2)～P∨Q(3)P∨～Q(4)～P∨～QS1(5)Q(1)(2)(6)P(1)(3)(7)Q∨～Q(1)(4)(8)P∨～P(1)(4)(9)Q∨～Q(2)(3)(10)P∨～P(2)(3)(11)～P(2)(4)(12)～Q(3)(4)10/29/2023127人工智能讲义归结过程的控制策略(盲目归结)S2(13)P(1)(7)(14)P∨Q(1)(8)(15)P∨Q(1)(9)(16)P∨Q(1)(10)(17)Q(1)(11)(18)P(1)(12)(19)Q

(2)(6)(20)～P∨Q(3)(4)(21)～P∨Q(2)(8)(22)～P∨Q(2)(9)(23)～P∨Q(2)(10)(24)～P(2)(12)(25)P(3)(5)(26)P∨～Q(3)(7)(27)P∨～Q(3)(8)(28)P∨～Q(3)(9)(29)P∨～Q(3)(10)(30)～Q(3)(11)(31)～P(4)(5)(32)～Q(4)(6)(33)～P∨～Q(4)(7)(34)～P∨～Q(4)(8)(35)～P∨～Q(4)(9)(36)～P∨～Q(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.10/29/2023128人工智能讲义归结过程的控制策略删除策略

设有两个子句C和D，若有置换ó使得Có⊂D成立，便说子句C把子句D归类。例C=P(X)D=P(a)∨Q(a)

取ó={a/x},便有Có=P(a)⊂{P(a),Q(a)}。删除策略：若对s使用归结推理过程中，当归结式Cj是重言式或Cj被S中子句或归结式Ci(i<j)归类时，便将Cj删除。10/29/2023129人工智能讲义归结过程的控制策略支持集策略

支持集：设S的子集T，说T是支持集，如果S-T是可满足。（目标公式的否定或由它们的后裔产生的子句）策略：每次归结时，至少有一个子句来自于T或由T导出的归结式。例S={P∨Q,∼P∨R,∼Q∨R,∼R}取T={∼R}10/29/2023130人工智能讲义归结过程的控制策略语义归结策略

将子句集S分成两部分，约定每部分内的子句间不允许做归结。还引入文字次序，约定归结时其中的一个子句被归结文字只能是该子句中“最大”的文字。例S={∼P∨∼Q∨R,P∨R,Q∨R,∼R}文字次序：P>Q>R解释I={∼P,∼Q,∼R}10/29/2023131人工智能讲义归结过程的控制策略线性归结策略首先从子句集S中选取一个称为顶子句的子句C0开始做归结，其次是归结过程中所得到的归结式Ci立即同另一个子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(j<i)。10/29/2023132人工智能讲义归结过程的控制策略单元归结：在归结过程中，每次归结都有一个子句是单元（只含一个文字）子句或单元因子时的归结过程。10/29/2023133人工智能讲义归结过程的控制策略输入归结：在归结过程中，对两个子句所做的每一次归结，其中必须有一个是S的子句时，便称作输入归结。10/29/2023134人工智能讲义归结过程的控制策略控制策略的方法删除 => 完备采用支撑集 <=>完备语义归结 <=> 完备线性归结 <=>完备单元归结 => 完备输入归结 => 完备10/29/2023135人工智能讲义谓词逻辑的归结方法对于子句C1L1和C2L2，如果L1与~L2可合一，且s是其合一者，则(C1C2)s是其归结式。例：P(x)Q(y),~P(f(z))R(z) =>Q(y)R(z)10/29/2023136人工智能讲义归结举例设公理集： (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)10/29/2023137人工智能讲义 (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)10/29/2023138人工智能讲义目标求反：

~(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)