人工智能實(shí)驗(yàn)指導(dǎo)書

人工智能實(shí)驗(yàn)指導(dǎo)書軟件工程教研室遼寧工業(yè)大學(xué)2008年9月目 錄實(shí)驗(yàn)一 Prolog初識(shí) 1實(shí)驗(yàn)二 數(shù)據(jù)結(jié)構(gòu)與列表 4實(shí)驗(yàn)三 經(jīng)典問題舉例 12實(shí)驗(yàn)四 專家系統(tǒng) 16實(shí)驗(yàn)五 五子棋游戲 22實(shí)驗(yàn)一 Prolog初識(shí)一、實(shí)驗(yàn)?zāi)康?、熟悉AmziProlog 運(yùn)行環(huán)境；2、掌握PROLOG語(yǔ)言中常量、變量的表示方法；3、掌握利用 PROLOG進(jìn)行事實(shí)庫(kù)、規(guī)則庫(kù)的編寫方法；4、掌握利用 PROLOG中的謂詞 assert 和retract 進(jìn)行數(shù)據(jù)管理。二、相關(guān)知識(shí)1、Prolog 簡(jiǎn)介Prolog在英語(yǔ)中的意思就是ProgramminginLogic（邏輯編程）。它是建立在邏輯學(xué)的理論基礎(chǔ)之上的，最初是運(yùn)用于自然語(yǔ)言的研究領(lǐng)域。然而現(xiàn)在它被廣泛的應(yīng)用在人工智能的研究中，它可以用來(lái)建造專家系統(tǒng)、自然語(yǔ)言理解、智能知識(shí)庫(kù)等。同時(shí)它對(duì)一些通常的應(yīng)用程序的編寫也很有幫助。使用它能夠比其他的語(yǔ)言更快速地開發(fā)程序，因?yàn)樗木幊谭椒ǜ笫鞘褂眠壿嫷恼Z(yǔ)言來(lái)描述程序。本門課程實(shí)驗(yàn)程序?qū)⒃?/p>

AmziProlog

上實(shí)現(xiàn)。2、AmziProlog

的使用1)在桌面上為 AmziProlog建一快捷方式，執(zhí)行文件為 d:\AmziProlog\bin\wideW.exe。在d盤建一prologxx（xx為學(xué)號(hào)后兩位）文件夾，用以保存同學(xué)們自己的程序。3)編輯AmziProlog程序：執(zhí)行桌面上AmziProlog快捷方式，在AmziProlog集成環(huán)境中新建（或打開）一Prolog程序，并保存到d:\prologxx文件夾中。4)運(yùn)行程序：選擇菜單項(xiàng)Listener—Start（打開“解釋器”），之后選擇菜單Listener—Consult,在打開窗口中打開保存過的文件，然后就可以在“解釋器”的“?-”提示符后輸入要查詢的問題了。5）如需修改程序，應(yīng)先關(guān)閉“解釋器” ，修改完程序并保存后，再執(zhí)行 4）步進(jìn)入。三、實(shí)驗(yàn)內(nèi)容及步驟新建一文件： ，保存至 d:\prologxx在該文件中建立如下事實(shí)數(shù)據(jù)庫(kù)：like(ellen,tennis).like(john,football).like(tom,baseball).like(eric,swimming).like(mark,tennis).like(tom,tennis).注：謂詞名（如： like）和常量（如： mark）用小寫字母，每條語(yǔ)句以點(diǎn)‘ .’結(jié)束。請(qǐng)進(jìn)入解釋器詢問吧。查詢1：?-like(mark,tennis).{查詢的目標(biāo)(goal)}yes.{有某個(gè)事實(shí)與目標(biāo)匹配，查詢成功，回顯'yes.'}查詢2：?-like(mark,football).no.{沒有與目標(biāo)匹配的事實(shí)，查詢失敗，回顯'no.'}查詢3：?-like(X,tennis).{X為變量（大寫），匹配中X與ellen被綁定}X=ellen{按回車鍵}yes.{表示還有答案}如果用戶輸入分號(hào)(;)，Prolog就開始尋找其他的答案。首先它必須釋放（unbinds）變量X。然后從上一次成功的位置的下一條子句開始繼續(xù)搜索。這個(gè)過程叫做回溯（backtracking）。?-like(X,tennis).X=ellen；X=mark；X=tom；no{表示沒有答案了}查詢4：?-like(X,tennis),!.X=ellen；no截?cái)嘀^詞cut，prolog內(nèi)部謂詞，使用符號(hào)！來(lái)表示。cut能夠有效地抑制其左邊的子目標(biāo)與其父目標(biāo)的回溯，而它右邊的目標(biāo)則不受影響,如下面查詢：?-like(X,tennis),!like(tom,Y),查詢5：讓我們來(lái)控制一下輸出吧，退出解釋器，在數(shù)據(jù)庫(kù)中加入如下規(guī)則，并保存。do:-like(X,tennis),write(X),tab(2),write('liketennis.').重新進(jìn)入解釋器。?-do.ellen liketennis.yes注：:-即為←。謂詞之間的逗號(hào)表示‘與’的關(guān)系。write()為Prolog實(shí)現(xiàn)輸出內(nèi)部謂詞，每次輸出一項(xiàng)內(nèi)容。tab(2)Prolog內(nèi)部謂詞，實(shí)現(xiàn)輸出兩個(gè)空格。查詢6：讓我們調(diào)用 debug來(lái)觀察一下查詢的過程。?-debug.??-do. {進(jìn)入debug窗口，用 creep逐步追蹤}注：Prolog的目標(biāo)有四個(gè)端口用來(lái)控制運(yùn)行的流程，每個(gè)端口的功能如下：call（調(diào)用）開始使用目標(biāo)搜尋子句。exit（退出）目標(biāo)匹配成功，在成功的子句上作記號(hào)，并綁定變量。redo（重試）試圖重新滿足目標(biāo)，首先釋放變量，并從上次的記號(hào)開始搜索。fail（失?。┍硎驹僬也坏礁嗟臐M足目標(biāo)的子句了。查詢7：前面這個(gè)查詢只輸出一個(gè)查詢結(jié)果，讓我們?cè)賮?lái)修改一下剛加入的規(guī)則

