人工智能 第二章 问题求解的基本方法

第二章问题求解的基本方法2.1一般图搜索2.2问题规约2.3基于归结的演绎推理2.4基于规则的演绎推理2.5本章小结问题求解系统知识贫乏系统（依靠搜索技术）知识丰富系统（依靠推理识别技术）本章两大部分搜索技术一般图搜索基于问题规约的与或图搜索推理技术基于归结的谓词演算基于规则的演绎推理2.1一般图搜索2.1.1问题状态描述2.1.2一般图搜索策略2.1.3启发式搜索2.1.4状态空间抽象和生成－测试法2.1.5启发式搜索的适用性讨论试探搜索方法通过在某个可能的解空间中寻找一个解来求解问题。基于解答空间的问题表示和求解方法即状态空间法。以状态和算符为基础来表示和求解问题。问题求解过程中由初始状态可能到达的所有状态的集合就构成该问题的状态空间或问题空间。2.1.1问题状态描述1、状态（state）是为描述某类不同事物间的差别而引入的一组最少变量q0、q1…、

qn的有序集合。其矢量形式如下：Q=[q0,q1,…,

qn]T式中每个元素qi（i=0,1,…,n)为集合的分量，称为状态变量。给定每个分量的一组值，就得到一个具体的状态，如Qk=[q0k,q1k,…,

qnk]T2、算符（操作符operator） 即：使问题从一种状态变化为另一种状态的手段。 可分为：走步、过程、规则、数学算子、运算符号或逻辑符号等。3、状态空间（statespace）状态空间是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合I、操作符集合O以及目标状态集合G。可记为：三元状态(I,O,G)。 二元状态(S,O)

状态空间

---有向图例1、传教士和野人问题设N个传教士带N个野人划船渡河，为安全起见，需遵循两个约束条件：（1）船上人数不得超过K；（2）任何时刻（两岸、船上）野人数目不得超过传教士数目。取N=3,K=2设m，c分别表示传教士和野人在左岸或船上的实际人数，b指示船是否在左岸(1表示在左岸)。问题条件即：m+c≤2，m≥c。问题简化为：(3,3,1)(0,0,0)(0,0,0)(1,0,0)(2,0,0)(3,0,0)(0,0,1)(1,0,1)(2,0,1)(3,0,1)(0,1,0)(1,1,0)(2,1,0)(3,1,0)(0,1,1)(1,1,1)(2,1,1)(3,1,1)(0,2,0)(1,2,0)(2,2,0)(3,2,0)(0,2,1)(1,2,1)(2,2,1)(3,2,1)(0,3,0)(1,3,0)(2,3,0)(3,3,0)(0,3,1)(1,3,1)(2,3,1)(3,3,1)思考:m_c问题中，N＝5，K＝3，分析并给出状态空间图。课后作业1：1）P76/二/1.有一农夫带一只狐狸、一只小羊和一蓝菜过河（从左岸到右岸）。假设船太小，农夫每次只能带一样东西过河；考虑到安全，无农夫看管时，狐狸和小羊不能在一起，小羊和那蓝菜也不能在一起。请为该问题的解决设计状态空间，并画出状态空间图。

2）有两个无刻度标志的水壶，分别可装5升和2升的水。设另有一水缸，可用来向水壶灌水或倒出水，两个水壶之间，水也可以相互倾灌。已知5升壶为满壶，2升壶为空壶，问如何通过倒水或灌水操作，使能在2升的壶中量出一升的水来。上周回顾人工智能的历史、发展和成果重要代表人物人工智能研究的原则存在的问题和前景状态空间搜索4、状态空间的搜索以SE表示：SE=(S,O,E,I,G)基本思想：通过搜索引擎寻找一个操作算子的调用序列，使问题从初始状态变迁到目标状态之一，而变迁过程中的状态序列或相应的操作算子调用序列称为从初始状态到目标状态的解答路径。或图由于一个状态可以有多个可供选择的操作算子，导致了多个待搜索的解答路径。这种选择在逻辑上称为“或”关系，这样的有向图称为或图。常用的状态空间一般都表示为或图，因而也称为一般图。例2、八数码难题

(8puzzleproblem)1372468512384765(a)初始(b)目标状态空间图搜索图搜索时直接涉及到的节点和弧线构成的图。解答路径例3、猴子和香蕉问题在一个房间内有一只猴子，一个箱子和一串香蕉。香蕉挂在天花板下方，但猴子的高度不足以碰到它。那么这只猴子怎么样才能摘到香蕉呢？2.1.2一般图搜索策略1、搜索术语节点深度：搜索图是一种有根图，根节点指示初始状态，令根节点深度为0，则搜索图中其他节点的深度dn=dn-1+1。路径：相邻节点间的弧线构成的折线，通常要求是无环的。节点扩展：应用操作算子将上一状态变迁到下一状态。路径代价：C(ni,ng)=C(ni,nj)+C(nj,ng)

2、图搜索的一般过程（GraphSearch）G:=G0(G0=S),OPEN:=(S);CLOSED:=();LOOP:ifOPEN=()THENexit(fail);n:=first(OPEN),remove(n,OPEN),add(n,CLOSED);ifgoal(n)thenexit(success);expand(n)→{mi},G:=add(mi,G);add(mj,OPEN),并标记mj到n的指针 计算是否要修改mk、ml到n的指针,

