用A算法解决八数码问题

1、用A*算法解决八数码问题一、 题目：八数码问题也称为九宫问题。在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。二、 问题的搜索形式描述状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。初始状态：任何状态都可以被指定为初始状态。操作符：用来产生4个行动（上下左右移动）。目标测试：用来检测状态是否能匹配上图的目标布局。路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。现

2、在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态算法介绍三、 解决方案介绍1.A*算法的一般介绍A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。A star算法在静态路网中的应用2.算法伪代码创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。w

3、hile(OPEN!=NULL)从OPEN表中取估价值f最小的节点n;if(n节点=目标节点)break;for(当前节点n 的每个子节点X) 算X的估价值;if(X in OPEN) if( X的估价值小于OPEN表的估价值 )把n设置为X的父亲;更新OPEN表中的估价值; /取最小路径的估价值 if(X inCLOSE) if( X的估价值小于CLOSE表的估价值 )把n设置为X的父亲;更新CLOSE表中的估价值;把X节点放入OPEN /取最小路径的估价值 if(X not inboth)把n设置为X的父亲;求X的估价值;并将X插入OPEN表中; /还没有排序 /end for将n节点插入

4、CLOSE表中;按照估价值将OPEN表中的节点排序; /实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。/end while(OPEN!=NULL)保存路径，即 从终点开始，每个节点沿着父节点移动直至起点，这就是你的路径.四、 源程序#include <iostream> #include <ctime> #include <vector> using namespace std; constint ROW = 3; constint COL = 3; constint MAXDISTANCE = 10000; constint MAXNUM

5、 = 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; / 储存节点boolisEmptyOfOPEN() /判断Open表是否空 for (inti = 0; i<node_v.size(); i+) if (node_vi.dist != MAXNUM) ret

6、urn false; return true; boolisEqual(int index, int digitCOL) /判断节点是否与索引值指向的节点相同 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

7、 (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.index;

8、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) /获取节点 for (inti = 0; i< ROW; i+) for (int j =

9、 0; j < COL; j+) node.digitij = node_vindex.digitij; intGetMinNode() /获取启发值最小的节点 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 + node

10、_vi.dep; returnloc; boolisExpandable(Node& node) /判断是否可扩展 for (inti = 0; i<node_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+

11、) 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、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.digitx

13、 - 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.digitxy, no

14、de_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 > 0

15、) 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_

16、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.dis

17、t = MAXNUM; int main() int number; cout<< "输入初始状态:" <<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<< "输入目标状态" <<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