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

2023/1/24,人工智能一般搜索算法原理153,人工智能一般搜索算法原理153,2023/1/24,人工智能一般搜索算法原理153,2,盲目搜索,图搜索策略深度优先搜索宽度优先搜索等代价搜索,2023/1/24,人工智能一般搜索算法原理153,3,一些基本概念,节点深度：根节点深度=0其它节点深度=父节点深度+1,0,1,2,3,2023/1/24,人工智能一般搜索算法原理153,4,一些基本概念（续1）,路径设一节点序列为(n0,n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。,2023/1/24,人工智能一般搜索算法原理153,5,一些基本概念（续1）,扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。,2023/1/24,人工智能一般搜索算法原理153,6,一般的图搜索算法（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);,2023/1/24,人工智能一般搜索算法原理153,7,一般的图搜索算法（续）,7,标记和修改指针：ADD(mj,OPEN),并标记mj到n的指针；计算是否要修改mk、ml到n的指针；计算是否要修改ml到其后继节点的指针；8,对OPEN中的节点按某种原则重新排序；9,GO LOOP；,2023/1/24,人工智能一般搜索算法原理153,8,深度优先搜索,在深度优先搜索中，首先扩展最新产生的(最深的)节点，深度 相等的节点可以任意排列。“最晚产生的节点最先扩展”,2023/1/24,人工智能一般搜索算法原理153,9,深度优先搜索算法,1,G=G0(G0=s),OPEN=(s),CLOSED=();2,LOOP:IF OPEN=()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;,2023/1/24,人工智能一般搜索算法原理153,10,2 31 8 47 6 5,1,2,3,4,5,6,7,8,9,a,b,c,d,目标,2023/1/24,人工智能一般搜索算法原理153,11,深度优先搜索的性质,一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法,2023/1/24,人工智能一般搜索算法原理153,12,宽度优先搜索,如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。这种搜索使逐层进行的，在对下一层的任意节点进行搜索之前，必须搜索完本层的所有节点。“先产生的节点先扩展”,2023/1/24,人工智能一般搜索算法原理153,13,宽度优先搜索算法,1,G=G0(G0=s),OPEN=(s),CLOSED=();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,G=ADD(mi,G);7,IF 目标在mi中 THEN EXIT(SUCCESS);8,ADD(OPEN,mj),并标记mj到n的指针;9,GO LOOP;,2023/1/24,人工智能一般搜索算法原理153,14,2 31 8 47 6 5,1,2,5,6,7,3,目标,8,4,2023/1/24,人工智能一般搜索算法原理153,15,宽度优先搜索的性质,当问题有解时，一定能找到解当问题为单位耗散值，且问题有解时，一定能找到最优解方法与问题无关，具有通用性效率较低属于图搜索方法,2023/1/24,人工智能一般搜索算法原理153,16,等代价搜索,宽度优先搜索可被推广用来解决寻找从起始节点到目标节点具有最小代价路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。,2023/1/24,人工智能一般搜索算法原理153,17,等代价搜索算法,算法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,EXPAND(i)j,G=ADD(j,G);6,对每个后继节点j,计算g(j)=g(i)+c(i,j)且ADD(OPEN,j),并标记j到i的指针;7,GO LOOP;,2023/1/24,人工智能一般搜索算法原理153,18,启发式图搜索,利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最 优解弱：一般导致工作量加大，极限情况下变为 盲目搜索，但可能可以找到最优解,2023/1/24,人工智能一般搜索算法原理153,19,希望：,引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。,2023/1/24,人工智能一般搜索算法原理153,20,基本思想,定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。,2023/1/24,人工智能一般搜索算法原理153,21,1，启发式搜索算法A（A算法）,评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数h(n)：启发函数,2023/1/24,人工智能一般搜索算法原理153,22,符号的意义,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)的估计值,2023/1/24,人工智能一般搜索算法原理153,23,A算法,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);,2023/1/24,人工智能一般搜索算法原理153,24,A算法（续）,ADD(mj,OPEN),标记mj到n的指针；IF f(n,mk)f(mk)f(mk)=f(n,mk),标记mk到n的指针；IF f(n,ml)f(ml,)f(ml)=f(n,ml),标记ml到n的指针,ADD(ml,OPEN);7,OPEN中的节点按f值从小到大排序；8,GO LOOP；,2023/1/24,人工智能一般搜索算法原理153,25,一个A算法的例子,定义评价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数,2 8 31 6 47 5,1 2 38 47 6 5,2023/1/24,人工智能一般搜索算法原理153,26,h计算举例,h(n)=4,2 8 31 6 47 5,1 2 3,45,7 6,8,2023/1/24,人工智能一般搜索算法原理153,27,2 8 31 6 47 5,s(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),目标,1,2,3,4,5,6,定义评价函数：f(n)=g(n)+h(n)g(n)为从初始节点到当前节点的耗散值h(n)为当前节点“不在位”的将牌数,2023/1/24,人工智能一般搜索算法原理153,28,最佳图搜索算法A*（A*算法）,在A算法中，如果满足条件：h(n)h*(n)则A算法称为A*算法。,2023/1/24,人工智能一般搜索算法原理153,29,A*条件举例,8数码问题h(n)=“不在位”的将牌数h(n)=将牌“不在位”的距离和,2023/1/24,人工智能一般搜索算法原理153,30,A*算法的性质,定理1：对有限图，如果从初始节点s到目标节点t有路径存在，则算法A一定成功结束。,2023/1/24,人工智能一般搜索算法原理153,31,A*算法的性质（续1）,引理2.1：对无限图，若有从初始节点s到目标节点t的路径，则A*不结束时，在OPEN表中即使最小的一个f值也将增到任意大，或有f(n)f*(s)。,2023/1/24,人工智能一般搜索算法原理153,32,A*算法的性质（续2）,引理2.2：A*结束前，OPEN表中必存在f(n)f*(s)。,2023/1/24,人工智能一般搜索算法原理153,33,A*算法的性质（续3）,定理2：对无限图，若从初始节点s到目标节点t有路径存在，则A*一定成功结束。,2023/1/24,人工智能一般搜索算法原理153,34,A*算法的性质（续4）,推论2.1：OPEN表上任一具有f(n)f*(s)的节点n，最终都将被A*选作扩展的节点。,2023/1/24,人工智能一般搜索算法原理153,35,A*算法的性质（续5）,定理3(可采纳性定理)：若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。,2023/1/24,人工智能一般搜索算法原理153,36,A*算法的性质（续6）,推论3.1：A*选作扩展的任一节点n，有f(n)f*(s)。,2023/1/24,人工智能一般搜索算法原理153,37,A*算法的性质（续7）,定理4：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n)h1(n)，则在具有一条从s到t的路径的隐含图上，搜索结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。简写：如果h2(n)h1(n),则A1扩展的节点数A2扩展的节点数,2023/1/24,人工智能一般搜索算法原理153,38,A*算法的改进,问题的提出：因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致搜索效率下降。,2023/1/24,人工智能一般搜索算法原理153,39,一个例子：,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),2023/1/24,人工智能一般搜索算法原理153,40,出现多次扩展节点的原因,在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。,2023/1/24,人工智能一般搜索算法原理153,41,解决的途径,对h加以限制能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。对算法加以改进能否对算法加以改进，避免或减少节点的多次扩展。,2023/1/24,人工智能一般搜索算法原理153,42,改进的条件,可采纳性不变不多扩展节点不增加算法的复杂性,2023/1/24,人工智能一般搜索算法原理153,43,对h加以限制,定义：一个启发函数h，如果对所有节点ni和nj，其中nj是ni的子节点，满足h(ni)-h(nj)c(ni,nj)h(t)=0则称h是单调的。,h(ni),ni,nj,h(nj),c(ni,nj),2023/1/24,人工智能一般搜索算法原理153,44,h单调的性质,定理5：若h(n)是单调的，则A*扩展了节点n之后，就已经找到了到达节点n的最佳路径。即：当A*选n扩展时，有g(n)=g*(n)。,2023/1/24,人工智能一般搜索算法原理153,45,h单调的性质（续）,定理6：若h(n)是单调的，则由A*所扩展的节点序列其f值是非递减的。,2023/1/24,人工智能一般搜索算法原理153,46,h单调的例子,8数码问题：h为“不在位”的将牌数 1h(ni)-h(nj)=0(nj为ni的后继节点)-1 h(t)=0c(ni,nj)=1 满足单调的条件。,2023/1/24,人工智能一般搜索算法原理153,47,对算法加以改进,一些结论：OPEN表上任一具有f(n)f*(s)的节点定会被扩展。A*选作扩展的任一节点，定有f(n)f*(s)。,2023/1/24,人工智能一般搜索算法原理153,48,改进的出发点,OPEN=(),f*(s),f值小于f*(s)的节点,f值大于等于f*(s)的节点,fm：到目前为止已扩展节点的最大f值，用fm代替f*(s),2023/1/24,人工智能一般搜索算法原理153,49,修正过程A,1,OPEN=(s),f(s)=g(s)+h(s),fm=0;2,LOOP:IF OPEN=()EXIT(FAIL);3,NEST=ni|f(ni)fmIF NEST()n=NEST中g最小的节点 ELSE n=FIRST(OPEN),fm=f(n);4,8:同过程A。,2023/1/24,人工智能一般搜索算法原理153,50,前面的例子：,OPEN表,CLOSED表,fm,s(0+10),s(0+10),10,A(6+1)B(3+5)C(1+8),s(0+10)C(1+8),10,A(6+1)B(2+5),s(0+10)C(1+8)B(2+5),10,A(3+1),s(0+10)C(1+8)B(2+5)A(3+1),10,G(11+0),2023/1/24,人工智能一般搜索算法原理153,51,例子：传教士与野人问题,设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡河过去？,2023/1/24,人工智能一般搜索算法原理153,52,问题表示：需要考虑两岸的修道士人数和野人人数，船的位置。用三元式表示状态：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*算法的限制条件。,2023/1/24,人工智能一般搜索算法原理153,53,f(n)=d(n)+m+c-2b,h,h=3,f=5,2023/1/24,人工智能一般搜索算法原理153,54,4.5 AO*算法,搜索与或图的A*算法节点评价方法 A*算法中，对节点n的评价，实际上是对“初始节点-节点n-目标节点”这一条路径的评价 AO*算法中，由于与节点的存在，解对应的不是一条路径，而是一个子图，因此对节点的评价，实际是对局部解图的评价,2023/1/24,人工智能一般搜索算法原理153,55,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),与或图节点扩展与评价,2023/1/24,人工智能一般搜索算法原理153,56,算法的两个阶段,第一阶段：自上而下的图生成过程对于每一个已经扩展过的节点，都对应一个指针，指向该节点后继节点中，代价值小的那条边。图生成过程，就是从初始节点出发，按照该指针向下搜索，一直到找到一个未扩展的节点为止。然后扩展该节点。第二阶段：自下而上的代价值计算过程设n为最新被扩展的节点，计算节点n对应的最小代价值，并标记一个指针指向对应最小代价的边。对于n的父节点，进行同样的计算。重复这一过程，直到初始节点s为止。这时，从s出发，选择那些指针所指向的边得到的局部图，为当前代价值最小的局部图。,2023/1/24,人工智能一般搜索算法原理153,57,具体步骤,Step1 建立一个仅由初始节点s构成的搜索图G，计算h(s)Step2 在以下两过程间循环，直到s标记为可解或不可解，或其代价值大于阈值：2.1 选择节点进行扩展 2.2 根据扩展情况修改节点的可解性与代价值,2023/1/24,人工智能一般搜索算法原理153,58,Step2.1 选择节点进行扩展：1 根据指针找出待扩展的局部解图G。2 选择G中的一个非终节点n作为当前节点。3 扩展节点n，如不能扩展，则标记为不可解，否则生成子节点集，如子节点为非终节点，计算其代价值，若为终节点，标注其可解。将所有子节点添加到G中。4 建立含n的单一节点集合S，S:n,2023/1/24,人工智能一般搜索算法原理153,59,Step2.2 修改节点的可解性与代价值 重复以下步骤，直到S为空：1 从S中挑选一个子孙节点都不在S中的节点m 2 计算始于m的每条连接线的代价，取其中最小值为m对应的代价，并在对应于最小代价的连接线上加指针。3 如果连接于最小代价连接线上的所有节点都可解，则标注m可解。4 如果m的可解性或代价值发生改变，则把m的所有祖先节点添加到S中。,2023/1/24,人工智能一般搜索算法原理153,60,AO*算法举例,h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0连接线的代价=后继节点个数,2023/1/24,人工智能一般搜索算法原理153,61,n0,n1,n2,n3,n4,n5,n6,n7,n8,n0(3),n1(2),n4(1),n5(1),红色代价：4蓝色代价：3,2023/1/24,人工智能一般搜索算法原理153,62,n0,n1,n2,n3,n4,n5,n6,n7,n8,n4(1),n5(1),红色代价：4蓝色代价：6,n1(2-5),n2(4),n3(4),n0(3),n0(3-4),2023/1/24,人工智能一般搜索算法原理153,63,n0,n1,n2,n3,n4,n5,n6,n7,n8,n4(1),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),n0(4),n5(1),n5(1-2),2023/1/24,人工智能一般搜索算法原理153,64,n0,n1,n2,n3,n4,n5,n6,n7,n8,红色代价：5蓝色代价：6,n0(4),n4(1),n5(1-2),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),n0(4-5),2023/1/24,人工智能一般搜索算法原理153,65,n0,n1,n2,n3,n4,n5,n6,n7,n8,n0(5),n4(1),n5(2),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),2023/1/24,人工智能一般搜索算法原理153,66,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,n0(5),n4(1),n5(2),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),2023/1/24,人工智能一般搜索算法原理153,67,目标,目标,初始节点,n0,n1,n2,n3,n4,n5,n6,n7,n8,初始节点可解,n0(5),n4(1),n5(2),n1(5),n2(4),n3(4),n6(2),n7(0),n8(0),2023/1/24,人工智能一般搜索算法原理153,68,归结原理,概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制,2023/1/24,人工智能一般搜索算法原理153,69,归结原理,概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制,2023/1/24,人工智能一般搜索算法原理153,70,概述,归结原理由J.A.Robinson由1965年提出。与演绎法完全不同，新的逻辑演算算法。一阶逻辑中，至今为止的最有效的半可判定的算法。即，一阶逻辑中任意恒真公式，使用归结原理，总可以在有限步内给以判定。语义网络、框架表示、产生式规则等等都是以推理方法为前提的。即，有了规则已知条件，顺藤摸瓜找到结果。而归结方法是自动推理、自动推导证明用的。（“数学定理机器证明”）本课程只讨论一阶谓词逻辑描述下的归结推理方法，不涉及高阶谓词逻辑问题。,2023/1/24,人工智能一般搜索算法原理153,71,归结原理,概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制,2023/1/24,人工智能一般搜索算法原理153,72,归结原理,概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制,2023/1/24,人工智能一般搜索算法原理153,73,命题逻辑的归结法,基本单元：简单命题（陈述句）例：命题：A1、A2、A3 和 B求证：A1A2A3成立，则B成立，即：A1A2A3 B反证法：证明A1A2A3B 是矛盾式（永假式）,2023/1/24,人工智能一般搜索算法原理153,74,命题逻辑的归结法,建立子句集合取范式：命题、命题和的与，如：P（PQ）（PQ）子句集S：合取范式形式下的子命题（元素）的集合例：命题公式：P（PQ）（PQ）子句集 S：S=P,PQ,PQ,2023/1/24,人工智能一般搜索算法原理153,75,命题逻辑的归结法,归结式消除互补对，求新子句得到归结式。如子句：C1=C1L,C2=C2 归结式：R(C1,C2)=C1 C2注意：C1C2 R(C1,C2)，反之不一定成立。,假言推理:由合适公式W1和W1 W2产生合适公式W2,如何用归结法证明?,2023/1/24,人工智能一般搜索算法原理153,76,命题逻辑的归结法,归结过程 对结论作否定,并加入前提中将命题写成合取范式求出子句集对子句集使用归结推理规则归结式作为新子句参加归结归结式为空子句，S是不可满足的（矛盾），原命题成立。（证明完毕）谓词的归结：除了有量词和函数以外，其余和命题归结过程一样。,2023/1/24,人工智能一般搜索算法原理153,77,命题逻辑的归结法,例 证明先将化为合取范式 建立子句集 S=对S做归结 P NIL,2023/1/24,人工智能一般搜索算法原理153,78,归结原理,概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制,2023/1/24,人工智能一般搜索算法原理153,79,归结原理,概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制,2023/1/24,人工智能一般搜索算法原理153,80,子句形,引用Herbrand定理，以说明归结原理的意义及一个原理形成的根基与背景SKOLEM标准形前束范式：把所有的量词都提到前面去，然后消掉所有量词。定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。即(Q1x1)(Qnxn)M(x1,xn),其中Qixi为存在量词或全称量词,M(x1,xn)为合取范式(由一些子句的合取组成)。,2023/1/24,人工智能一般搜索算法原理153,81,子句形(Skolem 标准形),量词消去原则：消去存在量词“”，略去全程量词“”。注意：左边有全称量词的存在量词，消去时该变量改写成为全称量词的函数(Skloem函数)；如没有，改写成为常量。,例子：见人工智能及其应用P75,2023/1/24,人工智能一般搜索算法原理153,82,子句形(Skolem 标准形),定理：谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义：消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。,2023/1/24,人工智能一般搜索算法原理153,83,子句形(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),2023/1/24,人工智能一般搜索算法原理153,84,子句形,子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：G SKOLEM标准形 消去存在变量 以“，”取代“”，并表示为集合形式。,2023/1/24,人工智能一般搜索算法原理153,85,子句形,G是不可满足的 S是不可满足的G与S不等价，但在不可满足的意义下是一致的。定理：若G是给定的公式，而S是相应的子句集，则G是不可满足的 S是不可满足的。注意：G真不一定S真，而S真必有G真。即：S=G,2023/1/24,人工智能一般搜索算法原理153,86,子句形,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不可满足,2023/1/24,人工智能一般搜索算法原理153,87,归结原理,概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制,2023/1/24,人工智能一般搜索算法原理153,88,归结原理,概述命题逻辑的归结法子句形Herbrand定理归结原理归结过程的策略控制,2023/1/24,人工智能一般搜索算法原理153,89,Herbrand定理,问题：一阶逻辑公式的永真性（永假性）的判定是否能在有限步内完成？,2023/1/24,人工智能一般搜索算法原理153,90,Herbrand定理,1936年图灵(Turing)和邱吉(Church)互相独立地证明了：,“没有一般的方法使得在有限步内判定一阶逻辑的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步内判定它是永真（或永假）。对于非永真（或永假）的公式就不一定能在有限步内得到结论。判定的过程将可能是不停止的。”,2023/1/24,人工智能一般搜索算法原理153,91,Herbrand定理,Herbrand的思想定义：公式G永真：对于G的所有解释，G都为真。思想：寻找一个已给的公式是真的解释。然而，如果所给定的公式的确是永假的，就没有这样的解释存在，并且算法在有限步内停止。,2023/1/24,人工智能一般搜索算法原理153,92,Herbrand定理,H域H解释语义树结论：Herbrand定理,2023/1/24,人工智能一般搜索算法原理153,93,Herbrand定理,H域H解释语义树结论：Herbrand定理,2023/1/24,人工智能一般搜索算法原理153,94,Herbrand定理（H域）,基本方法：因为量词是任意的，所讨论的个体变量域D是任意的，所以解释的个数是无限、不可数的。简化讨论域。建立一个比较简单、特殊的域，使得只要在这个论域上，该公式是不可满足的。此域称为H域：H0为G中所出现的常量的集合，若G中没有常量，就任取常量，H0=a。规定 为H域 例题请参考教科书P27,2023/1/24,人工智能一般搜索算法原理153,95,H域举例,例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)，,2023/1/24,人工智能一般搜索算法原理153,96,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上的真值可确定。成为可数问题。,2023/1/24,人工智能一般搜索算法原理153,97,原子集举例,例1 S=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),2023/1/24,人工智能一般搜索算法原理153,98,Herbrand定理（H域）,没有变量出现的原子、文字、子句和子句集，分别称作基原子、基文字、基子句和基子句集。它们在讨论子句集S的不可满足性时占有重要置。,2023/1/24,人工智能一般搜索算法原理153,99,Herbrand定理,H域H解释语义树结论：Herbrand定理,2023/1/24,人工智能一般搜索算法原理153,100,Herbrand定理,H域H解释语义树结论：Herbrand定理,2023/1/24,人工智能一般搜索算法原理153,101,Herbrand定理（H解释）,解释I*：取一个值得到一个结论I映射S中到所有常量符号到它们本身。(即原子集)令f是n元函数，I是f下的一个指派，即H中的元素到f的一个映射（函数值）。简单地说(P29)，A中的各元素真假组合都是H的解释。（或真或假只取一个）问题：对于所有的解释，全是假才可判定。因为所有解释代表了所有的情况，如可穷举，问题便可解决。,2023/1/24,人工智能一般搜索算法原理153,102,H解释-举例,例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*=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成立。,2023/1/24,人工智能一般搜索算法原理153,103,Herbrand定理（H解释）,如下三个定理保证了归结法的正确性：定理1：设I是S的论域D上的解释，存在对应于I的H解释I*，使得若有S|I=T，必有 S|I*=T。定理2：子句集S是不可满足的，当且仅当所有的S的H解释下为假。定理3：子句集S是不可满足的，当且仅当对每一个解释I下，至少有S的某个子句的某个基例为假。,2023/1/24,人工智能一般搜索算法原理153,104,Herbrand定理（H解释）,基例S中某子句中所有变元符号均以S的H域中的元素代入时，所得的基子句C称为C的一个基例。若一个子句为假，则此解释为假。一般来说，D是无穷不可列的，因此，子句集S也是无穷不可列的。但S确定后H是无穷可列的。不过在H上证明S的不可满足性仍然是不可能的。解决问题的方法：语义树,2023/1/24,人工智能一般搜索算法原理153,105,Herbrand定理,H域H解释语义树结论：Herbrand定理,2023/1/24,人工智能一般搜索算法原理153,106,Herbrand定理,H域H解释语义树结论：Herbrand定理,2023/1/24,人工智能一般搜索算法原理153,107,Herbrand定理（语义树）,构成方法原子集中所有元素逐层添加的一棵二叉树。将元素的是与非分别标记在两侧的分枝上（可不完全画完）。(P34)特点一般情况H是可数集，S的语义树是无限树。,2023/1/24,人工智能一般搜索算法原理153,108,Herbrand定理（语义树）,意义S H A 语义树可以理解语义树为H域的图形解释。目的：把每个解释都摊开。语义树中包含原子集的全部元素，因此，语义树是完全的。每一个直到叶子节点的分支对应S的一个解释。可以通过对语义树每一个分支来计算S的真值。如果每个基例都为假，则可认为是不可满足的。,2023/1/24,人工智能一般搜索算法原理153,109,语义树-举例,例1 设子句集S的原子集 A=P,Q,R 语义树：N0,N11,N12,N21,N22,N23,N24,N31,N32,N33,N34,N35,N36,N37,N38,P,Q,Q,R,R,P,I(N)表示从根节点到节点N分枝上所标记的所有文字的并集。如 I(N34)=P,Q,R,2023/1/24,人工智能一般搜索算法原理153,110,Herbrand定理（语义树）,几个概念失败结点：当（由上）延伸到点N时，I(N)已表明了S的某子句的某基例假。但N以前尚不能判断这事实。就称N为失败结点。完全语义树：如果对语义树的所有叶结点N来说，I(N)包含了S的原子集 A=A1,A2,中的所有元素Ai或 Ai，I=1 n。封闭语义树：如果S的完全语义树的每个分枝上都有一个失败结点，就称它是一棵封闭语义树。,2023/1/24,人工智能一般搜索算法原理153,111,封闭语义树-举例,例 子句集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,N11,N12,N21,N22,N23,N24,N31,N32,N33,N34,N35,N36,N37,N38,P(a),Q(a),P(f(a),N41,N42,N43,N44,N45,N46,N47,N48,N49,N410,N411,N413,N415,N412,N414,N416,这是一个无限树，然而它是否是一个封闭树？,Q(f(a),I(N41)=P(a),Q(a),P(f(a),Q(f(a),它使S的子句Q(f(y)的基例Q(f(a)为假，而N41的父辈不能使子句的基例为假,2023/1/24,人工智能一般搜索算法原理153,112,封闭语义树-举例,例 子句集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,N11,N12,N21,N22,N23,N24,N31,N32,N36,N37,N38,P(a),Q(a),P(f(a),N41,N42,N49,N410,N413,N414,Q(f(a),2023/1/24,人工智能一般搜索算法原理153,113,Herbrand定理,H域H解释语义树结论：Herbrand定理,2023/1/24,人工智能一般搜索算法原理153,114,Herbrand定理,H域H解释语义树结论：Herbrand定理,2023/1/24,人工智能一般搜索算法原理153,115,Herbrand定理（结论）,Herbrand定理：子句集S是不可满足的，当且仅当对应于S的完全语义数是棵有限封闭树。子句集S是不可满足的，当且仅当存在不可满足的S的有限基例集。,2023/1/24,人工智能一般搜索算法原理153,116,Herbrand定理（结论）,定理的意义Herbrand定理已将证明问题转化成了命题逻辑问题。由此定理保证，可以放心的用机器来实现自动推理了。（归结原理）注意Herbrand定理给出了一阶逻辑的半可判定算法，即仅当被证明定理是成立时