计算是否要修改ml到其后继节点的指针;add(ml,OPEN);resort(OPEN);GOLOOP;{mi}={mj}∪{mk}∪{ml}1）{mj}为OPEN和CLOSED中未出现过的子节点2）{mk}为已出现在OPEN中的子节点3）{ml}为在CLOSED中的子节点s－－指示初始状态节点；G－－指示搜索图；OPEN－－作为存放待扩展节点的表；CLOSED－－作为存放已被扩展节点的表；s123456s123456扩展节点6和节点1得到的搜索图注：实心圆点在CLOSED表中，空心圆点在OPEN表中思考题：第二章习题二、解析题第3题3、盲目搜索（无信息）（1）深度优先搜索（depth-firstsearch)首先扩展最新产生的（即最深的）节点。扩展当前节点后生成的子节点总是置于OPEN表的前端，即OPEN表作为栈使用。如果扩展当前节点后生成的任一个后继节点是个目标节点，则找到一个解答，成功退出。567586427301586427310586407321586427031586420317586470321506487321586047321586027431586402317580426317586471320580476321560487321056487321586047321586047321586207431086527431586042317586412307506482317508426317586471302508476321567480321456087321408321………………………123456789101112131415161718起始节点目标节点有界深度优先搜索算法：OPEN:=(S);CLOSED:=();ifgoal(S)thenexit(success);LOOP:ifOPEN=()THENexit(fail);n:=first(OPEN),remove(n,OPEN),add(n,CLOSED);ifdepth(n)=最大深度thenGOLOOP；expand(n)→{mi};把{mi}放到OPEN表的前头;if在{mi}中有任一个为目标节点thenexit(success);GOLOOP;（2）宽度优先搜索（breadth-firstsearch)扩展当前节点后生成的子节点总是置于OPEN表的后端，即OPEN表作为队列使用。如果扩展当前节点后生成的任一个后继节点是个目标节点，则找到一个解答，成功退出。586427301586427310586407321586427031586420317586470321506487321586047321586027431125586402317580426317586471320580476321560487321056487321586047321586047321586207431086527431586042317586412307506482317508426317586471302508476321567480321456087321567408321102021………………………221123361224132571426起始节点目标节点4891516171819解决方法——用启发式知识指导排序两种方式：局部排序——仅对新扩展出来的子节点排序全局排序——对OPEN表中的所有节点排序2.1.3启发式搜索启发式知识对于搜索的指导作用可归纳为3个方面：（1）选择下一个要被扩展的节点，排序OPEN表中的待扩展节点；（2）在扩展一个节点时，仅仅有选择地生成部分有用的节点，而非所有可能的子节点；（3）修剪掉某些估计不可能导致成功的子节点。本节讨论的内容1.启发式搜索策略总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索。2.估价函数（评价函数）估价函数（evaluationfunction）：是用来估算节点希望程度的量度。它能提供一个评定候选扩展节点的方法，以便确定哪个节点最有可能在通向目标的最佳路径上。我们用符号f来标记估价函数，用f(n)来表示节点n的估价函数值。3.算法A是应用估价函数来实现启发式搜索的典型算法。利用估价函数f(n)＝g(n)+h(n)

来排序OPEN表节点顺序的图搜索算法。其中:

f(n)——从s经由节点n到达ng估计的最小路径代价；

g(n)——到目前为止，从s到n估计的最短路径代价；

h(n)——从n到ng估计的最小路径代价。它要依赖于启发式知识来加以估算，因而h(n)称为启发式函数。启发式搜索算法A的过程:OPEN:=(s);f(s)=g(s)+h(s);CLOSED:=();LOOP:ifOPEN=()thenexit(fail);n:=first(OPEN);ifgoal(n)thenexit(success);remove(n,OPEN);add(n,CLOSED);expand(n){mi},计算f(n,mi)=g(n,mi)+h(mi);//f(n,mi)是从s通过n、mi到ng的耗散估计;//g(n,mi)是从s通过n到mi的耗散值估计;→

•add(mj,OPEN);标记mj到n的指针; •iff(n,mk)<f(mk)thenf(mk):=f(n,mk);标记mk到n的指针; //f(mk)是扩展n之前计算的耗散值

•iff(n,ml)<f(ml)thenf(ml):=f(n,ml);标记ml到n的指针;add(ml,OPEN);OPEN中的节点按f值从小到大排序;goLOOP;例4：应用算法A解答八数码难题解：令f(n)=d(n)+w(n)d(n):当前被考察和扩展的节点n在搜索图中的节点深度。w(n):值为节点n与目标节点ng相比较，错位的棋牌个数。103724685123804765上周回顾状态空间搜索（作业讲解）一般图搜索策略相关术语一般图搜索算法盲目搜索启发式搜索策略估价函数算法A思考题：第二章习题二、解析题第4题4.实现启发式搜索的关键因素（1）算法的可采纳性在存在解答路径的情况下，若一个搜索法总能找到最短（代价最小）的解答路径，则称该算法具有可采纳性。 为考察算法A的可采纳性，引入估价函数f*(n)=g*(n)+h*(n)。 条件：当经由节点n的最短解答路径找到时

f*(n)——实际的路径代价

g*(n)——该路径前段的代价

h*(n)——该路径后段的代价理想情况下，设计g(n)=g*(n),h(n)=h*(n)，然而，g*(n)和h*(n)在最短路径找到前是未知的，所以设计出这种理想的评价函数是几乎不可能的，即便是要设计接近f*的f也困难。再看前述八数码的例子，若用p(n)（每个错位棋牌在不受阻的情况下移到目标状态所需走步的总和）代替w(n)(错位棋牌个数)，则搜索更优，因为p(n)比w(n)更接近于h*(n)。应用p(n)的八数码难题搜索图见图2.1.9。A*算法可以证明：若确保对于搜索图中的节点n，总是有h(n)≤h*(n)，则算法A具有可采纳性。称满足h(n)≤h*(n)的算法A为A*。A*算法是可采纳的。（2）启发式函数的强弱及其影响

可用h(n)接近h*(n)的程度去衡量启发式函数的强弱：①当h(n)<h*(n)且差距较大时，

h(n)过弱→OPEN表中节点排序的误差较大；②当h(n)>h*(n)，

h(n)过强→算法A失去可采纳性。设计接近、又总是小于等于h*(n)的h(n)是应用A*算法(h(n)≤h*(n))搜索问题解答的关键。

（3）设计h(n)的实用考虑

在许多实用场合，人们并不要求找到最优解答，通过牺牲可采纳性来换取h(n)设计的简化和减少计算h(n)的工作量还是可行的。

