【文档说明】人工智能一般搜索算法原理153课件.ppt，共(153)页，1.431 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-13146.html

以下为本文档部分文字说明：

2022/11/15人工智能一般搜索算法原理153人工智能一般搜索算法原理1532022/11/15人工智能一般搜索算法原理153盲目搜索•图搜索策略•深度优先搜索•宽度优先搜索•等代价搜索2022/11/15人工智能一般搜索算法原理1

53一些基本概念•节点深度：根节点深度=0其它节点深度=父节点深度+101232022/11/15人工智能一般搜索算法原理153一些基本概念（续1）•路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-

1具有一个后继节点ni，则该序列称为从n0到nk的路径。•路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。2022/11/15人工智能一般搜索算法原理153一些基本概念（续1）

•扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。2022/11/15人工智能一般搜索算法原理153一般的图搜索算法（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);2022/11/15人工智能一般搜索算法原理153一般的图

搜索算法（续）7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GOLOOP；2022/11/15人工智能一般

搜索算法原理153深度优先搜索•在深度优先搜索中，首先扩展最新产生的(最深的)节点，深度相等的节点可以任意排列。“最晚产生的节点最先扩展”2022/11/15人工智能一般搜索算法原理153深度优先搜索算法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;2022/11/15人工智能一般搜索算法原理153231847652

3184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652

83641752831675483214765283714652814376528314576123456789abcd12384765目标2022/11/15人工智能一般搜索算法原理153深度优先搜索的性质•一般不能保证找

到最优解•当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制•最坏情况时，搜索空间等同于穷举•与回溯法的差别：图搜索•是一个通用的与问题无关的方法2022/11/15人工智能一般搜索算法原理153宽度优先搜索•如果搜索是以接近起始节点的程度依次扩展节点的，那么

这种搜索就叫做宽度优先搜索。这种搜索使逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”2022/11/15人工智能一般搜索算法原理153宽度优先搜索算法1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IFOPE

N=()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;2022/11/15人工智能一般搜索算法原理1532318476523184765283147652318476528

3147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标82341876542022/11/15人工智能一般搜索算法原理153宽度优先搜索的性质•

当问题有解时，一定能找到解•当问题为单位耗散值，且问题有解时，一定能找到最优解•方法与问题无关，具有通用性•效率较低•属于图搜索方法2022/11/15人工智能一般搜索算法原理153等代价搜索•宽度优先搜索可被

推广用来解决寻找从起始节点到目标节点具有最小代价路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。2022/11/15人工智能一般搜索算法原理153等代价搜索算法•算法1,G=G0(G0=s),OPEN=(s),CLOSED=(),g(s)=0;2,L

OOP: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;2022/11/15人工智能一般搜索算法原理153启

发式图搜索•利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。•启发信息的强度–强：降低搜索工作量，但可能导致找不到最优解–弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解2022/11/15人工智能一般搜

索算法原理153希望：•引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。2022/11/15人工智能一般搜索算法原理153基本思想•定义一个评价函数f，对当前的搜索状态进行评估，找出一个

最有希望的节点来扩展。2022/11/15人工智能一般搜索算法原理1531，启发式搜索算法A（A算法）•评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数h(n)：启发函数2022/11/15人工智能一般搜索算法原理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/11/15人工智能一般搜索算法原理153A算法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);2022/11/15人工智能一般搜索算法原理153A算法（续）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；2022/11/15人工智能一般搜索算法原理153一个A算法的例子

定义评价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数28316475123847652022/11/15人工智能一般搜索算法原理153h计算举例h(n)=4283164751

23457682022/11/15人工智能一般搜索算法原理153283164752831476528316475283164752318476528314765283147652837146583214765231847652318476512384765123847651237

8465s(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)为当前节点“不在位”的将牌数2022/11/15人工智能一般搜索算法原理153最佳图搜索算法A*（A*算法）•在A算法中，如果满足条件：h(n)≤h*(n)则A算法称为A*算法。2022/11/1

5人工智能一般搜索算法原理153A*条件举例•8数码问题–h(n)=“不在位”的将牌数–h(n)=将牌“不在位”的距离和2831647512345768将牌1：1将牌2：1将牌6：1将牌8：22022/11/15人工智能一般搜索算法原理153A*算法的性质定理1：对有限