do。其中

nl

表示換行，fail

強(qiáng)制回溯，直到失敗為止。do:-like(X,tennis),write(X),tab(2),write('liketennis.'),nl,.fail.?-do.ellenliketennismarkliketennistomliketennisno?-debug.{再debug看看吧}??-do.查詢8：動(dòng)態(tài)數(shù)據(jù)庫(kù)管理。?-listing(like).{listing(謂詞名)列出所有該名謂詞}?-assert((like(ellen,football)).{assert或assertz在所有l(wèi)ike謂詞后動(dòng)態(tài)加入新謂詞}?-listing(like).?-asserta((like(ellen,swimming)).{在所有l(wèi)ike謂詞前動(dòng)態(tài)加入新謂詞}?-listing(like).?-retract(like(ellen,football)).{刪除動(dòng)態(tài)加入的新謂詞}?-listing(like).注：assert只動(dòng)態(tài)地將謂詞加入到內(nèi)存數(shù)據(jù)庫(kù)中，并未加入到為件中四、思考題1、試分析 Prolog 的推理方式（正向 /逆向）。2、試分析 Prolog 推理時(shí)，目標(biāo)與子句的匹配順序。實(shí)驗(yàn)二 數(shù)據(jù)結(jié)構(gòu)與列表一、實(shí)驗(yàn)?zāi)康?.了解

PROLOG中數(shù)據(jù)結(jié)構(gòu)和列表的設(shè)計(jì)與使用。2.了解

PROLOG中利用列表實(shí)現(xiàn)遞歸方法。二、實(shí)驗(yàn)內(nèi)容及步驟1、數(shù)據(jù)結(jié)構(gòu)除了前面實(shí)驗(yàn)用到的事實(shí)、查詢以及規(guī)則中的簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)外， Prolog還可以通過把這些簡(jiǎn)單的數(shù)據(jù)組合起來(lái)，生成復(fù)雜的數(shù)據(jù)類型，我們稱之為結(jié)構(gòu)。結(jié)構(gòu)由結(jié)構(gòu)名和一定數(shù)量的參數(shù)組成，結(jié)構(gòu)的參數(shù)可以是簡(jiǎn)單的數(shù)據(jù)類型或者是另一個(gè)結(jié)構(gòu)。如：結(jié)構(gòu)名(參數(shù)1,參數(shù)2,...)例如，下面的結(jié)構(gòu)描述了物品的顏色、大小以及數(shù)量。object(apple,red,small,1).我們可以把結(jié)構(gòu)用作謂詞的參數(shù)，我們定義一個(gè)謂詞 locat:****************** *********************locat(object(apple,red,small,1),kitchen).locat(object(cabbage,green,small,1),kitchen).locat(object(radish,red,small,1),kitchen).locat(object(table,blue,big,1),kitchen).locat(object(chair,blue,small,6),kitchen).locat(object(computer,while,small,2),office).locat(object(book,various,small,many),office).對(duì)于這段描述我們可以進(jìn)行如下詢問：?-locat(X,kitchen).X=object(apple,red,small,1);X=object(cabbage,green,small,1);X=object(radish,red,small,1);X=object(table,blue,big,1);X=object(chair,blue,small,6);noProlog變量是沒有數(shù)據(jù)類型之分的，所以它可以很容易的綁定為結(jié)構(gòu)，如同它綁定為原子一樣。事實(shí)上，原子就是沒有參數(shù)的最簡(jiǎn)單的結(jié)構(gòu)。我們還可以讓變量綁定為結(jié)構(gòu)中的某些參數(shù)，如下面的詢問可以找出廚房中所有紅色的東西。?-locat(object(X,red,S,W),kitchen).X=appleS=smallW=1;X=radishS=smallW=1;no如果不關(guān)心大小和數(shù)量，可以使用下面的詢問，其中變量 ‘_是’匿名變量。?-locat(object(X,red,_,_),kitchen).X=apple;X=radish;no讓我們添加如下謂詞，使得只有在物品所在的房間且物品較輕的才能被拿起。here(kitchen).cantake(Thing):-here(Room),locat(object(Thing,_,small,_),Room).看一看如下查詢的結(jié)果吧。?-cantake(apple).?-cantake(table).?-cantake(book).同時(shí)，也可以把不能拿取某物品的原因說(shuō)得更詳細(xì)一些，例如添加如下規(guī)則：cantake(Thing):-here(Room),locat(object(Thing,_,big,_),Room),write('The'),write(Thing),write('istoobigtocarry.'),nl,fail.cantake(Thing):-here(Room),not(locat(object(Thing,_,_,_),Room)),write('Thereisno'),write(Thing),write('here.'),nl,fail.下面來(lái)試試功能。?-cantake(table).?-cantake(book).?-cantakes(desk).結(jié)構(gòu)可以任意的嵌套，例如：locat(object(desk,color(brown),size(large),amount(1)) ，office).下面是針對(duì)它的一條查詢。?-locat(object(X,_,size(large),_),office).列表為了能夠更好地表達(dá)一組數(shù)據(jù)，簡(jiǎn)化程序， Prolog引入了列表這種數(shù)據(jù)結(jié)構(gòu)。列表是一組項(xiàng)目的集合，此項(xiàng)目可以是Prolog的任何數(shù)據(jù)類型，包括結(jié)構(gòu)和列表。列表的元素由方括號(hào)括起來(lái)，項(xiàng)目中間使用逗號(hào)分隔。例如下面的列表列出了廚房中的物品。[apple,cabbage,radish,table]我們可以使用列表來(lái)代替多個(gè)子句。例如：locate(apple,kitchen).locate(cabbage,kitchen).locate(radish,kitchen).locate(table,kitchen).可表示成：********************************loclist([apple,cabbage,radish,table],kitchen).當(dāng)某個(gè)列表中沒有項(xiàng)目時(shí)我們稱之為空表，使用的句子表示 hall中沒有東西。