从估价函数f(n)=g(n)+h(n)可以看出：①若h(n)≡0，则意味着先进入OPEN表的节点（g(n)较小）会优先被考察和扩展；②若g(n)≡0，则导致后进入OPEN表的节点（h(n)较小）会优先被考察和扩展。为了更有效地搜索解答，可使用估价函数f(n)=g(n)+wh(n)。在搜索图的上部，可让w取较大值，以使g(n)所占比例很小；在下部，可让w取较小值，以使g(n)所占比例很大，并确保wh(n)≤h*(n)。接近于宽度优先搜索接近于深度优先搜索5.爬山法和回溯策略

在g(n)≡0的情况下，若限制只用估价函数f(n)=h(n)去排序新扩展出来的子节点（即局部排序），就可以实现较为简单的搜索策略：爬山法和回溯策略。（1）爬山法——是实现启发式搜索的最简单方法。要求：只能向山顶爬去，不准后退。特点：不需保存任何待扩展节点；仅从当前状态节点扩展出子节点，并将h(n)最小的子节点（对应到顶峰最近的上爬路径）作为下一次考察和扩展的节点，其余子节点全部丢弃。

①n:=s; //s为初始节点②LOOP:ifgoal(n)thenexit(success);③expand(n)→{mi};计算h(mi); nextn:=m(min(h(mi))的节点);④ifh(n)<h(nextn)thenexit(fail);//相当于前面已无路可走，所以失败！⑤n:=nextn;⑥goLOOP;过程（Hill-climbing）：（2）回溯策略（BacktrackingStrategies）特点：在问题求解过程中，如果发现应用一条不适合的规则会阻挠或拖延达到目标的过程，可以先试一试某一条规则，如果以后发现这条规则不合适，则允许退回去，另选一条规则来试。算法名backtrack(n)，n为当前被扩展的节点，初次调用式是backtrack(s)。①ifgoal(n)thenreturnnil;//成功即返回空表nil②ifdeadend(n)thenreturnfail;//失败则返回fail，必须回溯③expand(n);将生成的子节点放入列表SNL;并按估价函数f(k)=h(k)的值从小到大排序;④ifisempty(SNL)thenreturnfail;⑤n’=first(SNL);⑥path:=backtrack(n’);⑦ifpath=‘fail’thengoto④;⑧将n’加到path表首;returnpath;

过程：例5：回溯法解决n后问题。

1）问题描述 在一个n×n格的棋盘上放置n个皇后，使得他们彼此不受攻击。按国际象棋的规则，一个皇后可以攻击与之处于同一行或同一列或同一斜线上的其他任何棋子。因此，n后问题等价于要求在一个n×n格的棋盘上放置n个皇后，使得任何2个皇后不能被放在同一行或同一列或同一斜线上。

2）利用启发式函数解决四皇后（n＝4）问题设计f(n)=h(n)=D(n)：状态n下最新一个皇后位置所在的长对角线的长度（格子数）。

2.1.4状态空间抽象

和生成－测试法

1.状态空间抽象这是减少搜索量的重要技术，适合于寻找令人满意的解答。常用方式：将状态空间按子问题进行划分，子问题构成抽象空间。复杂问题还可采用多级抽象。例如，旅行者可先用只描述主要公路的全国交通图决定大致路线，然后决定每一段的详细行程，这就需要沿途城市的详细地图。

2.生成－测试法

两部分合作完成：可能解的生成器和修剪不正确解答的测试器。实际应用的生成－测试器常是分层的。2.1.5启发式搜索的

适用性讨论纵观启发式搜索技术的应用，它面临着3个关键选择：确定性或非确定性搜索方式；搜索目标状态（确定性）本身还是达到目标状态的解答路径（非确定性）；搜索一个（确定性）还是全部或最优解答（非确定性）。可以说，后两者在一定程度上决定了前者。

2.2问题规约2.2.1问题规约的描述2.2.2与或图搜索2.2.3与或图的启发式搜索

问题规约（problemreduction），就是把复杂的问题变换为若干需要同时处理的较为简单的子问题后再加以分别求解。问题的解答就由子问题的解答联合构成。 采用问题规约表示可由下列3部分组成： （1）一个初始问题描述； （2）一套把问题变换为子问题的操作符； （3）一套本原问题描述。所谓本原问题就是不可或不需再通过变换化简的“原子”问题。问题规约的实质：从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题规约为一个平凡的本原问题集合。2.2.1问题规约的描述1.问题规约的表示问题规约是一种广义的状态空间搜索技术，其状态空间同样可表示为二元组SP=（S,O）不同的是：

S——问题状态，可以通过子问题状态的联合加以表示；

O——操作算子，其执行可以导致问题的变换。

2.问题的变换变换可区分为下列3种情况：

1）状态变迁——导致问题从上一状态变迁到下一状态。

2）问题分解——分解问题为需要同时处理的子问题，但不改变问题状态。

3）基于状态变迁的问题分解——先导致状态变迁，再实现问题分解，实际上就是前两个操作的联合执行。（1）字母重写问题

1）问题描述初始状态为字母列表（ABC），目标状态为只包含x、y、z的字母列表。提供两类操作算子：

a、面向问题分解——通过将表示问题状态的字母列表分解为若干子表来实现问题的分解，该操作由单一操作算子Split(n)实现（n是当前问题状态节点）。3.举例说明b、面向状态变迁——设计为字母列表的重写规则：(A)→(DF)(A)→(G) (BC)→(E)(B)→(H)(C)→(IJK) (D)→(x) (E)→(yz)(F)→(xyz)(G)→(z) (H)→(xx) (I)→(yy)(J)→(zz)(K)→(xz)

2）问题求解

像图2.2.1所示的应用问题规约策略得到的状态空间图，也称为“与或图”或者“超图”。其用圆弧将几条节点间关联弧连接在一起去指示问题分解为子问题，这些子问题的求解具有逻辑“与”关系，只有全部解决才会使问题得以解决。由于存在“或”分枝，上述问题有4个解答：(xxyzyz)、(zyz)、(xxyzxxyyzzxz)、(zxxyyzzxz)。 对于这个问题，可以把面向状态变迁的操作和面向问题分解的操作合并为基于状态变迁的问题分解操作，以获得更为紧凑的问题规约描述。紧凑的重写规则如下：