图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。2022/11/15人工智能一般搜索算法原理153A*算法的性质（续1）引理2.1：对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPE

N表中即使最小的一个f值也将增到任意大，或有f(n)>f*(s)。2022/11/15人工智能一般搜索算法原理153A*算法的性质（续2）引理2.2：A*结束前，OPEN表中必存在f(n)≤f*(s)

。2022/11/15人工智能一般搜索算法原理153A*算法的性质（续3）定理2：对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。2022/11/15人工智能一般搜索算法原理153A*算法的性质（续4）推论2.1：OP

EN表上任一具有f(n)<f*(s)的节点n，最终都将被A*选作扩展的节点。2022/11/15人工智能一般搜索算法原理153A*算法的性质（续5）定理3(可采纳性定理)：若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。2022/11/15人工智能一般搜索算

法原理153A*算法的性质（续6）推论3.1：A*选作扩展的任一节点n，有f(n)≤f*(s)。2022/11/15人工智能一般搜索算法原理153A*算法的性质（续7）定理4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)>h1(n

)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)>h1(n),则A1扩展的节点数≥A2扩展的节点数2022

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

)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/11/15人工智能一般搜索算法原理153出现多次扩展节点的原因•在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。2022/11/15人工智能一般搜索算法原

理153解决的途径•对h加以限制–能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。•对算法加以改进–能否对算法加以改进，避免或减少节点的多次扩展。2022/11/15人工智能一般搜索算法原理153改进的条件•可采纳性不变•不多扩

展节点•不增加算法的复杂性2022/11/15人工智能一般搜索算法原理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/11/15人工智能一般搜索算法原理153h单调的性质•定理5：若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有g(n)=g*(n)。2022/11/15人工智能一般搜索算法原理153h单调的性质

（续）•定理6：若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。2022/11/15人工智能一般搜索算法原理153h单调的例子•8数码问题：–h为“不在位”的将牌数1h(ni)-h(nj)=0(nj为ni的后继节点)-1h(t)=0c(ni,nj)=1满足单调的条件。2

022/11/15人工智能一般搜索算法原理153对算法加以改进•一些结论：–OPEN表上任一具有f(n)<f*(s)的节点定会被扩展。–A*选作扩展的任一节点，定有f(n)≤f*(s)。2022/11/15人工智能一般搜索算法原理153改进的出发点

OPEN=(…………)f*(s)f值小于f*(s)的节点f值大于等于f*(s)的节点fm：到目前为止已扩展节点的最大f值，用fm代替f*(s)2022/11/15人工智能一般搜索算法原理153修正过程A1,OPEN=(s),f(s)=g(s)+h(s),fm=0;2,LOOP:IFO

PEN=()EXIT(FAIL);3,NEST={ni|f(ni)<fm}IFNEST≠()n=NEST中g最小的节点ELSEn=FIRST(OPEN),fm=f(n);4,…,8:同过程A。2022/11/15人工智能一般搜索算法原理153s(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)2022/11/15人工智能一般搜索算法原理153例子：传教士与野人问题设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全

地把所有人都渡河过去？2022/11/15人工智能一般搜索算法原理153问题表示：需要考虑两岸的修道士人数和野人人数，船的位置。用三元式表示状态：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*算法的限制条件。2022/11/15人工智能一般搜索算法原理153(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)2022/11/15人工智能一般搜索算法原理1534.5AO*算法•搜索与或图的A*算法•节点评价方法A*算法中，对节点n的评价，实

际上是对“初始节点--节点n--目标节点”这一条路径的评价AO*算法中，由于与节点的存在，解对应的不是一条路径，而是一个子图，因此对节点的评价，实际是对局部解图的评价2022/11/15人工智能一般搜索算法原理153A(6)BCD(3)(4)(5)f(A)=min{(B)+(

C)+2,(D)+1}GHEF(4)(4)(5)(7)(10)(9)(6)(11)与或图节点扩展与评价2022/11/15人工智能一般搜索算法原理153算法的两个阶段第一阶段：自上而下的图生成过程对于每一个已经扩展过的节点，都对应一个指针，指向该节点后继节点中，

代价值小的那条边。图生成过程，就是从初始节点出发，按照该指针向下搜索，一直到找到一个未扩展的节点为止。然后扩展该节点。第二阶段：自下而上的代价值计算过程设n为最新被扩展的节点，计算节点n对应的最小代价值，并标记一个指针指

