人工智能二野人過河問題實驗3

1、.word格式.專業(yè).專注課程名稱 實驗項目 實驗儀器人工智能野人過河問題_電月百、visualC+系別計算機學院專業(yè)_計算機科學與技術(shù)班級/學號學生姓名實驗日期2010年月日成績指導教師實驗目的理解并熟悉掌握深度優(yōu)先搜索和廣度優(yōu)先搜索地方法。二、實驗內(nèi)容題目：設有3個傳教士和3個野人來到河邊，打算乘一只船從右岸到左岸去。該船三、代碼和結(jié)果#include <stdio.h>#include <stdlib.h>#include <ctype.h> #define maxloop 100 /* #define pristnum 3 /* #define sl

2、avenum 3 struct SPQ int sr,pr;*/int sl,pl; /* int ssr,spr; /*的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去？最大層數(shù)，對于不同的擴展方法自動調(diào)整取值*/初始化時設定有3個野人3個傳教士，實際可以改動*/*船運行一個來回后河右岸的野人、傳教士的人數(shù)船運行一個來回后河左岸的野人、傳教士的人數(shù)*/回來（由左向右時）船上的人數(shù)*/intsst,spt;/*去時(由右向左時)船上的人數(shù)*/intloop;/*本結(jié)點所在的層數(shù)*/structSPQ*upnode,*n

3、extnode;/*本結(jié)點的父結(jié)點和同層的下一個結(jié)點的地址*/spq;intloopnum;/*記錄總的擴展次數(shù)*/intopenednum;/*記錄已擴展節(jié)點個數(shù)*/intunopenednum;/*記錄待擴展節(jié)點個數(shù)*/intresultnum;structSPQ*opened;structSPQ*oend;structSPQ*unopened;structSPQ*uend;structSPQ*result;voidinitiate。；voidreleasemem();voidshowresult();voidaddtoopened(structSPQ*ntx);intsearch();v

4、oidgoon();intstretch(structSPQ*ntx);voidrecorder。；intmain()intflag;/*標記擴展是否成功*/for(;)initiate。；flag=search();if(flag=1)recorder();releasemem();showresult();goon();elseprintf("無法找到符合條件的解");releasemem();goon();system("pause");return0;voidinitiate。intx;charchoice;uend=unopened=(stru

5、ctSPQ*)malloc(sizeof(spq);if(uend=NULL)printf("n內(nèi)存不夠！n");exit(0);unopenednum=1;openednum=0;unopened->upnode=unopened;/*保存父結(jié)點的地址以成鏈表*/unopened->nextnode=unopened;unopened->sr=slavenum;unopened->pr=pristnum;unopened->sl=0;unopened->pl=0;unopened->sst=0;unopened->spt=0

6、;unopened->ssr=0;unopened->spr=0;unopened->loop=0;printf("題目：設有n個傳教士和m個野人來到河邊，打算乘一只船從右岸到左岸去。n");printf("該船的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人n");printf("就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去？n");printf("n默認的n、m值皆為3n");for(;)printf("n是否修改？(Y/N)");scanf

7、("%s",&choice);choice=toupper(choice);if(choice='Y')printf("n請輸入傳教士人數(shù)");for(;)scanf("%d",&x);if(x>0)unopened->pr=x;break;elseprintf("n輸入值應大于0!n請重新輸入");printf("n請輸入野人人數(shù)");for(;)scanf("%d",&x);if(x>0)unopened->

8、sr=x;break;elseprintf("n輸入值應大于0!n請重新輸入");break;if(choice='N')break;int search()int flag;struct SPQ *ntx;for(;)ntx = unopened;/*/*提供將要擴展的結(jié)點的指針*/從待擴展鏈表中提取最前面的一個*/if(ntx->loop = maxloop) return 0;addtoopened(ntx); /*表中去掉*/flag = stretch(ntx); /*if(flag = 1)return 1;int stretch(stru

9、ct SPQ *ntx)int fsr , fpr ; /*int fsl , fpl ; /*int sst , spt ; /*int ssr , spr ; /*在右岸上的人數(shù)在左岸上的人數(shù)ntxntx*/*/加入已擴展鏈表，并將這個節(jié)點從待擴展鏈進行擴展，返回-1,0,1 */出發(fā)時在船上的人數(shù) 返回時船上的人數(shù)*/*/structSPQ*newnode;for(sst=0;sst<=2;sst+)/*討論不同的可能性并判斷是否符合條件*/fsr=ntx->sr;fpr=ntx->pr;fsl=ntx->sl;fpl=ntx->pl;if(sst<=

10、fsr)&&(2-sst)<=fpr)/*滿足人數(shù)限制*/spt=2-sst;fsr=fsr-sst;fpr=fpr-spt;if(fpr=0)&&(fsr=0)/*搜索成功*/newnode=(structSPQ*)malloc(sizeof(spq);if(newnode=NULL)printf("n內(nèi)存不夠！n");exit(0);newnode->upnode=ntx;/*保存父結(jié)點的地址以成鏈表*/newnode->nextnode=NULL;newnode->sr=0;newnode->pr=0;ne

11、wnode->sl=opened->sr;newnode->pl=opened->pr;newnode->sst=sst;newnode->spt=spt;newnode->ssr=0;newnode->spr=0;newnode->loop=ntx->loop+1;oend->nextnode=newnode;oend=newnode;openednum+;return1;elseif(fpr-fsr)*fpr>=0)/*判斷是否滿足傳教士人數(shù)必須大于或等于野人人數(shù)*/fsl=fsl+sst;fpl=fpl+spt;fo

