用A算法解決八數(shù)碼問題.doc

用A*算法解決八數(shù)碼問題一、 題目：八數(shù)碼問題也稱為九宮問題。在33的棋盤，有八個棋子，每個棋子上標(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)描述了8個棋子和空位在棋盤的9個方格上的分布。初始狀態(tài)：任何狀態(tài)都可以被指定為初始狀態(tài)。操作符：用來產(chǎn)生4個行動（上下左右移動）。目標(biāo)測試：用來檢測狀態(tài)是否能匹配上圖的目標(biāo)布局。路徑費用函數(shù)：每一步的費用為1，因此整個路徑的費用是路徑中的步數(shù)。現(xiàn)在任意給定一個初始狀態(tài)，要求找到一種搜索策略，用盡可能少的步數(shù)得到上圖的目標(biāo)狀態(tài)算法介紹三、 解決方案介紹1.A*算法的一般介紹A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。對于幾何路網(wǎng)來說，可以取兩節(jié)點間歐幾理德距離（直線距離）做為估價值，即；這樣估價函數(shù)f在g值一定的情況下，會或多或少的受估價值h的制約，節(jié)點距目標(biāo)點近，h值小，f值相對就小，能保證最短路的搜索向終點的方向進行。明顯優(yōu)于盲目搜索策略。A star算法在靜態(tài)路網(wǎng)中的應(yīng)用2.算法偽代碼創(chuàng)建兩個表，OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點。算起點的估價值，將起點放入OPEN表。while(OPEN!=NULL)從OPEN表中取估價值f最小的節(jié)點n;if(n節(jié)點=目標(biāo)節(jié)點)break;for(當(dāng)前節(jié)點n 的每個子節(jié)點X) 算X的估價值;if(X in OPEN) if( X的估價值小于OPEN表的估價值 )把n設(shè)置為X的父親;更新OPEN表中的估價值; /取最小路徑的估價值 if(X inCLOSE) if( X的估價值小于CLOSE表的估價值 )把n設(shè)置為X的父親;更新CLOSE表中的估價值;把X節(jié)點放入OPEN /取最小路徑的估價值 if(X not inboth)把n設(shè)置為X的父親;求X的估價值;并將X插入OPEN表中; /還沒有排序 /end for將n節(jié)點插入CLOSE表中;按照估價值將OPEN表中的節(jié)點排序; /實際上是比較OPEN表內(nèi)節(jié)點f的大小，從最小路徑的節(jié)點向下進行。/end while(OPEN!=NULL)保存路徑，即 從終點開始，每個節(jié)點沿著父節(jié)點移動直至起點，這就是你的路徑.四、 源程序#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; / 儲存節(jié)點boolisEmptyOfOPEN() /判斷Open表是否空 for (inti = 0; inode_v.size(); i+) if (node_vi.dist != MAXNUM) return false; return true; boolisEqual(int index, int digitCOL) /判斷節(jié)點是否與索引值指向的節(jié)點相同 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é)點 for (inti = 0; i ROW; i+) for (int j = 0; j COL; j+) node.digitij = node_vindex.digitij; intGetMinNode() /獲取啟發(fā)值最小的節(jié)點 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) /判斷是否可擴展 for (inti = 0; inode_v.size(); i+) if (isEqual(i, node.digit) return false; return true; int Distance(Node& node, int digitCOL) /計算距離 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) /展開節(jié)點 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 -