“[]表”示。也可以使用

nil

來(lái)表示。下面loclist([],hall)變量也可以與列表聯(lián)合

,就像它與其他的數(shù)據(jù)結(jié)構(gòu)聯(lián)合一樣。

假如數(shù)據(jù)庫(kù)中有了上面的子句，就可以進(jìn)行如下的詢問。?-loclist(X,kitchen).X=[[apple,cabbage,radish,table]?-[_,X,_]=[apples,cabbage,radish].X=cabbageProlog提供了兩個(gè)特性，可以方便的實(shí)現(xiàn)對(duì)列表元素的訪問。首先， Prolog提供了把表頭項(xiàng)目與列表剩下部分分離的方法。其次， Prolog強(qiáng)大的遞歸功能可以方便地訪問除去表頭項(xiàng)目后的列表。首先，列表的一般形式為： [X|Y]使用此列表可以與任意的列表匹配，匹配成功后， X綁定為列表的第一個(gè)項(xiàng)目的值，我們稱之為表頭（ head）。而Y則綁定為剩下的列表，我們稱之為表尾（ tail)。下面我們看幾個(gè)把表頭項(xiàng)目與列表剩下部分分離例子：?-[a|[b,c,d]]=[a,b,c,d]. {等號(hào)兩邊的列表是等價(jià)的 }yes?-[a|b,c,d]=[a,b,c,d]. {在“|”之后只能是一個(gè)列表，而不能是多個(gè)項(xiàng)目。 }no注意：表尾一定是列表，而表頭則是一個(gè)項(xiàng)目，即可以是表，也可以是其他的任何數(shù)據(jù)結(jié)構(gòu)。下面是其它的一些列表的例子。?-[H|T]=[apple,cabbage,radish,table].H=appleT=[cabbage,radish,table]?-[H|T]=[a,b,c,d,e].H=aT=[b,c,d,e]?-[H|T]=[a,b].H=aT=[b]?-[H|T]=[a,[b,c,d]]. {這個(gè)例子中的第一層列表有兩個(gè)項(xiàng)目 a和[b,c,d]。}H=aT=[[b,c,d]]?-[H|T]=[a]. {列表中只有一個(gè)項(xiàng)目的情況 }H=aT=[]?-[H|T]=[]. {空表不能與[H|T]匹配，因?yàn)樗鼪]有表頭。 }no注意：最后這個(gè)匹配失敗非常重要，在遞歸過程中經(jīng)常使用它作為邊界檢測(cè)。即只要表不為空，那么它就能與 [X|Y]匹配，當(dāng)表為空時(shí)，就不能匹配，表示已經(jīng)到達(dá)邊界條件。我們還可以在第二個(gè)項(xiàng)目后面使用 “|，”事實(shí)上，“|前”面的都是項(xiàng)目，后面的是一個(gè)表。?-[One,Two|T]=[a,b,c,d].One=aTwo=bT=[c,d]表可以看作是表頭項(xiàng)目與表尾列表組合而成。而表尾列表又是由同樣的方式組成的。所以表的定義本質(zhì)上是遞歸定義。我們來(lái)看看下面的例子。?-[a|[b|[c|[d|[]]]]]=[a,b,c,d].Yes?-X=[a,b,c,d],write(X),nl,display(X),nl. {內(nèi)部謂詞 display以遞歸的方式顯示列表 }[a,b,c,d].(a,.(b,.(c,.d(,[]))))?-X=[a,b,[c,d],e],write(X),nl,display(X),nl.[a,b,[c,d],e].(a,.(b,.(.(c,.(d,[])),.(e,[]))))3.用遞歸處理列表首先我們來(lái)編寫謂詞 member，它能夠判斷某個(gè)項(xiàng)目是否在列表中。*************** L ****************member(H,[H|T]).member(X,[H|T]):-member(X,T).第一個(gè)子句是遞歸的邊界條件， 即如果H表示的項(xiàng)目是列表的表頭則匹配成功， 遞歸過程結(jié)束。第二個(gè)子句表示：如果 X表示的項(xiàng)目不是列表的表頭，則讓 X與列表的的表尾匹配。把上面的兩個(gè)子句放入一 prolog文件中，讓我們來(lái)詢問一下吧。?-member(apple,[apple,cabbage，radish]).yes?-member(cabbage,[apple,cabbage，radish]).yes?-member(banana,[apple,cabbage，radish]).no?-debug. {請(qǐng)觀察一下單步運(yùn)行的結(jié)果吧 }??-member(b,[a,b,c]).如果詢問的第一參數(shù)是變量， member/2可以把列表中所有的項(xiàng)目找出來(lái)。?-member(X,[apple,broccoli,crackers]).X=apple;X=broccoli;X=crackers;No打印表中元素的例子：*******************************write_a_list([]).write_a_list([H|T]):-write(H),nl,write_a_list(T).?-write_a_list([1,2,3]).我們?cè)賮?lái)編寫能夠把兩個(gè)列表連接成一個(gè)列表的謂詞 append/3。*****************************append([],X,X).append([H|L1],L2,[H|L3]):-append(L1,L2,L3).?-append([a,b,c],[d,e,f],New).

