1、一、 問(wèn)題描述迷宮圖從入口到出口有若干條通路，求從入口到出口最短路徑的走法。 圖1.1 迷宮示意圖二、 設(shè)計(jì)原理圖1.1為一簡(jiǎn)單迷宮示意圖的平面坐標(biāo)表示 。以平面坐標(biāo)圖來(lái)表示迷宮的通路時(shí)，問(wèn)題的狀態(tài)以所處的坐標(biāo)位置來(lái)表示，即綜合數(shù)據(jù)庫(kù)定義為(x, y) | 1x, y 4 ，則迷宮問(wèn)題歸結(jié)為求解從 (1, 1) 到 (4, 4)的最短路徑。迷宮走法規(guī)定為向東、南、西、北前進(jìn)一步，由此可得規(guī)則集簡(jiǎn)化形式如下。右移 R1：if(x, y) then (x+1, y) 如果當(dāng)前在(x, y)點(diǎn)，則向右移動(dòng)一步下移 R2：if(x, y) then (x,y -1) 如果當(dāng)前在(x, y)點(diǎn)，則向下移

2、動(dòng)一步左移 R1: if(x, y) then (x -1,y) 如果當(dāng)前在(x, y)點(diǎn)，則向左移動(dòng)一步上移 R2：if(x, y) then (x, y+1) 如果當(dāng)前在(x, y)點(diǎn)，則向上移動(dòng)一步給出其狀態(tài)空間如圖2.1所示為求得最佳路徑，可使用A*算法。A*算法f 函數(shù)定義 f(n) g(n) h(n) 設(shè)：每一步的耗散值為1（單位耗散值）定義：g(n) d(n) 從初始節(jié)點(diǎn)s到當(dāng)前節(jié)點(diǎn)n的搜索深度 h(n) | XgXn | | YgYn | 當(dāng)前節(jié)點(diǎn)n與目標(biāo)節(jié)點(diǎn)間的坐標(biāo)距離其中：( Xg, Yg) 目標(biāo)節(jié)點(diǎn)g坐標(biāo) ( Xn, Yn )當(dāng)前節(jié)點(diǎn)n坐標(biāo)顯然滿(mǎn)足： h(n) h*(n)

3、 OPEN表節(jié)點(diǎn)排序 按照f(shuō) 值 升序排列 如果f 值相同，則深度優(yōu)先A*算法的搜索過(guò)程如下：1、OPEN(s)， f(s)=g(s)+h(s)2、LOOP：if OPEN( ) then EXIT(FAIL)3、n FIRST(OPEN)4、if GOAL(n) THEN EXIT(SUCCESS)5、REMOVE(n,OPEN)，ADD(n,CLOSED)6、mi EXPAND(n) 計(jì)算f(n,mi)=g(n,mi)+h(mi)，(自s過(guò)n，mi到目標(biāo)節(jié)點(diǎn)的耗散值) ADD(mj,OPEN)，標(biāo)記mj到n的指針(mj不在OPEN和CLOSED中) if f(n,mk) f(mk) the

4、n f(mk) f(n,mk)，標(biāo)記mk到n的指針(mk在 OPEN中) if f(n,ml) f(ml) then f(ml) f(n,ml)，標(biāo)記ml到n的指針(ml在 CLOSED中)ADD(ml,OPEN)，把ml放回到OPEN中7、OPEN中的節(jié)點(diǎn)按照f(shuō)值升序排列8、GO LOOPA*算法的搜索圖示如圖2.2所示。則其搜索結(jié)果如圖2.3所示。 圖2.3 迷宮搜索結(jié)果示意圖三、 詳細(xì)設(shè)計(jì)（1）數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)為了在程序中表示迷宮圖，定義了一個(gè)6*6的二維整型數(shù)組int Maze77=3,1,3,1,3,0,3, 0,4,1,4,1,4,1, 3,1,3,0,3,1,3, 1,4,1,4,1