向对应最小代价的边。对于n的父节点，进行同样的计算。重复这一过程，直到初始节点s为止。这时，从s出发，选择那些指针所指向的边得到的局部图，为当前代价值最小的局部图。2022/11/15人工智能一般搜索算法原理153具体步骤S

tep1建立一个仅由初始节点s构成的搜索图G，计算h(s)Step2在以下两过程间循环，直到s标记为可解或不可解，或其代价值大于阈值：2.1选择节点进行扩展2.2根据扩展情况修改节点的可解性与代价值2022/11/15人工智能一般搜索算法原理153Step

2.1选择节点进行扩展：1根据指针找出待扩展的局部解图G′。2选择G′中的一个非终节点n作为当前节点。3扩展节点n，如不能扩展，则标记为不可解，否则生成子节点集，如子节点为非终节点，计算其代价值，若为终节点，标注其可解。将所有子节点添加到G中。4建立含n的单一节点集合S，S:

＝{n}2022/11/15人工智能一般搜索算法原理153Step2.2修改节点的可解性与代价值重复以下步骤，直到S为空：1从S中挑选一个子孙节点都不在S中的节点m2计算始于m的每条连接线的代价，取其中最小值为m对应的代价，并在对应于最小代价的连接线上加指针。3如果连接于最小代价连

接线上的所有节点都可解，则标注m可解。4如果m的可解性或代价值发生改变，则把m的所有祖先节点添加到S中。2022/11/15人工智能一般搜索算法原理153AO*算法举例目标目标初始节点n0n1n2n3n4n5n6n7n8h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h

(n5)=1h(n6)=2h(n7)=0h(n8)=0连接线的代价=后继节点个数2022/11/15人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8n0(3)n1(2)n4(1)n5(1)红色代价：4蓝色代价：3

2022/11/15人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8n4(1)n5(1)红色代价：4蓝色代价：6n1(2->5)n2(4)n3(4)n0(3)n0(3->4)2022/11/15人工智能一般

搜索算法原理153n0n1n2n3n4n5n6n7n8n4(1)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4)n5(1)n5(1->2)2022/11/15人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8红色代价：5蓝色代价

：6n0(4)n4(1)n5(1->2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)n0(4->5)2022/11/15人工智能一般搜索算法原理153n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(

2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022/11/15人工智能一般搜索算法原理153目标目标初始节点n0n1n2n3n4n5n6n7n8n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022/11/15人工智能一般搜

索算法原理153目标目标初始节点n0n1n2n3n4n5n6n7n8初始节点可解n0(5)n4(1)n5(2)n1(5)n2(4)n3(4)n6(2)n7(0)n8(0)2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑

的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/15人工智能一般搜索算法原理153概述•归结原理由J.

A.Robinson由1965年提出。–与演绎法完全不同，新的逻辑演算算法。–一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。–语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，

有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）•本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子

句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/1

5人工智能一般搜索算法原理153命题逻辑的归结法•基本单元：简单命题（陈述句）例：命题：A1、A2、A3和B求证：A1ΛA2ΛA3成立，则B成立，即：A1ΛA2ΛA3→B反证法：证明A1ΛA2ΛA3Λ～B是矛盾

式（永假式）2022/11/15人工智能一般搜索算法原理153命题逻辑的归结法•建立子句集–合取范式：命题、命题和的与，如：PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命题（元素）的集合例：命题公

式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}2022/11/15人工智能一般搜索算法原理153命题逻辑的归结法•归结式消除互补对，求新子句→得到归结式。如子句：C1=C1′∨L,C2=C2′∨

归结式：R(C1,C2)=C1′∨C2′注意：C1ΛC2→R(C1,C2)，反之不一定成立。假言推理:由合适公式W1和W1→W2产生合适公式W2,如何用归结法证明?2022/11/15人工智能一般搜索算法原理153命题逻辑的归

结法•归结过程–对结论作否定,并加入前提中–将命题写成合取范式–求出子句集–对子句集使用归结推理规则–归结式作为新子句参加归结–归结式为空子句□，S是不可满足的（矛盾），原命题成立。•（证明完毕）•谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。2022/11/