(ABC)→(A)(BC)(ABC)→(A)(B)(C)(A)→(D)(F) (A)→(G) (BC)→(E)(B)→(H) (C)→(I)(J)(K)（2）汉诺塔难题(Tower-of-HanoiPuzzle）

1）问题描述

有3个柱子（1，2和3）和3个不同尺寸的圆盘（A，B和C）。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。以三元组来描述问题状态，3个元素依次指示盘子A、B、C所在的柱子编号。如此，该问题可以描述为（111）→（333）。2）问题求解 可以把该问题规约为3个子问题：（111）→（221），可分解为：

(111)→(311)、(311)→(321)、(321)→(221)（221）→（223）（223）→（333），可分解为：

(223)→(123)、(123)→(133)、(133)→(333)

现在所有问题均为本原问题，只要依次解决就可到达目标状态。

（3）符号积分问题

符号积分是求不定积分原函数的问题，通过应用各种代数和三角变换以及不定积分性质可以把复杂的积分问题逐步规约为若干个本原积分问题（可利用积分表直接求出原函数）。（4）分子结构识别问题

把分子式重写为原子数较少的分子式和原子间结合关系的混合结构，将混合结构的识别再分解为子识别问题，每个子问题只是单一分子式或原子间结合关系的表示。2.2.2与或图搜索可以认为：与或图是对一般图的扩展；一般图是与或图的特例。一般图不允许节点间具有“与”关系，所以又被称为或图。1．与或图搜索的基本概念（1）K-连接用于表示从父节点到子节点的连接，也称为父节点的外向连接，并以圆弧指示同父子节点间的“与”关系，K为这些子节点的个数。一个父节点可有多个外向的K-连接，K>1的连接也称为超链接，K=1时，超链接蜕化为普通连接，而当所有超链接的K都等于1时，与或图就蜕化为一般图（或图）。（2）根、叶、终节点 根节点：无父节点的节点，用于指示问题的初始状态。 叶节点：无子节点的节点。 由于问题规约伴随着问题分解，所以目标状态不再由单一节点表示，而是应由一组节点联合表示。能用于联合表示目标状态的节点就称为终节点。 终节点必是叶节点，反之不然。（3）解图的生成 生成过程：自根节点开始选一外向连接，并从该连接指向的每个子节点出发，再选一外向连接，如此反复进行，直到所有外向连接都指向终节点为止。2．举例说明图2.2.4抽象的与或图（叶子节点均为终节点）n0n6n5n4n3n2n1n12n11n17n16n15n14n13n20n19n18n7n8n9n102142312113

在与或图是无环的假定下，解图可递归定义如下：（1）解图 一个与或图G中，从节点n到节点集N的解图记为G’，G’是G的子图。 ①若n是N的一个元素，则G’由单一节点组成；② 若n有一个指向节点{n1,…,nk}的外向连接符K，使得从每一个ni到N有一个解图（i=1,…,k），则G’由节点n，连接符K，及{n1,…,nk}中的每一个节点到N的解图所组成；③ 否则n到N不存在解图。

3．相关定义（2）解图代价 在搜索解图的过程中，还需要进行代价（耗散值）的计算。设连接符K的代价规定为：K-连接符的代价=K，若从节点n到N的解图代价记为C(n)，则可递归计算如下： ①若n是N的一个元素，则C(n)=0；②若n有一个外向K-连接指向后继节点{n1,…,nk}，且这些子节点每个都有到N的解图，则有：C(n)=K+C(n1)+…+C(nk)

① 终节点是能解节点；② 若非终节点有“或”子节点，当且仅当其子节点至少有一能解，该非终节点才能解；③ 若非终节点有“与”子节点，当且仅当其子节点均能解，该非终节点才能解。（3）能解节点（SOLVED）

① 没有后裔的非终节点是不能解节点；② 若非终节点有“或”子节点，当且仅当所有子节点均不能解时，该非终节点才不能解；③ 若非终节点有“与”子节点，当至少有一子节点不能解时，该非终节点才不能解。（4）不能解节点（UNSOLVED）课后作业2：P77习题二二、解析题第8题上周回顾实现启发式搜索的关键因素算法的可采纳性启发式函数的强弱及其影响爬山法和回溯策略4皇后问题问题规约字母重写问题（例）Hanoi问题与或图搜索思考：第二章习题P77二、解析题第7题初始状态(C,B,Z)，目标状态是只含M的列表规则：C=>(D,L)C=>(B,M)B=>(M,M)Z=>(B,B,M)2.2.3与或图的启发式搜索

启发式的与或图搜索过程和普通图类似，也是通过评价函数f(n)来引导搜索过程。由于搜索的是一个解图，因而考察待扩展节点n的历史情况时，已不是从初始节点到n这条路径的g(n)就能说明问题，因此只考虑h(n)这个分量，并企图通过h(n)对h*(n)进行估计。

由于与或图中子节点或子节点组间可以存在“或”关系，所以在搜索过程中会同时出现多个候选的待扩展局部解图，应估计所有这些局部解图的可能代价，并从中选择一个可能代价最小的用于下一步搜索。 从父节点n到终节点集合解图的可能代价f(n)可以用如下公式计算：f(n)=K+h(n1)+h(n2)+…+h(nk)

其中，{n1,…,nk}是父节点n的外向K-连接指向的子节点集合，每个子节点都估算了其h(ni)的值（i=1,…,k）。1.与或图启发式搜索算法AO*

设：G——搜索图；G’——被选中的待扩展局部解图；LGS——候选的待扩展局部解图集；n0——根节点；n——被选中的待扩展节点；过程：① G:=n0,LGS为空集;② ifgoal(n0)thenmark(n0,solved)else计算f(n0)=h(n0);把G作为0号候选局部解图加进LGS;③ ifismarked(n0)thenreturnsuccess;//若n0标记为能解节点，则成功返回④ ifLGS=nullthenreturnfailelse从LGS选择fi(n0)最小的待扩展局部解图作为G’;⑤ G’中选择一个尚未用于扩展出子节点的节点作为n;⑥ expand(n)→{n1,…,nk};

从中删去导致有环的子节点以及和它们有“与”关系的子节点;if子节点集=nullthen{mark(n,unsolved);从LGS中删去G’;}else{计算每个子节点ni的f(ni);并通过建立外向K-连接将所有子节点加到图G中;}⑦ if存在j>1个K-连接then{从LGS删去G’;将j个新局部解图加进LGS;}⑧ G’中或在取代G’的j个新局部解图中用f(n)=K+h(n1)+h(n2)+…+h(nk)的计算结果取代原先的f(n);并传递到fi(n0);将终节点的子节点标记为能解节点;并传递节点的能解性;⑨ goto③;2.算法应用举例

下面就以图2.2.4所示与或图为例，观察如何应用AO*算法来搜索解图。

为了使用方便，将h(n)函数对图2.2.4中各节点的假想估值先列出如下（实际应用中是节点生成出来之后才根据h(n)定义式计算）：h(n0)=3h(n1)=2 h(n2)=1h(n3)=1h(n4)=4h(n5)=2h(n6)=2h(n7)=1h(n8)=1h(n13)=3

此外，仍假设K-连接符的代价=K。搜索过程可参照表2.2.1。

3.算法应用的若干问题

（1）从局部解图中选择加以扩展的节点

应选择导致解图代价发生较大变化的节点优先加以扩展，以使搜索的注意力快速地聚焦到实际代价较小的候选解图上，而且会促使及时修改局部解图的标记。

这种选择需要附加的启发式知识，若应用领域挖掘不出这样的启发式知识，可随机选择加以扩展的节点。

（2）AO*算法的可采纳性 同A*算法类似，若存在解图，当h(n)≤h*(n)且h(n)满足单调限制条件时，则AO*算法一定能找到最佳解图，即AO*算法具有可采纳性。当h(n)≡0时，AO*算法也蜕化为宽度优先算法。单调限制条件是指：对隐含图中，从节点n→{n1,…,nk}的每一个连接符都施加限制，即假定h(n)≤K+h(n1)+h(n2)+…+h(nk)。

（3）搜索算法AO*与A*的比较

（4）解图代价的重复计算

解图中某些子节点可能会有多个父节点，或者说多个节点的外向连接符可能指向同一个子节点。依据前述解图代价的递归计算方式，显然这种子节点到终节点集合解图的代价在计算自根节点出发的解图时被重复累计了。

n0n3n4n5n10n11n12n16n172.3基于归结的演绎推理2.3.1谓词演算2.3.2归结演绎方法2.3.3归结反演人类的问题求解行为更像是一个解答识别而非解答搜索过程。识别解答或部分解答依赖于应用领域特有的知识，符号推理则成为基于知识来求解问题的主要手段。符号推理的重要方式是演绎推理，其基础即谓词演算。谓词逻辑（predicatelogic）允许我们表达那些无法用命题逻辑表达的事情，它是一种形式化语言，其根本目的在于把数学中的逻辑论证符号化。2.3.1谓词演算

1.一阶谓词演算的基本概念（1）谓词的概念首先考察几个例子。例1：（a）5是质数x是质数（b）张明生于北京x生于y

（c）7＝3×2x＝y×z

右侧是每个例子的模式，“是质数”刻画x的性质，“生于”刻画x和y的关系，“…＝…×…”刻画x、y、z的关系。我们把“5”、“张明”、“北京”、“7”、“3”、“2”叫做个体，代表个体的变元叫做个体变元。刻画个体的性质或几个个体间关系的模式叫做谓词。“是质数”、“生于”、“…＝…×…”都是谓词。谓词一般用大写字母表示，个体用小写字母表示。设F表示“是质数”，则“x是质数”表示为F(x)；G表示“生于”，则“x生于y”表示为G(x,y)；H表示“…＝…×…”，则“x＝y×z”表示为H(x,y,z)。F(x)、G(x,y)、H(x,y,z)等叫做谓词命名式，简称谓词。谓词命名式中个体变元的取值范围叫做论域或个体域。谓词中所包含的个体变元的个数称为谓词元数。含有n个个体变元的谓词称为n元谓词。设P(x1,x2,…,xn)是n元谓词，其中，x1，x2，…，xn是个体变元，则P(x1,x2,…,xn)称为谓词演算的原子公式。（2）谓词演算谓词逻辑的基本组成部分是谓词符号、变量符号、函数符号和常量符号，并用圆括弧、方括弧、花括弧和逗号隔开，以表示论域内的关系。例如，要表示“机器人（ROBOT）在1号房间（r1）内”，我们可应用简单的原子公式：INROOM（ROBOT，r1）式中，ROBOT和r1为常量符号，INROOM为谓词符号。一般，原子公式由若干谓词符号和项组成，项包括以下三类：常量符号是最简单的项，用来表示论域内的物体或实体，它可以是实际的物体和人，也可以是概念或具有名字的任何事情。变量符号允许我们不必明确涉及是哪一个实体。例如INROOM（x，y）。函数符号表示论域内的函数。例如，mother(Li)可用来表示Li和他的母亲之间的一个映射。用下列谓词公式表示“李（Li）的母亲和他的父亲已结婚”这个关系：MARRIED[father(Li),mother(Li)]2.连词和量词

原子公式是谓词演算的基本积木块。通过引入连词和量词，可以把原子公式组合为复合谓词公式。通常将复合谓词公式称为逻辑语句，所以谓词演算也称为谓词逻辑。

（1）连词1）否定～（非）：在谓词公式前面加连词～（非）称为否定，也称为取反。2）与∧：用连词∧连接谓词公式称为合取，其每个成分称为合取项。3）或∨：用连词∨连接谓词公式称为析取，其每个成分称为析取项。4）蕴涵→：用连词→连接谓词公式产生蕴涵式，→左部称为前项，右部称为后项。5）等价：用连词连接谓词公式产生等价式。

真值表如表2.3.1。

1）量词的概念看如下两个命题： 所有的人都是要死的。 有些人是要死的。这两个命题中的个体词和谓词均相同，区别在于“所有的”和“有些”这两个表示数量的词。表示数量的词在谓词逻辑中称为量词，量词包括全称量词和存在量词两种。（2）量词全称量词：对应于日常语言中的“一切”、“所有的”、“任意的”等词，表示对个体域中的所有个体，用符号“”表示。存在量词：对应于日常语言中的“存在着”、“至少有一个”、“有些”等词，表示存在着个体域中的个体，用符号“”表示。当个体域有限时，设之为{a1，a2，…，an}。

xF(x)F(a1)∧F(a2)∧…∧F(an)

xF(x)F(a1)∨F(a2)∨…∨F(an)如果个体域时全总个体域，xF(x)表示宇宙间所有论述对象都是要死的，xF(x)表示存在着要死的个体。显然与原命题表达的含义不同，因此，有必要引入新的谓词，将人类分离出来。上述两个命题可分别描述为：对于所有的个体，如果它是人，则它是要死的。存在这样的个体，它是人并且是要死的。用M(x)表示“x是人”，这时两命题可以符号化为：x(M(x)→F(x))

x(M(x)∧F(x))用F(x)表示“x是要死的”2）变元约束 在谓词公式xA和xA中，x称为量词的指导变元或作用变元；A称为量词的辖域或作用域。辖域中x的所有出现称为约束出现，也称x受相应量词指导变元的约束，A中不是约束出现的其他变元的出现称为自由出现。 例如，xP(x)→P(y)中，的辖域是P(x)，指导变元是x。整个公式中，x是约束出现，受x的约束，y是自由出现。3）约束变元的改名规则将量词辖域中出现的某个约束变元及相应的指导变元换成一个辖域中未曾出现过的个体变元名，公式的其余部分不变。4）自由变元的代入规则

对某自由出现的个体变元，用与原公式中所有变元名不同的变元名代入，且处处代入。

例如：（3）一阶谓词演算 若限定不允许对谓词、连词、量词和函数名进行量化处理，且项不能是谓词公式，则这样的谓词演算是一阶的。换言之，一阶谓词演算不允许在谓词、连词、量词和函数名的出现位置上使用变量。3.合适公式（合式公式）原子(谓词)公式原子公式::=谓词名+“(”+项[,项]+“)”项::=常量|变量|函数函数::=函数名+“(”+参数[,参数]+“)”（1）合适公式的定义

递归定义如下：1)