5、,4,1, 3,0,3,1,3,0,3, 1,4,1,4,1,4,1, 3,0,3,1,3,1,3;其中數(shù)字3代表坐標(biāo)點(diǎn)，1代表兩個(gè)坐標(biāo)點(diǎn)之間存在路徑，0代表兩個(gè)坐標(biāo)點(diǎn)之間不存在路徑，數(shù)字4沒(méi)有意義。從這個(gè)二維整型數(shù)組抽象出來(lái)的迷宮如下所示： 每個(gè)坐標(biāo)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下: struct Data int x; int y;int g; int f; struct Data *parent;其中x代表數(shù)組的第幾行對(duì)應(yīng)實(shí)際坐標(biāo)的y值，y代表數(shù)組的第幾列對(duì)應(yīng)實(shí)際坐標(biāo)的x值，g代表從入口到該坐標(biāo)點(diǎn)的耗散值，f代表代表評(píng)價(jià)函數(shù)值，parent代表路徑上的該坐標(biāo)點(diǎn)的前一個(gè)坐標(biāo)點(diǎn)。程序中對(duì)應(yīng)入口坐標(biāo)為（6，0

6、）也就是實(shí)際中的入口（1,1），實(shí)際中每走一步對(duì)應(yīng)程序中是x+2或x-2或y+2或y-2。程序中對(duì)應(yīng)的出口坐標(biāo)為（0,6）實(shí)際對(duì)應(yīng)著出口（4,4）。 實(shí)際中的h函數(shù)對(duì)應(yīng)程序中的h(n) |x0|/2| y6 |/2。因?yàn)閷?shí)際坐標(biāo)與程序中坐標(biāo)不對(duì)應(yīng)，所以需要一個(gè)轉(zhuǎn)換公式，如下:實(shí)際坐標(biāo)的x值等于程序中坐標(biāo)點(diǎn)的y值除以2再加1實(shí)際坐標(biāo)的y值等于5減去程序中坐標(biāo)點(diǎn)的x值除以2再減1判斷兩個(gè)坐標(biāo)點(diǎn)a,b之間是否存在路徑：p=(a-x+b-x)/2; q=(a-y+b-y)/2;如果Mazepq=1,則說(shuō)明a，b之間存在路徑，Mazepq=0，則說(shuō)明不存在路徑。為了將搜索結(jié)果圖形輸出，則又設(shè)置了Maze

7、pq=5，代表“”, Mazepq=6，代表“”，Mazepq=7，代表“”，Mazepq=8，代表“”。為了滿(mǎn)足open表中節(jié)點(diǎn)如果f 值相同，則深度優(yōu)先，使用一個(gè)棧來(lái)表示open表，closed表也是用一個(gè)棧來(lái)表示。（2）函數(shù)說(shuō)明bool bound(Data *a)函數(shù)功能:判斷一個(gè)坐標(biāo)點(diǎn)是否越過(guò)邊界，返回值bool值int h(Data *a)函數(shù)功能:h函數(shù)Data* Nopen(Data *a)函數(shù)功能:在open表中搜索結(jié)點(diǎn)a.若找到則返回結(jié)點(diǎn)a的地址，否則返回0Data* Nclosed(Data *a)函數(shù)功能: 在closed表中搜索結(jié)點(diǎn)a.若找到則返回結(jié)點(diǎn)a的地址，否則返

8、回0void sort()函數(shù)功能:對(duì)open表中節(jié)點(diǎn)按照f(shuō)值升序排列void Expand(Data *a)函數(shù)功能: 擴(kuò)展當(dāng)前結(jié)點(diǎn)avoid printmaze()函數(shù)功能:輸出迷宮void printpath(Data *a)函數(shù)功能:輸出搜索結(jié)果int A()函數(shù)功能: A*算法void main()函數(shù)功能:主函數(shù)（3）詳細(xì)程序設(shè)計(jì)#include#includeusing namespace std;int Maze77=3,1,3,1,3,0,3, 0,4,1,4,1,4,1, 3,1,3,0,3,1,3, 1,4,1,4,1,4,1, 3,0,3,1,3,0,3, 1,4,1,

9、4,1,4,1, 3,0,3,1,3,1,3;/3代表節(jié)點(diǎn)，1代表兩個(gè)節(jié)點(diǎn)之間有線，0代表兩個(gè)節(jié)點(diǎn)之間沒(méi)有線，4無(wú)意義struct Dataint x;int y;int g;int f;struct Data *parent;/坐標(biāo)點(diǎn)結(jié)構(gòu)體stack open; /open表stack closed; /close表bool bound(Data *a) /邊界函數(shù) return (a-xx=0)&(a-yy=0); int h(Data *a) /h函數(shù) return abs(a-x-0)/2)+abs(a-y-6)/2); Data* Nopen(Data *a)/在open表搜索a坐標(biāo)

