I.8數字問題
八位數問題也叫九宮問題。在3×3的棋盤上,有8個棋子,每個棋子上都標有1到8的數字,不同棋子上所標的數字是不同的。棋盤上還有壹個空格,與空格相鄰的棋子可以移到空格裏。要解決的問題是:給定壹個初始狀態和壹個目標狀態,求從初始狀態到目標狀態移動步數最少的壹個移動步。所謂問題的壹種狀態就是棋盤上棋子的壹種排列。棋子移動後,狀態會發生變化。求解八位數問題,其實就是找出從初始狀態到目標狀態的壹系列中間過渡態。
八個數字問題壹般用搜索法解決。搜索方法包括廣度優先搜索法、深度優先搜索法和A*算法。在這裏,我們通過用不同的方法解決八位數問題來比較不同搜索方法的效果。
2.搜索算法基類
1.八位數問題的狀態表示
八位數問題的壹種狀態是在棋盤上放置八個數字的方法。每壹顆棋子用它上面標註的數字表示,空格用0表示,這樣棋盤上壹顆棋子的狀態就可以存放在壹個壹維數組p[9]中,存放順序是從左上角開始,從左到右,從上到下。也可以用二維數組來存儲。
2.節點
在搜索算法中,問題的狀態由節點描述。除了描述狀態的數組p[9]外,還有壹個父指針last,記錄了當前節點的父節點號。如果由節點U的狀態變化產生壹個節點V,則節點U是節點V的父節點,節點V的last記錄節點U的編號,到達目標節點後,通過last可以找到搜索路徑。
3.階級結構
在C++中,節點由類表示,類封裝了與節點相關的數據操作。
不同的搜索算法都有壹定的特點和各自的個性,所以在這裏,不同搜索算法的所有數據和功能都封裝在壹個基類中,然後通過繼承實現不同的搜索算法。
4.節點擴展規則
搜索就是按照壹定的規則展開已知節點,直到找到目標節點或者所有節點都無法展開。
數字問題的節點展開要遵守棋子的移動規律。根據棋子移動的規則,壹個相鄰於壹個空間的棋子可以壹次移動到壹個空間中,實際上可以看作是向相反方向移動的空間。空間運動的方向可以是右、下、左、上,當然不能移出邊界。棋子的位置,即保存狀態的數組元素的下標。移動空間後,其位置會發生變化。不出界時,向右、下、左、上移動空格後,新位置分別為1、3、-1和-3的原位置。如果空間分別用0、1、2、3向右、下、左、上移動,空間移動引起的狀態變化通過將數組p[]中0新位置的數與0交換來反映。
5.8位數問題的基類
八位數問題的基類及其成員函數實現如下:
#定義編號9
階級鬥爭
{
公共:
TEight(){}
TEight(char * fname);//用文件數據構造節點
虛擬void Search()= 0;//搜索
受保護:
int p[Num];
int last,spac
靜態int q[Num],d[],total
void Printf();
布爾運算符= =(const TEight & amp;t);
bool Extend(int I);
};
int TEight::q[Num];//保存目標節點
int TEight::d[]={1,3,-1,-3 };//方向
int TEight::total = 0;//步驟
TEight::TEight(char *fname)
{
ifstream fin
fin.open(fname,IOs::in);
如果(!鰭)
{
cout & lt& lt"無法打開數據文件!"& lt& ltendl
返回;
}
int I;
for(I = 0;我& ltNum)//獲取源節點
fin & gt& gtp[i++];
fin & gt& gtspac
for(I = 0;我& ltNum)//獲取目標節點
fin & gt& gtq[i++];
fin . close();
last =-1;
總計= 0;
}
Void TEight::Printf()//打印結果文件的路徑。
{
ofstream fout
fout.open("eight_result.txt ",IOs::ate | IOs::app);
fout & lt& lttotal++ & lt;& lt”t”;
for(int I = 0;我& ltNum)
fout & lt& lt" " " & lt& ltp[i++];
fout & lt& ltendl
fout . close();
}
bool TEight::operator = =(const TEight & amp;T)//判斷兩個狀態是否相同。
{
for(int I = 0;我& ltNum)
if(T.p[i]!=p[i++])
返回0;
返回1;
}
bool eight::extend(int I)//擴展
{
if(I = = 0 & amp;& ampspac%3==2 || i==1。& ampspac & gt五
| | i = = 2 & amp& ampspac % 3 = = 0 | | i = = 3 & amp& ampspac & lt3)
返回0;
int temp = spac
spac+= d[I];
p[temp]= p[spac];
p[spac]= 0;
返回1;
}
數據文件的結構:
A * * *三行,第壹行是用空格隔開的9個數字0~8,這是初始狀態。第二行是數字,空格的位置(數字0),第三行也是用空格隔開的9個數字0~8,這是目標狀態。
三。線性表
在搜索過程中,搜索方法需要使用壹個隊列來存儲搜索到的中間節點。為了在找到目標節點後找到從初始節點到目標節點的路徑,需要保留所有搜索到的節點。另壹方面,對於不同的問題,甚至同壹問題,在不同的搜索方法中,需要存儲的節點數差異很大,所以這裏采用鏈式線性表作為存儲結構,同時為了適應不同的問題,線性表被設計成類似模板的形式。
模板& lt類類型& gtclass TList//線性表前瞻定義
模板& lt類類型& gt類TNode //線性表節點類模板
{
友元類列表& ltType & gt;
公共:
TNode(){}
TNode(常量類型& ampdat);
私人:
TNode & ltType & gt*下壹個;
類型數據;
};
模板& lt類類型& gt類別列表
{
公共:
TList(){ Last = First = 0;長度= 0;}//構造函數
int Getlen()const { return Length;}//成員函數,返回線性表的長度。
int Append(const Type & amp;t);//成員函數,從頁腳添加節點。
int Insert(const Type & amp;t,int k);//成員函數,插入節點
類型get data(int I);//成員函數,返回節點數據成員。
void SetData(常量類型& ampt,int k);//成員函數,設置節點數據成員。
私人:
TNode & ltType & gt*第壹,*最後;//數據成員,線性表頭尾指針
int長度;//數據成員,線性表長度
};
模板& lt類類型& gtint TList & ltType & gt* Append(常量類型& ampt)
{
插入(T,長度);
返回1;
}
模板& lt類類型& gtint TList & ltType & gt*插入(常量類型& ampt,int k)
{
TNode & ltType & gt* p =新TNode<。Type & gt;
p->;數據= T;
如果(第壹)
{
if(k & lt;=0)
{
p->;Next = First
first = p;
}
if(k & gt;長度-1)
{
最後-& gt;next = p;
Last = Last-& gt;接下來;
最後-& gt;next = 0;
}
if(k & gt;0 & amp& ampk & lt長度)
{
k-;
TNode & ltType & gt* q =第壹;
while(k->;0)
q = q-& gt;接下來;
p->;next = q-& gt;接下來;
q->;next = p;
}
}
其他
{
first = Last = p;
首先-& gt;下壹個=最後壹個-& gt;next = 0;
}
長度++;
返回1;
}
模板& lt類類型& gt類型TList & ltType & gt* get data(int k)
{
TNode & ltType & gt* p =第壹;
while(k->;0)
p = p-& gt;接下來;
返回p-& gt;數據;
}
模板& lt類類型& gtvoid TList & ltType & gt* SetData(常量類型& ampt,int k)
{
TNode & ltType & gt* p =第壹;
while(k->;0)
p = p-& gt;接下來;
p->;數據= T;
}
線性表作為頭文件單獨存儲。
四。廣度優先搜索方法
在搜索方法中,廣度優先搜索法是尋找最短路徑的首選方法。
1.廣度優先搜索算法的基本步驟
1)建立壹個隊列,將初始節點入隊並設置隊列頭和尾指針。
2)取出隊列頭(頭指針所指)的節點進行擴展,並從中展開子節點,按照展開的順序將這些節點添加到隊列中。
3)如果擴展的新節點與隊列中的節點重復,則丟棄新節點並跳到步驟6。
4)如果擴展的新節點與隊列中的節點不重復,則記錄其父節點,將其添加到隊列中,並更新隊列尾指針。
5)如果擴展節點是目標節點,則輸出路徑,程序結束。否則,繼續下壹步。
6)如果隊列頭的節點可以擴展,直接返回第二步。否則,將隊列頭指針指向下壹個節點,並返回第二步。
2.搜索路徑的輸出
搜索完目標節點後,需要輸出搜索路徑。每個節點都有壹個數據字段last,記錄了該節點的父節點,所以輸出搜索路徑時,從目標節點Q開始,根據last找到它的父節點,然後根據這個節點的last找到它的父節點,...,最後找到初始節點。搜索路徑是從初始節點到目標節點的反方向路徑。
3.基於廣度優先搜索方法的TBFS類結構
廣度優先搜索方法TBFS類是TEight類的子類。其類的結構及其成員函數的實現如下:
TBFS類:公共照明
{
公共:
TBFS(){}
TBFS(char * fname):TEight(fname){ }
虛擬void Search();
私人:
void Printl(TList & lt;TBFS & gt& ampl);
int Repeat(TList & lt;TBFS & gt& ampl);
int Find();
};
void TBFS::Printl(TList & lt;TBFS & gt& ampl)
{
TBFS T = * this
if(T.last==-1)
返回;
其他
{
t = L . get data(t . last);
T.printl(L);
T.printf();
}
}
int TBFS::Repeat(TList & lt;TBFS & gt& ampl)
{
int n = L . Getlen();
int I;
for(I = 0;我& ltn;i++)
if(L.GetData(i)==*this)
打破;
返回I;
}
int TBFS::Find()
{
for(int I = 0;我& ltNum)
if(p[i]!=q[i++])
返回0;
返回1;
}
void TBFS::Search()
{
TBFS T = * this
TList & ltTBFS & gtl;
長度追加(T);
int head=0,tail = 0;
while(head & lt;=尾巴)
{
for(int I = 0;我& lt4;i++)
{
t = L . get data(head);
if(T . Extend(I )& amp;& ampT.Repeat(L)>尾巴)
{
T.last = head
長度追加(T);
tail++;
}
if(T.Find())
{
T.printl(L);
T.printf();
返回;
}
}
head++;
}
}
4.廣度優先搜索方法的缺點
廣度優先搜索法在有解的情況下,總能保證最短路徑,即步驟數最少的路徑。但是廣度優先搜索法最大的問題是要搜索的節點太多,因為在廣度優先搜索法中,每壹個可能的節點都是搜索的對象。隨著搜索樹中節點深度的增加,搜索節點的數量會迅速增加並呈指數級擴展,從而所需的存儲空間和搜索時間也會呈指數級增長。
動詞 (verb的縮寫)A*算法
1.啟發式搜索
廣度優先搜索和雙向廣度優先搜索都屬於盲搜索,在狀態空間不大的時候是非常合適的算法,但是當狀態空間很大的時候,它們的效率太低,往往在搜索了大量不相關的狀態節點之後才遇到解,甚至無法遇到解。
搜索是壹個試探性的搜索過程。為了減少搜索的盲目性,提高試驗的準確性,應采用啟發式搜索。所謂啟發式搜索,就是對每次搜索的位置進行評估,選擇最容易到達目標的位置,然後從這個位置向前搜索,這樣可以在搜索中省略大量無關節點,提高效率。
2.A*算法
A*算法是壹種常用的啟發式搜索算法。
在A*算法中,通過評估函數來評估節點的位置。A*算法的評估函數可以表示為:
f'(n) = g'(n) + h'(n)
這裏f’(n)是評價函數,g’(n)是從起點到終點的最短路徑值(也稱為最小費用或最小費用),h’(n)是從n到目標的最短路徑的啟發式值。由於不能預先知道這個f′(n ),所以實際上使用下面的評估函數:
f(n) = g(n) + h(n)
其中g(n)是從初始節點到節點N的實際成本,h(n)是從節點N到目標節點的最佳路徑的估計成本。這裏主要是h(n)體現了搜索的啟發式信息,因為g(n)是已知的。用f(n)作為f′(n)的近似值,即用g(n)代替g′(n),用h′(n)代替h′。這必須滿足兩個條件:(1)g(n)>=g'(n)(多數情況下滿足,可以忽略),f必須單調遞增。(2)h必須小於或等於實際最小成本h (n)
3.A *算法的步驟
A*算法基本上和廣度優先搜索壹樣,但是壹個節點擴展後,要計算它的評價函數,並根據評價函數對要擴展的節點進行排序,以保證每個擴展的節點都是評價函數最小的節點。
A*算法的步驟如下:
1)建立隊列,計算初始節點的評價函數f,對初始節點進行排隊,設置隊列頭、尾指針。
2)取出隊列頭的節點(由隊列頭指針指向)。如果該節點是目標節點,則輸出路徑,程序結束。否則,展開節點。
3)檢查擴展後的新節點是否與隊列中的節點重復,如果與不能再擴展的節點重復(隊列頭指針前),則丟棄;如果新節點與要擴展的節點重復(隊列頭指針之後),則比較兩個節點的評價函數中G的大小,保留G值較小的節點。跳到第五步。
4)如果擴展後的新節點與隊列中的節點不重復,則根據其評價函數f的大小,將其插入隊列中頭節點之後待擴展節點的適當位置,使它們按照從小到大的順序排列,最後更新隊列尾指針。
5)如果隊列頭的節點可以展開,直接返回第二步。否則,將隊列頭指針指向下壹個節點,並返回第二步。
4.八位數問題A*算法的評價函數
在評價函數中,主要是計算H,對於不同的問題,H有不同的含義。那麽八位數問題中的H是什麽意思呢?八位數問題的壹個狀態,其實就是數字0~8的排列。它由壹個數組p[9]存儲,數組中每個元素的下標就是數字在排列中的位置。例如,在壹個狀態中,p[3]=7,那麽數字7的位置是3。如果目標狀態數字3的位置是8,那麽數字7離目標狀態的偏移距離是3,因為它必須移動三步才能回到目標狀態的位置。
在八位數問題中,每個數字可以有九個不同的位置。因此,任意狀態下的每個數字與目標狀態下的同壹個數字之間有9*9種相對距離。可以先計算出這些相對距離,存儲在壹個矩陣中,這樣只要知道同壹個數位在兩種狀態下的位置,就可以求出它們的相對距離,也就是該數位的偏移距離:
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
比如在壹種狀態下,數字8的位置是3,在另壹種狀態下,位置是7,那麽從矩陣的3行7列中就可以找到2,這就是8在兩種狀態下的偏移距離。
評估函數中的h是所有數字偏移距離的總和。顯然,要計算同壹個數在兩種不同狀態下的偏移距離,就需要知道這個數在每種狀態下的位置,這就需要掃描數組p[9]。因為狀態變了,每個數的位置也變了,所以每次計算H時,都要沿線掃描數組,確定數組中每個數的位置。為了簡化計算,用壹個數組來存儲每個數在狀態中的位置,它隨著狀態的變化而變化,這樣就不需要每次計算H時都掃描狀態數組。
例如,在某個狀態下,數字5的位置是8,如果該位置由數組r[9]存儲,則有r[5]=8。
現在用數組r[9]存儲當前狀態的數字位置,用數組s[9]存儲目標狀態的數字位置,那麽當前狀態的數字I離目標狀態的偏移距離就是矩陣中行r[i]和列s[i]的對應值。
5.A *算法的類結構
A*算法的類聲明如下:
TAstar類:公共照明
{
公共:
TAstar(){} //構造函數
TAstar(char * fname);//帶參數的構造函數
虛擬void Search();//A*搜索方法
私人:
int f,g,h;//評估函數
int r[Num];//存儲狀態中每個數位位置的輔助數組。
static int s[Num];//存儲目標狀態下每個數字位置的輔助數組。
靜態int e[];//壹個輔助數組,用於存儲每個數字的相對距離。
void Printl(TList & lt;TAstar & gtl);//成員函數,輸出搜索路徑。
int Expend(int I);//成員函數,A*算法的狀態擴展函數
int Calcuf();//成員函數,計算評價函數。
void排序(TList & ltTAstar & gt& ampl,int k);//成員函數,將新展開的節點按f降序插入到待展開節點隊列中。
int Repeat(TList & lt;TAstar & gt& ampl);//成員函數,檢查節點是否重復。
};
int TAstar::s[數字],TAstar::e[數字*數字];
TAstar::TAstar(char * fname):TEight(fname)
{
for(int I = 0;我& ltNum)
{
r[p[I]]= I;//存儲初始狀態下每個數字的位置。
s[q[I]]= i++;//存儲目標狀態的每壹位的位置。
}
ifstream fin
fin.open("eight_dis.txt ",IOs::in);//打開數據文件
如果(!鰭)
{
cout & lt& lt"無法打開數據文件!"& lt& ltendl
返回;
}
for(int I = 0;我& ltNum * NumI++) //讀入每個數字的相對距離值。
fin & gt& gte[I];
fin . close();
f = g = h = 0;//評估函數的初始值
}
void TAstar::Printl(TList & lt;TAstar & gtl)
{
TAstar T = * this
if(T.last==-1)返回;
其他
{
t = L . get data(t . last);
T.printl(L);
T.printf();
}
}
int TAstar::Expend(int i)
{
If(Extend(i)) //節點是可擴展的。
{
int temp = r[p[r[0]];//狀態改變後數字位置改變,改變後的位置被存儲。
r[p[r[0]]= r[0];
r[0]= temp;
返回1;
}
返回0;
}
int TAstar::Calcuf()
{
h = 0;
for(int I = 0;我& ltNumI++) //計算評價函數的h。
h+= e[Num * r[I]+s[I]];
return ++ g+h;
}
void TAstar::Sort(TList & lt;TAstar & gt& ampl,int k)
{
int n = L . Getlen();
int I;
for(I = k+1;我& ltn;i++)
{
TAstar T = L . get data(I);
如果(this-& gt;f & lt=T.f)
打破;
}
長度插入(*這個,我);
}
int TAstar::Repeat(TList & lt;TAstar & gt& ampl)
{
int n = L . Getlen();
int I;
for(I = 0;我& ltn;i++)
if(L.GetData(i)==*this)
打破;
返回I;
}
void TAstar::Search()
{
TAstar T = * this//初始節點
T . f = T . Calcuf();//初始節點的評估函數
TList & ltTAstar & gtl;//建立隊列
長度追加(T);//初始節點入隊
int head=0,tail = 0;//隊列頭和尾指針
while(head & lt;=tail) //如果隊列不為空,則循環。
{
for(int I = 0;我& lt4;I++) //空格可能在方向上移動。
{
t = L . get data(head);//轉到隊列頭節點
If(T.h==0) //是目標節點。
{
T.printl(L);//輸出搜索路徑
T.printf();//輸出目標狀態
返回;//結束
}
If(t . expect(I))//如果節點是可擴展的,
{
int k = T . Repeat(L);//返回與擴展節點重復的序列號。
if(k & lt;Head) //如果是不能擴展的節點,
繼續;//丟棄
T.last = head//不是不能擴展的節點,記錄父節點。
T . f = T . Calcuf();//計算f
if(k & lt;=tail) //新節點與可擴展節點重復。
{
TAstar Temp = L . get data(k);
if(temp . g & gt;T.g) //比較兩個節點的G值。
長度SetData(T,k);//保留G值小的。
繼續;
}
T.Sort(L,head);//將新節點插入可擴展節點隊列。
tail++;//隊列尾指針向後移動。
}
}
head++;//壹個節點無法展開,隊列頭指針指向下壹個節點。
}
}
不及物動詞測試程序
A*算法的測試:
int main()
{
TAstar aStar(" eight . txt ");
阿斯塔。search();
系統(“pauze”);
返回0;
}
eight.txt文件中的數據(初始狀態和目標狀態):
A * * *三行,第壹行是用空格隔開的9個數字0~8,這是初始狀態。第二行是數字,空格的位置(數字0),第三行也是用空格隔開的9個數字0~8,這是目標狀態。
8 3 5 1 2 7 4 6 0
八
1 2 3 4 5 6 7 8 0
eight_dis.txt中的數據(由估算函數使用)
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中的結果(運行後的結果)。
七、算法運行結果
六五四三八+0。BFS算法只能適用於到達目標節點的步數較少的情況。如果步數超過15,說明運行時間過長,實際上已經不起作用了。
2.對於隨機產生的同壹可解狀態,BFS算法最慢,DBFS算法較慢,A*算法較快。但是,在15步內,DBFS算法和A*算法差別不大。15步之後,隨著步數的增加,A*算法的優勢逐漸明顯,A*算法比DBFS算法快5倍以上,並且隨著步數的增加而增加。超過25步後,DBFS也因運行時間過長而失去價值。
3.壹般來說,移動步數每增加1,程序的運行時間就會增加5倍以上。由於八位數問題本身的特點,需要檢查的節點數隨著步數的增加呈指數增長。即使使用A*算法,也很難解決移動步數較多的問題。
八、問題的可解性
八位數問題的壹個狀態,其實就是0~9的排列。對於任何給定的初始狀態和目標,都不壹定有解,也就是說,從初始狀態可能達不到目標狀態。因為有兩種排列:奇排列和偶排列,奇排列不能轉化為偶排列,反之亦然。
如果壹個數字0~8的隨機排列是871526340,則用F(X)來表示比它小的數的個數,所有數的F(X)之和為Y=∑(F(X))。如果Y是奇數,原數的排列叫奇數,如果Y是偶數,叫偶數。
比如871526340。
y = 0+0+0+1+1+3+2+3+0 = 10
10是偶數,所以是偶數。871625340
y = 0+0+0+1+1+2+2+3+0 = 9
9是奇數,所以是奇數。
因此,您可以在運行程序之前檢查初始狀態和目標狀態是否相同。如果它們相同,問題就可以解決,並且應該搜索路徑。否則無解。
PS:整理自網絡