AI實(shí)驗(yàn)指導(dǎo)書(shū)-走迷宮

實(shí)驗(yàn)一走迷宮問(wèn)題一、實(shí)驗(yàn)?zāi)康模菏煜ず驼莆諉l(fā)式搜索的定義、估價(jià)函數(shù)和算法過(guò)程，并利用A*算法求解走迷宮問(wèn)題，理解求解流程和搜索順序。二、實(shí)驗(yàn)原理：A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)函數(shù)的定義上。對(duì)于一般的有序搜索，總是選擇f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此，f是根據(jù)需要找到一條最小代價(jià)路徑的觀點(diǎn)來(lái)估算節(jié)點(diǎn)的，所以，可考慮每個(gè)節(jié)點(diǎn)n的估價(jià)函數(shù)值為兩個(gè)分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的代價(jià)以及從節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的代價(jià)。三、實(shí)驗(yàn)環(huán)境1.VC6.0/C++/C2.走迷宮程序流程圖四、實(shí)驗(yàn)內(nèi)容1以走迷宮問(wèn)題為例實(shí)際求解A*算法。2畫(huà)出A*算法求解框圖。3分析估價(jià)函數(shù)對(duì)搜索算法的影響。4分析A*算法的特點(diǎn)。五、實(shí)驗(yàn)步驟1.分析問(wèn)題，定義估價(jià)函數(shù)。2.編寫(xiě)程序，實(shí)驗(yàn)算法。3.改變估價(jià)函數(shù)，比較不同估價(jià)函數(shù)對(duì)算法的影響。六、實(shí)驗(yàn)報(bào)告要求1

A*算法流程圖和算法框圖。2

試分析估價(jià)函數(shù)的值對(duì)搜索算法速度的影響。3

根據(jù)A*算法分析啟發(fā)式搜索的特點(diǎn)。七、參考程序說(shuō)明：該程序只作為參考程序，作為走迷宮問(wèn)題的算法，從時(shí)間復(fù)雜度和空間復(fù)雜度考慮，它不是最優(yōu)算法，但它利用了啟發(fā)信息，能找到最短路徑。同學(xué)們可以從時(shí)間復(fù)雜度上考慮寫(xiě)出更優(yōu)的算法。函數(shù)調(diào)用說(shuō)明：

1、

voidAddClosed(structGather

*des)

des為structGather*類(lèi)型的結(jié)點(diǎn)；

該函數(shù)的功能是將des結(jié)點(diǎn)加到CLOSED集合中，無(wú)返回值。

2、

voidPartInit_Point(void)

無(wú)行參，無(wú)返回值。

該函數(shù)的功能是初始化PointP[]中的部分成員。

3、

voidAddOpen(structPointdes)

行參為structPoint類(lèi)型，可以直接將P[i]作行參。

該函數(shù)的功能是將點(diǎn)des加到OPEN集合中。

4、

boolGoal(structGather*n)

行參為structGather*類(lèi)型,返回值為bool型。

該函數(shù)的功能是判斷n是不是目標(biāo)結(jié)點(diǎn)。是返回TRUE,否返回FALSE;

５、

boolIsOpenEmpty(void)

返回值為bool型。OPEN集合為空，返回TRUE,否則返回FALSE;

６、

voidRemove(structGather*des)

des為structGather*類(lèi)型的結(jié)點(diǎn)；

該函數(shù)的功能是將des從OPEN集合中刪除。

７、

structGather*First(void)

返回structGather*類(lèi)型的結(jié)點(diǎn)；

該函數(shù)的功能是取OPEN集合中存儲(chǔ)的第一個(gè)有效結(jié)點(diǎn)。創(chuàng)建OPEN集合時(shí)，頭結(jié)點(diǎn)未存有效結(jié)點(diǎn)。

８、

intInOPENorCLOSED(structPointR)

返回值為int型，行參為structPoint類(lèi)型。用法InOPENorCLOSED(P[i])

該函數(shù)的功能是判斷點(diǎn)R在OPEN集合，或者CLOSED集合，或者都不在

在OPEN中，返回0

在CLOSED中，返回1

都不在，返回2

9、

voidExpand(structGather*curr)

無(wú)返回值，行參為structPoint類(lèi)型

該函數(shù)的功能是擴(kuò)展當(dāng)前結(jié)點(diǎn)curr。

10、

voidDrawMap(void)

