大連理工大學人工智能課程項目設計

人工智能(項目設計)專業(yè)：計算機科學與技術班級：電計1203學號：201281303姓名：劉陽一.問題描述與分析傳教士人數(shù)M，野人數(shù)C，M≥C，開始都在岸左邊。

①船最多只能載K人，傳教士和野人都會劃船，當然必須有人劃船

②兩岸邊保證野人人數(shù)不能大于傳教士人數(shù)

把所有人都送過河，求解過河方案。如果求取最優(yōu)解應使用A*算法，但如果輸出整個解空間使用DFS比較直接，并且對于大多數(shù)情況而言，幾種過河方案代價基本相同。在程序中需要保證狀態(tài)節(jié)點向下拓展以提高效率。即如果搜索的狀態(tài)在之前已經(jīng)出現(xiàn)過了，就不深入下去了，否則會出現(xiàn)死循環(huán)。搜索算法這里采用DFS的非遞歸描述，如果當前節(jié)點無法繼續(xù)拓展或者已經(jīng)拓展到目標狀態(tài)，那么將當前解中位于棧頂?shù)谝粋€待拓展狀態(tài)之前的狀態(tài)全部出棧（棧非空的情況下），如果當前達到目標狀態(tài)還需要將解壓入解空間中。程序中回溯不可避免因為總有不可繼續(xù)拓展的節(jié)點，但是向上拓展必須避免因為這會導致搜索陷入錯誤的循環(huán)。二.程序源碼及注釋#include<iostream>#include<vector>#include<string>#include<stdio.h>#include<conio.h>#defineMAXSIZE50usingnamespacestd;typedefstruct{intperson;//左岸傳教士人數(shù)intwild;//左岸野人人數(shù)boolboat;//true表示船在左岸intmethod;//到達本狀態(tài)上一步使用的方法intLast;//記錄父狀態(tài)編號}state;//狀態(tài)節(jié)點intLastMethod=0;//記錄上一步使用的方法，防止循環(huán)intLastState=-1;//上一步狀態(tài)編號boolflag=true;//ture表示船在左岸vector<vector<state>>answer;//最終解集vector<state>temp;//當前解空間暫存數(shù)組stateStack[MAXSIZE];//用于非遞歸DFS的狀態(tài)棧intf=0,r=0;//棧頂與棧底intA,B;//記錄傳教士與野人初始人數(shù)intk;//小船最多載的人數(shù)//函數(shù)聲明intDFS(intM,intC,intm,intc);intjudge(intM,intC,intm,intc);intnext_judge(intM,intC,intm,intc,intmet);intif_repeat(intM,intC,boolf);intdisp();intDFS(intM,intC,intm,intc)//非遞歸DFS{intX=M,Y=C,x=m,y=c;stateindex;judge(X,Y,x,y);//初始情況進棧while(r!=f){index=Stack[--r];X=index.person;Y=index.wild;x=M-X;y=C-Y;temp.push_back({X,Y,index.boat,index.method,index.Last});LastState++;LastMethod=index.method;if((!flag&&X==0&&Y==0))//全部運輸過去{answer.push_back(temp);if(r==f)break;elseif(r!=f){statet1;t1=temp.back();//將解集暫存數(shù)組temp中棧頂狀態(tài)后的狀態(tài)刪除while(Stack[r-1].Last!=t1.Last){temp.pop_back();t1=temp.back();}temp.pop_back();index=Stack[--r];//將棧頂待拓展狀態(tài)出棧temp.push_back({index.person,index.wild,index.boat,index.method,index.Last});LastMethod=index.method;LastState=index.Last;//重置上一步狀態(tài)編號LastState++;flag=index.boat;X=index.person;Y=index.wild;x=M-X;y=C-Y;}}if(!judge(X,Y,x,y)){if(r!=f)//如果棧中仍有待拓展節(jié)點，才需要將棧頂狀態(tài)后的狀態(tài)刪除{statet2;t2=temp.back();while(Stack[r-1].Last!=t2.Last){temp.pop_back();t2=temp.back();}temp.pop_back();flag=Stack[r-1].boat;LastState=Stack[r-1].Last;}}}if(0==answer.size())return0;elsereturn1;}intjudge(intM,intC,intm,intc)//將下一步可能狀態(tài)進棧{inti,j,signal=0;intT=1;if(1==flag){flag=!flag;for(i=0;i<=k;i++){for(j=0;(i+j)<=k;j++,T++)if(next_judge(M-i,C-j,m+i,c+j,T)&&(if_repeat(M-i,C-j,flag&!((i==0)&&(j==0)))){Stack[r++]={M-i,C-j,flag,T,LastState};signal=1;}}}else{flag=!flag;for(i=0;i<=k;i++){for(j=0;(i+j)<=k;j++,T++)if(next_judge(M+i,C+j,m-i,c-j,T)&&(if_repeat(M+i,C+j,flag&&(!((i==0)&&(j==0)))){Stack[r++]={M+i,C+j,flag,T,LastState};signal=1;}}}returnsignal;}//判斷接下來的可能狀態(tài)是否非法intnext_judge(intM,intC,intm,intc,intmet){if(M<0||C<0||m<0||c<0)//非法return0;if(M>A||C>B||m>A||c>B)//非法return0;if((M==A)&&(C==B))//防止回溯到初始節(jié)點return0;if((M&&C>M)||(m&&c>m))//野人會吃傳教士return0;if(LastMethod==met)//回溯return0;return1;}//判斷接下來的可能狀態(tài)是否與棧或當前解中已有狀態(tài)重復intif_repeat(intM,intC,boolf){//判斷接下來的可能狀態(tài)是否與當前棧中待拓展狀態(tài)重復，防止回溯for(intx=0;x<r;x++)if((Stack[x].person==M)&&(Stack[x].wild==C)&&(Stack[x].boat==f))return0;//判斷接下來的可能狀態(tài)是否與當前解空間中已經(jīng)存在的狀態(tài)重復，防止循環(huán)for(unsignedintx=0;x<temp.size();x++)if((temp[x].person==M)&&(temp[x].wild==C)&&(temp[x].boat==f))return0;return1;}intdisp()//輸出解集{printf("一共有%d種解法\n",answer.size());unsignedintm,n;inti,j,T;for(m=0;m<answer.size();m++){printf("第%d種解法：\n",m+1);printf("(%d,%d)boat=left\n",A,B);for(n=0;n<answer[m].size();n++){for(T=1,i=0;i<=k;i++){for(j=0;(i+j)<=k;j++,T++)if(T==answer[m][n].method){cout<<"("<<i<<","<<j<<")"<<endl;}}if(answer[m][n].boat)printf("(%d,%d)boat=left\n",answer[m][n].person,answer[m][n].wild);elseprint