(1.1.1.20)--第2章 人工智能程序设计语言.ppt

《(1.1.1.20)--第2章 人工智能程序设计语言.ppt》由会员分享，可在线阅读，更多相关《(1.1.1.20)--第2章 人工智能程序设计语言.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第2章章 人工智能程序设计语言人工智能程序设计语言 第第2章章 人工智能程序设计语言人工智能程序设计语言 2.1 综述综述2.2 函数型程序设计语言函数型程序设计语言LISP 2.3 逻辑型程序设计语言逻辑型程序设计语言PROLOG 2.4 Turbo PROLOG程序设计程序设计第第2章章 人工智能程序设计语言人工智能程序设计语言 2.1 综述综述2.1.1函数型语言LISP是一种函数型程序设计语言。LISP程序由一组函数组成，程序的执行过程就是一系列的函数调用和求值过程。20世纪70年代:J.Backus还提出了一种纯函数型程序设计语言FP。但仅限于理论研究，实现上还存在一定困难。第第2

2、章章 人工智能程序设计语言人工智能程序设计语言 2.1.2逻辑型语言逻辑型程序设计语言起源于PROLOGPROLOG,ProgramminginLogic。PROLOG语言由法国马塞大学的Colmerauer和它的研究小组于1972年研制成功，在欧洲得到进一步发展。1981年日本宣布要以PROLOG作为他们正在研制的新一代计算机智能计算机的核心语言，更使PROLOG举世瞩目，迅速风靡世界。第第2章章 人工智能程序设计语言人工智能程序设计语言 PROLOG语言以Horn子句逻辑为基础，是目前最具代表性的一种逻辑程序设计语言。早期PROLOG版本都是解释型的，1986年美国的Borland公司推出

3、了编译型:TurboPROLOG，很快在PC机上流行。运行在Windows环境下的可视化编程语言VisualPROLOG也已面世（5.2/6.0v)。（下载地址：www.visual-)第第2章章 人工智能程序设计语言人工智能程序设计语言 2.1.3面向对象语言20世纪80年代以来，面OOP发展迅速，日渐成熟，成为主流程序设计方法。面向对象程序以信息隐蔽、封装、继承、多态、消息传递等一系列优良机制改善了软件的复杂性、模块性、重用性和可维护性，有望从根本上解决软件的生产效率问题。另一方面，由于面向对象程序设计的类、对象、继承等概念，与AI的知识表示理论与方法和知识库技术产生了天然的联系。因此OO

4、P语言也成为一种人工智能程序设计语言特别是知识工程、专家系统程序设计。面向对象程序设计语言也种类繁多，已发展成为一个大家族。其中最纯正、最具面向对象风格的语言当推Smalltalk，而最流行的OOP语言是C+、Java。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.1.4混合型语言以上三种语言都各有所长，但也都有其不足之处。为了扬长避短，于是便出现了基于这三种语言的混合型语言。1.函数型与逻辑型相结合的语言函数型与逻辑型语言的结合方式有耦合型和统一型两类。统一型又可分为具有归结语义的函数型语言和集成式语言两个子类。2.函数型与面向对象相结合的语言在LISP语言的基础上再扩充面向对象

5、机制而产生的语言，称为函数型的面向对象程序设计语言(亦称为面向对象的LISP)。3.逻辑型与面向对象相结合的语言第第2章章 人工智能程序设计语言人工智能程序设计语言 2.3 逻辑型程序设计语言逻辑型程序设计语言PROLOG 2.3.1PROLOG的语句PROLOG语言只有三种语句，分别称为事实、规则和问题。1.事实(fact)格式().其中谓词名是以小写英文字母打头的字母、数字、下划线等组成的字符串，项表是以逗号隔开的项序列。第第2章章 人工智能程序设计语言人工智能程序设计语言 PROLOG中的项包括:由常量或变量表示的简单对象;函数、结构、表事实的形式是一个原子谓词公式。例如：student

