人工智能實(shí)驗(yàn)二

1、實(shí)驗(yàn)二圖搜索技術(shù)一、實(shí)驗(yàn)?zāi)康募由顚W(xué)生對(duì)圖搜索技術(shù)的理解。掌握?qǐng)D搜索基本編程方法。能初步運(yùn)用圖搜索技術(shù)解決一些實(shí)際應(yīng)用問題。二、預(yù)習(xí)要求復(fù)習(xí)廣度優(yōu)先搜索算法。復(fù)習(xí)深度優(yōu)先搜索算法。設(shè)計(jì)初步的搜索算法。三、實(shí)驗(yàn)內(nèi)容（必做）利用深度優(yōu)先和廣度優(yōu)先搜索技術(shù)解決傳道士和野人問題。修道士和野人問題如下：有三個(gè)傳教士和三個(gè)野人一起來到河邊準(zhǔn)備渡河，河邊有一條空船，且傳教士和野人都 會(huì)劃船，但每次最多可供兩人乘渡。河的任何一岸以及船上一旦出現(xiàn)野人人數(shù)超過傳教士人 數(shù)，野人就會(huì)把傳教士吃掉。為完全地渡河，傳教士應(yīng)如何規(guī)劃渡河方案？（選做）若傳教士和野人的數(shù)目均為五人，渡船至多可乘三人，請(qǐng)定義一個(gè)啟發(fā)函 數(shù)，并給

2、出相應(yīng)的搜索樹。四、實(shí)驗(yàn)要求：程序運(yùn)行時(shí)，應(yīng)能在屏幕上顯示結(jié)果。界面直觀、友好。3 .交實(shí)驗(yàn)報(bào)告。五、實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)截圖：有4種方式渡河.請(qǐng)輸入修道士與野人的人數(shù)n :4請(qǐng)輸入船可客納的人致匚；2無法渡河成功=請(qǐng)輸入修道士與野人的人裁。:(331)(11)(22B)(222)(1&)(321)(321)(2)(300)(300)(01)(311)(321)(20)-(11S)(11)(11)(221)(221)(20)-(020)(020)(01)(331)（。31)(02)-(&15)(010)(10)(111)(111)(11)-(000)(000)渡河.成功(331)-(11)(22B)

3、(220)(10)(321)(321)(02)(30B)(30)(01)(311)(311)(20)(110)(110)(11)(221)(221)(2&)(a2B)(020)(01)(031)(031)(02)(013)(010)(1)(021)(B21)(02)(BBB)(0&)渡河成耐有4神方式渡河。造輸入修道士與野人的人數(shù)口 :1ST請(qǐng)輸入修道主與野人的人數(shù)m3請(qǐng)輸入船可容納的人數(shù)匚：2 TOC o 1-5 h z (331)-(02)-(310)(310)-(81)(02)-(BSS)(300)-(01)(20)-(110)(110)-(11)(2B)(326)(0 2 0 )-(3

4、1)(02)_(010)(6 1 0 )-(10)(11)-(BBB)( 0 0 0 ) 渡河成功！實(shí)驗(yàn)代碼:/ yeren.cpp : Defines the entry point for the console application./#include stdafx.h#include #include #include typedef structint xds; /xiudaoshiint yr; /yerenint cw; /chuanweiDataType;DataType fa50000;typedef struct nodeDataType data;struct node

5、 *son;struct node *bro;struct node *par;struct node *next;Ltable;void Ltableinit(Ltable *head)/初始化鄰接表的操作 *head=(Ltable *)malloc(sizeof(Ltable); /動(dòng)態(tài)分配空間(*head)-son=NULL;(*head)-bro=NULL;(*head)-par=NULL;(*head)-next=NULL;void insertson(Ltable *head, DataType x)/在鄰接表中插入兒子結(jié)點(diǎn)的操作Ltable *q,*s;q=(Ltable *)

6、malloc(sizeof (Ltable);q-data=x;head-son=q;s=head;while (s-next!=NULL)s=s-next;q-par=head;q-son=NULL;q-bro=NULL;s-next=q;q-next=NULL;void insertbro(Ltable *head, DataType x)/在鄰接表中插入兄弟結(jié)點(diǎn)的操作，所有的兄弟結(jié)點(diǎn)都指向他們右邊的結(jié)點(diǎn)；Ltable *q,*s;q=(Ltable *)malloc(sizeof (Ltable);s=head-son;q-data=x;while (s-bro!=NULL)s=s-br

7、o;s-bro=q;s-next=q;q-next=NULL;q-bro=NULL;q-par=head;q-son=NULL;int findfa(DataType x, int n)/生成在船上修道士仍安全的幾種情況；int i=0,a,b,t=0;if (x.cw)a=0;b=n-a;while (a+b=1)t+;while (b=0)fai.xds=a;fai.yr=b;i+；a+;b-;a=0;b=n-a-t;elsea=1;b=0;t=0;while (a+b=0)fai.xds=a*(-1);fai.yr=b*(-1);i+;a-;b+;a=fa0.xds*(-1)+t;b=0

8、;return i;int jiancha(DataType x, int n) /安全性檢測，檢查當(dāng)前情況下，修道士是否安全if(x.xds=x.yr|x.xds=0)&(n-x.xds)=(n-x.yr)|x.xds=n)&x.xds=0&x.xds=0&x.yrdata;q=q-par;while (-i)-1)(printf( %d %d %d )”,ai.xds,ai.yr,ai.cw);if(!(ai.xds=0&ai.yr=0&ai.cw=0)if (ai.cw=1)printf( - ( %d %d ) - ( %d %d0 )n”,ai.xds-ai-1.xds,ai.yr-

9、ai-1 .yr,ai-1.xds,ai-1.yr);elseprintf( - ( %d %d ) son;while (q!=NULL)flag=0;j=findfa(q-data, c);for (i=0;idata.xds-fai.xds;tem.yr=q-data.yr-fai.yr;tem.cw=1-q-data.cw;t=q;if (jiancha (tem, n)flag1=1;while (t!=p)if (tem.xds=t-data.xds&tem.yr=t-data.yr&tem.cw=t-data.cw)flag1=0;break;t=t-par;if (flag1=

10、1)if (flag=0)insertson(q, tem);flag=1;elseinsertbro(q,tem);if(tem.xds=0&tem.yr=0&tem.cw=0)print(q, p);count+;q=q-next;if (count=0)printf(無法渡河成功。n);else printf(有1種方式渡河。n”,count) int main() /輸入Ltable *p;DataType tem;Ltableinit(&p);/初始化鄰接表； int n,c; while (1) printf(請(qǐng)輸入修道士與野人的人數(shù) n:n);scanf(%d”,&n); if (n=0) break;printf(請(qǐng)輸入船可容納的人數(shù) c:n);scanf(%d”,&c);tem.xds=n;tem.