人工智能程序設計

其次章PROLOGPROLOG利用人工智能語言，依據(jù)學問表達、學問推理、學問獵取技術與方法，設計和編寫相應的程序，才能構成各種人工智能系統(tǒng)，實現(xiàn)人工智能的應用。一．人工智能程序的特點學問信息處理：在人工智能系統(tǒng)中，通常需要進展符號形式的學問信息處理。如，比較、選擇、分類、檢索、存取?。對文字、圖像、圖形、語言進展理解和識別的符號信息處理。非確定性推理：如在專家系統(tǒng)中，往往需要利用專家的閱歷學問以及有關問題的啟發(fā)信息進展非確定性推理，其中包括，模糊性——與人的思維、語言、行為的非確定性有關；隨機性——與大事發(fā)生的偶然性有關。動態(tài)執(zhí)行：由于人工智能問題求解過程的非確定性，在執(zhí)行過程中需要動態(tài)的調用、存儲學問，同時，需要動態(tài)地安排與釋放存儲空間。學問治理：人工智能的問題求解是以學問獵取、表達、存儲和學問推理、利用為根底的。人工智能系統(tǒng)的學問水平的凹凸和解題力量的水平，取決于系統(tǒng)所擁有的學問多少和學問治理的水平。因此，如何對大量的學問信息進展合理存儲以及有效治理、設計和建筑相應學問庫以及治理系統(tǒng)，是需要解決的關鍵技術問題。“開放式”系統(tǒng)：所謂“開放式”系統(tǒng)是指其性能和構造可以不斷修改、擴大的系統(tǒng)。由于人工智能問題的非確定性，動態(tài)執(zhí)行的需要，以及學問庫增刪、二． 人工智能程序設計語言輯推理、規(guī)劃決策、分析論證、符號處理等，要求語言便于進展學問表達、存儲、處理的角度來看，對人工智能程序設計語言要求如下：回溯功能Back-trackin，即返回追蹤功能；守護功能Demo，即在非確定性算法中的程序守護功能；模式調用功能Pattern-directedInvocatio，即模式匹配功能；過程證明功能ProcedureSpecificatio，用于解釋推理過程；并行處理功能Parallel-Proceedin現(xiàn)有的人工智能語言，可分為兩大類：函數(shù)型語言主要用于表處理和函數(shù)處理，其典型的語言如LISP，特點是：程序不是逐字操作方式；程序與數(shù)據(jù)是分開的，程序本身不涉及數(shù)據(jù)，可以通用；程序有層次構造，可用簡潔程序構造簡單程序；程序是靜態(tài)的、非重復的；程序用的內(nèi)部函數(shù)和函數(shù)型都是可通用的；程序描寫的是確定性問題的求解過程。用戶編程時，要知道解方法；還要告知計算機“怎么做規(guī)律型語言主要目的是用于學問信息處理，通過規(guī)律推理求解問題。其代表的語言是PROLOG，這類語言的特點是：具有符號處理、模式匹配、檢索查詢、自我擴大，在非確定環(huán)境中運用；化；高度并行處理，適合于并行推理；尚處于開發(fā)過程中，還有另一些有待爭論的問題。由于人工智能程序設計的特點，傳統(tǒng)的指令型語言使用不便利，效率較低，只能在簡潔的系統(tǒng)中應用。而函數(shù)型、規(guī)律型語言比指令型語言更適合于人工智能的應用。其中，LISP和PROLOG典型代表語言LISP和PROLOG外，還有很多其它的人工智能語言，在此不再贅述。其次節(jié)PROLOG語言的應用進展與特點一． PROLOG語言的進展和應用PROLOG—“ProgramminginLogic”(用規(guī)律進展程序設計)的縮寫。它的思想最早由R.Kawalski1972年世界上第一個PROLOG系統(tǒng)由A.Colmeraner及其爭論小組在法國馬賽研制成功。PROLOG及規(guī)律程序設計為根底，最初目的是想設計一個處理規(guī)律推理問題的會話式語言，以處理一階謂詞短語為背景。后來，由于它簡潔的文法、豐富的表達。現(xiàn)在PROLOG語言已被廣泛地應用于關系數(shù)據(jù)庫、抽象問題求解、數(shù)理規(guī)律、公式處理、自然語言理解、專家系統(tǒng)以及人工智能的很多領域，例如，1984年美國得克薩斯大學計算機科學系的RobertSimmons教授用PROLOG和LISP混合實1981RROLOG作為第五代計算機的PROLOGPROLOG更加令人矚目。到目前為止，PROLOG是一種最主要的人工智能程序設計語言。因此了解把握PROLOG語言對計算機科學工作等，特別是從事人工智能和第五代計算機爭論工作的人員是格外重要的。二． PROLOG語言的特點作為一種程序設計語言，PROLOG具有兩方面的特性：一是它描寫求解問題的方式，二是語言本身的特點。眾所周知，通常的程序設計語言〔如，F(xiàn)ORTRAN，PASCAL〕求解問題時需PROLOG描述對象和事實之間的規(guī)律關系。程序員一般不必告知計算機運算執(zhí)行的先后次序，因此，從能夠描述問題本身，而不必描述求解問題的具體步驟這一點講，PROLOG是更高級的語言，它可看作一種描述性語言。PROLOG作為一種規(guī)律型的人工智能除了具備的特點之外，它本身還具備如下特點：PROLOG的數(shù)據(jù)和程序構造統(tǒng)一，它供給了一種全都性的數(shù)據(jù)構造〔即項—term〕全部數(shù)據(jù)和程序都是由想構造而成的；PROLOG能自動實現(xiàn)模式匹配和回溯，這些人工智能系統(tǒng)中最常用的、最根本的操作。由于PROLOG系統(tǒng)供給了自動完成這些操作的功能，使用戶在PROLOG語言這一級不必考慮這些問題；與LISPPROLOG語言的主要特點，它反映在程序和理。PROLOG的全部這些特性，使得PROLOG用于自然語言處理、推理證明、專家系統(tǒng)等。第三節(jié) 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個有一條通路；有規(guī)章：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語言僅供給了三個根本語句：⑴事實：它說明一個問題中的對象和它們之間的關系的一些事實；⑵規(guī)章：它用來定義對象和它們之間的關系，用來描述一個事實依靠于其他一組事實；⑶詢問：用來詢問有關對象和它們之間的關系。PASCALLISP和PROLOG三種語言進展編程，從中可以看出PROLOG語言與其它種語言的區(qū)分：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的語法是面對規(guī)律而不是面對機器的，它的語法是以謂詞規(guī)律的詞語為根底的。二． 事實句型：P 語意為，P永久為真。例：owns(Susan,horse) ；蘇珊有一匹馬Like(Phillip,Susan) ；菲力譜寵愛蘇珊如：JohnlikesMary. 表示為likes(John,Mary)系的。在PROLOG中，對象與對象之間的關系是以數(shù)據(jù)庫的形式來存放的，所以數(shù)據(jù)庫是PROLOG的核心。在宣稱的這些事實之后，就可以對系統(tǒng)進展提問。？—likes(John,Mary)Yes？—likes(John,Abby)No.說明：全部關系的名字和對象名，不能承受小寫；關系符寫在前面，對象在其后而且用括號括起來；當事實描述完畢，則用“.”來完畢。在上述例子中，likesJohn,Mary則為變元。變量，不能用大寫字母，它是一種規(guī)律型的變量，而且是一種靜態(tài)的關系，即一旦確定之后，便不再轉變。如：？—likes(John,x)一旦在事實庫中找到likes(John,Mary)之后，則x=”Mary”，x便不再轉變。x=”Mary”PROLOG中，一個名字一經(jīng)使用，這個名字就指一特定的對象，因此，當我們使用名字時，必需打算如何來解釋這個名字，只要在一給定的問題中所使用的名字解釋全都，就不會有任何問題。假設有以下事實：likes(John,flowers).likes(John,Mary).likes(Paul,Mary).提問時應當留意：⑴？—likes(John,x)①x=flowers ↘只有一個結果，便可回車②x=flowers ；假設再連續(xù)查找，John還寵愛什么，用分號，再回車個開頭，即接著上次匹配的下一個數(shù)據(jù)開頭；二是使變量x的事實無效—脫解。⑵假設向John？—likes〔John,x〕x=flowers;x=Mary;no.⑶對JohnMary？—likes(John,x),likes(Mary,x)三．規(guī)章

