第二章人工智能程序设计.docx
- 文档编号:11013988
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:20
- 大小:38.71KB
第二章人工智能程序设计.docx
《第二章人工智能程序设计.docx》由会员分享,可在线阅读,更多相关《第二章人工智能程序设计.docx(20页珍藏版)》请在冰点文库上搜索。
第二章人工智能程序设计
第二章PROLOG语言与人工智能程序设计
PROLOG是一门人工智能语言,是各种人工智能机器或知识工程系统的重要工具。
利用人工智能语言,根据知识表达、知识推理、知识获取技术与方法,设计和编写相应的程序,才能构成各种人工智能系统,实现人工智能的应用。
第一节人工智能程序综述
一.人工智能程序的特点
1.知识信息处理:
在人工智能系统中,通常需要进行符号形式的知识信息处理。
如,比较、选择、分类、检索、存取…。
对文字、图像、图形、语言进行理解和识别的符号信息处理。
2.非确定性推理:
如在专家系统中,往往需要利用专家的经验知识以及有关问题的启发信息进行非确定性推理,其中包括,模糊性——与人的思维、语言、行为的非确定性有关;随机性——与事件发生的偶然性有关。
3.动态执行:
由于人工智能问题求解过程的非确定性,在执行过程中需要动态的调用、存储知识,同时,需要动态地分配与释放存储空间。
4.并行分布式处理:
在确定性信息处理过程中,有一组任务需要同时执行,“与并行”;在非确定性信息处理过程中,需要附加并行处理资源,如加入启发信息,“或并行”。
5.知识管理:
人工智能的问题求解是以知识获取、表达、存储和知识推理、利用为基础的。
人工智能系统的知识水平的高低和解题能力的水平,取决于系统所拥有的知识多少和知识管理的水平。
因此,如何对大量的知识信息进行合理存储以及有效管理、设计和建造相应知识库以及管理系统,是需要解决的关键技术问题。
6.“开放式”系统:
所谓“开放式”系统是指其性能和结构可以不断修改、扩充的系统。
由于人工智能问题的非确定性,动态执行的需要,以及知识库增删、更新的要求等,因此,人工智能系统应当是具有学习,适应能力的开放式系统。
二.人工智能程序设计语言
人工智能程序设计语言主要用于知识信息处理,求解非数值计算的问题,如逻辑推理、规划决策、分析论证、符号处理等,要求语言便于进行知识表达、存储、知识推理和知识获取。
我们把这种语言称为“面向知识工程”的语言。
从知识信息处理的角度来看,对人工智能程序设计语言要求如下:
1.回溯功能(Back-tracking),即返回追踪功能;
2.守护功能(Demon),即在非确定性算法中的程序守护功能;
3.模式调用功能(Pattern-directedInvocation),即模式匹配功能;
4.过程证明功能(ProcedureSpecification),用于解释推理过程;
5.并行处理功能(Parallel-Proceeding),或为并行处理功能,提高速度;
现有的人工智能语言,可分为两大类:
1.函数型语言
主要用于表处理和函数处理,其典型的语言如LISP,特点是:
●程序不是逐字操作方式;
●程序与数据是分开的,程序本身不涉及数据,可以通用;
●程序有层次结构,可用简单程序构造复杂程序;
●程序是静态的、非重复的;
●程序用的内部函数和函数型都是可通用的;
●程序描写的是确定性问题的求解过程。
用户编程时,要知道解方法;
●程序描写的是函数运算的算法。
用户编程时,不仅要告诉计算机“做什么”还要告诉计算机“怎么做”。
2.逻辑型语言
主要目的是用于知识信息处理,通过逻辑推理求解问题。
其代表的语言是PROLOG,这类语言的特点是:
●具有符号处理、模式匹配、检索查询、自我扩充,在非确定环境中运用;
●程序设计具有非过程性表达形式,便于高度模块化、程序设计和验证自动化;
●面向问题的程序设计语言,在用户编程时,只要告诉计算机“做什么”—即“求解什么问题”,而不告诉计算机“怎么做”;
●高度并行处理,适合于并行推理;
●尚处于开发过程中,还有另一些有待研究的问题。
由于人工智能程序设计的特点,传统的指令型语言使用不方便,效率较低,只能在简单的系统中应用。
而函数型、逻辑型语言比指令型语言更适合于人工智能的应用。
其中,LISP和PROLOG语言在人工智能应用领域影响最大,由于人工智能应用领域非常大,不同领域所使用语言的性能要求不同,因此人工智能程序设计语言族也很大。
除了典型代表语言LISP和PROLOG外,还有许多其它的人工智能语言,在此不再赘述。
第二节PROLOG语言的应用发展与特点
一.PROLOG语言的发展和应用
PROLOG—“ProgramminginLogic”(用逻辑进行程序设计)的缩写。
它的思想最早由R.Kawalski首先提出的。
1972年世界上第一个PROLOG系统由A.Colmeraner及其研究小组在法国马赛研制成功。
PROLOG及逻辑程序设计为基础,最初目的是想设计一个处理逻辑推理问题的会话式语言,以处理一阶谓词短语为背景。
后来,由于它简洁的文法、丰富的表达力和独特的非过程性语言,很快取得了世界上广泛的支持,引起越来越多的人的注意。
现在PROLOG语言已被广泛地应用于关系数据库、抽象问题求解、数理逻辑、公式处理、自然语言理解、专家系统以及人工智能的许多领域,例如,1984年美国得克萨斯大学计算机科学系的RobertSimmons教授用PROLOG和LISP混合实现了一个自然语言理解系统。
1981年日本宣布,选取RROLOG作为第五代计算机的核心计算机语言来研究开发,并设计制造PROLOG机器,使得PROLOG更加令人瞩目。
到目前为止,PROLOG是一种最主要的人工智能程序设计语言。
因此了解掌握PROLOG语言对计算机科学工作等,特别是从事人工智能和第五代计算机研究工作的人员是十分重要的。
二.PROLOG语言的特点
作为一种程序设计语言,PROLOG具有两方面的特性:
一是它描写求解问题的方式,二是语言本身的特点。
众所周知,通常的程序设计语言(如,FORTRAN,PASCAL)求解问题时需要指明算法,即对一给定的问题指明一系列计算机要执行的计算步骤,告诉计算机“如何做”。
而PROLOG语言解题时,要求程序员描述所解问题中的对象和反映它们的关系的某些已知事实,描述和定义诸对象和它们之间关系的某些规则,它强调描述对象和事实之间的逻辑关系。
程序员一般不必告诉计算机运算执行的先后次序,因此,从能够描述问题本身,而不必描述求解问题的详细步骤这一点讲,PROLOG是更高级的语言,它可看作一种描述性语言。
PROLOG作为一种逻辑型的人工智能除了具备的特点之外,它本身还具备如下特点:
●PROLOG的数据和程序结构统一,它提供了一种一致性的数据结构(即项—term)所有数据和程序都是由想构造而成的;
●PROLOG能自动实现模式匹配和回溯,这些人工智能系统中最常用的、最基本的操作。
由于PROLOG系统提供了自动完成这些操作的功能,使用户在PROLOG语言这一级不必考虑这些问题;
●与LISP语言一样,递归是PROLOG语言的主要特点,它反映在程序和数据结构中,由于这特性,一个大的数据结构常能够由一个小的程序来处理。
PROLOG的所有这些特性,使得PROLOG特别适用于描述智能程序,适用于自然语言处理、推理证明、专家系统等。
第三节PROLOG语言的基本语句
一.简单实例
如图2.1所示的有向图,下面用PROLOG来描述图中两点之间的通路关系。
图2.1
●若用connected(X,Y)表示从点X到点Y有一条有向边,则图中两点之间的关系可描述如下:
Connected(a,b)connected(a,c)connected(b,d)
Connected(e,b)connected(c,d)connected(d,e)
●定义两点之间的通路:
1.X到Y有一条有向边;
2.存在一点Z,X到Z有一有向边,
Z到Y个有一条通路;
有规则:
Path(x,y):
-connected(x,y).
Path(x,y):
-connected(x,z),path(z,y).
在此,“:
-”为定义符,含义为“如果”,“,”表示与的关系“并且”,“.”为规则定义结束符。
●有了上述规则和事实描述之后,就可进行以下询问,提问符为“?
—”:
?
—path(a,b);a到b有通路吗?
Yes;有
?
—path(b,a);b到a有通路吗?
No;没有
以上就是一个简单的PROLOG程序,一旦这个程序进入机器后,那就可以会话方式进行这个程序。
由上述程序可以看出PROLOG语言仅提供了三个基本语句:
⑴事实:
它说明一个问题中的对象和它们之间的关系的一些已知事实;
⑵规则:
它用来定义对象和它们之间的关系,用来描述一个事实依赖于其他一组事实;
⑶询问:
用来询问有关对象和它们之间的关系。
下面是一个求阶乘的例子,分别以PASCAL、LISP和PROLOG三种语言进行编程,从中可以看出PROLOG语言与其它种语言的区别:
1.PASCAL:
FunctionIP(a,b:
array[1:
n]ofinteger):
integer;
Vara,i:
integer;
Begin
C:
=0;
Fori:
=1tondo
C:
=c+a[i]*b[i];
End;
2.LISP
(defunIP(a,b)
(+First(a,b)Rest(a,b)))
(defunFirst(a,b)
(*CAR(a)CAR(b)))
(defunRest(a,b)
(IP(CDR(a)CDR(b)))
3.PROLOG:
IP([],[],Res):
-Resis0.
IP([],[b/Y],Res):
-Resis0.
IP([a/X],[],Res):
-Resis0.
IP([a/X],[b/Y],Res):
-Resis0.
由此可看出,PROLOG的语法是面向逻辑而不是面向机器的,它的语法是以谓词逻辑的词语为基础的。
二.事实
句型:
P语意为,P永远为真。
例:
owns(Susan,horse);苏珊有一匹马
Like(Phillip,Susan);菲力谱喜欢苏珊
如:
JohnlikesMary.表示为likes(John,Mary)
这便是一个事实。
事实是有关对象之间的关系的集合,在对象中,次序不能是随意的,这表示谁对谁的关系,也可宣称一些与日常生活中相矛盾的事实也是没关系的。
在PROLOG中,对象与对象之间的关系是以数据库的形式来存放的,所以数据库是PROLOG的核心。
在宣称的这些事实之后,就可以对系统进行提问。
?
—likes(John,Mary)
Yes
?
—likes(John,Abby)
No.
说明:
1.所有关系的名字和对象名,不能采用小写;
2.关系符写在前面,对象在其后而且用括号括起来;
3.当事实描述完毕,则用“.”来结束。
在上述例子中,likes成为谓词,反映了对象之间存在某种关系,而John,Mary则为变元。
变量,不能用大写字母,它是一种逻辑型的变量,而且是一种静态的关系,即一旦确定之后,便不再改变。
如:
?
—likes(John,x)
一旦在事实库中找到likes(John,Mary)之后,则x=”Mary”,x便不再改变。
总是x=”Mary”。
在PROLOG中,一个名字一经使用,这个名字就指一特定的对象,因此,当我们使用名字时,必须决定如何来解释这个名字,只要在一给定的问题中所使用的名字解释一致,就不会有任何问题。
若有下列事实:
likes(John,flowers).
likes(John,Mary).
likes(Paul,Mary).
提问时应该注意:
⑴?
—likes(John,x)
①x=flowers↘只有一个结果,便可回车
②x=flowers;若再继续查找,John还喜欢什么,用分号,再回车
说明:
这里的“;”有两个作用,一是使数据库指针从上次找的下一个开始,即接着上次匹配的下一个数据开始;二是使变量x的事实无效—脱解。
⑵若向John所有喜欢的
?
—likes(John,x)
x=flowers;
x=Mary;
no.
⑶对John和Mary的喜欢的事实同时进行提问
?
—likes(John,x),likes(Mary,x)
此时,两个提问中的变量x是一样的,则所提问的是John和Mary一样,即,Mary是否也喜欢John所喜欢的东西。
注意:
1.提问顺序按从左到右进行,每个目标语句之间用“,”分开;
2.在同一个结构中,若各目标语句使用同一变量,则当第一个目标语句中实现了匹配,则该变量被实化。
此时,其余的目标语句中的变量x均被实化,其内容与第一个语句实化后的内容相同。
3.同时对几个目标语句进行提问,而且使用同一变量,则第一个给第一个匹配,若其余都失败,第一个句子再次往下移动进行第二次实化,直至都满足,否则当数据库搜索完毕都不能匹配,则称整个提问失败。
三.规则
句型:
P:
-P1,P2,…Pn.
语义:
若P1∩P2∩…∩Pn为真,则P为真.
例:
likes(bill,x):
—likes(tom,x).只要汤姆喜欢的比尔也喜欢。
定义:
当所描述的一组事实要以来于另一组事实时,则可以用一个规则来表示。
如:
Likes(John,x):
-likes(x,flowers).
规则头定义符规则体结束符
上句规则的含义是:
如果x喜欢花,则John就喜欢他。
例:
buy(x,car):
-have(x,money).如果某人有钱,则他就买汽车
Bird(x):
-animal(x),feathers(x).如x是动物且有羽毛,则就是鸟
Sister(x,y):
-female(x),patents(x,f,m),parents(y,f,m)
如果x是女的,并且x和y有相同的父母,则x和y是姐妹。
规则是事实库中诸对象关系的陈述,一个规则由规则头和体,用定义符:
—连接而成。
规则的头描述了这条规则企图定义的事实;规则的体描述了一些目标的连接。
为使头成为真的,这些目标又逐个被满足,在规则体中,各目标之间可用“,”连接,表示“与”关系。
通常一个谓词(如:
likes,sister)能用事实和规则的混合来定义,如,
likes(John,food).
Likes(John,x):
-person(x).
这些事实和规则称为一阶谓词的子句,以后每当我们涉及一个事实和一个规则时,则用子句来统称。
关于规则定义中的两个概念:
1.常量:
常量用来命名特定的对象或特定的关系。
在PROLOG中,常量有两类,即:
原子和整数。
以小写字母开始的字母数字串,john,talk,like,sister
原子仅由符号组成:
=,→,:
—,?
—
常量
整数通常意义下的整数,由数学组成,不包括小数点
原子是构成各种事实或规则的基本符号。
2.变量:
变量是以大写字母或下划线符号“_”开头的字母数字符,中间也可有“_”,,如Input,Who,_3_blind_men,…它用来代表某些尚不能命名的对象,它好象代词。
有时需要用一个变量,但从不利用它的名字。
例如,要知道是否有人喜欢John但并不需要知道究竟是谁喜欢他,这时可以用无名变量来问。
无名变量用下划线符号“_”表示,如是否有人喜欢john,可提问?
—likes(_,john).无名变量的使用,往往发生在当叙述某一事情时,并不关心事情中某一变量究竟代表什么具体对象,而只需要关心它的存在。
四.询问
句型:
?
-P1,P2,…,Pn.
语义:
P1∩P2∩…∩Pn为真吗?
例:
likes(x,reading)andlikes(x,swimming).谁喜欢读书又喜欢游泳
虽然用户可以在任何时候向PROLOG提任何问题,但一般而言,程序员总是先把事实和规则提供给PROLOG,然后再询问有关问题。
询问格式“?
—”,当对PROLOG提问后,PROLOG就到它已取得的事实和规则的数据库中去找是否有这样一个事实或规则。
如果回答为yes,则成功,否则为no,有两种含义,一是不或没有等,二是不知道。
在搜索过程中,PROLOG中的变量可以是被实例化的,也可以是未被实例化的。
一个变量被实例化是指这个变量代表一个确定的对象,一个变量未被实例化是指当这个变量所代表的东西还不知道。
因此,PROLOG允许一个未实例化的变量匹配任何一个对象。
设事实库:
likes(john,flowers).
Likes(john,wine).
Likes(Paul,wine).
Likes(Paul,john).
考虑下面的一组提问:
?
—likes(john,x),likes(Paul,.).
这个语句有两个目标组成,每个目标包含一个x,像规则一样,这两个x表示同一个对象。
当PROLOG收到这个询问,它首先企图满足第一个目标,找是否有某样东西x,john喜欢。
在第一个目标匹配第一个事实,变量x被实例化,比如flowers,PROLOG企图满足第二个目标,如Paul,是否也喜欢flowers,但此时失败,于是,PROLOG回溯到第一个目标,企图重新满足这个目标,此时,它首先把x脱解为未实例化的,然后从第二个事实开始往下寻找。
当找到第二个事实匹配目标时,于是,这次x实例化为wine,现在第二个目标中x也为wine,这样目标likes(Paul,wine)匹配第三个事实,最后回答x=wine。
PROLOG中规则和询问中的变量的作用域仅是这个规则和这个询问,一旦某个变量,如x被实例化为某个对象,则在同一作用域内的所有x都被实例化为某个对象,在PROLOG中,变量是局部的,而原子符号则是全局的。
例:
如果一个人是小偷,并且他喜欢某样东西,则这个人可能会偷这个东西,若存在事实库:
thief(John).
Likes(Paul,food).
Likes(John,wine).
May_steal(John,x).
提问:
?
—_may_steal(John,x).
PROLOG系统搜索如下:
1首先搜索may_steal子句,于是,问题中的John匹配规则中的x,问题中的x匹配规则中的y,则称规则中的x被问题中的x实例化,而匹配的两个未被实例化的变量:
问题中的x和规则中的y,称为“共享”。
所谓“共享”是指当两个未实例化的变量相匹配后,以后只要这两个变量中的任何一个变量实例化为一特定的对象,则另一个变量也被实例化一特定的对象。
2匹配有两个规则:
thief(x)和likes(x,y),即:
x被John实例化。
3第二个匹配规则likes(x,y),因x=John,则又为一规则,现需要满足likes(Paul,x)。
4子目标likes(Paul,x)与likes(Paul,food)匹配。
5X被实例化为food,由共享原则,y也实例化为food。
6依次返回,整个匹配成功,则x=food。
五.几点说明
1.回溯问题的进一步讨论
一个询问提出了一组需被满足的目标,PROLOG利用已知的子句(事实或规则)来满足这些目标(只有匹配目标的子句才被利用)。
一个事实能引起一个目标立即被满足,而一个规则只能把满足任务化为满足一组子目标。
在逐步匹配满足过程中,如果一个不能被满足则将引起回溯。
回溯是回顾前面已满足的目标,且试图功过找到另一个可选择的途径来重新满足那些目标,为此,需先解脱那些已被实例化的变量,如果还不满足计算时你询问的回答,则打入“;”再启动一次回溯。
2.决定是否匹配的法则
1 一个未实例化的变量将匹配任何对象,作为匹配结果,或此变量被实例化 后化为那个对象或与它们共享;
2 一个整数或原子将只匹配它自己;
3 一个结构将匹配另一个具有相同函数符号和相同变元个数的结构。
3.PROLOG的大致编程过程
4 宣称有关对象及其之间关系的事实;
5 定义有关对象及其之间关系的规则;
6 对对象及其关系进行提问。
4.其他
7 在使用PROLOG编程时,变量名的选取很重要,如对于likes(john,wine),若定义为likes(j,w)则时间久就会不知道此语句是什么意思了。
因此在选取变量名时尽量使用事实与问题,比较清楚,真实。
8在PROLOG程序中,可以用“/*”和“*/”加入注释,帮助对事实和规则库的管理。
第四节PROLOG数据结构与语法
一.有关项的概念
PROLOG提供了一个一致的数据结构称为项,所有的数据和PROLOG程序都是由项构造而成的。
项的定义用BNF形式可写成:
〈项〉∷=〈常量〉|〈变量〉|〈结构〉|(〈项〉)
即,项可以是变量、常量、结构或括在括号中的项。
结构—或称为复合项,它是由一组其他对象组成的单个对象,这些其他对象称为它的成分,把几个成分组合成一个结构作为单个对象是很有用处的。
〈结构〉∷=〈函数符〉(〈项〉{,〈项〉})
〈函数符〉∷=〈原子〉
下面是一些结构的例子:
Owns(john,book)
Owns(john,book(pnday,author(clocksin,McLeish)))
A(b,c,d)
+(3,*(5,2))或3+5*2…
二.PROLOG语言的系统谓词
在PROLOG语言中,提供用户使用的内部谓词,即系统谓词,有以下几种:
1.比较谓词
两个关系表达式之间的关系符有:
<,<=,=,>,>=,<>
2.算术运算谓词:
+,-,*,/
3.算术函数:
random(x) 把x约束为一个大于0小于1的随机数
Round(x)返回x的四舍五入数
Xdivy返回x除以y的商
Abs(x)返回x的绝对值
Cos(x)返回弧度x的余弦
Sin(x)返回弧度x的正弦
Tan(x)返回弧度x的正切值
Arctan(x)返回弧度x的反正切值
Exp(x)返回e的x次幂,其中,e=2。
71828
Ln(x)返回x的自然对数
Log(x)返回x的以10为底的对数
Sqrt(x)返回x的平方根
4.输入/输出谓词
①write(“list1=”,l1,“list2=”,l2).
若l1被约束为[a,b],l2被约束为[1,2],
则结果list1=[a,b],list2[1,2]。
②nl为换行操作符。
③readln(line)变量line为串或符号类型;
输入一个串给line,读入的字符数最多为64k,每个串以回车结束。
④readint(x)x为整型变量;
输入一个整数给x。
⑤readreal(x)x为实型变量;
输入一个实型数给x。
⑥readchar(charparam)charparam为字符型变量;
输入一个字符给charparam。
5.控制谓词
用于控制PROLOG程序运行及其推
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第二 人工智能 程序设计