{第一個(gè)參數(shù)和第二個(gè)參數(shù)連接的表為第三個(gè)參數(shù)

}New=[a,b,c,d,e,f]和

member/2

一樣，append/3還有別的使用方法。下面這個(gè)例子顯示了

append/3是如何把一個(gè)表分解的。?-append(X,Y,[a,b,c]).X=[]Y=[a,b,c];X=[a]Y=[b,c];X=[a,b]Y=[c];X=[a,b,c]Y=[];no3．使用列表現(xiàn)在有了能夠處理列表的謂詞，我們可以完成一個(gè)小游戲。在廚房、書房等處分別有一些物品，并可以向這些地方添加物品。****************************************loclist([apple,cabbage,radish,table],kitchen).loclist([desk,computer,book],office).loclist([flashlight,envelope],desk).loclist([stamp,key],envelope).loclist(['washingmachine'],cellar).loclist([nani],'washingmachine').member(H,[H|T]).member(X,[H|T]):-member(X,T).location(X,Y):-loclist(List,Y),member(X,List).

{判斷

X

物品是否在

Y中}append([],X,X).append([H|L1],L2,[H|L3]):-append(L1,L2,L3).add_thing(New,Container,NewList):-loclist(OldList,Container),append([New],OldList,NewList). {向Container

中添加新物品

New，形成新列表

NewList}put_thing(Thing,Place):-retract(loclist(OldList,Place)),asserta(loclist([Thing|List],Place)).

{動(dòng)態(tài)修改數(shù)據(jù)庫(kù)

}我們可以進(jìn)行詢問了。?-add_thing(plum,kitchen,X).X=[plum,apple,broccoli,crackers]當(dāng)然，也可以直接使用 [Head|Tail]這種列表結(jié)構(gòu)來(lái)編寫 add_thing/3。add_thing2(NewThing,Container,NewList):-loc_list(OldList,Container),NewList=[NewThing|OldList].它和前面的 add_thing/3功能相同。?-add_thing2(plum,kitchen,X).X=[plum,apple,broccoli,crackers]我們還可以對(duì) add_thing2/3進(jìn)行簡(jiǎn)化，不是用顯式的聯(lián)合，而改為在子句頭部的隱式聯(lián)合。add_thing3(NewTh,Container,[NewTh|OldList]):-loclist(OldList,Container).它同樣能完成我們的任務(wù)。?-add_thing3(plum,kitchen,X).X=[plum,apple,broccoli,crackers]下面的put_thing/2，能夠直接修改動(dòng)態(tài)數(shù)據(jù)庫(kù)，請(qǐng)自己研究一下。三、思考題1、Prolog變量是否有數(shù)據(jù)類型之分。2、Prolog中的變量和常量是如何區(qū)分的。實(shí)驗(yàn)三 經(jīng)典問題舉例一、實(shí)驗(yàn)?zāi)康?、理解PROLOG編制遞歸程序的方法：邊界條件與遞歸部分的設(shè)計(jì)；2、加深理解人工智能中通過搜索解決問題的方法；3、熟悉分析、運(yùn)用遞歸方法解決問題。二、實(shí)驗(yàn)內(nèi)容及步驟（一)Hanoi 塔問題：如上圖，目的是把左邊的所有盤子移到右邊的桿子上。一次只能移動(dòng)一個(gè)盤子，可以使用中間的桿子作為臨時(shí)存放盤子的地方。在移動(dòng)的過程中，小盤子必須放在大盤子之上。分析：用遞歸來(lái)解決這個(gè)問題。如果只有一個(gè)盤子，直接移過去就行了，這是遞歸的邊界條件。如果要移動(dòng) N個(gè)盤子，就要分三步走：1、把N-1個(gè)盤子移動(dòng)到中間的桿子上（把右邊的桿子作為臨時(shí)存放盤子的位置）2、把最后一個(gè)盤子直接移到右邊的桿子上。3、最后把中間桿子上的盤子移到右邊的桿子上（把左邊的桿子作為臨時(shí)存放盤子的位置）上面第一、三步用到了遞歸。我們看到，通過遞歸把 N個(gè)盤子的問題變成了兩個(gè)子的問題。如此下去，最后就變成了 2個(gè)一個(gè)盤子的問題了，這也就是說(shuō)問題被解決了。