15人工智能一般搜索算法原理153命题逻辑的归结法•例证明先将化为合取范式建立子句集S=对S做归结PNIL2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2

022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/15人工智能一般搜索算法原理153子句形引用Herbrand定理，以说

明归结原理的意义及一个原理形成的根基与背景•SKOLEM标准形–前束范式：把所有的量词都提到前面去，然后消掉所有量词。定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都

延伸到公式的末端。即(Q1x1)…(Qnxn)M(x1,…,xn),其中Qixi为存在量词或全称量词,M(x1,…,xn)为合取范式(由一些子句的合取组成)。2022/11/15人工智能一般搜索算法原理153子句形(Skolem标准形)–量词消去原则：消去存在

量词“”，略去全程量词“”。注意：左边有全称量词的存在量词，消去时该变量改写成为全称量词的函数(Skloem函数)；如没有，改写成为常量。例子：见《人工智能及其应用》P752022/11/15人工智能一般搜索算法原理153子句形(

Skolem标准形)–定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。–SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。2022/11/15人工智能一般搜索算法原理153子句形(Sko

lem标准形)–例: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)202

2/11/15人工智能一般搜索算法原理153子句形•子句与子句集–文字：不含任何连接词的谓词公式。–子句：一些文字的析取（谓词的和）。–子句集S的求取：G→SKOLEM标准形→消去存在变量→以“，”取代“Λ”，并表示为集合形式。2022/11/15人工智能一般

搜索算法原理153子句形•G是不可满足的<=>S是不可满足的–G与S不等价，但在不可满足的意义下是一致的。–定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的<=>S是不可满足的。注意：G真不一定S真，而S真必有G真。即：S=>G

2022/11/15人工智能一般搜索算法原理153子句形•G=G1ΛG2ΛG3Λ…ΛGn的子句形–G的子句集可以分解成几个单独处理。–有SG=S1US2US3U„USn则SG与S1US2US3U…USn在不可满足的意义上是一致的。即SG不可满足<=>S1US2

US3U…USn不可满足2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/15人工智能一般搜索算法原理153归结原理•概述•

命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/15人工智能一般搜索算法原理153Herbrand定理•问题：一阶逻辑公式的永真性（永假性）的判定是否能在有限步内完成？2022/11/15人工智能一般搜索算法原理153Herbrand定理

•1936年图灵(Turing)和邱吉(Church)互相独立地证明了：“没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（或永假）的公式就不一定能在有限步内得到结论。判定的

过程将可能是不停止的。”2022/11/15人工智能一般搜索算法原理153Herbrand定理•Herbrand的思想–定义：公式G永真：对于G的所有解释，G都为真。–思想：寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就

没有这样的解释存在，并且算法在有限步内停止。2022/11/15人工智能一般搜索算法原理153Herbrand定理•H域•H解释•语义树•结论：Herbrand定理2022/11/15人工智能一般搜索算法原理153Herbrand定理

•H域•H解释•语义树•结论：Herbrand定理2022/11/15人工智能一般搜索算法原理153Herbrand定理（H域）•基本方法：–因为量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限、不可数的。–简化讨论域。建立一个比较简单、特殊的域，使得只要在这个论域上，该公式是

不可满足的。–此域称为H域：H0为G中所出现的常量的集合，若G中没有常量，就任取常量，H0={a}。规定为H域※例题请参考教科书P272022/11/15人工智能一般搜索算法原理153H域举例•例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))，„}2022/11/15人工智能一般

搜索算法原理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也是可数的。–一旦原子集内真值确定好（规定好），则S2022/11/15人工智能一般搜索算法原理153原子集举例•例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))),„}2022/11/15人工智能一般搜索算法原理153Herbrand定理（H域）•没有变量出现的原子、文字、子句和子句集，分别称作基原

子、基文字、基子句和基子句集。它们在讨论子句集S的不可满足性时占有重要置。2022/11/15人工智能一般搜索算法原理153Herbrand定理•H域•H解释•语义树•结论：Herbrand定理2022/11/15人工智能

