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

1、用 A* 算法解決八數(shù)碼問題題目：八數(shù)碼問題也稱為九宮問題。在 33 的棋盤，有八個(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，

2、因此整個(gè)路徑的費(fèi)用是路徑中的步數(shù)。 現(xiàn)在任意給定一個(gè)初始狀態(tài)， 要求找到一種搜索策略， 用盡可能少的步數(shù) 得到上圖的目標(biāo)狀態(tài)算法介紹解決方案介紹 *算法的一般介紹A*（A-Star）算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。 對(duì)于幾 何路網(wǎng)來說，可以取兩節(jié)點(diǎn)間歐幾理德距離（直線距離）做為估價(jià)值，即f g n sqrt dx nx * dx nx dy ny * dy ny ； 這樣估價(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)用

3、2.算法偽代碼創(chuàng)建兩個(gè)表， OPEN表保存所有已生成而未考察的節(jié)點(diǎn)， CLOSED表中 記錄已訪問過的節(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à)值 ; 源程序#include #include #include using namespace std;constint ROW = 3;

4、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; ist != MAXNUM) return false;return true;boolisEqual(int index, int digitCOL) igitij != digitij) return false;return true;ostream& operator(

5、ostream&os, Node& node) for (inti = 0; i ROW; i+) for (int j = 0; j COL; j+) osij ;osendl;returnos;void PrintSteps(int index, vector&rstep_v)ndex; while (index != 0) (node_vindex);index = node_vindex.index;for (inti = () - 1; i= 0; i-) cout Step () - i endlrstep_vi endl;void Swap(int& a, int& b) igi

6、tij;intGetMinNode() ist = MAXNUM)continue;else if (node_vi.dist + node_vi.dep) dist) loc = i;dist = node_vi.dist + node_vi.dep;returnloc;boolisExpandable(Node& node) igitij = 0) x =i; y = j;flag = true; break;else flag = false; if(flag) break;Node node_up; ep + 1; (node_up);Node node_down; ep + 1;(n

7、ode_down);Node node_left;ep + 1;(node_left);Node node_right; ep + 1;(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;ij = number;= 0;= 1;cout 輸入目標(biāo)狀態(tài) endl;for (int m = 0; m ROW; m+)for (int n = 0; n number;mn = number;(src);while (1) if (isEmptyOfOPEN() cout 找不到解 ! endl;return -1;else intloc; / the location of the minimize node loc = GetMinNode();if(isEqual(loc, )