用A算法解决八数码问题.doc

用A*算法解决八数码问题
一、 题目：八数码问题也称为九宫问题。在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
二、 问题的搜索形式描述
状态：状态描述了8个棋子和空位在棋盘的9个方格上的分布。
初始状态：任何状态都可以被指定为初始状态。
操作符：用来产生4个行动（上下左右移动）。
目标测试：用来检测状态是否能匹配上图的目标布局。
路径费用函数：每一步的费用为1，因此整个路径的费用是路径中的步数。
现在任意给定一个初始状态，要求找到一种搜索策略，用尽可能少的步数得到上图的目标状态算法介绍
三、 解决方案介绍
1.A*算法的一般介绍
A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即
；
这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于盲目搜索策略。

A star算法在静态路网中的应用
2.算法伪代码
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。算起点的估价值，将起点放入OPEN表。
　　while(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节点插入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 = 10000;

int abs(int a)
{
if (a>0) return a;
else return -a;
}

typedefstruct _Node{
int digit[ROW][COL];
intdist; // 距离
intdep; // 深度
int index; // 索引值
} Node;
Node src, dest;
vector<Node>node_v; // 储存节点
boolisEmptyOfOPEN() { //判断Open表是否空
for (inti = 0; i<node_v.size(); i++) {
if (node_v[i].dist != MAXNUM)
return false;
}
return true;
}
boolisEqual(int index, int digit[][COL]) {//判断节点是否与索引值指向的节点相同
for (inti = 0; i< ROW; i++)
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] != digit[i][j])
return false;
}
return true;
}

ostream& operator<<(ostream&os, Node& node) {
for (inti = 0; i< ROW; i++) {
for (int j = 0; j < COL; j++)
os<<node.digit[i][j] << ' ';
os<<endl;
}
returnos;
}

void PrintSteps(int index, vector<Node>&rstep_v){//输出步骤
rstep_v.push_back(node_v[index]);
index = node_v[index].index;
while (index != 0) {
rstep_v.push_back(node_v[index]);
index = node_v[index].index;
}

for (inti = rstep_v.size() - 1; i>= 0; i--)
cout<< "Step " <<rstep_v.size() - i
<<endl<<rstep_v[i] <<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 = 0; j < COL; j++)
node.digit[i][j] = node_v[index].digit[i][j];
}

intGetMinNode() {//获取启发值最小的节点
intdist = MAXNUM;
intloc; // the location of minimize node
for (inti = 0; i<node_v.size(); i++) {
if (node_v[i].dist == MAXNUM)
continue;
else if ((node_v[i].dist + node_v[i].dep) <dist) {
loc = i;
dist = node_v[i].dist + node_v[i].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 digit[][COL]) {//计算距离
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.digit[i][j] == digit[k][l]) {
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) {//展开节点
int x, y;
bool flag;
for (inti = 0; i< ROW; i++) {
for (int j = 0; j < COL; j++) {
if (node_v[index].digit[i][j] == 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.digit[x][y], node_up.digit[x - 1][y]);
if (isExpandable(node_up)) {
dist_up = Distance(node_up, dest.digit);
node_up.index = index;
node_up.dist = dist_up;
node_up.dep = node_v[index].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[x][y], node_down.digit[x + 1][y]);
if (isExpandable(node_down)) {
dist_down = Distance(node_down, dest.digit);
node_down.index = index;
node_down.dist = dist_down;
node_down.dep = node_v[index].dep + 1;
node_v.push_back(node_down);
}
}

Node node_left;//左移操作
Assign(node_left, index);
intdist_left = MAXDISTANCE;
if (y > 0) {
Swap(node_left.digit[x][y], node_left.digit[x][y - 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_v[index].dep + 1;
node_v.push_back(node_left);
}
}

Node node_right; //右移操作
Assign(node_right, index);
intdist_right = MAXDISTANCE;
if (y < 2) {
Swap(node_right.digit[x][y], node_right.digit[x][y + 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_v[index].dep + 1;
node_v.push_back(node_right);
}
}

node_v[index].dist = MAXNUM;
}

int main() {
int number;

cout<< "输入初始状态:" <<endl;
for (inti = 0; i< ROW; i++)
for (int j = 0; j < COL; j++) {
cin>> number;
src.digit[i][j] = 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.digit[m][n] = number;
}

node_v.push_back(src);

while (1) {
if (isEmptyOfOPEN()) {
cout<< "找不到解!" <<endl;
return -1;
}
else {
intloc; // the location of the minimize node
loc = GetMinNode();
if(isEqual(loc, dest.digit)) {
vector<Node>rstep_v;
cout<< "初始状态：" <<endl;
cout<<src<<endl;
PrintSteps(loc, rstep_v);
cout<< "成功!" <<endl;
break;
}
else
ProcessNode(loc);
}
}

return 0;
}