一般搜索算法原理153Herbrand定理•H域•H解释•语义树•结论：Herbrand定理2022/11/15人工智能一般搜索算法原理153Herbrand定理（H解释）•解释I*：取一个值得到一个结论–I映射S中到所有常量符号到它们本身。(即原

子集)–令f是n元函数，I是f下的一个指派，即H中的元素到f的一个映射（函数值）。简单地说(P29)，A中的各元素真假组合都是H的解释。（或真或假只取一个）•问题：对于所有的解释，全是假才可判定。因为所有解释代表了所有的情况，如可穷举，问题便可解决。2022/11/15人工智能一

般搜索算法原理153H解释-举例•例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*=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成立。2022/11/15人工智能一般搜索算法原理153Herbrand定理（H解释）•如下三个定理保证了归结法的正确性：–定理1：设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I=T，必有S|I*=T。–定理2：

子句集S是不可满足的，当且仅当所有的S的H解释下为假。–定理3：子句集S是不可满足的，当且仅当对每一个解释I下，至少有S的某个子句的某个基例为假。2022/11/15人工智能一般搜索算法原理153Herbrand定理（H解释）•基例S中某子句中所有变元符号均以S的H域中的元素代入

时，所得的基子句C’称为C的一个基例。•若一个子句为假，则此解释为假。•一般来说，D是无穷不可列的，因此，子句集S也是无穷不可列的。但S确定后H是无穷可列的。不过在H上证明S的不可满足性仍然是不可能的。2022/11/15人工智能一般搜索算法原理153Herbrand定理•H域•H解

释•语义树•结论：Herbrand定理2022/11/15人工智能一般搜索算法原理153Herbrand定理•H域•H解释•语义树•结论：Herbrand定理2022/11/15人工智能一般搜索算法原理153Herbrand定理（语义树）•构成方法–原子集中所有元素逐层添加的一棵

二叉树。将元素的是与非分别标记在两侧的分枝上（可不完全画完）。(P34)•特点–一般情况H是可数集，S的语义树是无限树。2022/11/15人工智能一般搜索算法原理153Herbrand定理（语义树）•意义–SHA语义树–可以理解语义树为H域的图形解释。目的：把每

个解释都摊开。语义树中包含原子集的全部元素，因此，语义树是完全的。每一个直到叶子节点的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。如果每个基例都为假，则可认为是不可满足的。2022/11

/15人工智能一般搜索算法原理153语义树-举例•例1设子句集S的原子集A={P,Q,R}语义树：N0N11N12N21N22N23N24N31N32N33N34N35N36N37N38P～QQR～R～PI(N)表示从根节点到节点N分枝上所标记的所有文字的并集。如

I(N34)={P,～Q,～R}2022/11/15人工智能一般搜索算法原理153Herbrand定理（语义树）•几个概念–失败结点：当（由上）延伸到点N时，I(N)已表明了S的某子句的某基例假。但N以前尚不能判断这

事实。就称N为失败结点。完全语义树：如果对语义树的所有叶结点N来说，I(N)包含了S的原子集A={A1,A2,…}中的所有元素Ai或～Ai，I=1…n。–封闭语义树：如果S的完全语义树的每个分枝上都有一个失败结点，就称它是一棵封闭语义树。2022/11/15人工智能一般搜索算法原理15

3封闭语义树-举例例子句集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)),…}语义树：N0N11N12N21N2

2N23N24N31N32N33N34N35N36N37N38P(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的父辈不能使子句的基例为假2022/11/1

5人工智能一般搜索算法原理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)),…}封闭

语义树：N0N11N12N21N22N23N24N31N32N36N37N38P(a)Q(a)P(f(a))N41N42N49N410N413N414Q(f(a))ΧΧΧΧΧΧΧΧΧΧ2022/11/15人工智能一般搜索算法原理153Herbrand

定理•H域•H解释•语义树•结论：Herbrand定理2022/11/15人工智能一般搜索算法原理153Herbrand定理•H域•H解释•语义树•结论：Herbrand定理2022/11/15人工智能一般搜索算法原理153Herbrand定理（

结论）Herbrand定理：1.子句集S是不可满足的，当且仅当对应于S的完全语义数是棵有限封闭树。2.子句集S是不可满足的，当且仅当存在不可满足的S的有限基例集。2022/11/15人工智能一般搜索算法原理153Herbrand定理（结论）•定理的意义–Herbra

