用Prolog求解傳教士和野人問題

用Prolog求解傳教士和野人問題實驗七用Prolog求解傳教士和野人問題1、實驗目的復習經(jīng)典謂詞演算中的歸結(jié)原理，掌握人工智能程序設計語言Prolog，理解通過搜索求解問題實現(xiàn)人工智能的思想。2、實驗原理謂詞演算中的消解法，3、實驗內(nèi)容設有3個傳教士和3個野人同在河的左岸，他們都要到對岸去;河里只有一條船，他們都會劃船，但每次渡船至多只能乘兩人;如果在任何一邊河岸上，野人的數(shù)量超過傳教士，野人就要吃掉傳教士，問怎樣才能用船將3個傳教士和3個野人從左岸都渡到右岸，又不會發(fā)生傳教士被吃的事件呢,通過Prolog程序，給出乘船過河的動作序列。4、實驗步驟(1)設計該問題的狀態(tài)。例如:((左岸牧師數(shù)，左岸野人數(shù)),(右岸牧師數(shù)，右岸野人數(shù)),船的位置)。(2)定義目標狀態(tài)。這里是:((0,0),(3,3),1)3)描述可能的動作。船上所能夠載人的狀態(tài)就是可能的操作。用謂詞(move表示。(4)判斷合法狀態(tài)(5)深度優(yōu)先搜索三個傳教士和三個野人的示例程序如下:move(1,0).move(0,1).move(0,2).move(2,0).move(1,1).legal((X,Y,_)):-legal1(X),legal1(Y).legal1((X,Y)):-X=:=0,Y>=0,!.legal1((X,Y)):-Y=:=0,X>=0,!.legal1((X,Y)):-X>=Y,X>=0,Y>=0.update((X,Y,0),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC+E,D1isD+F,A1isA-E,B1isB-F,Statu1=((A1,B1),(C1,D1),1).update((X,Y,1),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC-E,D1isD-F,A1isA+E,B1isB+F,Statu1=((A1,B1),(C1,D1),0).connect(Statu,Statu1):-move(X,Y),update(Statu,(X,Y),Statu1),legal(Statu1).findroad(X,X,L,L):-write(L).findroad(X,Y,L,L1):-connect(X,Z),not(member(Z,L)),findroad(Z,Y,[Z|L],L1).傳教士和野人問題有三個牧師和三個野人過河，只有一條能裝下兩個人的船，在河的任何一方或者船上，如果野人的人數(shù)大于牧師的人數(shù)，那么牧師就會有危險。你能不能找出一種安全的渡河方法呢,這個問題還可以擴展為N1個牧師和N2個野人，而船一次可以裝下M個人的情況。我們使用AmziProlog解決上面的問題。這是個典型的狀態(tài)圖搜索問題，所以我們首先需要解決的問題就是使用Prolog的數(shù)據(jù)結(jié)構(gòu)表達兩岸的狀態(tài)，以及對這些狀態(tài)可能的操作。我們用下面的復合結(jié)構(gòu)來表達問題的某個狀態(tài)。((左岸牧師數(shù)，左岸野人數(shù)),(右岸牧師數(shù)，右岸野人數(shù)),船的位置)上面的結(jié)構(gòu)中，船的位置為0表示船在左岸，為1表示在右岸。一開始，所有的人都在左岸。所以初始狀態(tài)如下:((3,3),(0,0),0)而我們的目標狀態(tài)則是:((0,0),(3,3),1)當然，這里只是為了方便起見，才使用了上面的結(jié)構(gòu)，實際上是沒有必要包括右岸的人數(shù)的，因為可以通過左岸的人數(shù)算出右岸的人數(shù)來。不過我們這里所選用的數(shù)據(jù)結(jié)構(gòu)也有其優(yōu)點，它可以是程序更加容易理解。船上所能夠載人的狀態(tài)就是可能的操作。用謂詞move表示。move(1,0).表示船上有一位牧師，沒有野人。move(0,1).move(0,2).move(2,0).move(1,1).有了上面的表達狀態(tài)的數(shù)據(jù)結(jié)構(gòu)以及移動的方法，我們還需要判斷狀態(tài)是否合法。下面的legal就是完成這個任務。legal((X,Y,_)):-%X為左岸狀態(tài)，Y為右岸狀態(tài)。legal1(X),%分別判斷兩岸的狀態(tài)是否合法。legal1(Y).legal1((X,Y)):-X=0,Y>=0,!.%牧師人數(shù)為0，野人的人數(shù)大于0，合法。legal1((X,Y)):-Y=0,X>=0,!.%野人人數(shù)為0，牧師的人數(shù)大于0，合法。legal1((X,Y)):-X>=Y,X>=0,Y>=0.%牧師數(shù)大于或等于野人數(shù)，且都大于0，合法。下面是使用legal/1的幾個例子:?-legal(((3,3),(0,0),1)).yes?-legal(((0,3),(3,0),1)).yes?-legal(((2,3),(1,0),0)).nolegal只判斷牧師與野人的人數(shù)是否會造成牧師受到傷害，而不判斷左右岸的人數(shù)之和是否正確。所以((2,1),(1,1),0)也是合法的狀態(tài)。不過不用擔心，在我們后面的程序中會避免這種情況出現(xiàn)的。下面的update謂詞能夠完成把合理的移動作用的某個狀態(tài)上，從而到達新的狀態(tài)。update((X,Y,0),Move,Statu1):-%船在左岸時(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC+E,D1isD+F,A1isA-E,B1isB-F,Statu1=((A1,B1),(C1,D1),1).update((X,Y,1),Move,Statu1):-%船在右岸時(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC-E,D1isD-F,A1isA+E,B1isB+F,Statu1=((A1,B1),(C1,D1),0).?-update(((3,3),(0,0),0),(1,1),X).X=(2,2),(1,1),1;no?-update(((0,0),(3,3),0),(1,1),X).X=(-1,-1),(4,4),1;no?-update(((1,2),(2,3),1),(3,4),X).X=(4,6),(-1,-1),0;no注意update只是簡單地進行加減運算，它并不判斷所得的新的狀態(tài)是否合法。有了以上的三個謂詞move，update，legal我們就可以很容易的做出判斷兩個合法的狀態(tài)相鄰的謂詞，當然，此謂詞也可以用來尋找某個狀態(tài)的相鄰狀態(tài)。connect(Statu,Statu1):-move(X,Y),update(Statu,(X,Y),Statu1),legal(Statu1).沒什么好解釋的，這是非常符合邏輯的謂詞。我們來看看功能:?-connect(((3,3),(0,0),0),X).X=(2,2),(1,1),1;一個野人與一個牧師過河X=(3,2),(0,1),1;一個野人過河X=(3,1),(0,2),1;兩個野人過河no再使用典型的深度搜索方法就可以找到答案了:findroad(X,X,L,L).%遞歸的邊界條件。findroad(X,Y,L,L1):-%L為儲存的路由表。connect(X,Z),not(member(Z,L)),%X所連接的節(jié)點Z不在已經(jīng)儲存的路由表中。findroad(Z,Y,[Z|L],L1).?-findroad(((0,0),(3,3),1),((3,3),(0,0),0),[((0,0),(3,3),1)],L).L=[((3,3),(0,0),0),((3,1),(0,2),1),((3,2),(0,1),0),((3,0),(0,3),1),((3,1),(0,2),0),((1,1),(2,2),1),((2,2),(1,1),0),((0,2),(3,1),1),((0,3),(3,0),0),((0,1),(3,2),1),((1,1),(2,2),0),((0,0),(3,3),1)]yesfindroad/4的第三個參數(shù)是初始路由表，在此我們把終點狀態(tài)放到其中，上面的findroad是從終點向起點尋找，由于是對稱的，這并不影響結(jié)果。使用廣度搜索也能完成相同的任務:findroad([],X,X).findroad(Moves,State,Crit):-findroad(PrMoves,State,NextState),not(member(NextState,PrMoves)),connect(NextState,Crit),append(PrMoves,[NextState],Moves).?-findroad(L,((3,3),(0,0),0),((0,0),(3,3),1)).L=[((3,3),(0,0),0),((2,2),(1,1),1),((3,2),(0,1),0),((3,0),(0,3),1),((3,1),(0,2),0),((1,1),(2,2),1),((2,2),(1,1),0),((0,2),(3,1),1),((0,3),(3,0),0),((0,1),(3,2),1),((0,2),(3,1),0)]好了，到此為止過河問題已經(jīng)基本上解決了。不過為了能夠使用本程序分析一般情況，即牧師與野人的人數(shù)和船的載客量為其它值的情況，我們來稍微改寫一下這個程序。謂詞insert_move(N)，動態(tài)地向內(nèi)存中加入船的載客量為N時，船上載客的所有可能情況。我們可以試試借用謂詞leagal(X,Y)來實現(xiàn):insert_move(N):-X+YisN,legal(X,Y),asserta(move(X,Y)).上面的asserta謂詞把它的參數(shù)作為子句加入到內(nèi)存中。這個程序看似簡潔，其實錯了，為什么呢,因為X，YisN有無窮組解。所以要用以下方法:get_integer(L,H,X):-L>H,!,fail.get_integer(L,H,L).get_integer(L,H,X):-L1isL+1,get_integer(L1,H,X).insert_move(N):-insert_move0(N),insert_move1(N).insert_move0(0).%野人或牧師有一方人數(shù)為0，則另一方的人數(shù)可以是0--N.insert_move0(N):-asserta(move(N,0)),asserta(move(0,N)),N1isN-1,insert_move0(N1).insert_move1(N):-%人數(shù)都不為0時，則野人的人數(shù)不能多于牧師的人數(shù)，并且總?cè)藬?shù)不能多于N.get_integer(1,N,X),get_integer(X,N,Y),X+Y=<N,asserta(move(Y,X)),fail.insert_move1(_).來試一下功能。?-insert_move(3).yes?-move(X,Y).X=2Y=1;X=1Y=1;X=0Y=1;X=1Y=0;X=0Y=2;X=2Y=0;X=0Y=3;X=3Y=0;no謂詞insert_statu(N1,N2)，動態(tài)地加入初始狀態(tài)與目標狀態(tài)，當然是N個牧師與N個野人的情況。insert_statu(N1,N2):-asserta(inistatu(((N1,N2),(0,0),0))),asserta(desstatu(((0,0),(N1,N2),1))).下面的謂詞用來從內(nèi)存中刪除以上的動態(tài)信息。del_move:-retract(move(X,Y)),fail.del_move.del_stat:-retract(inistatu(X)),retract(desstatu(Y)),!.del_stat.這些謂詞的第二個子句是為了保證謂詞永遠能夠成功，以免再調(diào)用它們時出現(xiàn)問題。最后我們再分別編寫使用廣度搜索與深度搜索的主程序。widesolve(N1,N2,M):-del_move,del_stat,insert_move(M),insert_statu1,(N1,N2),inistatu(X),desstatu(Y),!,findroad(L,X,Y),writelist(L),nl.deepsolve(N1,N2,M):-del_move,del_stat,insert_move(M),insert_statu(N1,N2),inistatu(X),desstatu(Y),!,findroad(Y,X,[Y],L),writelist(L),nl.第一個參數(shù)為野人與牧師的人數(shù)，第二個參數(shù)為船的最大載人量。它們分別調(diào)用findroad/3(廣度搜索)findroad/4(深度搜索)來完成搜索任務。(在Prolog中參數(shù)數(shù)目不同的謂詞，是不同的謂詞)我們在深度搜索中加入的截斷，因為我們想通過deepsolve判斷問題是否有解，而通過widesolve尋找出最優(yōu)解，這是因為廣度搜索先總是找出最短路徑。下面是完整的源程序:go.txt(解決過河問題的Prolog程序)get_integer(L,H,X):-L>H,!,fail.get_integer(L,H,L).get_integer(L,H,X):-L1isL+1,get_integer(L1,H,X).append([],X,X).append([A|X],Y,[A|Z]):-append(X,Y,Z).member(A,[A|X]).member(A,[B|X]):-member(A,X).del_move:-retract(move(X,Y)),fail.del_move.del_stat:-retract(inistatu(X)),retract(desstatu(Y)),!.del_stat.insert_move(N):-insert_move0(N),insert_move1(N).insert_move0(0).insert_move0(N):-asserta(move(N,0)),asserta(move(0,N)),N1isN-1,insert_move0(N1).insert_move1(N):-get_integer(1,N,X),get_integer(X,N,Y),X+Y=<N,asserta(move(Y,X)),fail.insert_move1(_).legal((X,Y,_)):-legal1(X),legal1(Y).legal1((X,Y)):-X=:=0,Y>=0,!.legal1((X,Y)):-Y=:=0,X>=0,!.legal1((X,Y)):-X>=Y,X>=0,Y>=0.update((X,Y,0),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC+E,D1isD+F,A1isA-E,B1isB-F,Statu1=((A1,B1),(C1,D1),1).update((X,Y,1),Move,Statu1):-(A,B)=X,(C,D)=Y,(E,F)=Move,C1isC-E,D1isD-F,A1isA+E,B1isB+F,Statu1=((A1,B1),(C1,D1),0).connect(Statu,Statu1):-move(X,Y),update(Statu,(X,Y),Statu1),legal(Statu1).findroad(X,X,L,L).%遞歸的邊界條件。findroad(X,Y,L,L1):-%L為儲存的路由表。connect(X,Z),not(member(Z,L)),%X所連接的節(jié)點Z不在已經(jīng)儲存的路由表中。findroad(Z,Y,[Z|L],L1).findroad([],X,X).findroad(Moves,State,Crit):-findroad(PrMoves,State,NextState),not(member(NextState,PrMoves)),connect(NextState,Crit),append(PrMoves,[NextState],Moves).insert_statu(N1,N2):-asserta(inistatu(((N1,N2),(0,0),0))),asserta(desstatu(((0,0),(N1,N2),1))).writelist([]).writelist([X|L]):-write(X),nl,writelist(L).widesolve(N1,N2,M):-del_move,del_stat,insert_move(M),insert_statu(N1,N2),inistatu(X),desstatu(Y),!,findroad(L,X,Y),writelist(L),nl.deepsolve(N1,N2,M):-del_move,del_stat,insert_move(M),insert_statu(N1,N2),inistatu(X),desstatu(Y),!,findroad(Y,X,[Y],L),writelist(L),nl.go(Start,Target):-path(Start,Target,[Start],Path),write(‘Asolutionis:’),nl,write_path(Path).path(Start,Target,Visited,Path):-move(Start,NextNode),%Generateamovenot(unsafe(NextNode)),%Checkthatitissafenot(member(NextNode,Visited)),%Checkforrecurrencepath(NextNode,Target,[NextNode|Visited],Path),!.path(Target,Target,Path,Path).%Reachedthegoalmove(state(X,X,G,C),state(Y,Y,G,C)):-opposite(X,Y).%FARMER&WOLF