单一谓词公式（原子公式）是合适公式；2)

若A是合适公式，则（～A）也是合适公式；3)

若A和B是合适公式，则（A∧B）、（A∨B）、（A→B）和（A

B）也都是合适公式；4)

若A是合适公式，x是约束变量，则

xA和

xA也都是合适公式；5)

只有有限次地应用1）～4）求得的公式，才是合适公式。课堂练习1P77二、解析题10.将以下语句：

（1）会朗读者是识字的，

（2）海豚都不识字，

（3）有些海豚是很机灵的，

（4）有些很机灵的东西不会朗读。

形式化表示为合适公式。

（2）合适公式的解释 一个解释（赋值）I由下面几部分构成：1）非空个体域D；2）D中一部分特定元素；3）D上一些特定的谓词。用一个解释I解释一个谓词公式A包括：将I的个体域D作为A的个体域，A中个体常元用I中的特定元素代替，谓词变元用I上的特定谓词代替。例1：考虑以下解释I：1）个体域D={0,1}；2）D中的特定元素a＝0；3）D上的特定谓词P：在解释I下，

xyP(x,y)和xP(x,a)是真还是假？解：

xyP(x,y)((P(0,0)P(0,1))(P(1,0)P(1,1)) (FT)(TF) TT T

xP(x,a) P(0,0)P(1,0) FT F（3）合适公式的永真性和可满足性设A为一谓词公式，如果A在某论域D的任何解释下都是真的，则称A是重言式（永真式）；如果A在某论域D的任何解释下都是假的，则称A是矛盾式（永假式），即A在D上是不可满足的；若在某论域D上，至少存在一种解释使A为真，则称A是可满足式。例2：设P(x)仅可解释为：1）A(x)：x是质数；2）B(x)：x是合数。论述域是{3，4}。所以，P(x)

xP(x)非永真式。P(x)xP(x)

xP(x)A(x)3111A(x)4010B(x)3010B(x)4111（4）合适公式的性质(可参照教材P43)~(~P)PP→Q~P∨Q~(P∨Q)~P∧~Q~(P∧Q)~P∨~QP∧(Q∨R)(P∧Q)∨(P∧R)P∨(Q∧R)(P∨Q)∧(P∨R)P∨QQ∨PP∧QQ∧P(P∧Q)∧RP∧(Q∧R)(P∨Q)∨RP∨(Q∨R)P→Q~Q→~P~(x)P(x)(x)(~P(x))~(x)P(x)(x)(~P(x))4.合适公式的标准化（1）标准化需求 合适公式的标准化是为基于谓词演算的演绎推理服务的，常见的基于谓词演算的推理有归结反演和规则演绎。这两种演绎推理都要求以所谓的量词前束范式来表示合适公式。下面就介绍相关概念。1）合取范式

定义如下：2）析取范式 是合取范式的对偶式。定义如下：3）前束范式一个谓词公式，如果量词均在全式的开头，且其辖域延伸到公式的末尾，则该公式称为前束范式。形如：(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)

其中，Qi（i＝1，2，…，n）是存在量词或全称量词，而母式M(x1,x2,…,xn)中不再含有量词。xi是量词的约束变元。归结反演要求母式M标准化为合取范式。（2）标准化过程

1）消去多余的量词 若一个量词的辖域内并未出现量词的约束变量，则该量词是多余的，应将其消去。例如，

xP(y)中的

x就可以消去。2）消去蕴涵符号 应用性质P→Q

~P∨Q将蕴涵符号消去。3）内移否定符号 使否定符号只出现在原子谓词公式前面，以构成否定文字。可以应用性质：4）变量换名应用上面提到的改名规则和代入规则进行换名。5）消去存在量词

对给定的一阶谓词逻辑公式G=A1∧A2∧A3∧~B，与它等价的前束范式是(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)设（Qrxr）1≤r≤n是第一个出现于(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)中的存在量词，即Q1，Q2，…，Qr－1均为全称量词。若r＝1，则将M(x1,x2,…,xn)中的所有变量x1均以某个常量C代之，但要求C不同于已出现在M(x1,x2,…,xn)中的任一常量。然后便可消去这个存在量词（Q1x1）即

x1。若1<r≤n，（Qrxr）的左边有全称量词(Qs1xs1)，(Qs2xs2)，…，(Qsmxsm)

而1≤s1<s2<…<sm<r，则将M(x1，…，xr，…，xn)中的所有变量xr均以变量xs1，…，xsm的某个函数如f(xs1，…，xsm)代之，但要求f不同于已出现在M(x1,x2,…,xn)中的任一函数，而对f的具体形式没有要求。然后消去这个存在量词（Qrxr）。反复使用这种方法于(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)，便可消去其中所有的存在量词，所得之公式称作公式G的SKOLEM标准形。

消去存在量词例：6）全称量词前束化 经过第4）步的变量换名后，所有量词的约束变量均有不同的名字，所以只要简单地将这些量词移动到合适公式的最前面集中存放即可。7）消去全称量词 假设所有变量均受全称量词的约束，则可以简单地删去全称量词，只留下母式。8）把母式转化为合取范式 应用合适的分配律将母式转化为合取范式。上周回顾与或图的启发式搜索算法AO*AO*算法应用的若干问题一阶谓词演算连词和量词变元约束合适公式合适公式的解释合适公式的永真性和可满足性合适公式的标准化例3：将下列合适公式标准化为消去量词的合取范式。3.内移否定符号 6.全称量词前束化4.变量换名5.消去存在量词7.消去全称量词8.把母式转换为合取范式2.消去蕴涵符号1.消去多余的量词课堂练习1P77二、解析题11（1）

2.3.2归结演绎方法设前提条件P={P1,P2,…,Pn},Pi(i=1,…,n)是合适公式,结论W也是合适公式。定理证明的实质就是要证明：P1

P2

…

PnW证明的方法分两类：演绎法 ：即直接证明P1

P2

…

PnW

反证法：P1

P2

…

Pn～WF本节的内容1.H域和海伯伦定理1）子句与子句集概念文字:原子公式或原子公式的否定。子句:仅由文字的析取组成的合适公式。子句集：以子句作为元素的集合。例子P(A)

~Q(x,y),~P(x,c)

R(x,y,f(x))都是子句。合取范式就是子句的合取，即子句集。上一节中的实例就可表示为子句集：为消除子句间不必要的交互作用（即保持子句间的相互独立性），需要做变量换名，使各子句都使用不同的变量。上述子句集转变为：可以将一个合适公式G化简为标准化的子句集S。公式G与其子句集S并不等价，但是G是不可满足的当且仅当S是不可满足的。2）H域（Herbrand域）对于一个谓词公式来说，不可满足性的证明是困难的。这是由于个体变量论域D的任意性，以及解释个数的无限性。如果对一个具体的谓词公式能找到一个比较简单的特殊的论域，使得只要在这个论域上公式是不可满足的，便能保证该公式在任一论域上也是不可满足的，这将是十分有益的。H域就具有上述性质。构造H域的方法：设G是已给的公式，定义在论域D上，令H0是G中所出现的常量的集合。若G中没有常量出现，就任取常量a∈D，而规定H0＝{a}。Hi

＝Hi－1{所有形如f(t1,t2,…,tn)的元素}，其中f(t1,t2,…,tn)是出现于G中的任一函数符号，而t1,t2,…,tn是Hi－1的元素，i=1,2,…。规定H

为G的H域（或说是相应的子句集S的H域）。举例：例1:S={P(a),~P(x)

P(f(x))}H0={a}H1=H0{f(a)}={a,f(a)}H2={a,f(a)}{f(a),f(f(a))}={a,f(a},f(f(a))}…H

={a,f(a),f(f(a)),…}A={P(a),P(f(a)),P(f(f(a))),…}例2:S={~P(z),P(x)

~Q(y)}H0={a}H1=H0H2=H1…H

={a}A={P(a),Q(a)}例3:S={P(f(x),a,g(y),b)}H0={a,b}H1={a,b,f(a),g(a),f(b),g(b)}H2={a,b,f(a),g(a),f(b),g(b),f(f(a)),f(g(a)),f(f(b)),f(g(b)),g(f(a)),g(g(a)),g(f(b)),g(g(b))}…H

=H0

H1

H2…A={P(a,a,a,a),P(a,a,a,b),…,P(f(a),a,a,a),…}如果在S中出现函数形如f(x,a)，仍视为f(x1,x2)的形式，这时若H0={a,b}，则H1中除有f(a,a)，f(b,a)外，还出现f(a,b)，f(b,b)。为了研究子句集S的不可满足性，除引入个体域H外，还需讨论H域上S中各谓词的真值。令集合A＝{所有形如P(t1,t2,…,tn)的元素}称作子句集S（或公式G）的原子集。其中，P(t1,t2,…,tn)是出现于S中的任意谓词符号，而t1,t2,…,tn是S的H域的任意元素。回看例1～3的原子集。例4：S={P(x)Q(x),R(f(y))}H={a,f(a),f(f(a)),…}A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),P(f(f(a))),Q(f(f(a))),R(f(f(a))),…}几个术语：基原子：没有变量出现的原子。基文字：没有变量出现的文字。基子句：没有变量出现的子句。 基子句集：没有变量出现的子句集。基例：当将S中的某子句C中所有变量符号均以S的H域的元素代入时，所得的基子句C’称作C的一个基例。例S={P(x),Q(f(y))R(y)}有H={a,f(a),f(f(a)),…}对任一bD，子句P(b),Q(f(b))R(b)都叫基子句。而P(a),P(f(a))都称作子句C=P(x)的基例；同样，Q(f(a))R(a),Q(f(f(a)))R(f(a))都是子句Q(f(y))R(y)的基例。注意：Q(a)R(a)不是基例！3)H解释