nd定理已将证明问题转化成了命题逻辑问题。–由此定理保证，可以放心的用机器来实现自动推理了。（归结原理）•注意–Herbrand定理给出了一阶逻辑的半可判定算法，即仅当被证明定理是成立时，使用该算法可以在有限步得证。而当被证定理并不

成立时，使用该算法得不出任何结论。但是2022/11/15人工智能一般搜索算法原理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个元素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提出了归结原理。2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制202

2/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/15人工智能一般搜索算法原理153归结原理•归结原理正确性的根本在于，找到矛盾可以肯定不真。•方法：–和命题逻辑一样

。–但由于有函数，所以要考虑合一和置换。(定义与例题参考教科书P41)2022/11/15人工智能一般搜索算法原理153归结原理•置换和合一的注意事项：1.谓词的一致性，P()与Q()，不可以2.常量的一致性，P(a,…)与P(b,….)，不可以常量与变量，P(a,….)与P(x,

…)，可以3.变量与函数，P(a,x,….)与P(x,f(x),…)，不可以；但P(a,x,…)与P(x,f(y),…)，可以1.是不能同时消去两个互补对，P∨Q与～2022/11/15人工智能一般搜索算法原理153归结原理•归结的过程(P48)写出谓词关系公式→

用反演法写出谓词表达试→SKOLEM标准形→子句集S→对S中可归结的子句做归结→归结式仍放入S中，反复归结过程→得到空子句▯得证2022/11/15人工智能一般搜索算法原理153归结原理•归结法的实质：–归结法是仅有一条推理规则的推理方法。–归结的过程是一个语义树

倒塌的过程。(P51)•归结法的问题–子句中有等号或不等号时，完备性不成立。※Herbrand定理的不实用性引出了可实用的归结法。2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略

控制2022/11/15人工智能一般搜索算法原理153归结原理•概述•命题逻辑的归结法•子句形•Herbrand定理•归结原理•归结过程的策略控制2022/11/15人工智能一般搜索算法原理153归结过程的控制策略•要解决的问题：–归结方法的

知识爆炸。•控制策略的目的–归结点尽量少•控制策略的原则–给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。2022/11/15人工智能一般

搜索算法原理153归结过程的控制策略•盲目归结例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)2022/11/15人工智能一般搜索算法原理153归结过

程的控制策略(盲目归结)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)(3

0)～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

.2022/11/15人工智能一般搜索算法原理153归结过程的控制策略•删除策略设有两个子句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删除。2022/11/15人工智能一般搜索算法原理153归结过程的控制策略•支持集策略支持集：设S的子集T，说T是支持集，如果S-T是可满足。（目标公式的否定或由它们的后裔产生的子句）策略：每次归结时，至少有一

个子句来自于T或由T导出的归结式。例S={P∨Q,∼P∨R,∼Q∨R,∼R}取T={∼R}2022/11/15人工智能一般搜索算法原理153归结过程的控制策略•语义归结策略将子句集S分成两部分，约定每部分内的子句间不允许做归结。还引入文字次序，约定归结时其中的一个子句被归结文字只能

是该子句中“最大”的文字。例S={∼P∨∼Q∨R,P∨R,Q∨R,∼R}文字次序：P>Q>R解释I={∼P,∼Q,∼R}2022/11/15人工智能一般搜索算法原理153归结过程的控制策略•线性归结策略首先从子句集S中选取一个称为顶子句的子句C0开始做归结

，其次是归结过程中所得到的归结式Ci立即同另一个子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(j<i)。2022/11/15人工智能一般搜索算法原理153归结过程的控制策略•单元归结：在归结过程中，每次归结都有一个子句是单元（只含一个文

字）子句或单元因子时的归结过程。2022/11/15人工智能一般搜索算法原理153归结过程的控制策略•输入归结：在归结过程中，对两个子句所做的每一次归结，其中必须有一个是S的子句时，便称作输入归结。2022/11/15人工智能一般搜索算法原理

153归结过程的控制策略•控制策略的方法–删除=>完备–采用支撑集<=>完备–语义归结<=>完备–线性归结<=>完备–单元归结=>完备–输入归结=>完备2022/11/15人工智能一般搜索算法原理153谓词逻辑的归结方法•对于子句C1L1和C2L2，如果L

