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:整理自網絡