昆明理工大學(xué) 人工智能 實驗一

昆明理工大學(xué)信息工程與自動化學(xué)院學(xué)生實驗報告（2011—2012學(xué)年第1學(xué)期）課程名稱：人工智能開課實驗室：4442011年12月9日年級、專業(yè)、班計科093學(xué)號200910405310姓名孫浩川成績實驗項目名稱傳教士與野人過河問題指導(dǎo)教師王劍教師評語該同學(xué)是否了解實驗原理： A.了解□ B.基本了解□ C.不了解□該同學(xué)的實驗?zāi)芰Γ? A.強□ B.中等□ C.差□該同學(xué)的實驗是否達到要求： A.達到□ B.基本達到□ C.未達到□實驗報告是否規(guī)范： A.規(guī)范□ B.基本規(guī)范□ C.不規(guī)范□實驗過程是否詳細記錄： A.詳細□ B.一般□ C.沒有□教師簽名：年月日一、實驗?zāi)康募皟?nèi)容實驗?zāi)康模豪斫獠⑹煜ふ莆丈疃葍?yōu)先搜索和廣度優(yōu)先搜索地方法。實驗內(nèi)容：設(shè)有3個傳教士和3個野人來到河邊，打算乘一只船從右岸到左岸去。該船的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去?二、實驗原理及基本技術(shù)路線圖（方框原理圖或程序流程圖）三、所用儀器、材料（設(shè)備名稱、型號、規(guī)格等或使用軟件）1臺PC以及VISUALC++6.0軟件四、實驗方法、步驟（或：程序代碼或操作過程） #include<stdio.h> #include<stdlib.h> #include<ctype.h> #definemaxloop100/*最大層數(shù)，對于不同的擴展方法自動調(diào)整取值*/ #definepristnum3/*初始化時設(shè)定有3個野人3個傳教士，實際可以改動*/ #defineslavenum3 structSPQ{intsr,pr;/*船運行一個來回后河右岸的野人、傳教士的人數(shù)*/ intsl,pl;/*船運行一個來回后河左岸的野人、傳教士的人數(shù)*/ intssr,spr;/*回來（由左向右時）船上的人數(shù)*/ intsst,spt;/*去時（由右向左時）船上的人數(shù)*/ intloop;/*本結(jié)點所在的層數(shù)*/ structSPQ*upnode,*nextnode;/*本結(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(); voidgoon(); intstretch(structSPQ*ntx); voidrecorder(); intmain() { intflag;/*標記擴展是否成功*/ for(;;) { initiate(); flag=search(); if(flag==1) { recorder(); releasemem(); showresult(); goon(); } else { printf("無法找到符合條件的解"); releasemem(); goon(); } } system("pause"); return0; } voidinitiate() { intx; charchoice; uend=unopened=(structSPQ*)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; unopened->ssr=0; unopened->spr=0; unopened->loop=0; printf("計科093班孫浩川200910405310\n\n"); printf("設(shè)有3個傳教士和3個野人來到河邊，打算乘一只船從右岸到左岸去。該船的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去?\n"); /*printf("該船的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人\n"); printf("就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去?\n");*/ for(;;) { printf("\n是否開始？(Y/N)"); scanf("%s",&choice); choice=toupper(choice); if(choice=='N') { printf("\n請輸入傳教士人數(shù)"); for(;;) { scanf("%d",&x); if(x>0) { unopened->pr=x; break; } elseprintf("\n輸入值應(yīng)大于0！\n請重新輸入"); } printf("\n請輸入野人人數(shù)"); for(;;) { scanf("%d",&x); if(x>0) { unopened->sr=x; break; } elseprintf("\n輸入值應(yīng)大于0！\n請重新輸入"); } break; } if(choice=='Y')break; } } intsearch() { intflag; structSPQ*ntx;/*提供將要擴展的結(jié)點的指針*/ for(;;) { ntx=unopened;/*從待擴展鏈表中提取最前面的一個*/ if(ntx->loop==maxloop) return0; addtoopened(ntx);/*將ntx加入已擴展鏈表，并將這個節(jié)點從待擴展鏈表中去掉*/ flag=stretch(ntx);/*對ntx進行擴展,返回-1,0,1*/ if(flag==1) return1; } } intstretch(structSPQ*ntx) { intfsr,fpr;/*在右岸上的人數(shù)*/ intfsl,fpl;/*在左岸上的人數(shù)*/ intsst,spt;/*出發(fā)時在船上的人數(shù)*/ intssr,spr;/*返回時船上的人數(shù)*/ structSPQ*newnode; for(sst=0;sst<=2;sst++)/*討論不同的可能性并判斷是否符合條件*/ { fsr=ntx->sr; fpr=ntx->pr; fsl=ntx->sl; fpl=ntx->pl; if((sst<=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; newnode->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; for(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); } newnode->upnode=ntx;/*保存父結(jié)點的地址以成鏈表*/ 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(structSPQ*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) { 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(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); } } voidshowresult() { 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->nextnode; free(nodefree); //printf("\n\n\t左岸人數(shù)船上人數(shù)及方向右岸人數(shù)\n"); printf("第%d輪\n",i); fpl=result->pl-result->spt+result->spr; fpr=result->pr-result->spr; fsl=result->sl