AI實驗指導書-走迷宮

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

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

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

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

1、

voidAddClosed(structGather

*des)

des為structGather*類型的結(jié)點；

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

2、

voidPartInit_Point(void)

無行參，無返回值。

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

3、

voidAddOpen(structPointdes)

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

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

4、

boolGoal(structGather*n)

行參為structGather*類型,返回值為bool型。

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

５、

boolIsOpenEmpty(void)

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

６、

voidRemove(structGather*des)

des為structGather*類型的結(jié)點；

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

７、

structGather*First(void)

返回structGather*類型的結(jié)點；

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

８、

intInOPENorCLOSED(structPointR)

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

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

在OPEN中，返回0

在CLOSED中，返回1

都不在，返回2

9、

voidExpand(structGather*curr)

無返回值，行參為structPoint類型

該函數(shù)的功能是擴展當前結(jié)點curr。

10、

voidDrawMap(void)

畫個草圖。#include<iostream>usingnamespacestd;constintPointNum=16;//迷宮點的總數(shù)constintSideNum=18;//迷宮邊的總數(shù)structPoint{intx;/*橫坐標*/inty;/*縱坐標*/intF;/*評價函數(shù)值*/intH;/*當前點到目標點的橫截距與縱截距之和*/intD;/*深度*/intindex;/*點的編號*/intpre;/*保存路徑，作標志指針之用*/};structIndex{intfrom;/*邊的起點*/intto;/*邊的終點注：由于是無向圖，from，to既是起點又是終點。*/};structGather{structPointpnode;structGather*next;};//存儲點的信息共PointNum個點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}};//存儲邊的信息共SideNum個邊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é)點不存數(shù)據(jù)，且設(shè)OPEN,CLOSED為指針類型的常量//確保OPEN,CLOSED兩全局指針不被意外修改。structGather*constOPEN=newstructGather;structGather*constCLOSED=newstructGather;//將結(jié)點加到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;}//將點加到OPEN集合中，插入，確保OPEN集合中的點是按照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;}///////////////////////////////////////////////////////////////////////////判斷是否到達終點,到達則返回TrueboolGoal(structGather*n){if(n->pnode.index==15)//該迷宮(課本)的目標結(jié)點編號是15[自定義]returntrue;elsereturnfalse;}//判斷Open集合是不是為空，空則返回TrueboolIsOpenEmpty(void){if(OPEN->next==NULL)returntrue;elsereturnfalse;}//將des結(jié)點從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集合中存的第一個結(jié)點[注意：OPEN頭結(jié)點未存數(shù)據(jù)]structGather*First(void){returnOPEN->next;}//判斷點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;//都不在}//擴展結(jié)點遇到的三種情況處理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;//標志指針（游標）}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é)點A的F值(*A).pre=curr->pnode.index;//標志指針（游標）}}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;//標志指針（游標）AddOpen(*A);//將A重新放到OPEN集合中}}}//擴展當前結(jié)點currvoidExpand(structGather*curr){for(inti=0;i<SideNum;i++){if(In[i].from==curr->pnode.index){intt=In[i].to;Process(&P[t],curr);}//由于是無向圖，可以由點from擴展到點to;同樣可以由點to擴展到點fromif(In[i].to==curr->pnode.index){intt=In[i].from;Process(&P[t],curr);}}//endfor}//畫初始的迷宮圖voidDrawMap(void){cout<<"Theprimarygraphis:"<<endl<<endl;cout<<"()_____()_____()()"<<endl<<"||"<<endl <<"||"<<endl<<"()_____()_____()_____()"<<endl<<"|||"<<endl <<"|||"<<endl<<"()_____()_____()_____()"<<endl <<"||"<<endl <<"|