你可以先把你寫的程序發(fā)上來，一方面是幫你修改一下，方便你學(xué)習(xí)，另一方面我的程序不一定適合你的要求。我們在上人工智能的時候?qū)戇^與之類似的程序，八數(shù)碼，八皇后，迷宮之類。
成都創(chuàng)新互聯(lián)主要為客戶提供服務(wù)項目涵蓋了網(wǎng)頁視覺設(shè)計、VI標(biāo)志設(shè)計、營銷推廣、網(wǎng)站程序開發(fā)、HTML5響應(yīng)式成都網(wǎng)站建設(shè)公司、手機(jī)網(wǎng)站制作設(shè)計、微商城、網(wǎng)站托管及成都網(wǎng)站維護(hù)公司、WEB系統(tǒng)開發(fā)、域名注冊、國內(nèi)外服務(wù)器租用、視頻、平面設(shè)計、SEO優(yōu)化排名。設(shè)計、前端、后端三個建站步驟的完善服務(wù)體系。一人跟蹤測試的建站服務(wù)標(biāo)準(zhǔn)。已經(jīng)為成都門窗定制行業(yè)客戶提供了網(wǎng)站營銷推廣服務(wù)。
八數(shù)碼問題
一.八數(shù)碼問題
八數(shù)碼問題也稱為九宮問題。在3×3的棋盤，擺有八個棋子，每個棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個空格，與空格相鄰的棋子可以移到空格中。要求解決的問題是：給出一個初始狀態(tài)和一個目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動棋子步數(shù)最少的移動步驟。所謂問題的一個狀態(tài)就是棋子在棋盤上的一種擺法。棋子移動后，狀態(tài)就會發(fā)生改變。解八數(shù)碼問題實際上就是找出從初始狀態(tài)到達(dá)目標(biāo)狀態(tài)所經(jīng)過的一系列中間過渡狀態(tài)。
八數(shù)碼問題一般使用搜索法來解。搜索法有廣度優(yōu)先搜索法、深度優(yōu)先搜索法、A*算法等。這里通過用不同方法解八數(shù)碼問題來比較一下不同搜索法的效果。
二.搜索算法基類
1.八數(shù)碼問題的狀態(tài)表示
八數(shù)碼問題的一個狀態(tài)就是八個數(shù)字在棋盤上的一種放法。每個棋子用它上面所標(biāo)的數(shù)字表示，并用0表示空格，這樣就可以將棋盤上棋子的一個狀態(tài)存儲在一個一維數(shù)組p[9]中，存儲的順序是從左上角開始，自左至右，從上到下。也可以用一個二維數(shù)組來存放。
2.結(jié)點
搜索算法中，問題的狀態(tài)用結(jié)點描述。結(jié)點中除了描述狀態(tài)的數(shù)組p[9]外，還有一個父結(jié)點指針last，它記錄了當(dāng)前結(jié)點的父結(jié)點編號，如果一個結(jié)點v是從結(jié)點u經(jīng)狀態(tài)變化而產(chǎn)生的，則結(jié)點u就是結(jié)點v的父結(jié)點，結(jié)點v的last記錄的就是結(jié)點u的編號。在到達(dá)目標(biāo)結(jié)點后，通過last 可以找出搜索的路徑。
3.類的結(jié)構(gòu)
在C++中用類來表示結(jié)點，類將結(jié)點有關(guān)的數(shù)據(jù)操作封裝在一起。
不同的搜索算法具有一定共性，也有各自的個性，因此這里將不同搜索算法的共有的數(shù)據(jù)和功能封裝在一個基類中，再通過繼承方式實現(xiàn)不同的搜索算法。
4.結(jié)點擴(kuò)展規(guī)則
搜索就是按照一定規(guī)則擴(kuò)展已知結(jié)點，直到找到目標(biāo)結(jié)點或所有結(jié)點都不能擴(kuò)展為止。
八數(shù)碼問題的結(jié)點擴(kuò)展應(yīng)當(dāng)遵守棋子的移動規(guī)則。按照棋子移動的規(guī)則，每一次可以將一個與空格相鄰棋子移動到空格中，實際上可以看作是空格作相反移動。空格移動的方向可以是右、下、左、上，當(dāng)然不能移出邊界。棋子的位置，也就是保存狀態(tài)的數(shù)組元素的下標(biāo)?？崭褚苿雍?，它的位置發(fā)生變化，在不移出界時，空格向右、下、左和上移動后，新位置是原位置分別加上1、3、-1、-3，如果將空格向右、下、左和上移動分別用0、1、2、3表示，并將-3、3、-1、1放在靜態(tài)數(shù)組d[4]中，空格位置用spac表示，那么空格向方向i移動后，它的位置變?yōu)閟pac+d[i]。空格移動所產(chǎn)生的狀態(tài)變化，反映出來則是將數(shù)組p[]中，0的新位置處的數(shù)與0交換位置。
5.八數(shù)碼問題的基類
八數(shù)碼問題的基類及其成員函數(shù)的實現(xiàn)如下：
#define Num 9
class TEight
{
public:
TEight(){}
TEight(char *fname); //用文件數(shù)據(jù)構(gòu)造節(jié)點
virtual void Search()=0; //搜索
protected:
int p[Num];
int last,spac;
static int q[Num],d[],total;
void Printf();
bool operator==(const TEight T);
bool Extend(int i);
};
int TEight::q[Num];//儲存目標(biāo)節(jié)點
int TEight::d[]={1,3,-1,-3};//方向
int TEight::total=0;//步數(shù)
TEight::TEight(char *fname)
{
ifstream fin;
fin.open(fname,ios::in);
if(!fin)
{
cout"不能打開數(shù)據(jù)文件!"endl;
return;
}
int i;
for(i=0;iNum;)//得到源節(jié)點
finp[i++];
finspac;
for(i=0;iNum;)//得到目標(biāo)節(jié)點
finq[i++];
fin.close();
last=-1;
total=0;
}
void TEight::Printf()//把路徑打印到結(jié)果文件
{
ofstream fout;
fout.open("eight_result.txt",ios::ate|ios::app);
fouttotal++"t";
for(int i=0;iNum;)
fout" "p[i++];
foutendl;
fout.close();
}
bool TEight::operator==(const TEight T)//判斷兩個狀態(tài)是否相同
{
for(int i=0;iNum;)
if(T.p[i]!=p[i++])
return 0;
return 1;
}
bool TEight::Extend(int i)//擴(kuò)展
{
if(i==0 spac%3==2 || i==1 spac5
|| i==2 spac%3==0 || i==3 spac3)
return 0;
int temp=spac;
spac+=d[i];
p[temp]=p[spac];
p[spac]=0;
return 1;
}
數(shù)據(jù)文件的結(jié)構(gòu)：
一共三行，第一行是用空格隔開的九個數(shù)字0~8，這是初始狀態(tài)。第二行是一個數(shù)字，空格（數(shù)字0）的位置，第三行也是用空格隔開的九個數(shù)字0~8，這是目標(biāo)狀態(tài)。
三.線性表
搜索法在搜索過程中，需要使用一個隊列存儲搜索的中間結(jié)點，為了在找到目標(biāo)結(jié)點后，能夠找到從初始結(jié)點到目標(biāo)結(jié)點的路徑，需要保留所有搜索過的結(jié)點。另一方面，不同問題甚至同一問題的不同搜索方法中，需要存儲的結(jié)點數(shù)量相差很大，所以這里采用鏈?zhǔn)骄€性表作為存儲結(jié)構(gòu)，同時，為適應(yīng)不同問題，線性表設(shè)計成類模板形式。
templateclass Type class TList; //線性表前視定義
templateclass Type class TNode //線性表結(jié)點類模板
{
friend class TListType;
public:
TNode(){}
TNode(const Type dat);
private:
TNodeType* Next;
Type Data;
};
templateclass Type class TList
{
public:
TList(){Last=First=0;Length=0;} //構(gòu)造函數(shù)
int Getlen()const{return Length;} //成員函數(shù)，返回線性表長度
int Append(const Type T); //成員函數(shù)，從表尾加入結(jié)點
int Insert(const Type T,int k); //成員函數(shù)，插入結(jié)點
Type GetData(int i); //成員函數(shù)，返回結(jié)點數(shù)據(jù)成員
void SetData(const Type T,int k); //成員函數(shù)，設(shè)置結(jié)點數(shù)據(jù)成員
private:
TNodeType *First,*Last; //數(shù)據(jù)成員，線性表首、尾指針
int Length; //數(shù)據(jù)成員，線性表長度
};
templateclass Type int TListType::Append(const Type T)
{
Insert(T,Length);
return 1;
}
templateclass Type int TListType::Insert(const Type T,int k)
{
TNodeType *p=new TNodeType;
p-Data=T;
if(First)
{
if(k=0)
{
p-Next=First;
First=p;
}
if(kLength-1)
{
Last-Next=p;
Last=Last-Next;
Last-Next=0;
}
if(k0 kLength)
{
k--;
TNodeType *q=First;
while(k--0)
q=q-Next;
p-Next=q-Next;
q-Next=p;
}
}
else
{
First=Last=p;
First-Next=Last-Next=0;
}
Length++;
return 1;
}
templateclass Type Type TListType::GetData(int k)
{
TNodeType *p=First;
while(k--0)
p=p-Next;
return p-Data;
}
templateclass Type void TListType::SetData(const Type T,int k)
{
TNodeType *p=First;
while(k--0)
p=p-Next;
p-Data=T;
}
線性表單獨以頭文件形式存放。
四.廣度優(yōu)先搜索法
在搜索法中，廣度優(yōu)先搜索法是尋找最短路經(jīng)的首選。
1.廣度優(yōu)先搜索算法的基本步驟
1）建立一個隊列，將初始結(jié)點入隊，并設(shè)置隊列頭和尾指針
2）取出隊列頭（頭指針?biāo)福┑慕Y(jié)點進(jìn)行擴(kuò)展，從它擴(kuò)展出子結(jié)點，并將這些結(jié)點按擴(kuò)展的順序加入隊列。
3）如果擴(kuò)展出的新結(jié)點與隊列中的結(jié)點重復(fù)，則拋棄新結(jié)點，跳至第六步。
4）如果擴(kuò)展出的新結(jié)點與隊列中的結(jié)點不重復(fù)，則記錄其父結(jié)點，并將它加入隊列，更新隊列尾指針。
5）如果擴(kuò)展出的結(jié)點是目標(biāo)結(jié)點，則輸出路徑，程序結(jié)束。否則繼續(xù)下一步。
6）如果隊列頭的結(jié)點還可以擴(kuò)展，直接返回第二步。否則將隊列頭指針指向下一結(jié)點，再返回第二步。
2.搜索路徑的輸出
搜索到目標(biāo)結(jié)點后，需要輸出搜索的路徑。每個結(jié)點有一個數(shù)據(jù)域last，它記錄了結(jié)點的父結(jié)點，因此輸出搜索路徑時，就是從目標(biāo)結(jié)點Q出發(fā)，根據(jù)last找到它的父結(jié)點，再根據(jù)這個結(jié)點的last找到它的父結(jié)點，....,最后找到初始結(jié)點。搜索的路徑就是從初始結(jié)點循相反方向到達(dá)目標(biāo)結(jié)點的路徑。
3.廣度優(yōu)先搜索法TBFS類的結(jié)構(gòu)
廣度優(yōu)先搜索法TBFS類是作為TEight類的一個子類。其類的結(jié)構(gòu)和成員函數(shù)的實現(xiàn)如下：
class TBFS:public TEight
{
public:
TBFS(){}
TBFS(char *fname):TEight(fname){}
virtual void Search();
private:
void Printl(TListTBFS L);
int Repeat(TListTBFS L);
int Find();
};
void TBFS::Printl(TListTBFS L)
{
TBFS T=*this;
if(T.last==-1)
return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}
int TBFS::Repeat(TListTBFS L)
{
int n=L.Getlen();
int i;
for(i=0;in;i++)
if(L.GetData(i)==*this)
break;
return i;
}
int TBFS::Find()
{
for(int i=0;iNum;)
if(p[i]!=q[i++])
return 0;
return 1;
}
void TBFS::Search()
{
TBFS T=*this;
TListTBFS L;
L.Append(T);
int head=0,tail=0;
while(head=tail)
{
for(int i=0;i4;i++)
{
T=L.GetData(head);
if(T.Extend(i) T.Repeat(L)tail)
{
T.last=head;
L.Append(T);
tail++;
}
if(T.Find())
{
T.Printl(L);
T.Printf();
return;
}
}
head++;
}
}
4.廣度優(yōu)先搜索法的缺點
廣度優(yōu)先搜索法在有解的情形總能保證搜索到最短路經(jīng)，也就是移動最少步數(shù)的路徑。但廣度優(yōu)先搜索法的最大問題在于搜索的結(jié)點數(shù)量太多，因為在廣度優(yōu)先搜索法中，每一個可能擴(kuò)展出的結(jié)點都是搜索的對象。隨著結(jié)點在搜索樹上的深度增大，搜索的結(jié)點數(shù)會很快增長，并以指數(shù)形式擴(kuò)張，從而所需的存儲空間和搜索花費的時間也會成倍增長。
五、A*算法
1.啟發(fā)式搜索
廣度優(yōu)先搜索和雙向廣度優(yōu)先搜索都屬于盲目搜索，這在狀態(tài)空間不大的情況下是很合適的算法，可是當(dāng)狀態(tài)空間十分龐大時，它們的效率實在太低，往往都是在搜索了大量無關(guān)的狀態(tài)結(jié)點后才碰到解答，甚至更本不能碰到解答。
搜索是一種試探性的查尋過程，為了減少搜索的盲目性引，增加試探的準(zhǔn)確性，就要采用啟發(fā)式搜索了。所謂啟發(fā)式搜索就是在搜索中要對每一個搜索的位置進(jìn)行評估，從中選擇最好、可能容易到達(dá)目標(biāo)的位置，再從這個位置向前進(jìn)行搜索，這樣就可以在搜索中省略大量無關(guān)的結(jié)點，提高了效率。
2.A*算法
A*算法是一種常用的啟發(fā)式搜索算法。
在A*算法中，一個結(jié)點位置的好壞用估價函數(shù)來對它進(jìn)行評估。A*算法的估價函數(shù)可表示為：
f'(n) = g'(n) + h'(n)
這里，f'(n)是估價函數(shù)，g'(n)是起點到終點的最短路徑值（也稱為最小耗費或最小代價），h'(n)是n到目標(biāo)的最短路經(jīng)的啟發(fā)值。由于這個f'(n)其實是無法預(yù)先知道的，所以實際上使用的是下面的估價函數(shù)：
f(n) = g(n) + h(n)
其中g(shù)(n)是從初始結(jié)點到節(jié)點n的實際代價，h(n)是從結(jié)點n到目標(biāo)結(jié)點的最佳路徑的估計代價。在這里主要是h(n)體現(xiàn)了搜索的啟發(fā)信息，因為g(n)是已知的。用f(n)作為f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。這樣必須滿足兩個條件：（1）g(n)=g'(n)（大多數(shù)情況下都是滿足的，可以不用考慮），且f必須保持單調(diào)遞增。（2）h必須小于等于實際的從當(dāng)前節(jié)點到達(dá)目標(biāo)節(jié)點的最小耗費h(n)=h'(n)。第二點特別的重要?？梢宰C明應(yīng)用這樣的估價函數(shù)是可以找到最短路徑的。
3.A*算法的步驟
A*算法基本上與廣度優(yōu)先算法相同，但是在擴(kuò)展出一個結(jié)點后，要計算它的估價函數(shù)，并根據(jù)估價函數(shù)對待擴(kuò)展的結(jié)點排序，從而保證每次擴(kuò)展的結(jié)點都是估價函數(shù)最小的結(jié)點。
A*算法的步驟如下：
1）建立一個隊列，計算初始結(jié)點的估價函數(shù)f，并將初始結(jié)點入隊，設(shè)置隊列頭和尾指針。
2）取出隊列頭（隊列頭指針?biāo)福┑慕Y(jié)點，如果該結(jié)點是目標(biāo)結(jié)點，則輸出路徑，程序結(jié)束。否則對結(jié)點進(jìn)行擴(kuò)展。
3）檢查擴(kuò)展出的新結(jié)點是否與隊列中的結(jié)點重復(fù)，若與不能再擴(kuò)展的結(jié)點重復(fù)（位于隊列頭指針之前），則將它拋棄；若新結(jié)點與待擴(kuò)展的結(jié)點重復(fù)（位于隊列頭指針之后），則比較兩個結(jié)點的估價函數(shù)中g(shù)的大小，保留較小g值的結(jié)點。跳至第五步。
4）如果擴(kuò)展出的新結(jié)點與隊列中的結(jié)點不重復(fù)，則按照它的估價函數(shù)f大小將它插入隊列中的頭結(jié)點后待擴(kuò)展結(jié)點的適當(dāng)位置，使它們按從小到大的順序排列，最后更新隊列尾指針。
5）如果隊列頭的結(jié)點還可以擴(kuò)展，直接返回第二步。否則將隊列頭指針指向下一結(jié)點，再返回第二步。
4.八數(shù)碼問題的A*算法的估價函數(shù)
估價函數(shù)中，主要是計算h，對于不同的問題，h有不同的含義。那么在八數(shù)碼問題中，h的含意是各什么？八數(shù)碼問題的一個狀態(tài)實際上是數(shù)字0~8的一個排列，用一個數(shù)組p[9]來存儲它，數(shù)組中每個元素的下標(biāo)，就是該數(shù)在排列中的位置。例如，在一個狀態(tài)中，p[3]=7，則數(shù)字7的位置是3。如果目標(biāo)狀態(tài)數(shù)字3的位置是8，那么數(shù)字7對目標(biāo)狀態(tài)的偏移距離就是3，因為它要移動3步才可以回到目標(biāo)狀態(tài)的位置。
八數(shù)碼問題中，每個數(shù)字可以有9個不同的位置，因此，在任意狀態(tài)中的每個數(shù)字和目標(biāo)狀態(tài)中同一數(shù)字的相對距離就有9*9種，可以先將這些相對距離算出來，用一個矩陣存儲，這樣只要知道兩個狀態(tài)中同一個數(shù)字的位置，就可查出它們的相對距離，也就是該數(shù)字的偏移距離：
0 1 2 3 4 5 6 7 8
0 0 1 2 1 2 3 2 3 4
1 1 0 1 2 1 2 3 2 3
2 2 1 0 3 2 1 4 3 2
3 1 2 3 0 1 2 1 2 3
4 2 1 2 1 0 1 2 1 2
5 3 2 1 2 1 0 3 2 1
6 2 3 4 1 2 3 0 1 2
7 3 2 3 2 1 2 1 0 1
8 4 3 2 3 2 1 2 1 0
例如在一個狀態(tài)中，數(shù)字8的位置是3，在另一狀態(tài)中位置是7，那么從矩陣的3行7列可找到2，它就是8在兩個狀態(tài)中的偏移距離。
估價函數(shù)中的h就是全體數(shù)字偏移距離之和。顯然，要計算兩個不同狀態(tài)中同一數(shù)字的偏移距離，需要知道該數(shù)字在每個狀態(tài)中的位置，這就要對數(shù)組p[9]進(jìn)行掃描。由于狀態(tài)發(fā)生變化，個數(shù)字的位置也要變化，所以每次計算h都沿線掃描數(shù)組，以確定每個數(shù)字在數(shù)組中的位置。為了簡化計算，這里用一個數(shù)組存儲狀態(tài)中各個數(shù)字的位置，并讓它在狀態(tài)改變時隨著變化，這樣就不必在每次計算h時，再去掃描狀態(tài)數(shù)組。
例如，某個狀態(tài)中，數(shù)字5的位置是8，如果用數(shù)組r[9]存儲位置，那么就有r[5]=8。
現(xiàn)在用數(shù)組r[9]存儲當(dāng)前狀態(tài)的數(shù)字位置，而用s[9]存儲目標(biāo)狀態(tài)的數(shù)字位置，那么當(dāng)前狀態(tài)數(shù)字i對目標(biāo)狀態(tài)的偏移距離就是矩陣中r[i]行s[i]列對應(yīng)的值。
5.A*算法的類結(jié)構(gòu)
A*算法的類聲明如下：
class TAstar:public TEight
{
public:
TAstar(){} //構(gòu)造函數(shù)
TAstar(char *fname); //帶參數(shù)構(gòu)造函數(shù)
virtual void Search(); //A*搜索法
private:
int f,g,h; //估價函數(shù)
int r[Num]; //存儲狀態(tài)中各個數(shù)字位置的輔助數(shù)組
static int s[Num]; //存儲目標(biāo)狀態(tài)中各個數(shù)字位置的輔助數(shù)組
static int e[]; //存儲各個數(shù)字相對距離的輔助數(shù)組
void Printl(TListTAstar L); //成員函數(shù)，輸出搜索路徑
int Expend(int i); //成員函數(shù)，A*算法的狀態(tài)擴(kuò)展函數(shù)
int Calcuf(); //成員函數(shù)，計算估價函數(shù)
void Sort(TListTAstar L,int k); //成員函數(shù)，將新擴(kuò)展結(jié)點按f從小到大順序插入待擴(kuò)展結(jié)點隊列
int Repeat(TListTAstar L); //成員函數(shù)，檢查結(jié)點是否重復(fù)
};
int TAstar::s[Num],TAstar::e[Num*Num];
TAstar::TAstar(char *fname):TEight(fname)
{
for(int i=0;iNum;)
{
r[p[i]]=i; //存儲初始狀態(tài)個個數(shù)字的位置
s[q[i]]=i++; //存儲目標(biāo)狀態(tài)個個數(shù)字的位置
}
ifstream fin;
fin.open("eight_dis.txt",ios::in); //打開數(shù)據(jù)文件
if(!fin)
{
cout"不能打開數(shù)據(jù)文件!"endl;
return;
}
for(int i=0;iNum*Num;i++) //讀入各個數(shù)字相對距離值
fine[i];
fin.close();
f=g=h=0; //估價函數(shù)初始值
}
void TAstar::Printl(TListTAstar L)
{
TAstar T=*this;
if(T.last==-1) return;
else
{
T=L.GetData(T.last);
T.Printl(L);
T.Printf();
}
}
int TAstar::Expend(int i)
{
if(Extend(i)) //結(jié)點可擴(kuò)展
{
int temp=r[p[r[0]]]; //改變狀態(tài)后數(shù)字位置變化，存儲改變后的位置
r[p[r[0]]]=r[0];
r[0]=temp;
return 1;
}
return 0;
}
int TAstar::Calcuf()
{
h=0;
for(int i=0;iNum;i++) //計算估價函數(shù)的 h
h+=e[Num*r[i]+s[i]];
return ++g+h;
}
void TAstar::Sort(TListTAstar L,int k)
{
int n=L.Getlen();
int i;
for(i=k+1;in;i++)
{
TAstar T=L.GetData(i);
if(this-f=T.f)
break;
}
L.Insert(*this,i);
}
int TAstar::Repeat(TListTAstar L)
{
int n=L.Getlen();
int i;
for(i=0;in;i++)
if(L.GetData(i)==*this)
break;
return i;
}
void TAstar::Search()
{
TAstar T=*this; //初始結(jié)點
T.f=T.Calcuf(); //初始結(jié)點的估價函數(shù)
TListTAstar L; //建立隊列
L.Append(T); //初始結(jié)點入隊
int head=0,tail=0; //隊列頭和尾指針
while(head=tail) //隊列不空則循環(huán)
{
for(int i=0;i4;i++) //空格可能移動方向
{
T=L.GetData(head); //去隊列頭結(jié)點
if(T.h==0) //是目標(biāo)結(jié)點
{
T.Printl(L);//輸出搜索路徑
T.Printf(); //輸出目標(biāo)狀態(tài)
return; //結(jié)束
}
if(T.Expend(i)) //若結(jié)點可擴(kuò)展
{
int k=T.Repeat(L); //返回與已擴(kuò)展結(jié)點重復(fù)的序號
if(khead) //如果是不能擴(kuò)展的結(jié)點
continue; //丟棄
T.last=head; //不是不能擴(kuò)展的結(jié)點，記錄父結(jié)點
T.f=T.Calcuf(); //計算f
if(k=tail) //新結(jié)點與可擴(kuò)展結(jié)點重復(fù)
{
TAstar Temp=L.GetData(k);
if(Temp.gT.g) //比較兩結(jié)點g值
L.SetData(T,k); //保留g值小的
continue;
}
T.Sort(L,head) ; //新結(jié)點插入可擴(kuò)展結(jié)點隊列
tail++; //隊列尾指針后移
}
}
head++; //一個結(jié)點不能再擴(kuò)展，隊列頭指針指向下一結(jié)點
}
}
六、測試程序
A*算法的測試：
int main()
{
TAstar aStar("eight.txt");
aStar.Search();
system("pauze");
return 0;
}
eight.txt文件中的數(shù)據(jù)（初始態(tài)和目標(biāo)態(tài)）：
一共三行，第一行是用空格隔開的九個數(shù)字0~8，這是初始狀態(tài)。第二行是一個數(shù)字，空格（數(shù)字0）的位置，第三行也是用空格隔開的九個數(shù)字0~8，這是目標(biāo)狀態(tài)。
8 3 5 1 2 7 4 6 0
8
1 2 3 4 5 6 7 8 0
eight_dis.txt中的數(shù)據(jù)（估計函數(shù)使用）
0 1 2 1 2 3 2 3 4
1 0 1 2 1 2 3 2 3
2 1 0 3 2 1 4 3 2
1 2 3 0 1 2 1 2 3
2 1 2 1 0 1 2 1 2
3 2 1 2 1 0 3 2 1
2 3 4 1 2 3 0 1 2
3 2 3 2 1 2 1 0 1
4 3 2 3 2 1 2 1 0
eight_Result.txt中的結(jié)果（運行后得到的結(jié)果）
七、算法運行結(jié)果
1.BFS算法只能適用于到達(dá)目標(biāo)結(jié)點步數(shù)較少的情況，如果步數(shù)超過15步，運行時間太長，實際上不再起作用。
2.對于隨機(jī)生成的同一個可解狀態(tài)，BFS算法最慢，DBFS算法較慢，A*算法較快。但在15步以內(nèi)，DBFS算法與A*算法相差時間不大，超過15步后，隨步數(shù)增加，A*算法的優(yōu)勢就逐漸明顯，A*算法要比DBFS算法快5倍以上，并隨步數(shù)增大而增大。到25步以上，DBFS同樣因運行時間過長而失去價值。
3.一般來說，解答的移動步數(shù)每增加1，程序運行時間就要增加5倍以上。由于八數(shù)碼問題本身的特點，需要檢查的節(jié)點隨步數(shù)增大呈指數(shù)形式增加，即使用A*算法，也難解決移動步數(shù)更多的問題。
八、問題可解性
八數(shù)碼問題的一個狀態(tài)實際上是0~9的一個排列，對于任意給定的初始狀態(tài)和目標(biāo)，不一定有解，也就是說從初始狀態(tài)不一定能到達(dá)目標(biāo)狀態(tài)。因為排列有奇排列和偶排列兩類，從奇排列不能轉(zhuǎn)化成偶排列或相反。
如果一個數(shù)字0~8的隨機(jī)排列871526340，用F(X)表示數(shù)字X前面比它小的數(shù)的個數(shù)，全部數(shù)字的F(X)之和為Y=∑(F(X))，如果Y為奇數(shù)則稱原數(shù)字的排列是奇排列，如果Y為偶數(shù)則稱原數(shù)字的排列是偶排列。
例如871526340這個排列的
Y=0+0+0+1+1+3+2+3+0=10
10是偶數(shù)，所以他偶排列。871625340
Y=0+0+0+1+1+2+2+3+0=9
9是奇數(shù)，所以他奇排列。
因此，可以在運行程序前檢查初始狀態(tài)和目標(biāo)狀態(tài)的窘是否相同，相同則問題可解，應(yīng)當(dāng)能搜索到路徑。否則無解。
PS:整理自網(wǎng)絡(luò)
通常我們傳遞值到另一個對象中時會使用兩種方法：JavaBean的構(gòu)造方法和set方法，其原理都是給對象中的某個屬性賦值。例：
public?class?Bean?{
private?int[]?datas;
//構(gòu)造方法賦值
public?Bean(int[]?datas)?{
this.datas?=?datas;
}???
//set方法賦值
public?void?setDatas(int[]?datas)?{
this.datas?=?datasa;
}
}
在鼠標(biāo)事件內(nèi)傳遞數(shù)組，只需要通過上述兩種方法傳遞即可。
import?java.awt.event.ActionEvent;
import?java.awt.event.ActionListener;
import?java.util.Arrays;
import?javax.swing.JButton;
import?javax.swing.JFrame;
import?javax.swing.JTextArea;
public?class?RandomArrayFrame?extends?JFrame?{
public?static?void?main(String[]?args)?{
new?RandomArrayFrame();
}
public?RandomArrayFrame()?{
setTitle("Hello");
setBounds(100,?100,?500,?500);
setVisible(true);
JButton?btn?=?new?JButton("生成隨機(jī)數(shù)組");
getContentPane().add(btn);
btn.addActionListener(new?ActionListener()?{
@Override
public?void?actionPerformed(ActionEvent?e)?{
//點擊事件，點擊生成一個數(shù)組并將數(shù)組傳遞到另一個窗口中。
int[]?arr?=?{?1,?3,?456,?7,?8,?9?};
new?ShowRandomArrayFrame(arr).setVisible(true);
}
});
}
}
class?ShowRandomArrayFrame?extends?JFrame?{
public?ShowRandomArrayFrame(int[]?arr)?{
setTitle("Hello");
setBounds(100,?100,?500,?500);
JTextArea?area?=?new?JTextArea(Arrays.toString(arr));
getContentPane().add(area);
}
}
結(jié)果如圖：
重慶分公司
重慶分公司
