用A算法解決八數(shù)碼問題參考模板

1、用A*算法解決八數(shù)碼問題一、 題目：八數(shù)碼問題也稱為九宮問題。在3×3的棋盤，有八個(gè)棋子，每個(gè)棋子上標(biāo)有1至8的某一數(shù)字，不同棋子上標(biāo)的數(shù)字不相同。棋盤上還有一個(gè)空格，與空格相鄰的棋子可以移到空格中。要解決的問題是：任意給出一個(gè)初始狀態(tài)和一個(gè)目標(biāo)狀態(tài)，找出一種從初始轉(zhuǎn)變成目標(biāo)狀態(tài)的移動(dòng)棋子步數(shù)最少的移動(dòng)步驟。二、 問題的搜索形式描述狀態(tài)：狀態(tài)描述了8個(gè)棋子和空位在棋盤的9個(gè)方格上的分布。初始狀態(tài)：任何狀態(tài)都可以被指定為初始狀態(tài)。操作符：用來產(chǎn)生4個(gè)行動(dòng)（上下左右移動(dòng)）。目標(biāo)測(cè)試：用來檢測(cè)狀態(tài)是否能匹配上圖的目標(biāo)布局。路徑費(fèi)用函數(shù)：每一步的費(fèi)用為1，因此整個(gè)路徑的費(fèi)用是路徑中的步數(shù)?，F(xiàn)

2、在任意給定一個(gè)初始狀態(tài)，要求找到一種搜索策略，用盡可能少的步數(shù)得到上圖的目標(biāo)狀態(tài)算法介紹三、 解決方案介紹1.A*算法的一般介紹A*（A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。對(duì)于幾何路網(wǎng)來說，可以取兩節(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)于盲目搜索策略。1 / 11A star算法在靜態(tài)路網(wǎng)中的應(yīng)用2.算法偽代碼創(chuàng)建兩個(gè)表，OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。算起點(diǎn)的估價(jià)值，將起點(diǎn)放入O

3、PEN表。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表中; /還沒有排序 /end for

4、將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)開始，每個(gè)節(jié)點(diǎn)沿著父節(jié)點(diǎn)移動(dòng)直至起點(diǎn)，這就是你的路徑.四、 源程序#include <iostream> #include <ctime> #include <vector> using namespace std; constint ROW = 3; constint COL = 3; constint MAXDISTANCE = 10000; constint

5、MAXNUM = 10000; int abs(int a) if (a>0) return a; else return -a; typedefstruct _Node int digitROWCOL; intdist; / 距離 intdep; / 深度 int index; / 索引值 Node; Node src, dest; vector<Node>node_v; / 儲(chǔ)存節(jié)點(diǎn)boolisEmptyOfOPEN() /判斷Open表是否空 for (inti = 0; i<node_v.size(); i+) if (node_vi.dist != MAXNU

6、M) 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

7、+) for (int j = 0; j < COL; j+) os<<node.digitij << ' ' os<<endl; returnos; void PrintSteps(int index, vector<Node>&rstep_v)/輸出步驟 rstep_v.push_back(node_vindex); index = node_vindex.index; while (index != 0) rstep_v.push_back(node_vindex); index = node_vindex.i

8、ndex; for (inti = rstep_v.size() - 1; i>= 0; i-) cout<< "Step " <<rstep_v.size() - i <<endl<<rstep_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 (i

9、nt 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; i<node_v.size(); i+) if (node_vi.dist = MAXNUM) continue; else if (node_vi.dist + node_vi.dep) <dist) loc = i; dist = node_vi.dist

10、+ node_vi.dep; returnloc; boolisExpandable(Node& node) /判斷是否可擴(kuò)展 for (inti = 0; i<node_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 < C

11、OL; 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)

12、/展開節(jié)點(diǎn) int x, y; bool flag; for (inti = 0; i< ROW; i+) for (int j = 0; j < COL; j+) if (node_vindex.digitij = 0) x =i; y = j; flag = true; break; else flag = false; if(flag) break; Node node_up; /上移操作 Assign(node_up, index); intdist_up = MAXDISTANCE; if (x > 0) Swap(node_up.digitxy, node_up.

13、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 < 2) Swap(node_down.digit

14、xy, node_down.digitx + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, dest.digit); node_down.index = index;node_down.dist = dist_down; node_down.dep = node_vindex.dep + 1; node_v.push_back(node_down); Node node_left;/左移操作 Assign(node_left, index); intdist_left = MAXDISTANCE; if (y

15、> 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); in

16、tdist_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_vind

17、ex.dist = MAXNUM; int main() int number; cout<< "輸入初始狀態(tài):" <<endl; for (inti = 0; i< ROW; i+) for (int j = 0; j < COL; j+) cin>> 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 < COL; n+) cin>> number; dest.digitmn = number; node_v.push_back(src); while (1) if (isEmptyOfOPEN() cout<< "找不到解!" <<endl; return -1; else intloc; / the location