xJohn和Mary一樣，即，Mary是否也寵愛John留意：1.提問挨次按從左到右進展，每個目標語句之間用“2語句中實現(xiàn)了匹配，則該變量被實化。此時，其余的目標語句中的變量x均被實化，其內(nèi)容與第一個語句實化后的內(nèi)容一樣。3.一個匹配，假設其余都失敗，第一個句子再次往下移動進展其次次實化，直至都滿足，否則當數(shù)據(jù)庫搜尋完畢都不能匹配，則稱整個提問失敗。句型：P:-P1，P2，?Pn.語義：假設P1∩P2∩?∩PnPlikebil，like〔to，.只要湯姆寵愛的比爾也寵愛。如：Likes〔John，x〕:-likes〔x，flowers〕.規(guī)章頭 定義符 規(guī)章體 完畢符上句規(guī)章的含義是：假設x寵愛花，則John例：buy〔x，car〕:-have〔x,money〕.假設某人有錢，則他就買汽車Bir:-anima〔feather.如x是動物且有羽毛，則就是鳥Siste〔y:-femal〔,patent〔xfparent〔yf，m〕假設x是女的，并且xyxy連接，表示“與”關系。通常一個謂詞〔如：likes，sister〕能用事實和規(guī)章的混合來定義，如，likes〔John，food〕.Likes〔John,x〕:-person〔x〕.這些事實和規(guī)章稱為一階謂詞的子句，以后每當我們涉及一個事實和一個規(guī)章時，則用子句來統(tǒng)稱。關于規(guī)章定義中的兩個概念：常量：PROLOG即：原子和整數(shù)。

