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

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

2、給定一個初始狀態(tài)，要求找到一種搜索策略，用盡可能少的步數(shù) 得到上圖的目標狀態(tài)算法介紹解決方案介紹*算法的一般介紹A*（ A-Star）算法是一種靜態(tài)路網(wǎng)中求解最短路最有效的方法。對于 幾何路網(wǎng)來說，可以取兩節(jié)點間歐幾理德距離（直線距離）做為估價值， 即f g n sqrt dx nx * dx nx dy ny * dy ny ；這樣估價函數(shù)f在g值一定的情況下，會或多或少的受估價值 h的制約, 節(jié)點距目標點近，h值小，f值相對就小，能保證最短路的搜索向終點的 方向進行。明顯優(yōu)于盲目搜索策略。A star 算法在靜態(tài)路網(wǎng)中的應(yīng)用2. 算法偽代碼創(chuàng)建兩個表，OPENft保存所有已生成而未考察的節(jié)

3、點，CLOSE表中 記錄已訪問過的節(jié)點。算起點的估價值，將起點放入OPEN表owhile（OPEN!=NULL）從OPEN表中取估價值f最小的節(jié)點n;if（n 節(jié)點 =目標節(jié)點 ）break;for（ 當前節(jié)點 n 的每個子節(jié)點 X）算 X 的估價值 ;if（X in OPEN）if（ X 的估價值小于OPEN表的估價值）把n設(shè)置為X的父親；四、更新OPEN表中的估價值；源程序#include <iostream>#include <ctime>#include <vector>using namespace std;constint ROW = 3;con

4、stint COL = 3;constint MAXDISTANCE = 10000;constint MAXNUM = 10000;int abs(int a)if (a>0) 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& ope

5、rator<<(ostream&os, Node& node) for (inti = 0; i< ROW; i+) for (int j = 0; j < COL; j+)os<<ij << ' 'os<<endl;returnos;void PrintSteps(int index, vector<Node>&rstep_v)ndex;while (index != 0) (node_vindex);index = node_vindex.index;for (inti = ()

6、 - 1; i>= 0; i-)cout<< "Step " <<() - i<<endl<<rstep_vi <<endl;void Swap(int& a, int& b) igitij;intGetMinNode() ist = MAXNUM)continue;else if (node_vi.dist + node_vi.dep) <dist) loc = i;dist = node_vi.dist + node_vi.dep;returnloc;boolisExpandable

7、(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; (node_down);Node node_left;ep + 1; (node_left);Node node_right; ep + 1; (node_right);node_vindex.dist = MAXNUM; int main() int number;cout<< &quo

8、t; 輸入初始狀態(tài) :" <<endl; for (inti = 0; i< ROW; i+) for (int j = 0; j < COL; j+) cin>> number;ij = number;= 0;= 1;cout<< " 輸入目標狀態(tài) " <<endl; for (int m = 0; m < ROW; m+) for (int n = 0; n < COL; n+) cin>> 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, ) vector<Node>rstep_v; cout<< " 初始狀態(tài)： " <<end