6、(john).like(mary,music).事实的功能：一般表示对象的性质或关系。特殊的，一个事实也可以只有谓词名而无参量。例如：abc.repeat.也是允许的。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.规则(rule)格式():-(),().其中“:-”号表示“if”（也可以直接写为if）。左部的谓词是规则的结论（亦称为头），右部的谓词是规则的前提（亦称为体），表示零次或多次重复，逗号表示and(逻辑与),即规则的形式是一个逻辑蕴含式。例如：bird(X):-animal(X),has(X,feather).grandfather(X,Y):-father(X,Z),f

7、ather(Z,Y).功能：一般表示对象间的因果关系、蕴含关系或对应关系。作为特殊情形，规则中的谓词也可以只有谓词名而无参量。例如：run:-start,step1(X),step2(X),end.第第2章章 人工智能程序设计语言人工智能程序设计语言 3.问题(question)格式?-(),().例如：?-student(john).?-like(mary,X).功能：问题表示用户的询问，它就是程序运行的目标。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.3.2PROLOG程序完整的PROLOG程序一般由一组事实、规则和问题组成。问题是程序执行的起点，称为程序的目标。例如：lik

8、es(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,reading),likes(X,music).friend(john,X):-likes(X,sports),likes(X,music).?-friend(john,Y).该程序中有四条事实、两条规则和一个问题。其中事实、规则和问题都分行书写。规则和事实可连续排列在一起，其顺序可随意安排，但同一谓词名的事实或规则必须集中排列在一起。问题不能与规则及事实排在一起，它作为程序的目标要么单独列出，要么在程序运

9、行时临时给出。第第2章章 人工智能程序设计语言人工智能程序设计语言 PROLOG程序中的目标可以变化，也可以含有多个语句(上例中只有一个)。如果有多个语句，则这些语句称为子目标。例如对上面的程序，其问题也可以是?-likes(mary,X).或?-likes(mary,music).或?-friend(X,Y).或?-likes(bell,sports),likes(mary,music),friend(john,X).对于不同的问题，程序运行的结果一般是不一样的。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.3.3PROLOG程序的运行机理PROLOG程序作为基于Horn子句的逻

10、辑程序，其运行机理基于归结原理的演绎推理（归结原理将在第3章介绍）。PROLOG程序运行是从目标出发，并不断进行匹配、合一、归结，有时还要回溯，直到目标被完全满足或不能满足时为止。什么是匹配、合一和回溯？第第2章章 人工智能程序设计语言人工智能程序设计语言 1.自由变量与约束变量PROLOG中称无值的变量为自由变量，有值的变量为约束变量。一个变量取了某值就说该变量约束于某值，或者说该变量被某值所约束，或者说该变量被某值实例化了。2.匹配合一两个谓词可匹配合一，是指两个谓词的名相同，参量项的个数相同，参量类型对应相同，并且对应参量项还满足下列条件之一：(1)如果两个都是常量，则必须完全相同。(2

11、)如果两个都是约束变量，则两个约束值必须相同。(3)如果其中一个是常量，一个是约束变量，则约束值与常量必须相同。(4)至少有一个是自由变量第第2章章 人工智能程序设计语言人工智能程序设计语言 例如：下面的两个谓词pre1(ob1,ob2,Z)pre1(ob1,X,Y)只有当变量X被约束为“ob2”，且Y、Z的约束值相同或者至少有一个是自由变量时，它们才是匹配合一的。3.回溯所谓回溯是在程序运行期间，当某一个子目标不能满足（即谓词匹配失败）时，控制就返回到前一个已经满足的子目标（如果存在的话），并撤消其有关变量的约束值，然后再使其重新满足。成功后，再继续满足原子目标。如果失败的子目标前再无子目标

12、，则控制就返回到该子目标的上一级目标（即该子目标谓词所在规则的头部）使它重新匹配。回溯是PROLOG的一个重要机制。第第2章章 人工智能程序设计语言人工智能程序设计语言 仍以上面的程序为例。设所给的询问是likes(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,reading),likes(X,music).friend(john,X):-likes(X,sports),likes(X,music).?-friend(john,Y)./john和谁是朋友?则