。N-1個(gè)盤1）Hanoi塔的Prolog代碼：hanoi(N):-move(N,left,middle,right).move(1,A,_,C):-inform(A,C),!. {! 為cut操作，截?cái)噙M(jìn)一步搜索 }move(N,A,B,C):-N1isN-1,move(N1,A,C,B),inform(A,C),move(N1,B,A,C).inform(Loc1,Loc2):-nl,write('Moveadiskfrom'-Loc1-'to'-Loc2).-hanoi(3).主程序?yàn)?hanoi，它的參數(shù)為盤子的數(shù)目。它調(diào)用遞歸謂詞 move來(lái)完成任務(wù)。三個(gè)桿子的名字分別為left 、middle、right 。第一個(gè)move子句是邊界情況，即只有一個(gè)盤子時(shí)， 直接調(diào)用 inform 顯示移動(dòng)盤子的方法。后面使用 cut，是因?yàn)椋喝绻挥幸粋€(gè)盤子，就是邊界條件，無(wú)需再對(duì)第二條子句進(jìn)行匹配了。第二個(gè)move子句為遞歸調(diào)用，首先把盤子數(shù)目減少一個(gè)，再遞歸調(diào)用move，把N-1個(gè)盤子從A桿通過C桿移到B桿，再把A桿上的最后一個(gè)盤子直接從A桿移到C桿上，最后再遞歸調(diào)用move，把B桿上的N-1個(gè)盤子通過A桿移到C桿上。這里的桿子都是使用變量來(lái)代表的，A、B、C桿可以是left、middle、right中的任何一個(gè)，這是在移動(dòng)的過程中決定的。inform ，把移動(dòng)過程通過 write 謂詞寫出，由于write 只能有一個(gè)參數(shù)， 所以使用“-”操作符相連。2）Hanoi塔的C語(yǔ)言代碼：#include<stdio.h>voidhanoi(intn,charA,charB,charC){if(n==1)printf("Movedisk%dfrom%cto%c\n",n,A,C);else{hanoi(n-1,A,C,B);printf("Movedisk%dfrom%cto%c\n",n,A,C);hanoi(n-1,B,A,C);}}main(){intn;printf("Entern:\n");scanf("%d",&n);hanoi(n,'A','B','C');getch();}（二)簡(jiǎn)化的騎士周游問題123在國(guó)際象棋中，騎士可以橫向或縱向移動(dòng)兩個(gè)方格后再沿垂直方向移動(dòng)456一個(gè)方格（只要不超出棋盤）。如：從3格可走到4或8格。本問題要求在一個(gè)3*3棋盤上，尋找一系列合法移動(dòng)，使騎士可以從一個(gè)方格移到另一個(gè)方789格。此問題可用狀態(tài)空間或產(chǎn)生式系統(tǒng)搜索。下面是狀態(tài)空間搜索的程序：*********************************move(1,6).move(3,4).move(6,7).move(8,3).{move謂詞列出了所有合法移動(dòng)}move(1,8).move(3,8).move(6,1).move(8,1).move(2,7).move(4,3).move(7,6).move(9,4).move(2,9).move(4,9).move(7,2).move(9,2).member(H,[H|T]).member(X,[H|T]):-member(X,T).path(Z,Z,L).path(X,Y,L):-move(X,Z),not(member(Z,L)),

