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

1、實 驗 報 告課程名稱 人工智能_ 實驗項目 野人過河問題_ 實驗儀器 電腦 、visual C+_ 系 別 計算機學(xué)院_ 專 業(yè) _計算機科學(xué)與技術(shù)_ 班級/學(xué)號 學(xué)生姓名 _ _實驗日期 2010年 月 日_ 成 績 _ 指導(dǎo)教師 一、 實驗?zāi)康睦斫獠⑹煜ふ莆丈疃葍?yōu)先搜索和廣度優(yōu)先搜索地方法。二、 實驗內(nèi)容題目：設(shè)有3個傳教士和3個野人來到河邊，打算乘一只船從右岸到左岸去。 該船的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人 就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去? 三、代碼和結(jié)果#include <stdio.h>#include &l

2、t;stdlib.h>#include <ctype.h>#define maxloop 100 /* 最大層數(shù)，對于不同的擴展方法自動調(diào)整取值 */#define pristnum 3 /*初始化時設(shè)定有3個野人3個傳教士，實際可以改動*/#define slavenum 3struct SPQ int sr,pr; /* 船運行一個來回后河右岸的野人、傳教士的人數(shù) */int sl,pl; /* 船運行一個來回后河左岸的野人、傳教士的人數(shù) */ int ssr,spr; /* 回來（由左向右時）船上的人數(shù) */ int sst,spt; /* 去時（由右向左時）船上的人數(shù)

3、 */ int loop; /* 本結(jié)點所在的層數(shù) */ struct SPQ *upnode ,*nextnode;/* 本結(jié)點的父結(jié)點和同層的下一個結(jié)點的地址 */spq; int loopnum;/* 記錄總的擴展次數(shù) */int openednum;/* 記錄已擴展節(jié)點個數(shù) */int unopenednum;/* 記錄待擴展節(jié)點個數(shù) */int resultnum;struct SPQ *opened;struct SPQ *oend;struct SPQ *unopened; struct SPQ *uend;struct SPQ *result;void initiate();v

4、oid releasemem();void showresult();void addtoopened(struct SPQ *ntx);int search();void goon();int stretch(struct SPQ* ntx);void recorder();int main() int flag; /* 標(biāo)記擴展是否成功 */ for( ; ; ) initiate(); flag = search (); if(flag = 1) recorder(); releasemem(); showresult(); goon(); else printf("無法找到符

5、合條件的解"); releasemem(); goon(); system("pause"); return 0;void initiate() int x; char choice; uend = unopened = (struct SPQ*)malloc(sizeof(spq); if(uend=NULL) printf("n內(nèi)存不夠！n"); exit(0); unopenednum=1; openednum=0; unopened -> upnode = unopened; /* 保存父結(jié)點的地址以成鏈表 */ unopened

6、 -> 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("題目：設(shè)有n個傳教士和m個野人來到河邊，打算乘一只船從右岸到左岸

7、去。n"); printf("該船的負載能力為兩人。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人n"); printf("就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去?n"); printf("n默認的n、m值皆為3n"); for(;) printf("n是否修改？(Y/N)"); scanf("%s",&choice); choice=toupper(choice); if(choice='Y') printf("n請輸入傳教士人

8、數(shù)"); for(;) scanf("%d",&x); if(x>0) unopened -> pr = x; break; else printf("n輸入值應(yīng)大于0！n請重新輸入"); printf("n請輸入野人人數(shù)"); for(;) scanf("%d",&x); if(x>0) unopened -> sr = x; break; else printf("n輸入值應(yīng)大于0！n請重新輸入"); break; if(choice=

9、9;N')break; int search() int flag; struct SPQ *ntx; /* 提供將要擴展的結(jié)點的指針 */ for( ; ; ) ntx = unopened; /* 從待擴展鏈表中提取最前面的一個 */ if(ntx->loop = maxloop) return 0; addtoopened(ntx); /* 將ntx加入已擴展鏈表，并將這個節(jié)點從待擴展鏈表中去掉 */ flag = stretch(ntx); /* 對ntx進行擴展,返回-1,0,1 */ if(flag = 1) return 1; int stretch(struct

10、SPQ *ntx) int fsr , fpr ; /* 在右岸上的人數(shù) */ int fsl , fpl ; /* 在左岸上的人數(shù) */ int sst , spt ; /* 出發(fā)時在船上的人數(shù) */ int ssr , spr ; /* 返回時船上的人數(shù) */ struct SPQ *newnode; for (sst = 0 ; sst <= 2 ; sst+) /* 討論不同的可能性并判斷是否符合條件 */ fsr = ntx -> sr; fpr = ntx -> pr; fsl = ntx -> sl; fpl = ntx -> pl; if (sst

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

12、ode -> 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

13、= newnode; oend = newnode; openednum+; return 1; else if (fpr - fsr) * fpr >= 0) /* 判斷是否滿足傳教士人數(shù)必須大于或等于野人人數(shù) */ fsl = fsl + sst; fpl = fpl + spt; for (ssr = 0 ; ssr <= 1 ; ssr+) /* 返回 */ int ffsl , ffpl; if (ssr <= fsl) && (1 - ssr) <= fpl) spr = 1 - ssr; ffsl = fsl - ssr; ffpl = f

14、pl - spr; if (ffpl - ffsl) * ffpl >= 0) /* 若符合條件則分配內(nèi)存并付值 */ int ffsr , ffpr; ffsr = fsr + ssr; ffpr = fpr + spr; newnode = (struct SPQ*) malloc (sizeof(spq); if(newnode=NULL) printf("n內(nèi)存不夠！n"); exit(0); newnode -> upnode = ntx; /* 保存父結(jié)點的地址以成鏈表 */ newnode -> sr = ffsr; newnode ->

15、; 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+; return 0;void addtoopened(struct SP

16、Q *ntx) unopened = unopened -> nextnode; unopenednum-; if (openednum = 0 ) oend = opened = ntx; oend -> nextnode = ntx; oend = ntx; openednum+;void recorder() int i , loop; struct SPQ *newnode; struct SPQ *ntx; loop = oend -> loop; ntx = oend; resultnum = 0; for( i = 0 ; i <= loop ; i+ )

17、 newnode = (struct SPQ*) 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 -> sp

18、t; 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+; void releasemem() int i; struct SPQ* nodefree; for ( i = 1 ; i < openednum ; i

19、+ ) nodefree = opened; opened = opened -> nextnode; free(nodefree); for ( i = 0 ; i < unopenednum ; i+ ) nodefree = unopened; unopened = unopened -> nextnode; free(nodefree); void showresult() int i; int fsr , fpr ; /* 在右岸上的人數(shù) */ int fsl , fpl ; /* 在左岸上的人數(shù) */ struct SPQ* nodefree; printf(&q

20、uot;%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("nnt左岸人數(shù) 船上人數(shù)及方向 右岸人數(shù)n"); printf("第%d輪n",i); fpl = result -> pl - result -> spt + result -> spr; fpr = result -> pr - result -> spr; fsl = result -&