以S={P(x)Q(x),R(f(y))}为例，有：

H={a,f(a),f(f(a)),…}A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),…}

凡对A中各元素真假值的一个具体设定，都是S的一个H解释。如：I1*={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),…}I2*={~P(a),~Q(a),~R(a),~P(f(a)),~Q(f(a)),~R(f(a)),…}I3*={P(a),~Q(a),~R(a),P(f(a)),Q(f(a)),~R(f(a)),…}上面出现的P(a)指P(a)取值为T，出现的~P(a)指~P(a)=T或说P(a)取值为F。显然在H域上，这样定义的I*下，S的真假值就确定了。如S|I1*=T,S|I2*=F,S|I3*=F4)H域解释的语义树n0n11n12n21n22n31n32P~PQ~QR~R图2.3.1简单的语义树从根节点到叶子节点的路径就指示了一个解释，记为I(n)，其表示为路径上标记的集合，每个标记是一个文字。例如，I(n32)={P,Q,~R}。设子句集S的原子集A={P,Q,R}(命题逻辑)，子句集S的语义树如下：例1：对子句集S={P(x)Q(y),~P(a),~Q(b)}画出相应的语义树。解：因为H={a,b}，A={P(a),Q(a),P(b),Q(b)}。从A出发便可画出S的语义树。n11n12n21n22P(a)~P(a)Q(a)~Q(a)P(b)~P(b)…Q(b)~Q(b)图2.3.2语义树例2：对子句集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)),…}n11n12n21n22P(a)~P(a)Q(a)~Q(a)P(f(a))~P(f(a))图2.3.3无限语义树………n0这是一棵无限树！在无限语义树中……如果某个分枝延伸到结点N时，I(N)已使S的某一子句的某一基例为假，就无需对N做延伸了。如果节点N的I(N)使S的某一子句的某一基例为假，而N的父辈节点不能判断这个事实，就说N是失败结点。如果S的完全语义树的每个分枝上都有一个失败结点，就说它是一棵封闭树。对于例2：S={~P(x)Q(x),P(f(y)),~Q(f(y))}。n11n12n21n22P(a)~P(a)Q(a)~Q(a)P(f(a))~P(f(a))n0×Q(f(a))n31×××××××××图2.3.4封闭语义树~Q(f(a))5）Herbrand定理定理1：子句集S是不可满足的，当且仅当对应于S的完全语义树是一棵有限的封闭语义树。定理2：S是不可满足的，当且仅当存在不可满足的S的有限基例集。课堂练习2P77二、解析题122.归结原理（消解原理）1）归结式（消解式）