{

用列表

L來(lái)記錄走過的方格

}write('-'),write(Z),path(Z,Y,[Z|L]).do(X,Y):-write('Thepathis:'),path(X,Y,[X]).?-do(1,3).Thepathis:-6-7-2-9-4-3Yes?-do(5,6).Thepathis:no試分析其遞歸調(diào)用的過程。（三）過河問題用C語(yǔ)言解決的過河問題。#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX_STEP20/*index:0- 狼，1－羊，2－菜，3－農(nóng)夫，value：0－本岸，1－對(duì)岸*/inta[MAX_STEP][4];intb[MAX_STEP];char*name[]={"takenone","takewolf","takegoat","takevegetable"};voidsearch(intiStep){inti;if(a[iStep][0]+a[iStep][1]+a[iStep][2]+a[iStep][3]==4){for(i=0;i<iStep;i++)if(a[i][3]==0)printf("%sarrive\n",name[b[i]+1]);elseprintf("%sback\n",name[b[i]+1]);printf("\n");return;}for(i=0;i<iStep;i++)if(memcmp(a[i],a[iStep],sizeof(a[i]))==0)return;if(a[iStep][1]!=a[iStep][3]&&(a[iStep][2]==a[iStep][1]||a[iStep][0]==a[iStep][1]))return;for(i=-1;i<=2;i++){b[iStep]=i;memcpy(a[iStep+1],a[iStep],sizeof(a[iStep+1]));a[iStep+1][3]=1-a[iStep+1][3];if(i==-1)search(iStep+1);elseif(a[iStep][i]==a[iStep][3]){a[iStep+1][i]=a[iStep+1][3];search(iStep+1);}}}intmain(){search(0);getch();return0;}三、思考題1、對(duì)于騎士周游問題，當(dāng)問題規(guī)模變大，如 8*8棋盤，用狀態(tài)空間搜索是否還適用？2、騎士周游問題用產(chǎn)生式如何表示其移動(dòng)規(guī)則？實(shí)驗(yàn)四 專家系統(tǒng)一、實(shí)驗(yàn)?zāi)康?、掌握專家系統(tǒng)的基本原理和實(shí)現(xiàn)方法；2、構(gòu)建簡(jiǎn)單的專家系統(tǒng)。二、實(shí)驗(yàn)內(nèi)容構(gòu)建一簡(jiǎn)單的動(dòng)物識(shí)別系統(tǒng)。

該系統(tǒng)向用戶提問該動(dòng)物是否具有的屬性，

根據(jù)用戶的回答，來(lái)判斷是哪一種動(dòng)物。該系統(tǒng)可識(shí)別

albatross

（信天翁）

,penguin

（企鵝）

,ostrich

（鴕鳥）,zebra

（斑馬），giraffe

（長(zhǎng)頸鹿）

,tiger

（老虎）

,cheetah