10、點(diǎn) Data *b,*d;stack c;while(!open.empty() b=open.top();if(b-x=a-x&b-y=a-y) while(!c.empty() d=c.top(); c.pop(); open.push(d);return b;open.pop();c.push(b);while(!c.empty()d=c.top();c.pop();open.push(d);return 0;Data* Nclosed(Data *a) 在closed表搜索a坐標(biāo)點(diǎn) Data *b,*d;stack c;while(!closed.empty() b=closed.to

11、p();if(b-x=a-x&b-y=a-y) while(!c.empty()d=c.top();c.pop();closed.push(d);return b;closed.pop();c.push(b);while(!c.empty() d=c.top();c.pop();closed.push(d);return 0;void sort() 對(duì)open表中坐標(biāo)點(diǎn)排序Data *p,*q,*r;stack c;int b=open.size();for(int i=0;ib;i+) p=open.top();open.pop();for(int j=i+1;jff)r=p;p=q;q=r

12、; open.push(q); c.push(p);while(!c.empty() q=c.top();c.pop();open.push(q); void Expand(Data *a)/擴(kuò)展a坐標(biāo)點(diǎn) int p,q;Data *d;struct Data *b4;for(int i=0;ix=a-x+2;b0-y=a-y;b1-x=a-x;b1-y=a-y-2;b2-x=a-x-2;b2-y=a-y;b3-x=a-x;b3-y=a-y+2;for(i=0;ix+a-x)/2;q=(bi-y+a-y)/2;if(Mazepq=1) if(Nopen(bi)=0&Nclosed(bi)=0)

13、 bi-g=a-g+1;bi-f=bi-g+h(bi);bi-parent=a;open.push(bi);else if(Nopen(bi) d=Nopen(bi);if(a-g+1g) d-g=a-g+1;d-f=bi-g+h(bi);d-parent=a;else if(Nclosed(bi) if(a-g+1g) bi-g=a-g+1;bi-f=bi-g+h(bi);bi-parent=a;open.push(bi); void printmaze() /輸出迷宮 cout (4,4) endl;for(int i=0;i7;i+) if(i=6)cout入口;elsecout ;if

14、(i%2=0) for(int j=0;j7;j+) if(Mazeij=3)cout;else if(Mazeij=1)cout;else if(Mazeij=5)cout;else if(Mazeij=6) cout;elsecout ;if(i=0)cout出口;coutendl;else for(int j=0;j7;j+) if(Mazeij=1)cout; else if(Mazeij=7) cout;else if(Mazeij=8) cout;elsecout ; coutendl; cout (1,1)endlendl;void printpath(Data *a)/輸出搜索

15、結(jié)果 int b,c;stack q;while(!a-parent=NULL) q.push(a);b=(a-parent-x+a-x)/2; c=(a-parent-y+a-y)/2;if(a-parent-x=a-x) if(a-parent-ya-y) Mazebc=5;else Mazebc=6;else if(a-parent-xa-x) Mazebc=7;elseMazebc=8;a=a-parent;q.push(a);while(!q.empty()cout(y/2+1,x/2+1) ; q.pop();coutendlendl;printmaze(); int A() /A

16、*算法 Data s=6,0,0,0,NULL;Data *n=&s; open.push(n);while(1) if(open.empty() cout不存在路徑!x=0&n-y=6) cout最短路徑長(zhǎng)度為:fendlendl; cout最短路徑為:;printpath(n);return 1; else open.pop(); closed.push(n); Expand(n); /擴(kuò)展n節(jié)點(diǎn)sort(); /open中節(jié)點(diǎn)按照f(shuō)值升序排列 void main()/主函數(shù) cout迷宮如下圖:endl;printmaze();A();四、 設(shè)計(jì)結(jié)果及分析（1） 實(shí)驗(yàn)結(jié)果（2）實(shí)驗(yàn)分析從上面的圖中可以看出程序運(yùn)行結(jié)果與分