设有两个子句C1=P

C1’C2=~P

C2’从中消去互补对，所得的新子句R(C1,C2)=C1’

C2’便称作子句C1,C2归结式，原来的两子句叫母体子句。没有互补对的两子句没有归结式。归结推理规则就指的是对两子句做归结，也即求归结式。例如，C1=P(A)

Q(x)R(f(x)),C2=~P(A)Q(y)R(y)C12=Q(x)

R(f(x))Q(y)R(y)常见的从母体子句求消解式的例子假言推理P~P

Q

REQ合并P

Q~P

Q RE Q

Q=Q重言式 P

Q~P

~Q REQ

~Q(P

~P)空子句(矛盾) ~PP RE NIL链环式(三段论) ~P

Q(即P

Q)~Q

R(即Q

R) RE~P

R(即P

R)上周回顾归结演绎方法子句和子句集H域、原子集、H解释H域解释的语义树海伯伦定理归结原理归结式空子句：当C1＝L和C2=~L时，归结式为空；以□指示为空的归结式，并称C＝□为空子句。显然C1和C2是一对矛盾子句——无论为子句集指派什么解释，C1和C2不可同时满足，所以空子句实际上是不可满足的子句，进而导致子句集不可满足。换言之，空子句成为用归结原理判定子句集不可满足的成功标志。2）归结式性质定理：两个子句C1和C2的归结式C是C1和C2的逻辑推论。推论：设C1和C2是子句集S中的两个子句，并以C作为它们的归结式，则通过往S中加入C而产生的扩展子句集S’与子句集S在不可满足的意义上是等价的，即：

