用A*算法解決八數(shù)碼問(wèn)題一、 題目：八數(shù)碼問(wèn)題也稱為九宮問(wèn)題。在33的棋盤，有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。要解決的問(wèn)題是：任意給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)棋子步數(shù)最少的移動(dòng)步驟。二、 問(wèn)題的搜索形式描述狀態(tài)：狀態(tài)描述了8個(gè)棋子和空位在棋盤的9個(gè)方格上的分布。初始狀態(tài)：任何狀態(tài)都可以被指定為初始狀態(tài)。操作符：用來(lái)產(chǎn)生4個(gè)行動(dòng)（上下左右移動(dòng)）。目標(biāo)測(cè)試：用來(lái)檢測(cè)狀態(tài)是否能匹配上圖的目標(biāo)布局。路徑費(fèi)用函數(shù)：每一步的費(fèi)用為1，因此整個(gè)路徑的費(fèi)用是路徑中的步數(shù)?，F(xiàn)在任意給定一個(gè)初始狀態(tài)，要求找到一種搜索策略，用盡可能少的步數(shù)得到上圖的目標(biāo)狀態(tài)算法介紹三、 解決方案介紹1.A*算法的一般介紹A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。對(duì)于幾何路網(wǎng)來(lái)說(shuō)，可以取兩節(jié)點(diǎn)間歐幾理德距離（直線距離）做為估價(jià)值，即；這樣估價(jià)函數(shù)f在g值一定的情況下，會(huì)或多或少的受估價(jià)值h的制約，節(jié)點(diǎn)距目標(biāo)點(diǎn)近，h值小，f值相對(duì)就小，能保證最短路的搜索向終點(diǎn)的方向進(jìn)行。明顯優(yōu)于盲目搜索策略。A star算法在靜態(tài)路網(wǎng)中的應(yīng)用2.算法偽代碼創(chuàng)建兩個(gè)表，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問(wèn)過(guò)的節(jié)點(diǎn)。算起點(diǎn)的估價(jià)值，將起點(diǎn)放入OPEN表。while(OPEN!=NULL)從OPEN表中取估價(jià)值f最小的節(jié)點(diǎn)n;if(n節(jié)點(diǎn)=目標(biāo)節(jié)點(diǎn))break;for(當(dāng)前節(jié)點(diǎn)n 的每個(gè)子節(jié)點(diǎn)X) 算X的估價(jià)值;if(X in OPEN) if( X的估價(jià)值小于OPEN表的估價(jià)值 )把n設(shè)置為X的父親;更新OPEN表中的估價(jià)值; /取最小路徑的估價(jià)值 if(X inCLOSE) if( X的估價(jià)值小于CLOSE表的估價(jià)值 )把n設(shè)置為X的父親;更新CLOSE表中的估價(jià)值;把X節(jié)點(diǎn)放入OPEN /取最小路徑的估價(jià)值 if(X not inboth)把n設(shè)置為X的父親;求X的估價(jià)值;并將X插入OPEN表中; /還沒(méi)有排序 /end for將n節(jié)點(diǎn)插入CLOSE表中;按照估價(jià)值將OPEN表中的節(jié)點(diǎn)排序; /實(shí)際上是比較OPEN表內(nèi)節(jié)點(diǎn)f的大小，從最小路徑的節(jié)點(diǎn)向下進(jìn)行。/end while(OPEN!=NULL)保存路徑，即 從終點(diǎn)開(kāi)始，每個(gè)節(jié)點(diǎn)沿著父節(jié)點(diǎn)移動(dòng)直至起點(diǎn)，這就是你的路徑.四、 源程序#include #include #include using namespace std; constint ROW = 3; constint COL = 3; constint MAXDISTANCE = 10000; constint MAXNUM = 10000; int abs(int a) if (a0) return a; else return -a; typedefstruct _Node int digitROWCOL; intdist; / 距離 intdep; / 深度 int index; / 索引值 Node; Node src, dest; vectornode_v; / 儲(chǔ)存節(jié)點(diǎn)boolisEmptyOfOPEN() /判斷Open表是否空 for (inti = 0; inode_v.size(); i+) if (node_vi.dist != MAXNUM) return false; return true; boolisEqual(int index, int digitCOL) /判斷節(jié)點(diǎn)是否與索引值指向的節(jié)點(diǎn)相同 for (inti = 0; i ROW; i+) for (int j = 0; j COL; j+) if (node_vindex.digitij != digitij) return false; return true; ostream& operator(ostream&os, Node& node) for (inti = 0; i ROW; i+) for (int j = 0; j COL; j+) osnode.digitij ; osendl; returnos; void PrintSteps(int index, vector&rstep_v)/輸出步驟 rstep_v.push_back(node_vindex); index = node_vindex.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.index; for (inti = rstep_v.size() - 1; i= 0; i-) cout Step rstep_v.size() - i endlrstep_vi endl; void Swap(int& a, int& b) /交換 int t; t = a; a = b; b = t; void Assign(Node& node, int index) /獲取節(jié)點(diǎn) for (inti = 0; i ROW; i+) for (int j = 0; j COL; j+) node.digitij = node_vindex.digitij; intGetMinNode() /獲取啟發(fā)值最小的節(jié)點(diǎn) intdist = MAXNUM; intloc; / the location of minimize node for (inti = 0; inode_v.size(); i+) if (node_vi.dist = MAXNUM) continue; else if (node_vi.dist + node_vi.dep) dist) loc = i; dist = node_vi.dist + node_vi.dep; returnloc; boolisExpandable(Node& node) /判斷是否可擴(kuò)展 for (inti = 0; inode_v.size(); i+) if (isEqual(i, node.digit) return false; return true; int Distance(Node& node, int digitCOL) /計(jì)算距離 int distance = 0; bool flag = false; for(inti = 0; i ROW; i+) for (int j = 0; j COL; j+) for (int k = 0; k ROW; k+) for (int l = 0; l COL; l+) if (node.digitij = digitkl) distance += abs(i - k) + abs(j - l); flag = true; break; else flag = false; if (flag) break; return distance; intMinDistance(int a, int b) /二者取小 return (a b ? a : b); void ProcessNode(int index) /展開(kāi)節(jié)點(diǎn) int x, y; bool flag; for (inti = 0; i ROW; i+) for (int j = 0; j 0) Swap(node_up.digitxy, node_up.digitx - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, dest.digit); node_up.index = index; node_up.dist = dist_up; node_up.dep = node_vindex.dep + 1; node_v.push_back(node_up); Node node_down; /下移操作 Assign(node_down, index); intdist_down = MAXDISTANCE; if (x 0) Swap(node_left.digitxy, node_left.digitxy - 1); if (isExpandable(node_left) dist_left = Distance(node_left, dest.digit); node_left.index = index; node_left.dist = dist_left; node_left.dep = node_vindex.dep + 1; node_v.push_back(node_left); Node node_right; /右移操作 Assign(node_right, index); intdist_right = MAXDISTANCE; if (y 2) Swap(node_right.digitxy, node_right.digitxy + 1); if (isExpandable(node_right) dist_right = Distance(node_right, dest.digit); node_right.index = index; node_right.dist = dist_right; node_right.dep = node_vindex.dep + 1; node_v.push_back(node_right); node_vindex.dist = MAXNUM; int main() int number; cout 輸入初始狀態(tài): endl; for (inti = 0; i ROW; i+) for (int j = 0; j number;src.digitij = number; src.index = 0; src.dep = 1; cout 輸入目標(biāo)狀態(tài) endl; for (int m = 0; m ROW; m+) for (int n = 0; n number; dest.digitmn = number; node_v.push_back(src); while (1) if (isEmptyOfOPEN() cout 找不到解! endl; return -