12、r(ssr=0;ssr<=1;ssr+)/*返回*/intffsl,ffpl;if(ssr<=fsl)&&(1-ssr)<=fpl)spr=1-ssr;ffsl=fsl-ssr;ffpl=fpl-spr;if(ffpl-ffsl)*ffpl>=0)/*若符合條件則分配內(nèi)存并付值*/intffsr,ffpr;ffsr=fsr+ssr;ffpr=fpr+spr;newnode=(structSPQ*)malloc(sizeof(spq);if(newnode=NULL)printf("n內(nèi)存不夠！n");exit(0);保存父結(jié)點的地址以

13、newnode->upnode=ntx;/*成鏈表*/newnode->sr=ffsr;newnode->pr=ffpr;newnode->sl=ffsl;newnode->pl=ffpl;newnode->sst=sst;newnode->spt=spt;newnode->ssr=ssr;newnode->spr=spr;newnode->loop=ntx->loop+1;uend->nextnode=newnode;uend=newnode;unopenednum+;return0;voidaddtoopened(st

14、ructSPQ*ntx)unopened=unopened->nextnode;unopenednum-;if(openednum=0)oend=opened=ntx;oend->nextnode=ntx;oend=ntx;openednum+;voidrecorder。inti,loop;structSPQ*newnode;structSPQ*ntx;loop=oend->loop;ntx=oend;resultnum=0;for(i=0;i<=loop;i+)newnode=(structSPQ*)malloc(sizeof(spq);if(newnode=NULL

15、)printf("n內(nèi)存不夠！n");exit(0);newnode->sr=ntx->sr;newnode->pr=ntx->pr;newnode->sl=ntx->sl;newnode->pl=ntx->pl;newnode->sst=ntx->sst;newnode->spt=ntx->spt;newnode->ssr=ntx->ssr;newnode->spr=ntx->spr;newnode->nextnode=NULL;ntx=ntx->upnode;if

16、(i=0)result=newnode;newnode->nextnode=result;result=newnode;resultnum+;voidreleasemem()inti;structSPQ*nodefree;for(i=1;i<openednum;i+)nodefree=opened;opened=opened->nextnode;free(nodefree);for(i=0;i<unopenednum;i+)nodefree=unopened;unopened=unopened->nextnode;free(nodefree);voidshowre

17、sult()inti;intfsr,fpr;/*在右岸上的人數(shù)*/intfsl,fpl;/*在左岸上的人數(shù)*/structSPQ*nodefree;printf("%d個傳教士",result->pr);printf("%d個里看人",result->sr);printf("%d個傳教士",result->pl);printf("%d個里看人",result->sl);for(i=1;i<resultnum;i+)nodefree=result;result=result->ne

18、xtnode;free(nodefree);printf("nnt左岸人數(shù)船上人數(shù)及方向右岸人數(shù)n");printf("第輪坨"力；fpl=result->pl-result->spt+result->spr;fpr=result->pr-result->spr;fsl=result->sl-result->sst+result->ssr;fsr=result->sr-result->ssr;printf("傳教士8d%8dt<-t%8dn",fpl,result->spt,fpr);printf("野A%8d%8dt<-t%8dn",fsl,result->sst,fsr);printf("傳教士8d%8dt->t%8dn",result->pl,result->spr,result->pr-result->spr);printf("野人8d%8dt->t%8dn&