畫(huà)個(gè)草圖。#include<iostream>usingnamespacestd;constintPointNum=16;//迷宮點(diǎn)的總數(shù)constintSideNum=18;//迷宮邊的總數(shù)structPoint{intx;/*橫坐標(biāo)*/inty;/*縱坐標(biāo)*/intF;/*評(píng)價(jià)函數(shù)值*/intH;/*當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的橫截距與縱截距之和*/intD;/*深度*/intindex;/*點(diǎn)的編號(hào)*/intpre;/*保存路徑，作標(biāo)志指針之用*/};structIndex{intfrom;/*邊的起點(diǎn)*/intto;/*邊的終點(diǎn)注：由于是無(wú)向圖，from，to既是起點(diǎn)又是終點(diǎn)。*/};structGather{structPointpnode;structGather*next;};//存儲(chǔ)點(diǎn)的信息共PointNum個(gè)點(diǎn)structPointP[PointNum]={{1,1,0,0,0,0,-1},{1,2,0,0,0,1,-2},{1,3,0,0,0,2,-2},{1,4,0,0,0,3,-2},{2,1,0,0,0,4,-2},{2,2,0,0,0,5,-2},{2,3,0,0,0,6,-2},{2,4,0,0,0,7,-2},{3,1,0,0,0,8,-2},{3,2,0,0,0,9,-2},{3,3,0,0,0,10,-2},{3,4,0,0,0,11,-2},{4,1,0,0,0,12,-2},{4,2,0,0,0,13,-2},{4,3,0,0,0,14,-2},{4,4,0,0,0,15,-2}};//存儲(chǔ)邊的信息共SideNum個(gè)邊structIndexIn[SideNum]={{0,1},{1,2},{2,6},{3,7},{4,5},{4,8},{5,6},{5,9},{6,7},{7,11},{8,9},{8,12},{9,10},{10,11},{10,14},{12,13},{13,14},{14,15}};//OPEN,CLOSED集合中頭結(jié)點(diǎn)不存數(shù)據(jù)，且設(shè)OPEN,CLOSED為指針類(lèi)型的常量//確保OPEN,CLOSED兩全局指針不被意外修改。structGather*constOPEN=newstructGather;structGather*constCLOSED=newstructGather;//將結(jié)點(diǎn)加到CLOSED集合中voidAddClosed(structGather*des){des->next=CLOSED->next;CLOSED->next=des;}//部分初始化voidPartInit_Point(void){for(inti=0;i<PointNum;i++){P[i].H=(4-P[i].x)+(4-P[i].y);}P[0].D=0;P[0].F=P[0].H+P[0].D;OPEN->next=NULL;CLOSED->next=NULL;}//將點(diǎn)加到OPEN集合中，插入，確保OPEN集合中的點(diǎn)是按照F值由小到大排序的voidAddOpen(structPointdes){structGather*q=OPEN,*r=NULL,*temp=newstructGather;temp->pnode=des;while((q->next!=NULL)&&(q->next->pnode.F<des.F)){q=q->next;}r=q->next;temp->next=r;q->next=temp;}///////////////////////////////////////////////////////////////////////////判斷是否到達(dá)終點(diǎn),到達(dá)則返回TrueboolGoal(structGather*n){if(n->pnode.index==15)//該迷宮(課本)的目標(biāo)結(jié)點(diǎn)編號(hào)是15[自定義]returntrue;elsereturnfalse;}//判斷Open集合是不是為空，空則返回TrueboolIsOpenEmpty(void){if(OPEN->next==NULL)returntrue;elsereturnfalse;}//將des結(jié)點(diǎn)從OPEN集合中刪除voidRemove(structGather*des){structGather*p=OPEN,*q=NULL;while((p->next!=NULL)&&(p->next->pnode.index!=des->pnode.index)){p=p->next;}if(p->next==NULL)cout<<"ErroroccurswhendeletenodefromOpen!"<<endl;else{q=p->next;p->next=q->next;}}//取OPEN集合中存的第一個(gè)結(jié)點(diǎn)[注意：OPEN頭結(jié)點(diǎn)未存數(shù)據(jù)]structGather*First(void){returnOPEN->next;}//判斷點(diǎn)R在OPEN,CLOSED集合中，還是都不在intInOPENorCLOSED(structPointR){for(structGather*p=OPEN;p->next!=NULL;p=p->next){if(p->next->pnode.index==R.index)return0;//在OPEN中}for(p=CLOSED;p->next!=NULL;p=p->next){if(p->next->pnode.index==R.index)return1;//在CLOSED中}return2;//都不在}//擴(kuò)展結(jié)點(diǎn)遇到的三種情況處理voidProcess(structPoint*A,structGather*curr){(*A).D++;(*A).F=(*A).D+(*A).H;if(InOPENorCLOSED(*A)==2)//如果A不在OPEN,CLOSED集合中{AddOpen(*A);//將A加到OPEN集合中(*A).pre=curr->pnode.index;//標(biāo)志指針（游標(biāo)）}if(InOPENorCLOSED(*A)==0)//如果A在OPEN集合中{structGather*r=OPEN;while((r->next!=NULL)&&(r->next->pnode.index!=(*A).index)){r=r->next;}if((*A).F<r->next->pnode.F){r->next->pnode.F=(*A).F;//修改OPEN集合中結(jié)點(diǎn)A的F值(*A).pre=curr->pnode.index;//標(biāo)志指針（游標(biāo)）}}if(InOPENorCLOSED(*A)==1)//如果A在CLOSED集合中{structGather*r=CLOSED;while((r->next!=NULL)&&(r->next->pnode.index!=(*A).index)){r=r->next;}if((*A).F<r->next->pnode.F){(*A).pre=curr->pnode.index;//標(biāo)志指針（游標(biāo)）AddOpen(*A);//將A重新放到OPEN集合中}}}//擴(kuò)展當(dāng)前結(jié)點(diǎn)currvoidExpand(structGather*curr){for(inti=0;i<SideNum;i++){if(In[i].from==curr->pnode.index){intt=In[i].to;Process(&P[t],curr);}//由于是無(wú)向圖，可以由點(diǎn)from擴(kuò)展到點(diǎn)to;同樣可以由點(diǎn)to擴(kuò)展到點(diǎn)fromif(In[i].to==curr->pnode.index){intt=In[i].from;Process(&P[t],curr);}}//endfor}//畫(huà)初始的迷宮圖voidDrawMap(void){cout<<"Theprimarygraphis:"<<endl<<endl;cout<<"()_____()_____()()"<<endl<<"||"<<endl <<"||"<<endl<<"()_____()_____()_____()"<<endl<<"|||"<<endl <<"|||"<<endl<<"()_____()_____()_____()"<<endl <<"||"<<endl <<"|