（印度豹）。動(dòng)物屬性有："chew_cud"（反芻）,"hooves"（蹄）,"mammal"（哺乳動(dòng)物）,"forward_eyes"（目視前方）,"claws"（爪）,"pointed_teeth"（尖牙，犬齒）,"eat_meat","lay_eggs","fly","feathers","ungulate" （有蹄動(dòng)物）,"carnivore" （食肉動(dòng)物） ,"bird","give_milk","has_hair","fly_well","black&white_color","can_swim","long_legs","long_neck","black_stripes"( 黑條紋),"dark_spots","tawny_color"( 茶色)下例用C++實(shí)現(xiàn)了一個(gè)簡(jiǎn)易的源程序如下：#include<string.h>#include<math.h>#include<stdio.h>#include<iostream.h>#defineTrue1#defineFalse0#defineDontKnow-1char*str[]={"chew_cud","hooves","mammal","forward_eyes","claws","pointed_teeth","eat_meat","lay_eggs","fly","feathers","ungulate","carnivore","bird","give_milk","has_hair","fly_well","black&white_color","can_swim","long_legs","long_neck","black_stripes","dark_spots","tawny_color","albatross","penguin","ostrich","zebra","giraffe","tiger","cheetah",0};intrulep[][6]={{22,23,12,3,0,0},{21,23,12,3,0,0},{22,19,20,11,0,0},{21,11,0,0,0,0},{17,19,20,13,-9,0},{17,18,13,-9,0,0},{16,13,0,0,0,0},{15,0,0,0,0,0},{14,0,0,0,0,0},{10,0,0,0,0,0},{8,7,0,0,0,0},{7,0,0,0,0,0},{4,5,6,0,0,0},{2,3,0,0,0,0},{1,3,0,0,0,0}};intrulec[]={30,29,28,27,26,25,24,3,3,13,13,12,12,11,11,0};classfact{private:intNumber;charName[21];intActive;intSucc;public:fact*Next;fact(intNum,char*L){strcpy(Name,L);Number=Num;Active=False; //-1 是已經(jīng)推理，不符合。是已經(jīng)推理，符合。Succ=DontKnow; //0 是無(wú)，-1是不知道，1是有。Next=NULL; }char*GetName(){char*L;L=newchar[21];strcpy(L,Name);returnL; }intGetNumber(){returnNumber;

}intGetAct(){returnActive;

}intGetSucc(){returnSucc;

}voidPutAct(constintAct0,intSuc0){Active=Act0;Succ=Suc0;}};fact*Fact;classlist{private:intNumber;public:list*Next;list(intNum){Number=Num;Next=NULL;}intGetNumber(){ returnNumber;

}};classrule{char*Name;list*Pre;intConc;public:rule*Next;rule(char*N,intP[],intC);~rule();intQuery();voidGetName(){ cout<<Name; }};rule::~rule(){list*L;while(Pre){L=Pre->Next;deletePre;Pre=L;}deleteName;}rule::rule(char*N,intP[],intC){inti;list*L;Name=newchar[strlen(N)+1];strcpy(Name,N);i=0;while(P[i]!=0){L=newlist(P[i++]);L->Next=Pre;Pre=L;Conc=C;}intrule::Query(){charc;intTag=0;list*L;fact*F;F=Fact;L=Pre;if(L==NULL)cout<<"\nError";while(L!=NULL){F=Fact;for(;;){if(abs(L->GetNumber())==F->GetNumber())break;F=F->Next;}if(L->GetNumber()>0){if((F->GetSucc())==True){L=L->Next;continue;}if((F->GetSucc())==False)returnFalse;}else{if((F->GetSucc())==True)returnFalse;if((F->GetSucc())==False){L=L->Next;continue; }}cout<<F->GetName()<<"(Y/N)"<<endl;c=getchar();flushall();if((c=='Y')||(c=='y')){if(L->GetNumber()>0)F->PutAct(1,True);if(L->GetNumber()<0){F->PutAct(1,True);Tag=-1;returnFalse; }}else{if(L->GetNumber()<0)F->PutAct(-1,False);else{F->PutAct(-1,False);Tag=-1;

// 已經(jīng)推理，不符合。returnFalse; }}L=L->Next;}F=Fact;for(;;){if(Conc==F->GetNumber())break;F=F->Next; }if(Conc<24){F->PutAct(1,True);returnFalse;}if(Tag!=-1){F=Fact;for(;;){if(Conc==F->GetNumber())break;F=F->Next; }if(Conc<24){F->PutAct(1,True);returnFalse; }cout<<"\nThisaniamalis"<<F->GetName()<<endl;returnTrue;}returnFalse;}intmain(){fact*F,*T;rule*Rule,*R;charch[8];inti=1;while(str[i-1]){F=newfact(i,str[i-1]);

// 初始化事實(shí)庫(kù)，倒序排列。F->Next=Fact;Fact=F;i++;}F=Fact;Fact=NULL;while(F){T=F;F=F->Next;T->Next=Fact;Fact=T; }

// 把倒序排列正過來(lái)。i=0;ch[0]='R';ch[1]='U';ch[2]='L';ch[3]='E';ch[4]='_';ch[5]='a';ch[6]='\0';Rule=NULL;for(i=0;i<15;i++)

// 初始化規(guī)則庫(kù)。{R=newrule(ch,rulep[i],rulec[i]);R->Next=Rule;Rule=R;ch[5]++;}for(;;){i=R->Query();if((i==1)||(i==-1))break;R=R->Next;if(!R)break;}if(!R)cout<<"Idon'tknow."<<endl;cout<<"pressanykeytoexit."<<endl;getchar();returnTrue;}三、思考題專家系統(tǒng)用 c++語(yǔ)言+數(shù)據(jù)庫(kù)的解決方案如何實(shí)現(xiàn)？實(shí)驗(yàn)五 五子棋游戲一、實(shí)驗(yàn)?zāi)康?、通過五子棋游戲了解人工智能實(shí)現(xiàn)博弈的方法。2、了解根據(jù)五子棋規(guī)則建立數(shù)學(xué)模型的過程 ,即從現(xiàn)實(shí)抽象到數(shù)學(xué)模型的過程。二、實(shí)驗(yàn)內(nèi)容五子棋規(guī)則：規(guī)則：分黑白兩方，輪流下棋。率先將 5子連線的一方獲勝。目標(biāo)：使機(jī)器在下棋的過程中攻守兼?zhèn)?，就像和一個(gè)真正的人類下棋一樣分析：為了方便說(shuō)明我們以 5X5這個(gè)最簡(jiǎn)單的棋盤來(lái)加以說(shuō)明。棋盤如圖所示：人類在下棋過程中每下一步前都會(huì)思考一下如果我們這樣走了后面會(huì)出現(xiàn)一個(gè)什么樣的情況？走了這步后對(duì)方會(huì)走哪步？如果對(duì)方做了這步后會(huì)是個(gè)什么樣的局面，我可以采取哪些走法？......。經(jīng)歷了預(yù)見，推理，預(yù)見，推理......這樣一個(gè)反復(fù)的過程，然而我們?nèi)四X能力有限，我們能預(yù)見的步數(shù)和記住每步的情況的能力有限制，即使再聰明的人也是有個(gè)限度的。而機(jī)器在記憶這方面卻是絕對(duì)的，所以我們可以模擬人下棋的過程使機(jī)器具備高超的下棋能力。首先需要將搜索的步數(shù)量化，以實(shí)現(xiàn)程序的高速查詢，也就是說(shuō)建立一張?zhí)厥獾摹氨怼?，其中?biāo)明了獲勝的所有情況。那么剩下的事就是實(shí)時(shí)查詢這張表來(lái)作為下一步的依據(jù)。就以上面所說(shuō)，我們采用5X5的棋盤，其獲勝的情況總共有12種，具體情況如下所示：情況坐標(biāo)0(0,0)(1,0)(2,0)(3,0)(4,0)橫向1(0,1)(1,1)(2,1)(3,1)(4,1)2(0,2)(1,2)(2,2)(3,2)(4,2)3(0,3)(1,3)(2,3)(3,3)(4,3)4(0,4)(1,4)(2,4)(3,4)(4,4)5 (0,0) (0,1) (0,2) (0,3) (0,4) 縱向6(1,0)(1,1)(1,2)(1,3)(1,4)7(2,0)(2,1)(2,2)(2,3)(2,4)8(3,0)(3,1)(3,2)(3,3)(3,4)9(4,0)(4,1)(4,2)(4,3)(4,4)10(0,0)(1,1)(2,2)(3,3)(4,4)交叉11(4,0)(3,1)(2,2)(1,3)(0,4)接下來(lái)就考慮怎么很好的利用它。那么在下棋過程中，人們是怎么來(lái)考慮當(dāng)前應(yīng)該下在哪個(gè)格子呢？一般來(lái)說(shuō)就是：看雙方哪些格子可以同時(shí)擁有多種獲勝方式，獲勝方式越多越具優(yōu)勢(shì)。比較雙方最具優(yōu)勢(shì)的格子，若對(duì)方最具優(yōu)勢(shì)格子比自己的的更具優(yōu)勢(shì)，便把棋子下到對(duì)方最具優(yōu)勢(shì)的格子，這樣體現(xiàn)了防守。否則，便把棋子下到自己最具優(yōu)勢(shì)的格子，這樣體現(xiàn)了進(jìn)攻。子有

3

以上兩條可以說(shuō)就是五子棋規(guī)則到編程的抽象。以種獲勝方式，中心點(diǎn)有 4種獲勝方式（以 (0,0)

5X5的棋盤，除了點(diǎn)舉例：即有0,5,10

2條對(duì)角的格三種獲勝方式），其余格子只有兩種獲勝方式。那么剩下的重點(diǎn)就是構(gòu)造一個(gè)評(píng)價(jià)函數(shù)來(lái)決定機(jī)器是防還是攻。接下來(lái)我們加以簡(jiǎn)單的代碼來(lái)說(shuō)明我們這個(gè)簡(jiǎn)單的“人工智能”具體怎么運(yùn)作。首先，我們先來(lái)建立獲勝表：typedefstruct{UINT8

last;

/*0

標(biāo)記該獲勝方式失效

*/UINT16

x[5];UINT16

Y[5];}WLIST;WLISTWLIST

WinListP[12];WinListC[12];

/*/*

人的獲勝表機(jī)器的獲勝表

*/*/如WinListC[12]記錄了上文的12種獲勝方式，我們以WinListC[0]加以說(shuō)明:WinListC[0].last=1;WinListC[0].x[0]=0;

/*1/*

表示獲勝方式有效， 0無(wú)效與上表的情況 0對(duì)應(yīng)，入錄坐標(biāo)

*/*/WinListC[0].y[0]=0;WinListC[0].x[4]=4;WinListC[0].y[4]=0;按照此法將 WinListC[0]--WinListC[11] 都與上表 12種獲勝情況一一對(duì)應(yīng)錄好坐標(biāo)，當(dāng)然WinListP 也與WinListC 一樣。下面請(qǐng)看獲勝表是怎么發(fā)生作用的。比如人把棋子下在(1,1)處，那么對(duì)于機(jī)器來(lái)說(shuō)，所有需要(1,1)組合的獲勝情況都將失效。即上表中擁有 (1,1)的1,6,10情況將失效，對(duì)應(yīng)的 WinListC[1].last=WinListC[6].lastWinListC[10].last=0;機(jī)器在下棋時(shí)，首先掃描棋盤上所有空出的格子，并根據(jù)獲勝表給每個(gè)空格打分。即有1種獲勝方式就給加1分，并調(diào)出得分最高的空格作為即將下的位置。同樣要計(jì)算人情況，得到打分最高的空格。若人得分最高空格比機(jī)器的高，那機(jī)器就把棋子下在人的得分最高空格上，否則就將棋子下在自己得分最高空格上。這樣就把前面的數(shù)學(xué)模型具體化在代碼中了。具體代碼可以這樣：UINT8Chessboard[5][5];/*記錄棋盤落子情況，1為人，2為機(jī)器*/UINT16ScoreP[5][5];/*用于人方每次給空格打分*/UINT16ScoreC[5][5];/*用于機(jī)器方每次給空格打分*/我們還是舉例來(lái)說(shuō)明目前的代碼在程序中是如何發(fā)生作用的：1.還是假如人在(1,1)處落子。2.先標(biāo)記棋盤落子情況，Chessboard[1][1]=1；然后修改機(jī)器方的獲勝表，即需(1,1)組合的1,6,10這3種獲勝方式將失效， WinLis