13、求解目标为friend(john,Y).这时，系统对程序进行扫描，寻找能与目标谓词匹配合一的事实或规则头部。显然，程序中前面的四条事实均不能与目标匹配。注意第五、六个语句的左端程序运行结果：Y=mary第第2章章 人工智能程序设计语言人工智能程序设计语言 上述程序的运行是一个通过推理实现的求值过程。我们也可以使它变为证明过程。例如，把上述程序中的询问改为?-friend(john,mary)则系统回答:yes若将询问改为：?-friend(john,smith)则系统回答:no第第2章章 人工智能程序设计语言人工智能程序设计语言 PROLOG程序的执行过程是一个（归结）演绎推理过程。其特点是：

14、推理方式为反向推理；控制策略是深度优先，且有回溯机制。具体实现方法是：匹配子句的顺序是自上而下；子目标选择顺序是从左向右；归结后产生的新子目标总是插入被消去的目标处（即目标队列的左部）。PROLOG的这种归结演绎方法被称为SLD(LinearresolutionwithSelectionfunctionforDefiniteClause)归结，或SLD反驳-消解法。SLD归结就是PROLOG程序的运行机理，它也就是所谓的PROLOG语言的过程性语义。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.4 Turbo PROLOG程序设计程序设计2.4.1TurboPROLOG的程序结构一

15、个完整的TurboPROLOG(2.0版)程序一般包括常量段、领域段、数据库段、谓词段、目标段和子句段等六个部分。各段以其相应的关键字constants、domains、database、predicates、goal和clauses开头加以标识。在程序的首部还可以设置指示编译程序执行特定任务的编译指令；在程序的任何位置都可设置注解。第第2章章 人工智能程序设计语言人工智能程序设计语言 一个完整的TurboPROLOG(2.0v)程序的结构如下/*/constantsdomainsdatabasepredicatesgoalclauses第第2章章 人工智能程序设计语言人工智能程序设计语言 一

16、个程序不一定要包括上述所有段，但一个程序至少要有一个predicates段、clauses段和goal段。在大多数情形中，需要一个domains段，以说明表、复合结构及用户自定义的域名。如若省略goal段，则可在程序运行时临时给出，但这仅当在开发环境中运行程序时方可给出。若要生成一个独立的可执行文件，则在程序中必须包含goal段。一个程序只能有一个goal段。第第2章章 人工智能程序设计语言人工智能程序设计语言 例2.3/*例子程序-1*/DOMAINSname=symbolPREDICATESlikes(name,name).friend(name,name)GOALfriend(john,

17、Y),write(Y=,Y).CLAUSESlikes(bell,sports).likes(mary,music).likes(mary,sports).likes(jane,smith).friend(john,X):-likes(X,sports),likes(X,music).friend(john,X):-likes(X,reading),likes(X,music).第第2章章 人工智能程序设计语言人工智能程序设计语言 表2.1TurboPROLOG的标准领域第第2章章 人工智能程序设计语言人工智能程序设计语言 谓词段该段说明程序中用到的谓词的名和参量项的名(但TurboPROLO

18、G的内部谓词无须说明)。子句段该段是TurboPROLOG程序的核心，程序中的所有事实和规则就放在这里，系统在试图满足程序的目标时就对它们进行操作。目目标标段段该段是放置程序目标的地方。目标段可以只有一个目标谓词，例如上面的例子中就只有一个目标谓词；也可以含有多个目标谓词，如：goalreadint(X),Y=X+3,write(Y=,Y).就有三个目标谓词。这种目标称为复合目标。称程序目标段中的目标为内部目标，而称在程序运行时临时给出的目标为外部目标。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.4.2TurboPROLOG的数据与表达式1.领域1)标准领域TurboPROLOG