1与~L2可合一，且s是其合一者，则(C1C2)s是其归结式。•例：P(x)Q(y),~P(f(z))R(z)=>Q(y)R(z)2022/11/15人工智能一般搜索算法原理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/11/15人工智能一般搜索算法原理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)(4)2022/11/15人工智能一般搜索算法原理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/11/15人工智能一般搜索算法原理

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/11/15

人工智能一般搜索算法原理153归结反演求解-提取回答的过程•先进行归结，证明结论的正确性；•用重言式代替结论求反得到的子句；•按照证明过程，进行归结；•最后，在原来为空的地方，得到的就是提取的回答。•修改后的证明树称为修改证明树2022/11/15人工智能一般搜索算法原

理153归结反演求解-举例“如果无论John到哪里去，Fido也就去那里，那么如果John在学校，Fido在哪里？”已知：(x)[AT(John,x)AT(Fido,x)]AT(John,School)求证：(x)AT(F

ido,x)如果我们首先证明公式(x)AT(Fido,x)在逻辑上遵循前提公式集，然后寻求一个存在x的例，那么就能解决“Fido在哪里”的问题。2022/11/15人工智能一般搜索算法原理153归结反演求解-基于归结的问答系统已知：(x)[AT(John,x

)AT(Fido,x)]AT(John,School)求证：(x)AT(Fido,x)子句集：~AT(John,x1)AT(Fido,x1)AT(John,School)~AT(Fido,x2)2022/11/15人工智能一般搜索算法原理153~AT(Fido,x2)~AT(John,

x1)AT(Fido,x1)子句集：~AT(John,x1)AT(Fido,x1)AT(John,School)~AT(Fido,x2)~AT(John,x2){x2/x1}AT(John,School)nil{School/x2}用重言式代替结论求反得到的子句2022/

11/15人工智能一般搜索算法原理153~AT(Fido,x2)~AT(John,x1)AT(Fido,x1)子句集：~AT(John,x1)AT(Fido,x1)AT(John,School)~AT(Fido,x2)~AT

(John,x2){x2/x1}AT(John,School)nil{School/x2}AT(Fido,x2)AT(Fido,x2)AT(Fido,School)2022/11/15人工智能一般搜

索算法原理153例：猴子摘香蕉问题c2022/11/15人工智能一般搜索算法原理153问题的表示已知：1,~ON(s0)2,(x)(s)(~ON(s)AT(box,x,push(x,s)))3,(s)

(ON(climb(s)))4,(s)((ON(s)AT(box,c,s))HB(grasp(s)))5,(x)(s)(AT(box,x,s)AT(box,x,climb(s)))求解：2022/11/15人工智能一般搜索算法原理153问题的子句集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)返回2022/11/15

人工智能一般搜索算法原理153~HB(s5)~ON(s3)~AT(box,c,s3)HB(grasp(s3))~ON(s3)~AT(box,c,s3){grasp(s3)/s5}ON(climb(s2)){climb(s

2)/s3}~AT(box,c,climb(s2))~ON(s0)ON(s1)AT(box,x1,push(x1,s1)){s0/s1}AT(box,x1,push(x1,s0))~AT(box,x4,s4)AT(bo

x,x4,climb(s4)){x4/x1,push(x4,s0)/s4}AT(box,x4,climb(push(x4,s0)))NIL{c/x4,push(c,s0)/s2}HB(s5)HB(grasp(s3))HB(grasp(cli

mb(s2)))HB(grasp(climb(push(c,s0))))2022/11/15人工智能一般搜索算法原理153例子任何兄弟都有同一个父亲，John和Peter是兄弟，且John的父亲是David,问Peter的

父亲是谁？2022/11/15人工智能一般搜索算法原理153例子某人被盗，公安局派出所派出5个侦察员却调查。研究案情时，侦察员A说：“赵与钱中至少有一人作案”；侦察员B说：“钱与孙中至少有一人作案”；侦察员C说：“孙与李中至少有一人作案”；侦察员D说：“赵与孙中至少有一人与此案无关”；侦

察员E说：“钱与李中至少有一人与此案2022/11/15人工智能一般搜索算法原理153归结方法小结•求子句集，进行归结，方法简单•通过修改证明树的方法，提取回答•方法通用•求解效率低，不宜引入启发信息•不宜理解推理过程2022/11/15人工智能一般搜索算法原理153演讲完毕，谢谢听讲!再见

，seeyouagain