人工智能程序设计.doc

此文档收集于网络，如有侵权，请联系网站删除第十章 人工智能程序设计 人工智能是计算机科学的分支，人工智能的实现是以计算机为工具的，分为硬件实现和软件实现两个层次。前者借助于专用的人工智能机（与通用的计算机体系结构有区别）实现人工智能；后者采用通用的计算机，由软件实现人工智能，是目前实现人工智能的主要途径。因此，计算机软件设计是人工智能的关键。为了合适和有效地表示知识和进行推理，以数值计算为主要目标的传统编程语言(诸如BASIC、FORTRAN和PASCAL等)已不能满足要求；一些专用于人工智能和智能系统的、面向任务和知识、以知识表示和逻辑推理为目标的符号和逻辑处理编程语言（LISP、PROLOG）、专用开发工具等便应运而生。10.1 符号和逻辑处理编程语言 在人工智能和智能系统的研究过程中，人们已开发出许多专用和通用程序设计语言。本节仅介绍几种通用编程语言，主要为PROLOG和LISP两种。大多数人工智能系统都是用这两种语言编写的。1.对符号和逻辑处理编程语言的要求符号和逻辑处理程序设计语言除了应具有一般程序设计语言的特性外，还必须具备下列特性或功能：(1)具有表结构形式。LISP的处理对象和基本数据结构是S表达式(即符号表达式)，具有一组用于表处理的基本函数，能对表进行比较自由的操作。PROLOG的处理对象是项。它是表的特例。由于这类语言都以结构数据作为处理对象，而且都具有对表的处理能力，因而特别适用于符号处理。(2)便于表示知识和逻辑计算。例如，PROLOG是以一阶谓词为基础的，而一阶逻辑是一种描述关系的形式语言(Formal Language)，很接近于自然语言的描述方式。智能控制(如专家控制)系统中的大量知识都是以事实和规则的形式表示的，所以用PROLOG表示知识就十分方便。(3)具有识别数据、确定控制匹配模式和进行自动演绎的能力。PROLOG具有搜索、匹配和回溯等推理机制，在编制问题求解程序时，无需编写出专用搜索算法。当用LISP编程时，不仅要对问题进行描述，而且要编写搜索算法或利用递归来完成求解。(4)能够建立框架结构，便于聚集各种知识和信息，并作为一个整体存取。(5)具有以最适合于特定任务的方式把程序与说明数据结合起来的能力。(6)具有并行处理的能力。2.现有的符号和逻辑处理编程语言 图10.1表示几种人工智能编程语言及其发展关系。图 10.1 逻辑型编程语言的分类 图中：IPL 很早期的表处理语言LISP目前应用最广泛的符号和逻辑处理语言INTERLISP新近开发的一种LISP方言，比纯粹LISP的规模大，并提供更广泛的数组能力SAIL 是ALGOL语言的变种，具有支持相关存储器等附加特性PLANNER 一种便于目标定向处理的早期语言KPL 一种能够支持复杂框架结构的语言PROLOG 一种基于规则的语言，把程序写为提供对象关系的规则。图10.1说明了上述各语言之间的相互关系。有两个起点：IPL和ALGOL。这些语言主要沿3个方向发展，即增加自动演绎功能、增加管理更复杂知识结构的机能以及提高句法灵活性等结构机能。各种编程语言在发展过程中都可能开发出多种型式和不同版本，以满足应用要求。例如，LISP语言就有原LISP、COMMON-LISP、GC-LISP；PROLOG语言就有原PROLOG、C-PROLOG、H-PROLOG、micro-PROLOG、Turbo-PROLOG和最近的Visual-PROLOG等型式。10.2 LISP语言 LISP是最早和最重要的符号处理编程语言之一，它于1958年由美国的J. McCarthy提出，并于1960年发表了他的第一篇关于LISP的论文。之后，LISP很快受到人工智能工作者的欢迎，获得广泛应用。LISP是LISt Processing(表处理)的缩写。 10.2.1 LISP的特点和数据结构1.LISP语言具有下列特点：(1)主要数据结构是表(符号表达式)，而不是作为算术运算对象的数。(2)特性表简单，便于进行表处理。(3)最主要的控制结构为递归，适于过程描述和问题求解。(4)LISP程序内外一致，全部数据均以表形式表示。(5)能够产生更复杂的函数和解释程序。(6)对大多数事物的约束发生在尽可能晚的时刻。(7)数据和过程都可以表示成表使得程序可能构成一个过程并执行这个过程。(8)大多数LISP系统可以交互方式运行，便于开发各类程序，包括交互程序。 2.数据结构在基本LISP中，仅有一种数据类型，即表结构。大多数LISP程序设计中，数据是以表或者原子为专门形式。原子：原子是LISP中最小的符号单位。原子有标识符，诸如I AM A STUDENT，3，XYZ，或者NIL等。它们没有组合部分，各种性质或属性可附加到单个原子上。一个原子最重要的属性除其名字外是值，这与变量有值同义。一些原子有标准值：原子NIL的值是NIL，T的值是T。任何数字原子，其相应的整数或浮点数是它的值。这里要注意，原子不是类型，任何原子，除常数外，可以给予任意值。 表：一个表递归地定义为括号内零个或n个元素的序列：(元素1 元素n)其中每一个元素是一个原子或是一个表。零或者空表写成()，或者NIL。NIL既是原子又是表。表的固有递归结构非常灵活，便于表示各种信号。例如：(4 6 7 9 14 17 20 24 76)一组数(-B)+(SQRT(B*B)-(4*A*C)代数表达式(I(know(that(gasoline can)explode)语法分析句子(YELLOW TABLE)断言(AND(ON A B)(ON A C)(NOT(TOUCH B C)合取子句表的数据结构：LISP表的内部表示是由称为CONS单元的基元构成。每个CONS单元是一个地址，它包括一对指针，每个指针指到一个原子，或者指到另一个CONS单元。LISP的表结构可以用来使任何数据结构模型化。例如，二维数组可以表示为由许多行组成的一张表，每行又是一张元素表。当然，对于许多目的，这种数组的实现是相当低效的。控制结构：LISP是函数式程序语言，LISP的控制结构主要是应用函数指导控制流，其中变元又可以是应用函数。这点与大多数程序设计语言的顺序控制结构不同，在那里分离的句子是一句接一句地执行。在LISP中，语句与表达式没有区别，过程与函数也没有区别。每个函数，不管是否是一个语言原语，或是由用户定义的，都以指向一个表结构的形式返回一个单值。3.变量约束及其辖域 在LISP中有3种主要的赋予符号含义的方法。这里我们将介绍其中最常用的2种：把变量约束到值上和建立函数。变量约束到值上：变量本身并无什么含义，它只是一个符号。通过这个符号可以达到这个值。变量本身只不过是具有当前值的原子名称而已。当把此名称输入到LISP去时，LISP通过告诉原子的当前值，作为回答。这个名称与原子当前具有的值之间的联系称为约束，例如可把x约束到5。每当您在程序中引用x时，LISP都理解为5。以后您可以重新把x约束到pen，这就破坏了原来的联系而代之以x和pen之间的联系，在这以后，当引用x时，LISP把它理解为pen。x值还可能是一般复杂数据。可以自由地用任意数据段约束任何一个任意选择的符号。在最简单的情况下，变量就是某个对象的名字，变量的值就是对象本身。因此，我们可以发明一些名词写入到程序中去，并对这些名词赋予含义。我们还可以改变这些含义。建立函数：我们希望能够建立函数，以对名词进行运算，产生新的名词。建立函数的方法与用值约束符号的方法相同。不过，这时的值不是事实，而是要做的事情。在完成这些之后，再把符号正确地输入到LISP中去，LISP不象以前那样理解对象，而是把对象理解为需要完成的某件事。当把有关的符号约束到含义上时，就规定了这件事。辖域：如前所述，当一个值约束一个变量时，约束一直有效，直到使用者改变它为止。当约束来自最高层即来自键盘时，这总是对的。来自函数内部所建立的约束可以是永久性的，但当函数完成时，这些约束往往就消失，变量的名字将成为无约束的。如果在整个程序执行过程中始终保持变量的约束，那么变量被认为是全程变量。如果变量的约束是建立在单个函数的内部，而且当函数约束时，约束就消失，那么这是该函数的局部变量。当然，这二者之间有各种状态：你可能希望在程序的某一点被赋值的变量在执行若干个子程序的过程中保持它的值，然后再失掉这些值。值得指出，如果局部变量已能解决问题，就不需要建立全程变量。不然的话，就会浪费计算机内存。10.2.2 LISP的基本函数 S-表达式的语法可表示为S-表达式=原子(S-表达式，S-表达式)图10.2绘出LISP所处理的各种对象间的关系：一个S-表达式(即符号表达式)可以是一张表或一个原子；一个原子可以是一个符号或一个数；一个数可为浮点数或定点数。 下面介绍LISP的一些基本函数： 图 10.2 LISP各对象间的关系 (1)CAR和CDR函数CDR是LISP的系统函数，它删除表中第一个元素，返回表的其余部分。函数CAR返回的却是表中的第一个元素，例如：(CAR (FAST COMPUTERS ARE NICE)FAST(CDR (FAST COMPUTERS ARE NICE)(COMPUTERS ARE NICE)CDR总是返回一张表。当CDR作用于一张仅有一个元素的表时，就得到一张空表，表示为()。可见，CAR和CDR使表内元素分离。(2)SET和SETQSET为赋值函数。一个原子符号的值是用SET建立起来的。SET使它的第二个自变量为第一个自变量的值，例如：(SETL(A B)(A B)即表达式的值为(A B)，其副作用使(A B)变为L的值。如果我们打入L，就会返回(A B)的结果。L(A B)SETQ和SET不同处只在于，SETQ不对第一个变量求值。SETQ比SET用得更经常。(3)APPEND，LIST和CONSAPPEND、LIST和CONS把表的元素放在一起。APPEND把所有作为自变量的表内各元素串在一起，例如：(SETL(A B)(A B)(APPEND L L)(A B A B)必须注意，APPEND只把其自变量中的所有元素放在一起，而对这些元素本身则不做任何事。LIST与APPEND不同，是用它的自变量造出一张表，每个自变量成为表中的一个元素。例如：(LIST L L L)(A B)(A B)(A B)CONS作用于一张表，在其中插入一个新的第一元素。CONS为表构造器的助记符。CONS函数可表示为：(CONS第一个元素某张表)例如：(CONS (A B)(C D)(A B)C D)(CAR(CONS A(B C )A(4)EVAL可直接用EVAL函数对一个自变量求值之后，再求一次值。例如：(SETQ A B)B(SETQ B C)C(EVAL A)C原子A第一次被求值是因为它是一个函数的未加引号的自变量。求值结果再被求值是因为该函数是EVAL。EVAL不管函数值如何，都要再求值。(5)DEFUNDEFUN使用户能够建立一些新的函数，其句法如下：(DEFUN函数名(参数1参数2参数n)过程描述)DEFUN不对其自变量求值，它仅仅查看一下自变量并建立一个函数定义，以后这个定义可以用函数名字来调用，只要函数名是被求值表的第一个元素。函数名必须是符号原子。用DEFUN时，也象其它函数一样，它也给出一个回答值。DEFUN回送的值是函数名，但这个值不是重要的结果，因为DEFUN的主要目的是建立函数定义，而不是回送一个有用的值。当用到函数的回送值时，称这个值为返回值。函数在返回值之后，它所完成的而且继续保留下来的作用称为副作用。DEFUN的副作用是给一个原子赋值。跟在函数名之后的表称为参数表。每一个参数都是可能出现在函数过程描述部分的符号原子。参数的值在一个函数被调用时由函数的一个自变量的值来确定。例如，(DEFUN F-TO-C(TEMP)(QUOTIENT (DIFFERENCE TEMP 32)1.8)F-TO-C当用F-TO-C时，它作为第一个元素出现在一张双元素的表中。第二个元素是F-TO-C的自变量。自变量被求值之后，这个值就成为函数参数的暂时值。在这个函数中，TEMP是参数，当F-T-OC求值时，自变量的值是已知的。(6)T和NIL更复杂函数的定义需要用到谓词函数。谓词返回两个特殊原子T或NIL中的一个。T和NIL两个值相当于逻辑上的真与假。常用的谓词函数有：EQ(X Y)比较两个原子X和Y，若它们相等则为真。EQUAL(X Y)比较两个S-表达式，如果它们相等则为真。这个函数更常使用。ATOM(X)如果X是个原子，则为真。NUMBERP(X)如果X的值是数字，则为真。ONEP(X)如果X的值为1，则为真。GREATERP(X Y)如果X值大于Y值，则为真。LESSP(X Y)如果X值小于Y值，则为真。NULL(X)如果X值为NIL，则为真。MEMBER(X Y)如果X的值是Y值表中的元素，则S 表达式为真。ZEROP(X)若数字自变量X为0，则取真值。MINUSP(X)若数字X为负，则取真值。一个谓词以P结尾，这个P是谓词(Predicate)的助记符。不过有些例外，如AUTO等。(7)AND、OR及NOTAND和OR可以进行组合测试。只有当所有的自变量均为非NIL时才返回非NIL。OR只要有一个自变量为非NIL时就返回非NIL。这两个谓词都可取任意多个自变量。NOT仅当其自变量为NIL时才返回T。(8)CONDCOND函数是一个条件函数，语法形式为：(COND ( .)( .)( .)函数名COND后跟着一些表。每个表包含一个测试部分和如果测试成功后的返回值部分。每一个表叫做一个子句。该函数的功能是搜索每一个子句，对每个子句的第一个元素求值，直到找到一个非NIL的值，这样该子句为成功的子句。然后在这个成功的子句中其余各个元素被求值，该子句最后一个元素的求值结果作为COND函数的值。如果没有找到成功的子句，COND返回NIL。当成功的子句只含有一个元素，那么这个元素本身的值就是返回值，即测试元素与结果元素可以是同一个。(9)PROGPROG是个通用函数，它能设立新的变量，提供清晰的迭代过程。PROG也可以只用于把几个依次执行的S-表达式组合起来，成为一个序列。PROG不对它的第一个自变量求值，第一个自变量必须是一个原子表或空表。一旦遇到函数RETURN，则PROG立即终止。PROG1能返回第一个自变量的值。(10)GET和PUTPROPGET函数用于检索特征值，而补函数PUTPROP用于存放特征值或替代特征值。(11)LAMBDALAMBDA用于定义匿名函数。为了避免无用函数名的激增，对于局部使用的函数可去掉函数名，采用新的函数定义方法，称为-表达式，它用原子LAMBDA代替DEFUN。(12)READ和PRINTREAD和PRINT函数用于进行对话。PRINT函数对它的单个变量求值，并把其值打印在新的一行上。PRINT函数回答T作为它的值。例如:(PRINTEXAMPLE)EXAMPLET当遇到(READ)时，LISP程序暂停并等待用户在键盘上打入一个S-表达式。该表达式不必求值便成为(READ)的值。例如，在下例中当用户遇到(READ)函数后打入EXAMPLE(跟着打入一空格)：(READ)EXAMPLEEXAMPLE以上仅介绍LISP的基本函数和个别特别重要的函数。下面将介绍LISP的递归和迭代。其它函数请读者参阅有关参考文献。10.2.3 递归和迭代函数通过简化问题求解过程，将被简化的问题再交给一个或多个与自己完全一样的函数，从而让程序解决此问题。这就叫做递归，它是重复地做某件事情的一种方法。1.递归递归是重复完成相同工作的有效方法。SHORTEN函数所用的是递归，其中包括一行LISP码，这行码使SHORTEN在它自身内部又发生一次。换句话说，SHORTEN执行中的一部分涉及再次执行SHORTEN，例如：(DEFUN SHORTEN(l)(COND(NULL l) NIL)(T (PRINT l)(SHORTEN (CDR l)当程序运行，LISP求值器到达箭头所示的那行末尾时，已经建立了这个函数的一种新版本。这种新版本的自变量不同于输入数据。当求值器在新的SHORTEN中达到相同点时，同样的事情再次发生。如此重复，直到某一点，最后一行建立一个以空表作为自变量的SHORTEN的新版本。在最后这个循环中，不能达到箭头所指这点，因为COND把求值器引向NIL或什么也不做的指令。为便于说明，我们试对这个函数输入一个很短的表：(SETQ ANIMALS(DOG CAT MOUSE)当输入(SHORTEN ANIMALS) 时所发生的过程如图10.3所示。 图 10.3 递归过程示例之一在数据已经减少为NIL的循环中，机器不需要做什么。下一步机器所要做的工作是结束所有那些被部分地完成了的SHORTEN版本，并且回到最高层。为了使这个过程更清楚一些，我们把这个函数改写为：(DEFUN SHORTEN(l)(COND(NULLl)NIL)(T(SHORTEN(CDR l)(PRINT l)在这种情况下，1不是在每个向前的循环中被打印，而是留到CONS已最终结束递归后再打印。所以，首先打印只留下一个元素的那个版本的1，因为当1中只留下一个元素时，1的CDR是NIL。这样，在下一个被打印的1版本中有两个元素，如此继续，直到整个表为止。整个过程如图10.4所示。图 10.4 递归过程示例之二2.迭代另一种重复地做相同事情的方法要简单得多，称为迭代。迭代函数包含一个循环，不同于递归。迭代只执行函数的一种版本，并且不涉及展开程序。迭代只是简单的循环，它不同于递归的一个方面是，递归发生在逐渐加深的层次上，而迭代始终在同一层中，迭代循环步骤如下： (1)约束某些变量。(2)测试变量以检查出口(停止)条件是否适用。若适用，则进行(3)。(3)以某种方法改变变量的值。 (4)返回(2)。在不同的LISP方言中，用于实现迭代的指令各不相同，功能也有所区别，以下是一种基本的PROG循环的例子。 (PROGVARSTAG停止试验(主体)(GO TAG)其中主体可为所需的任何LISP指令序列，但其中至少有一条是用于改变某个变量的值，而且这个变量将在停止试验中被测试。例如： (DEFUN SHORTEN(l)(PROG()TAG(COND (NULL l)(RETURN NIL)(T(PRINT l)(SETQ l (CDR l)(GO TAG)其中COND的第一个子句是停止试验，T子句是PROG指令的主体。在打印了l表的当前值之后，不是重新调用具有被截短的自变量SHORTEN，而是把l重新置为它自己的CDR，然后重复TAG和GO TAG这两个指令之间的程序。这样的循环一直继续到试验成功为止，即到l是NIL止。这时，RETURN指令停止程序，可RETURN所希望的任何LISP表达式，这些表达式中最后的值就成为PROG的最后的值。在前面的对循环的说明中的第一条指出，约束某些局部变量；约束的含义是对这些变量赋值。在PROG指令中，任何变量如果其名字(符号)被直接放在PROG后面的括号内，那么这些变量就被约束(置)为NIL。但SHORTEN不需要任何这样的变量，所以在此例子中，上述括号形成一个空表。10.2.4 LISP编程举例前面就LISP语言的基本内容作了介绍，下面将通过一个LISP程序设计的实例，简单说明程序设计的基本方法和LISP程序的基本结构。我们曾经提到LISP程序的通常形式是一串函数定义，后面跟着一串函数调用。LISP程序的大致格式为： (DEFINE(函数名)(形式参数表)(函数定义体)(函数名)(形式参数表)(函数定义体)(函数名)(形式参数表)(函数定义体)(函数名 实在参数表)(函数名 实在参数表)(函数名 实在参数表)LISP程序设计的一般步骤如下： (1)将问题用递归的表处理方式表示，即问题的概念化。(2)根据问题求解的要求，设计问题求解的搜索推理过程。(3)根据所设计的求解过程，定义所需要的工作函数。(4)根据求解过程，给出函数调用的顺序。(5)根据问题求解的目标和解的评价准则，给出程序结束的标志。实例-梵塔问题：如图10.5所示放置3根柱子，其中一根从上往下按由小到大顺序串有若干个圆盘，要求通过3根柱子移动圆盘。若规定每次只能移动1片，且不许大盘放在小盘之上，最后要将圆盘从一根柱子移动到另一根柱子上。 初始状态目标状态1目标状态2图 10.5 梵塔问题1.梵塔问题的描述设3根柱子为A、B、C，n个圆盘从小到大为1，2，n(n为有限正整数)。初始状态：圆盘DISK=(1,2,，n)全在柱子A上。目标状态圆盘全在柱子B上。移动规则为每次只移动1个圆盘，但大盘不能放在小盘上。2.问题求解步骤用递归算法求解梵塔问题的步骤如下： (1)先将A柱上n个圆盘中的上面(n-1)个圆盘移至缓冲的C柱上。(2)再将最大的圆盘n从A柱移到B柱。(3)逐步将圆盘(1，2，n-1)从C柱移到B柱。实际上这是对梵塔问题进行降阶处理，以递归方式求解。3.定义函数定义一个TRANSFER函数，以实现将n个圆盘从X柱(开始为A柱)移到Y柱(开始为B柱)并利用Z柱(开始为C柱)过渡。定义一个MOVE函数，其功能为移动一个圆盘，并打印输出。梵塔问题的LISP程序及运行结果如下： (DEFINE HANOI(N)(TRANSFER ABC N)(DEFINE MOVE(X Y)(PRINT(LISTMOVE(CAR(EVAL X)FROM XTO Y)(COND(NULL(EVAL X)(PRINT(LIST XEMPTY)；柱子无圆盘(OR(NULL(EVAL Y)；柱子为空(GREATERP(CAR(EVAL Y)(CAR(EVAL X)；柱子上有一比移动圆盘大的圆盘(SET Y(CONS(CAR(EVAL X)(EVAL Y)；圆盘加到新柱子上(SET X(CDR(EVAL X)；圆盘从老柱子上移走(T(PRINT(LIST CANNOTMOVE；非法移动(CAR(EVAL X)ONTO(CAR(EVAL Y)(LIST(LISTMOVE(CAR(EVAL Y)FROM XTO Y)(DEFINE TRANSFER(X Y Z NUMBER)(COND(EQN NUMBER 1)(MOVE X Y)；移动一片(T(APPEND (TRANSFER X；从X移到Z上ZY；利用Y作临时存放柱(SUB1 NUMBER)；(n-1)个圆盘(MOVE X Y)；搬走最下面的一片(TRANSFER ZYX(SUB1 NUMBER)；(n-1)个圆盘将n个圆盘从A柱搬到B柱，只需调用函数HANOI，并以所需移动圆盘数为实参。如搬动三个圆盘从A柱到B柱：(SETQ(1 2 3)B NIL C NIL)(HANOI 3)运行后程序将打印出下面的结果： MOVE 1 FROM A TO BMOVE 2 FROM A TO CMOVE 1 FROM B TO CMOVE 3 FROM A TO BMOVE 1 FROM C TO AMOVE 2 FROM C TO BMOVE 1 FROM A TO B 10.3 PROLOG语言 PROLOG语言是法国的柯尔迈伦(Alain Colmerauer)和他在马赛大学的助手于1962年发明的一种高效率逻辑型语言。PROLOG的主要基础就是逻辑程序编制的概念(PROgramming in LOGig)，本身就是一个演绎推理机，具有表处理功能，通过合一、置换、消解、回溯和匹配等机制来求解问题。PROLOG已被应用于许多符号运算研究领域。 10.3.1 语法与数据结构用PROLOG语言编程包括规定操作对象以及关系的某些事实，规定操作对象及关系的规则，询问操作对象以及关系的问题。1.项的定义PROLOG的操作对象是项，所有程序和数据均由项表示。项的定义如下： =(，)原子用来标识事物的名字及谓词、函数名，变量则用来表示暂时不不能命名，或不需命名的事物，以及未知的数字。为了区别两者，有的PROLOG系统要求变量一律用大写字母开头。2.子句PROLOG中，称一个语句为子句(Horn)。语句分事实、规则和问题3种形式。(1)事实事实的句型为P1，是P1-的缩写。P1的成立不依赖于别的目标，P1恒为真。(2)规则规则的句型为P1-P2，P3，Pn.其中，- 的含义为蕴涵于，等价于一阶谓词逻辑中的，而，(即逗号)表示合取(即AND逻辑)。此句型的语义表示：如果P2P3Pn为真那么P1为真(3)问题问题又叫目标子句，其句型为：? -P1，P2，Pn其中P1，P2，Pn均为谓词。问题的含义表示：P1P2Pn为真吗?3.表结构 PROLOG的基本数据结构也是表。表是有若干元素的有序序列，表中元素可为常量、变量、项，也可以为表。PROLOG中采用一对方括号把表元素括起来。每个元素间用逗号或空格分开。例如： m,n,d,fthe,robot,moves,down在PROLOG内引入符号，如XY表示一个以X为首，以Y为尾的表。的引入省去了LISP语句中的CAR、CDR和CONS运算。例如表m,n,d,f中，表头为m，表尾为n,d,f。10.3.2 PROLOG程序设计原理PROLOG的程序分为两部分，即前提部分和问题部分。前提部分是所有规则和事实；问题部分为一目标子句序列。PROLOG程序的执行过程就是定理证明过程。如果目标子句为：? -Q1，Q2，Qn.其执行过程从左到右检测目标Q1，Q2，Qn。1.匹配(matching)PROLOG对目标的处理原则是： (1)设法满足一个目标从事实和规则的顶部开始搜索，有两种可能：(a)找到一个与之匹配的事实或规则的头。这时，目标获得匹配。如果匹配的是事实，则例示已匹配的且未曾例示过的变量。如果是与一条规则的头相匹配，将首先满足此规则。这个目标匹配成功，PROLOG设法满足规则右边的目标。(b)找不到相匹配的事实或规则的头，则目标失败。此时，PROLOG设法重新满足这个目标左边的第一个目标，即返回前一目标的含义。(2)设法重新满足这一目标在这种情况下，首先必须把先前满足这个目标时例示的所有变量恢复成原来的未示例状态，即忘记先前由此目标所做过的工作。其次，PROLOG从上次匹配的事实或规则处开始查寻。现在这种新的回溯目标，或者成功，或者失败，即或到(1)中之(a)，或者到(1)中之(b)。由此可见，PROLOG程序的执行是通过合一和回溯实现的。2.合一(unification)在PROLOG中，两子句的合一是指其谓词名和参数个数相同，且对应参数项可合一。未受囿的自由变量可与自身或任何不含该变量的项合一，并把变量受囿为与其合一的项。如果非受囿变量相互合一，则称为其变量共享。一组共享变量，如果其中一个变量受囿为某一项，则其它变量也自动地受囿为该项，常量只能与自身或变量合一。一个复合项与另一个复合项的函数符和参数数目都相同，且对应的参数项相互合一，则这两个复合项可合一。在PROLOG中，一个目标与一个事实合一是指目标子句与事实子句合一。一个目标与一个规则合一是指目标子句与规则头部合一，其合一原则如下：(1)对事实子句(或规则)中的变量进行换名，使其不与目标中的变量同名，对变量受囿表进行初始化。(2)检查目标子句与事实子句(或规则)的下一个相异项是否不存在；若不存在，则结束合一过程，合一成功，返回合一过程中产生的变量受囿表；若存在，则转(3)。(3)根据合一原则，判断目标子句与事实子句(或规则)的下一个相异项是否可合一。若可合一，就把这两项加入到变量受囿表中，并对目标子句和事实子句(或规则)中的有关变量进行置换，然后转(2)；若不可合一，则结束合一过程，释放变量受囿表，返回不可合一信息。3.回溯(backtracking)PROLOG中的回溯过程如下： (1)在系统执行问题语句时，先把问题语句作为初始目标，并置其为激发状态，开始执行该目标。(2)系统处于激发状态时，首先为该目标保存必要的回溯信息，然后判断它是否是单一子句组成的目标。如果是就转(3)；否则就依次从左到右求解激发目标的各个子目标。当所有的子目标都得到满足时，激发目标就成功返回。否则，激发目标就失败返回。(3)系统执行一个由单一子句组成的激发目标时，就从事实规则库中取出与激发目标子句句首谓词符号相同的子句子集，从该子句子集的顶部开始查找可与激发目标合一的子句。可分为五种情况处理：(a)找到与激发目标合一的事实，对它们进行合一，并将合一结果通知激发目标的父辈目标，把父目标中的有关变量进行置换，并通过父辈目标把激发目标的兄弟目标中的有关变量进行置换。(b)如果找到与激发目标合一的规则，就先把规则中受囿过的变量置换为其受囿值，然后把规则中作为激发目标的子目标进行求解。如果子目标成功返回，就把执行完子目标后激发目标中变量的受囿情况通知激发目标之父目标，对父目标中的有关变量进行置换，并通过父目标，把激发目标的兄弟目标中的有关变量进行置换，如果子目标执行失败，系统就从下一条事实或规则开始查找可与激发目标合一的事实或规则，重新求解该激发目标。(c)如果系统找不到可与激发目标合一的事实或规则，该激发目标执行失败，系统收回该激发目标所占用的内存空间，并回溯到激发目标被执行前的最后一个成功目标，对其进行重新求解。目标失败返回时，系统自动撤消它。(d)如果所有目标都得到满足，那么问题就获得解决，系统把初始目标中变量的受囿情况作为结果输出。(e)如果系统找不到解或找不到新的解，即系统已回溯到初始目标，且事实规则库中不再有另外的可与初始目标合一的事实或规则，那么系统就回答NO，并收回求解该问题时所占用的全部空间，开始执行下一语句。 10.3.3 PROLOG编程举例PROLOG已在专家系统、数据库和知识库系统、定理证明系统、决策支持系统、过程智能控制系统以及机器人规划与控制系统等方面得到成功应用。下面仍以梵塔问题为例，看看如何用PROLOG程序实现梵塔问题求解。实例-梵塔问题：梵塔问题我们已在上面讨论LISP语言中加以举例，这里考虑的是怎样用PROLOG程序实现梵塔问题的求解。 hanoi(N):-move(N,left,centre,right)move(0,_，_，_，)：-! .move(N,A,B,C):- M is N-1, move(M，A，C，B)，inform(A,B),move(M,C,B,A)inform(X,Y):- write(move,a,disc,from,the,X,pole,to,the,Y,pole),n1.?- honoi(3).move a disc from the A pole to the B polemove a disc from the A pole to the C polemove a disc from the B pole to the C polemove a disc from the A pole to the B polemove a disc from the C pole to the A polemove a disc from the C pole to the B polemove a disc from the A pole to the B pole本例中谓词honoi只有1个变元，表示如果有N个圆盘在A柱上，则hanoi将输出N个圆盘由A柱移到B柱的移动轨迹序列；谓词move有4个变元，其中第一个为要移动的盘的个数，第二、三、四变元分别为源柱子、目标柱子、临时存放柱；谓词inform利用write来输出移动的轨迹。10.4 专用开发工具 在人工智能系统开发与应用研究中，越来越多地使用各种专用开发工具。我们在第七章第五节所讨论的专家系统开发工具就是这方面的有代表性的开发工具，在此不予重述。除了专家系统开发工具之外，还有其它一些开发工具，如神经网络系统开发工具、模糊系统开发工具以及视觉和听觉系统开发工具等。感兴趣者请查寻有关开发工具的版本。10.5 人工智能机 设计专用人工智能机的思想始于1960年，其目标在于使用计算机直接实现信息处理语言，使它比常