人工智能程序设计

其次章PROLOGPROLOG利用人工智能语言，依据学问表达、学问推理、学问猎取技术与方法，设计和编写相应的程序，才能构成各种人工智能系统，实现人工智能的应用。一．人工智能程序的特点学问信息处理：在人工智能系统中，通常需要进展符号形式的学问信息处理。如，比较、选择、分类、检索、存取„。对文字、图像、图形、语言进展理解和识别的符号信息处理。非确定性推理：如在专家系统中，往往需要利用专家的阅历学问以及有关问题的启发信息进展非确定性推理，其中包括，模糊性——与人的思维、语言、行为的非确定性有关；随机性——与大事发生的偶然性有关。动态执行：由于人工智能问题求解过程的非确定性，在执行过程中需要动态的调用、存储学问，同时，需要动态地安排与释放存储空间。学问治理：人工智能的问题求解是以学问猎取、表达、存储和学问推理、利用为根底的。人工智能系统的学问水平的凹凸和解题力量的水平，取决于系统所拥有的学问多少和学问治理的水平。因此，如何对大量的学问信息进展合理存储以及有效治理、设计和建筑相应学问库以及治理系统，是需要解决的关键技术问题。“开放式”系统：所谓“开放式”系统是指其性能和构造可以不断修改、扩大的系统。由于人工智能问题的非确定性，动态执行的需要，以及学问库增删、二． 人工智能程序设计语言辑推理、规划决策、分析论证、符号处理等，要求语言便于进展学问表达、存储、处理的角度来看，对人工智能程序设计语言要求如下：回溯功能Back-trackin，即返回追踪功能；守护功能Demo，即在非确定性算法中的程序守护功能；模式调用功能Pattern-directedInvocatio，即模式匹配功能；过程证明功能ProcedureSpecificatio，用于解释推理过程；并行处理功能Parallel-Proceedin现有的人工智能语言，可分为两大类：函数型语言主要用于表处理和函数处理，其典型的语言如LISP，特点是：程序不是逐字操作方式；程序与数据是分开的，程序本身不涉及数据，可以通用；程序有层次构造，可用简洁程序构造简单程序；程序是静态的、非重复的；程序用的内部函数和函数型都是可通用的；程序描写的是确定性问题的求解过程。用户编程时，要知道解方法；还要告知计算机“怎么做规律型语言主要目的是用于学问信息处理，通过规律推理求解问题。其代表的语言是PROLOG，这类语言的特点是：具有符号处理、模式匹配、检索查询、自我扩大，在非确定环境中运用；化；高度并行处理，适合于并行推理；尚处于开发过程中，还有另一些有待争论的问题。由于人工智能程序设计的特点，传统的指令型语言使用不便利，效率较低，只能在简洁的系统中应用。而函数型、规律型语言比指令型语言更适合于人工智能的应用。其中，LISP和PROLOG典型代表语言LISP和PROLOG外，还有很多其它的人工智能语言，在此不再赘述。其次节PROLOG语言的应用进展与特点一． PROLOG语言的进展和应用PROLOG—“ProgramminginLogic”(用规律进展程序设计)的缩写。它的思想最早由R.Kawalski1972年世界上第一个PROLOG系统由A.Colmeraner及其争论小组在法国马赛研制成功。PROLOG及规律程序设计为根底，最初目的是想设计一个处理规律推理问题的会话式语言，以处理一阶谓词短语为背景。后来，由于它简洁的文法、丰富的表达。现在PROLOG语言已被广泛地应用于关系数据库、抽象问题求解、数理规律、公式处理、自然语言理解、专家系统以及人工智能的很多领域，例如，1984年美国得克萨斯大学计算机科学系的RobertSimmons教授用PROLOG和LISP混合实1981RROLOG作为第五代计算机的PROLOGPROLOG更加令人瞩目。到目前为止，PROLOG是一种最主要的人工智能程序设计语言。因此了解把握PROLOG语言对计算机科学工作等，特别是从事人工智能和第五代计算机争论工作的人员是格外重要的。二． PROLOG语言的特点作为一种程序设计语言，PROLOG具有两方面的特性：一是它描写求解问题的方式，二是语言本身的特点。众所周知，通常的程序设计语言〔如，FORTRAN，PASCAL〕求解问题时需PROLOG描述对象和事实之间的规律关系。程序员一般不必告知计算机运算执行的先后次序，因此，从能够描述问题本身，而不必描述求解问题的具体步骤这一点讲，PROLOG是更高级的语言，它可看作一种描述性语言。PROLOG作为一种规律型的人工智能除了具备的特点之外，它本身还具备如下特点：PROLOG的数据和程序构造统一，它供给了一种全都性的数据构造〔即项—term〕全部数据和程序都是由想构造而成的；PROLOG能自动实现模式匹配和回溯，这些人工智能系统中最常用的、最根本的操作。由于PROLOG系统供给了自动完成这些操作的功能，使用户在PROLOG语言这一级不必考虑这些问题；与LISPPROLOG语言的主要特点，它反映在程序和理。PROLOG的全部这些特性，使得PROLOG用于自然语言处理、推理证明、专家系统等。第三节 PROLOG语言的根本语句一． 简洁实例如图２.1所示的有向图，下面用PROLOG来描述图中两点之间的通路关系。bdebdec2.1假设用connected(X,Y)表示从点X到点Y有一条有向边，则图中两点之间的关系可描述如下：Connected(a,b) connected(a,c) connected(b,d)Connected(e,b) connected(c,d) connected(d,e)定义两点之间的通路：X到Y有一条有向边； 存在一点Z，XZ有一有向边，ZY个有一条通路；有规章：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语言仅供给了三个根本语句：⑴事实：它说明一个问题中的对象和它们之间的关系的一些事实；⑵规章：它用来定义对象和它们之间的关系，用来描述一个事实依靠于其他一组事实；⑶询问：用来询问有关对象和它们之间的关系。PASCALLISP和PROLOG三种语言进展编程，从中可以看出PROLOG语言与其它种语言的区分：PASCAL：FunctionIP(a,b:array[1:n]ofinteger):integer;Var a,i:integer;BeginC:=0;Fori:=1tondoC:=c+a[i]*b[i];End;LISP(defun IP(a,b)(+ First(a,b) Rest(a,b)))(defun First(a,b)(* CAR(a) CAR(b)))(defun Rest(a,b)(IP (CDR(a) CDR(b)))PROLOG:IP([],[],Res):-Res is0.IP([],[b/Y],Res):-Res is0.IP([a/X],[],Res):-Res is0.IP([a/X],[b/Y],Res):-Res is0.由此可看出，PROLOG的语法是面对规律而不是面对机器的，它的语法是以谓词规律的词语为根底的。二． 事实句型：P 语意为，P永久为真。例：owns(Susan,horse) ；苏珊有一匹马Like(Phillip,Susan) ；菲力谱宠爱苏珊如：JohnlikesMary. 表示为likes(John,Mary)系的。在PROLOG中，对象与对象之间的关系是以数据库的形式来存放的，所以数据库是PROLOG的核心。在宣称的这些事实之后，就可以对系统进展提问。？—likes(John,Mary)Yes？—likes(John,Abby)No.说明：全部关系的名字和对象名，不能承受小写；关系符写在前面，对象在其后而且用括号括起来；当事实描述完毕，则用“.”来完毕。在上述例子中，likesJohn,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.⑶对JohnMary？—likes(John,x),likes(Mary,x)三．规章

xJohn和Mary一样，即，Mary是否也宠爱John留意：1.提问挨次按从左到右进展，每个目标语句之间用“2语句中实现了匹配，则该变量被实化。此时，其余的目标语句中的变量x均被实化，其内容与第一个语句实化后的内容一样。3.一个匹配，假设其余都失败，第一个句子再次往下移动进展其次次实化，直至都满足，否则当数据库搜寻完毕都不能匹配，则称整个提问失败。句型：P:-P1，P2，„Pn.语义：假设P1∩P2∩„∩PnPlikebil，like〔to，.只要汤姆宠爱的比尔也宠爱。如：Likes〔John，x〕:-likes〔x，flowers〕.规章头 定义符 规章体 完毕符上句规章的含义是：假设x宠爱花，则John例：buy〔x，car〕:-have〔x,money〕.假设某人有钱，则他就买汽车Bir:-anima〔feather.如x是动物且有羽毛，则就是鸟Siste〔y:-femal〔,patent〔xfparent〔yf，m〕假设x是女的，并且xyxy连接，表示“与”关系。通常一个谓词〔如：likes，sister〕能用事实和规章的混合来定义，如，likes〔John，food〕.Likes〔John,x〕:-person〔x〕.这些事实和规章称为一阶谓词的子句，以后每当我们涉及一个事实和一个规章时，则用子句来统称。关于规章定义中的两个概念：常量：PROLOG即：原子和整数。

以小写字母开头的字母数字串，john,talk,like，sister原子 仅由符号组成=，→：—，？—常量整数通常意义下的整数，由数学组成，不包括小数点原子是构成各种事实或规章的根本符号。变量：_有“_”,，如Input，Who，_3_blind_men，„它用来代表某些尚不能命名的对象，它好象代词。宠爱John但并不需要知道到底是谁宠爱他，这时可以用无名变量来问。johlikes〔_,john〕.无名变量的使用，往往发生在当表达某一事情时，并不关心事情中某一变量到底代表什么具体对象，而只需要关心它的存在。四.询问句型：？－P1，P2，„，Pn.语义：P1∩P2∩„∩Pn例： likes〔x，reading〕andlikes〔x，swimming〕.谁宠爱读书又宠爱游泳虽然用户可以在任何时候向PROLOG提任何问题，但一般而言，程序员总是先把事实和规章供给应PROLOG，然后再询问有关问题。PROLOGPROLOG的数据库中去找是否有这样一个事实或规章。假设答复为yes，则成功，否则为no，有两种含义，一是不或没有等，二是不知道。PROLOG中的变量可以是被实例化的一个变量被实例化是指这个变量代表一个确定的对象，一个变量未被实例化是指当这个变量所代表的东西还不知道。因此，PROLOG允许一个未实例化的变量匹配任何一个对象。设事实库：likes〔john,flowers〕.Likes〔john,wine〕.Likes〔Paul，wine〕.Likes〔Paul,john〕.考虑下面的一组提问：？—like〔john,，likePaul,.这个语句有两个目标组成，每个目标包含一个x，像规章一样，这两个x表示同一个对象。当PROLOG收到这个询问，它首先企图满足第一个目标，找是否有某样东西x，john宠爱。在第一个目标匹配第一个事实，变量x被实例化，比方flowers，PROLOGPaulflowers，但此时失败，于是，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①首先搜寻may_stealJohnx，问题x匹配规章中的y，则称规章中的x被问题中的xx和规章中的y对象。②thiex〕和like〔，yx被John实例化。③其次个匹配规章like，y，因x=Johlike〔Pau，。④子目标likes〔Paul，x〕与likes〔Paul，food〕匹配。⑤X被实例化为food，由共享原则，y也实例化为food。⑥依次返回，整个匹配成功，则x=food。五．几点说明回溯问题的进一步争论PROLOG利用的子句〔事实或规章〕来满足这些目标〔只有匹配目标的子句才被利用。一个事实能引起一个目标马上被满足还不满足计算时你询问的答复，则打入“打算是否匹配的法则①一个未实例化的变量将匹配任何对象作为匹配结果或此变量被实例化 后化为那个对象或与它们共享；②一个整数或原子将只匹配它自己；③一个构造将匹配另一个具有一样函数符号和一样变元个数的构造。PROLOG④宣称有关对象及其之间关系的事实；⑤定义有关对象及其之间关系的规章；⑥对对象及其关系进展提问。其他⑦在使用PROLOGwine，假设定义为like〕则时间久就会不知道此语句是什么意思了。因此在选取变量名时尽量使用事实与问题，比较清楚，真实。⑧在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比较谓词两个关系表达式之间的关系符有：<，<=，=，>,>=,<>算术运算谓词：+，-，*，/算术函数：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。71828Ln〔x〕 返回x的自然对数Log〔x〕 返回x的以10为底的对数Sqrt〔x〕 返回x的平方根输入/输出谓词①writlist1，l“list2，l〕.l1a，b]，l2[1，2]，则结果list1=[a，b]，list2[1，2]。②nl③readln〔line〕变量line输入一个串给line64k，每个串以回车完毕。④readint〔x〕 x输入一个整数给x。⑤readreal〔x〕x输入一个实型数给x。⑥readchar〔charparam〕 charparam为字符型变量；输入一个字符给charparam。掌握谓词用于掌握PROLOG程序运行及其推理求解而设立的①fail表示失败，即推理求解过程失败。用fail作为子目PROLOG程序运行到fail，必引起回溯〔即强制回溯；的回溯是不行能的。截断元素主要用于两个方面。ⅰ〕当事先知道不行能产生有意义的解，且回溯会铺张时间和空间，使用截断能加快程序运行且能节约空间。ⅱ〕程序的规律构造在下述三种状况下，需要用截断谓词：用它阻挡对规章中的前几个子目标的回溯，例如：ra,bc 这是我们仅对子目标的a,b兴趣用它来阻挡对下一个子句的回溯r的三个子句R1：—，，，cR：—，dR3：—e两截断词使r1r2r3用它来将非确定性子句转化为确定性的子句。三．PROLOGfdfdcahebgi图2.2 建筑物平面图所谓“迷宫”问题，即迷宫搜寻〔SearchingMaze〕问题。设某建筑物有在哪个房间，何处是出口，因此需要搜寻。当找到建筑物出口时，假设已经找到了有的房间，那么搜寻完毕。该建筑物各房间可以自由出入为此，在搜寻过程中需要有个登记表，记录已搜寻过的房间。这样，凡登记表上有的房间号不再搜寻，凡没有登记过的，可进展搜寻并登记房间号。如此，边搜寻边登记，直到找到出口而且在登记表中已有的房间号为止。该建筑物的平面构造如下图。其中，b,c,d,e,g,h,i为房间号，a为建筑物的入口，f为建筑物的出口，房间之间有门〔door〕相通，在房间g中，有关事实表示如下：Door〔a，b〕.Door〔b，i〕Door〔b，e〕.Door〔e，d〕Door〔i，g〕Door〔e，h〕Door〔g，e〕Door〔d，f〕Door〔d，c〕hasphone〔g〕“迷宫”问题搜寻步骤如下：①到某房间的门口；②假设此房间号在登记表〔visitedrooms〕中，则不再搜寻，返回①；④是都出口？⑤假设为出口，且在房间中有，则搜寻成功，则表中所登记的搜寻路径即为问题的解，停顿搜寻，打印搜寻路径。⑥假设不符合，返回①，连续搜寻。go由入口here向出口thereGo〔her，ther〕ifrout〔hertherher〕子句go调用routehereRouteRoute〔f，f，visitedrooms〕ifHasphone〔tel〕andMember(tel,visitedooms)andReversevisitedrooms,temp)andWrite(temp)andnl.f搜寻路径，在这里求解出的只有一条路径。其中，member子句用来推断表中是否含有某元素。Member〔x，[x1_]〕.Member〔x，[_1H]〕ifmember〔x，H〕.由于收集到visitedrooms在后，承受reverse子句可得visitedroomsRevers，Y：revers〔[，，Y〕.Reverse〔Y，[]，Y〕.ReversX，[u|X2，：—revers〔[u|X1，X，Y.RouteRoute〔room，way_out,visitedrooms〕ifNeighborroom(room,nextroom)andNot(member(nextroom,visitedrooms))andRoute(nextroom,way_out,(nextroom(visitedrooms))).roomneighborroom子