以小寫字母開頭的字母數(shù)字串，john,talk,like，sister原子 僅由符號組成=，→：—，？—常量整數(shù)通常意義下的整數(shù)，由數(shù)學組成，不包括小數(shù)點原子是構成各種事實或規(guī)章的根本符號。變量：_有“_”,，如Input，Who，_3_blind_men，?它用來代表某些尚不能命名的對象，它好象代詞。寵愛John但并不需要知道到底是誰寵愛他，這時可以用無名變量來問。johlikes〔_,john〕.無名變量的使用，往往發(fā)生在當表達某一事情時，并不關心事情中某一變量到底代表什么具體對象，而只需要關心它的存在。四.詢問句型：？－P1，P2，?，Pn.語義：P1∩P2∩?∩Pn例： likes〔x，reading〕andlikes〔x，swimming〕.誰寵愛讀書又寵愛游泳雖然用戶可以在任何時候向PROLOG提任何問題，但一般而言，程序員總是先把事實和規(guī)章供給應PROLOG，然后再詢問有關問題。PROLOGPROLOG的數(shù)據(jù)庫中去找是否有這樣一個事實或規(guī)章。假設答復為yes，則成功，否則為no，有兩種含義，一是不或沒有等，二是不知道。PROLOG中的變量可以是被實例化的一個變量被實例化是指這個變量代表一個確定的對象，一個變量未被實例化是指當這個變量所代表的東西還不知道。因此，PROLOG允許一個未實例化的變量匹配任何一個對象。設事實庫：likes〔john,flowers〕.Likes〔john,wine〕.Likes〔Paul，wine〕.Likes〔Paul,john〕.考慮下面的一組提問：？—like〔john,，likePaul,.這個語句有兩個目標組成，每個目標包含一個x，像規(guī)章一樣，這兩個x表示同一個對象。當PROLOG收到這個詢問，它首先企圖滿足第一個目標，找是否有某樣東西x，john寵愛。在第一個目標匹配第一個事實，變量x被實例化，比方flowers，PROLOGPaulflowers，但此時失敗，于是，PROLOG回溯到第一個目標，企圖重滿足這個目標，此時，它首先把x脫解為未實例化的，然后從其次個事實開頭往下查找。當找到其次個事實匹配目標時，于是，這次x實例化為wine，現(xiàn)在其次個目標中x也為wine，這樣likes〔Paul，wine〕匹配第三個事實，最終答復x=wine。PROLOG中規(guī)章和詢問中的變量的作用域僅是這個規(guī)章和這個詢問，一旦某個變量，如x被實例化為某個對象，則在同一作用域內(nèi)的全部x都被實例化為某個對象，在PROLOG例：假設一個人是小偷，并且他寵愛某樣東西，則這個人可能會偷這個東西，假設存在事實庫：thief〔John〕.Likes〔Paul，food〕.Likes〔John，wine〕.May_steal〔John，x〕.提問：？—_may_steal(John,x).PROLOG①首先搜尋may_stealJohnx，問題x匹配規(guī)章中的y，則稱規(guī)章中的x被問題中的xx和規(guī)章中的y對象。②thiex〕和like〔，yx被John實例化。③其次個匹配規(guī)章like，y，因x=Johlike〔Pau，。④子目標likes〔Paul，x〕與likes〔Paul，food〕匹配。⑤X被實例化為food，由共享原則，y也實例化為food。⑥依次返回，整個匹配成功，則x=food。五．幾點說明回溯問題的進一步爭論PROLOG利用的子句〔事實或規(guī)章〕來滿足這些目標〔只有匹配目標的子句才被利用。一個事實能引起一個目標馬上被滿足還不滿足計算時你詢問的答復，則打入“打算是否匹配的法則①一個未實例化的變量將匹配任何對象作為匹配結果或此變量被實例化 后化為那個對象或與它們共享；②一個整數(shù)或原子將只匹配它自己；③一個構造將匹配另一個具有一樣函數(shù)符號和一樣變元個數(shù)的構造。PROLOG④宣稱有關對象及其之間關系的事實；⑤定義有關對象及其之間關系的規(guī)章；⑥對對象及其關系進展提問。其他⑦在使用PROLOGwine，假設定義為like〕則時間久就會不知道此語句是什么意思了。因此在選取變量名時盡量使用事實與問題，比較清楚，真實。⑧在PROLOG程序中，可以用“/*”和“*/”參加注釋，幫助對事實和規(guī)章庫的治理。第四節(jié)PROLOG一． 有關項的概念PROLOG供給了一個全都的數(shù)據(jù)構造稱為項，全部的數(shù)據(jù)和PROLOG程序都是由項構造而成的。項的定義用BNF〈項|〕即，項可以是變量、常量、構造或括在括號中的項。構造—或稱為復合項，它是由一組其他對象組成的單個對象，這些其他對象稱為它的成分，把幾個成分組合成一個構造作為單個對象是很有用處的。}〕〈函數(shù)符〉∷=〈原子〉下面是一些構造的例子：Owns〔john，book〕Owns〔john，book〔pnday，author〔clocksin，McLeish〕〕A〔b，c，d〕+〔3，*〔5，2〕或3+5*2 ?二．PROLOG在PROLOG比較謂詞兩個關系表達式之間的關系符有：<，<=，=，>,>=,<>算術運算謂詞：+，-，*，/算術函數(shù)：random〔x〕 把x約束為一個大于0小于1的隨機數(shù)Round〔x〕 返回x的四舍五入數(shù)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的自然對數(shù)Log〔x〕 返回x的以10為底的對數(shù)Sqrt〔x〕 返回x的平方根輸入/輸出謂詞①writlist1，l“l(fā)ist2，l〕.l1a，b]，l2[1，2]，則結果list1=[a，b]，list2[1，2]。②nl③readln〔line〕變量line輸入一個串給line64k，每個串以回車完畢。④readint〔x〕 x輸入一個整數(shù)給x。⑤readreal〔x〕x輸入一個實型數(shù)給x。⑥r(nóng)eadchar〔charparam〕 charparam為字符型變量；輸入一個字符給charparam。掌握謂詞用于掌握PROLOG程序運行及其推理求解而設立的①fail表示失敗，即推理求解過程失敗。用fail作為子目PROLOG程序運行到fail，必引起回溯〔即強制回溯；的回溯是不行能的。截斷元素主要用于兩個方面。ⅰ〕當事先知道不行能產(chǎn)生有意義的解，且回溯會鋪張時間和空間，使用截斷能加快程序運行且能節(jié)約空間。ⅱ〕程序的規(guī)律構造在下述三種狀況下，需要用截斷謂詞：用它阻擋對規(guī)章中的前幾個子目標的回溯，例如：ra,bc 這是我們僅對子目標的a,b興趣用它來阻擋對下一個子句的回溯r的三個子句R1：—，，，cR：—，dR3：—e兩截斷詞使r1r2r3用它來將非確定性子句轉化為確定性的子句。三．PROLOGfdfdcahebgi圖2.2 建筑物平面圖所謂“迷宮”問題，即迷宮搜尋〔SearchingMaze〕問題。設某建筑物有在哪個房間，何處是出口，因此需要搜尋。當找到建筑物出口時，假設已經(jīng)找到了有的房間，那么搜尋完畢。該建筑物各房間可以自由出入為此，在搜尋過程中需要有個登記表，記錄已搜尋過的房間。這樣，凡登記表上有的房間號不再搜尋，凡沒有登記過的，可進展搜尋并登記房間號。如此，邊搜尋邊登記，直到找到出口而且在登記表中已有的房間號為止。該建筑物的平面構造如下圖。其中，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〕中，則不再搜尋，返回①；④是都出口？⑤假設為出口，且在房間中有，則搜尋成功，則表中所登記的搜尋路徑即為問題的解，停頓搜尋，打印搜尋路徑。⑥假設不符合，返回①，連續(xù)搜尋。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子