19、中不定义变量的类型，只说明谓词中各个项的取值域。2)结构结构也称复合对象，它是TurboPROLOG谓词中的一种特殊的参量项（类似于谓词逻辑中的函数）。第第2章章 人工智能程序设计语言人工智能程序设计语言 结构的一般形式为()其中函子及参量的标识符与谓词相同。注意，这意味着结构中还可包含结构。所以，复合对象可表达树形数据结构。例如:likes(Tom,sports(football,basketball,table-tennis).person(张华,student(西安石油学院),address(中国,陕西,西安).reading(王宏,book(人工智能技术基础教程,电子科技大学出版社).

20、friend(father(Li),father(Zhao).第第2章章 人工智能程序设计语言人工智能程序设计语言 复合对象在程序中可以分层进行。例如：likes(Tom,sports(football,basketball,table-tennis).在程序中可说明如下：domainsname=symbolsy=symbolsp=sports(sy,sy,sy)predicateslikes(name,sp)第第2章章 人工智能程序设计语言人工智能程序设计语言 3)表表的一般形式是x1,x2,xn其中xi(i=1,2,n)为PROLOG的项，一般要求同一个表的元素必须属于同一领域。不含任何元

21、素的表称为空表，记为。例如：1,2,3apple,orange,banana,grape,canePROLOG,MAENS,PROGRAMMING,inlogica,b,c,d,e表的最大特点是其元素个数可在程序运行期间动态变化。第第2章章 人工智能程序设计语言人工智能程序设计语言 表的元素是结构或表时，其元素可以属于不同领域。例如：name(LiMing),age(20),sex(male),address(xian)1,2,3,4,5,6,7都是合法的表。后一个例子说明，表也可以嵌套。实际上，表是一种特殊的结构。它是递归结构的另一种表达形式。这个结构的函数名取决于具体的PROLOG版本。这

22、里用一个圆点来表示。例如：结构形式表形式(a,)a(a,(b,)a,b(a,(b,(c,)a,b,c第第2章章 人工智能程序设计语言人工智能程序设计语言 表的说明:在其组成元素说明符后加一个星号*：domainslists=string*predicatespl(lists)说明谓词pl中的项lists是一个由串string组成的表。由结构组成的表，分三步说明。例如对于谓词p中的表p(name(Liming),age(20)则需这样说明:domainsrec=seg*seg=name(string);age(integer)predicatesp(rec)第第2章章 人工智能程序设计语言人工智

23、能程序设计语言 2.常量与变量TurboPROLOG的常量有整数、实数、字符、串、符号、结构、表和文件这八种数据类型。同理，TurboPROLOG的变量也就有这八种取值。变量名要求必须是以大写字母或下划线开头的字母、数字和下划线序列，或者只有一个下划线。这种变量称为无名变量。第第2章章 人工智能程序设计语言人工智能程序设计语言 3.算术表达式TurboPROLOG提供基本算术运算：+、-、*、/、mod。这五种运算的顺序为：*、/、mod优先于+、-。同级从左到右按顺序运算，括号优先。算术表达式的形式与数学中的形式基本一样。例如：PROLOG中的算术表达式X+Y*ZA*B-C/DUmodV即T

24、urboPROLOG中算术表达式采用通常数学中使用的中缀形式。这种算术表达式为PROLOG的一种异体结构，若以PROLOG的结构形式来表示，则它们应为+(X,*(Y,Z)-(*(A,B),/(C,D)mod(U,V)所以，运算符+、-、*、/和mod实际也就是PROLOG内部定义好了的函数符第第2章章 人工智能程序设计语言人工智能程序设计语言 如果一个算术表达式中的变元全部被实例化（即被约束）的话，则这个算术表达式的值就会被求出。用一个算术表达式的值实例化一个变量的方法是用谓词“is”或“=”来实现。例如：YisX+5或Y=X+5可以看出，这里对变量Y的实例化方法类似于其他高级程序语言中的“赋

25、值”，但又不同于赋值。例如，在PROLOG中下面的式子是错误的:X=X+1第第2章章 人工智能程序设计语言人工智能程序设计语言 4.关系表达式TurboPROLOG提供了六种常用的关系运算：,=,关系表达式的形式和数学中的也基本一样，例如：X+1=YXYTurboPROLOG中的关系式也用中缀形式。当然，这种关系式为TurboPROLOG中的异体原子。若按TurboPROLOG中的原子形式来表示，则上面的两个例子为=(X+1,Y)和(X,Y)第第2章章 人工智能程序设计语言人工智能程序设计语言 即是说，TurboPROLOG中的关系式也用中缀形式。当然，这种关系式为TurboPROLOG中的异

26、体原子。若按TurboPROLOG中的原子形式来表示，则上面的两个例子为=(X+1,Y)(X,Y)又如：brother(Name1,Name2):-person(Name1,man,Age1),person(Name2,man,Age2),mother(Z,Name1),mother(Z,Name2),Age1Age2.第第2章章 人工智能程序设计语言人工智能程序设计语言 2.4.3输入与输出readln(X)功能：从键盘上读取一个字符串，然后约束给变量X。readint(X)。功能：从键盘上读取一个整数，然后约束给变量X，如果键盘上打入的不是整数则该谓词失败。readreal(X)。功能：从

27、键盘上读取一个实数，然后约束给变量X，如果键盘上打入的不是实数则该谓词失败。readchar(X)。功能：从键盘上读取一个字符，然后约束给变量X，如果键盘上打入的不是单个字符，则该谓词失败。write(X1,X2,Xn)。功能：输出项Xi(i=1,2,n)的值，当有某个Xi未实例化时，该谓词失败，其中的Xi可以是变量，也可以是字符串或数字。第第2章章 人工智能程序设计语言人工智能程序设计语言 换行谓词nl：使后面的输出(如果有的话)另起一行。，利用write的输出项“n”也同样可起换行作用。例如：write(name),nl,write(age)与write(name,n,age)效果完全一样

28、。第第2章章 人工智能程序设计语言人工智能程序设计语言 例2.4一个简单的学生成绩数据库查询程序。PREDICATESstudent(integer,string,real)gradeGOALgrade.CLAUSESstudent(1,张三,90.2).student(2,李四,95.5).student(3,王五,96.4).grade:-write(请输入姓名:),readln(Name),student(-,Name,Score),nl,write(Name,的成绩是,Score).grade:-write(“对不起，找不到这个学生!”).程序运行时的屏幕显示:请输入姓名：王五王五的成

29、绩是96.4第第2章章 人工智能程序设计语言人工智能程序设计语言 2.4.4分支与循环PROLOG中并无专门的分支和循环语句1.分支实现对于通常的IF-THEN-ELSE分支结构，可用两条同头的并列规则实现。例如Br:-x0,x=1.Br:-x=0.对于多分支，可以用多条规则实现。例如：Br:-x0,x=1.Br:-x=0,x=0.Br:-x0,x=-1.第第2章章 人工智能程序设计语言人工智能程序设计语言 2.循环例：记数循环，它使得write语句重复执行了三次，而打印输出了三个学生的记录。student(1,张三,90.2).student(2,李四,95.5).student(3,王五,

30、96.4).print:-student(Number,Name,Score),write(Number,Name,Score),nl,Number=3.第第2章章 人工智能程序设计语言人工智能程序设计语言 不计数DO循环。student(1,张三,90.2).student(2,李四,95.5).student(3,王五,96.4).print:-student(Number,Name,Score),write(Number,Name,Score),nl,fail.print:-.这个程序段中的fail是一个内部谓词，它的语义是恒失败。这个程序段与上面的程序段的差别仅在于把原来用计数器（或标

31、记数）循环控制语句变成了恒失败谓词fail，另外再增加了一个print语句。增加这个语句的目的是为程序设置一个出口。因为fail是恒失败，下面若无出口的话，将引起print本身的失败。进而又会导致程序中的连锁失败。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.4.5动态数据库动态数据库就是在内存中实现的动态数据结构。它由事实组成，程序可以对它操作，所以在程序运行期间它可以动态变化。TurboPROLOG提供了三个动态数据库操作谓词:asserta().把fact插入当前动态数据库中的同名谓词的事实之前；assertz().把fact插入当前动态数据库中的同名谓词的事实之后；retr

32、act().把fact从当前动态数据库中删除。第第2章章 人工智能程序设计语言人工智能程序设计语言 例如语句asserta(student(20,李明,90.5).将在内存的谓词名为student的事实前插入一个新事实：student(20,李明,90.5)如果内存中还没有这样的事实，则它就是第一个。又如语句retract(student(20,-,-).将从内存的动态数据库中的删除事实student(20,-,-)它可解释为学号为20的学生的记录。注意，这里用了无名变量-。第第2章章 人工智能程序设计语言人工智能程序设计语言 可以看出，PROLOG提供的动态数据库机制，可非常方便地实现堆栈、

33、队列等动态数据结构，提供的数据库操作谓词大大简化了编程。PROLOG还提供了谓词save().consult().前者可将当前的动态数据库存入磁盘文件，后者则可将磁盘上的一个事实数据文件调入内存。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.4.6表处理与递归表是PROLOG中一种非常有用的数据结构。序列、集合，通常语言中的数组、记录等均可用表来表示。表的最大特点是其长度不固定，在程序的运行过程中可动态地变化。具体来讲，就是在程序运行时，可对表施行一些操作，如给表中添加一个元素，或从中删除一个元素，或者将两个表合并为一个表等等。用表还可以方便地构造堆栈、队列、链表、树等动态数据结构

34、。第第2章章 人工智能程序设计语言人工智能程序设计语言 表可分为头和尾两部分。表头是表中第一个元素，而表尾是表中除第一个元素外的其余元素按原来顺序组成的表。例如下面的例子：表表头表尾1,2,3,4,512,3,4,5apple,orange,bananaappleorange,bananaa,b,c,d,ea,bc,d,ePROLOGPROLOG“无定义无定义在程序中是用竖线“|”来区分表头和表尾的，而且还可以使用变量。可以用H|T来表示一个表，其中H、T都是变量，H为表头，T为表尾。注意，此处H是一个元素（表中第一个元素），而T则是一个表（除第一个元素外的表中其余元素按原来顺序组成的表）。表

35、的这种表示法表的操作提供了极大的方便。第第2章章 人工智能程序设计语言人工智能程序设计语言 表1表2合一后的变量值X|Ya,b,cX=a,Y=b,cX|YaX=a,Y=a|YX,bX=a,Y=bX,Y,Za,b,cX=a,Y=b,Z=c a,Y|Z X,b,c X=a,Y=b,Z=c第第2章章 人工智能程序设计语言人工智能程序设计语言 表中的竖杠“|”后面只能有一个变量。例如：X|Y,Z是错误的。竖杠的前面的变量可以多于一个。例如：X,Y|Z是允许的。这个表同a,b,c匹配合一后，有X=a,Y=b,Z=c竖杠前面和后面也可以是常量，例如a|Y和X|b都是允许的，但注意，后一个表称为无尾表，如果

36、它同表a|Y匹配，则有X=a,Y=b（而不是Y=b）如果无竖杠“|”，则不能分离出表尾。例如，表X,Y,Z与a,b,c合一后得X=a,Y=b,Z=c。其中变量Z并非等于c。第第2章章 人工智能程序设计语言人工智能程序设计语言 例2.5设计一个判断对象X是表L的成员的程序。可以这样设想：(1)如果X与表L中的第一个元素（即表头）是同一个对象，则X就是L的成员;(2)如果X是L的尾部的成员，则X也就是L的成员。根据这种逻辑关系，于是有程序：member(X,X|Tail).member(X,Head|Tail):-member(X,Tail).第第2章章 人工智能程序设计语言人工智能程序设计语言

37、例2.6表的拼接程序append(,L,L).append(H|T,L2,H|Tn):-append(T,L2,Tn).这个程序刻划了两个表与它们的拼接表之间的逻辑关系。可以看出，谓词append是递归定义的，子句append(,L,L).为递归出口。如果询问Goal:append(1,2,3,4,5,L).则系统便三次递归调用程序中的第二个子句，最后从第一个子句终止，然后反向依次求出每次的拼接表，最后输出L=1,2,3,4,5第第2章章 人工智能程序设计语言人工智能程序设计语言 例2.7表的输出。print().print(H|T):-write(H),print(T).例2.8表的倒置，即

38、求一个表的逆序表。reverse(,).reverse(H|T,L):-reverse(T,L1),append(L1,H,L).这里，reverse的第一个项是输入，即原表，第二个项是输出，即原表的倒置。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.4.7回溯控制PROLOG在搜索目标解的过程中，具有回溯机制，即当某一个子目标Gi不能满足时，就返回到该子目标的前一个子目标Gi-1，并放弃Gi-1的当前约束值，使它重新匹配合一。实际问题中，有时不需要回溯，为此PROLOG中专门定义了一个阻止回溯的内部谓词“!”，称为截断谓词。第第2章章 人工智能程序设计语言人工智能程序设计语言 截

39、断谓词!的语义是：(1)若将“!”插在子句体内作为一个子目标，它总是立即成功；(2)若“!”位于子句体的最后，则它就阻止对它所在子句的头谓词的所有子句的回溯访问，而让回溯跳过该头谓词(子目标)，去访问前一个子目标（如果有的话）；(3)若“!”位于其他位置，则当其后发生回溯且回溯到“!”处时，就在此处失败，并且“!”还使它所在子句的头谓词（子目标）整个失败（即阻止再去访问头谓词的其余子句（如果有的话），迫使系统直接回溯到该头谓词(子目标)的前一个子目标(如果存在)。第第2章章 人工智能程序设计语言人工智能程序设计语言 例2.9考虑下面的程序：p(a).p(b).q(b).r(X):-p(X),q

40、(X).r(c).对于目标:r(Y).可有一个解Y=b改为：r(X):-p(X),!,q(X).则无解。由于添加“!”。求解子目标p(X)时，X被约束到a，然后跳过“!”，但在求解子目标q(a)时遇到麻烦，于是又回溯到“!”，而“!”阻止了对p(X)的下一个子句p(b)和r的下一个定义子句r(c)的访问。从而，导致整个求解失败。第第2章章 人工智能程序设计语言人工智能程序设计语言 2.4.8程序举例例2.11简单的路径查询程序。predicatesroad(symbol,symbol)path(symbol,symbol)clausesroad(a,b).road(a,c).road(b,d)

41、.road(c,d).road(d,e).road(b,e).path(X,Y):-road(X,Y).path(X,Y):-road(X,Z),path(Z,Y).abcde程序中未含目标，所以运行时需给出外部目标。当给目标：path(a,e).系统将回答:yes但当给目标:path(e,a).时，系统则回答：no第第2章章 人工智能程序设计语言人工智能程序设计语言 在程序中增加子句run:-path(a,X),write(X=,X),nl,fail.run.屏幕上将会输出:X=bX=cX=dX=eX=dX=eX=e即从a出发到其他节点的全部路径。第第2章章 人工智能程序设计语言人工智能程序

42、设计语言 例2.12求阶乘程序。domainsn,f=integerpredicatesfactorial(n,f)goalreadint(I),factorial(I,F),write(I,!=,F).clausesfactorial(1,1).factorial(N,Res):-N0,N1=N-1,factorial(N1,FacN1),Res=N*FacN1.程序运行时，从键盘输入一个整数，屏幕上将显示其阶乘数。第第2章章 人工智能程序设计语言人工智能程序设计语言 例2.13表的排序程序，采用插入排序法。/*insertsort*/domainslisti=integer*predica

43、tesinsert_sort(listi,listi)insert(integer,listi,listi)asc_order(integer,integer)clausesinsert_sort(,).insert_sort(H|Tail,Sorted_list):-insert_sort(Tail,Sorted_Tail),insert(H,Sorted_Tail,Sorted_list).insert(X,Y|Sorted_list,Y|Sorted_list1):-asc_order(X,Y),!,insert(X,Sorted_list,Sorted_list1).insert(X,Sorted_list,X|Sorted_list).asc_order(X,Y):-XY.第第2章章 人工智能程序设计语言人工智能程序设计语言 程序中对表处理使用了递归。程序目标需要在运行时临时给出。例如当给目标：insert_sort(5,3,4,2,6,1,7,8,9,0,L).系统将输出:L=0,1,2,3,4,5,6,7,8,9