S’的不可满足

S的不可满足3）归结推理过程

（1）命题逻辑中的归结推理过程

在命题逻辑情况下，子句中文字只是原子命题公式或取其反，由于不带变量，易于判别哪些子句对包含互补文字。例如：S＝{

P

Q,P

R,

Q,

R}

其归结演绎树如右图所示：

P

QP

RQ

R

Q

RR图2.3.5归结演绎树(2)置换与合一

置换定义：置换是形为{t1/x1,t2/x2,…,tn/xn}的一个有限集。其中，xi是变量而ti是不同于xi的项（常量、变量、函数），且xi

xj（i

j）,i,j=1,…,n。置换可作用于某个谓词上，也可作用于某个项上。作用于谓词E，就是将E中出现的变量xi均以ti代入，结果以E

表示。作用于项t，就是将t中出现的变量xi均以ti代入，结果以t

表示。

例:

={a/x,f(b)/y,u/z}

E=P(x,y,z),t=g(x,y)

那么，E

=P(a,f(b),u)

t

=g(a,f(b))对所有变量只能一次同时置换完毕!合一定义:对于表达式的集合{E1,E2,…,Ek},如果存在一个置换，使得E1

=E2

=…=EK

,则称{E1,E2,…,Ek}是可合一的,称

为{E1,E2,…,Ek}的合一置换。例:表达式集