中文XML论坛--请大家帮我看看这个程序 a*算法解决八数码问题

源程序：
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;

const int ROW = 3;
const int COL = 3;
const int MAXDISTANCE = 10000;
const int MAXNUM = 10000;

typedef struct _Node{
int digit[ROW][COL];
int dist; // distance between one state and the destination
int dep; // the depth of node
// So the comment function = dist + dep.
int index; // point to the location of parent
} Node;

Node src, dest;

vector <Node> node_v; // store the nodes

bool isEmptyOfOPEN() {
for (int i = 0; i < node_v.size(); i++) {
if (node_v[i].dist != MAXNUM)
return false;
}
return true;
}

bool isEqual(int index, int digit[][COL]) {
for (int i = 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 (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++)
os < < node.digit[i][j] < < ' ';
os < < endl;
}
return os;
}

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 (int i = 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 (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
node.digit[i][j] = node_v[index].digit[i][j];
}

int GetMinNode() {
int dist = MAXNUM;
int loc; // the location of minimize node
for (int i = 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;
}
}

return loc;
}

bool isExpandable(Node& node) {
for (int i = 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(int i = 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);//abs()求得是正数的绝对值。
   flag = true;
   break;
  }
  else
   flag = false;
  }
  if (flag)
  break;
}
return distance;
}

int MinDistance(int a, int b) {
return (a < b ? a : b);
}

void ProcessNode(int index) {
int x, y;
bool flag;
for (int i = 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);
int dist_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);
int dist_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);
int dist_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);
int dist_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 < < "Input source:" < < endl;
for (int i = 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 < < "Input destination:" < < 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);

cout < < "Search..." < < endl;
clock_t start = clock();
while (1) {
if (isEmptyOfOPEN()) {
cout < < "Cann't solve this statement!" < < endl;
return -1;
}
else {
int loc; // the location of the minimize node
loc = GetMinNode();
if(isEqual(loc, dest.digit)) {
  vector <Node> rstep_v;
  cout < < "Source:" < < endl;
  cout < < src < < endl;
  PrintSteps(loc, rstep_v);
  cout < < "Successful!" < < endl;
  cout < < "Using " < < (clock() - start) / CLOCKS_PER_SEC
   < < " seconds." < < endl;
  break;
}
else
  ProcessNode(loc);
}
}

return 0;
}

这是一个A*算法解决八数码问题：
所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是，在3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。
A*算法描述如下：
(1)生成一个只包含开始结点 n0 的搜索图 G，把 n0 放在 OPEN 列表上；
(2)生成一个 CLOSE 列表，它的初始值为空；
(3)若 OPEN 为空，则失败退出；
(4)选择 OPEN 的第一个结点，把它从 OPEN 表移入 CLOSE 表，称该结点为 n；
(5)若 n 是目标结点，顺着 G 中从 n 到 n0 的指针找到一条路径，获得解决方案，成功退出(该指针定义了一个搜索树，在第(7)步建立)；
(6)扩展结点 n，生成其后继结点集 M。在 G 中，n 的祖先不能在 M 中。在 G 中安置 M 的成员，使它们成为n 的后继；
(7)从 M 的每一个不在 G 中的成员建立一个指向 n 的指针。把 M 的这些成员加入到 OPEN 表中。对 M 中的每一个已在 OPEN 表或 CLOSE 表中的成员 m，若到目前为止找到的到达 m 的最好路径通过 n，就把它的指针指向 n；对已在 CLOSE 表中的 M 的每一个成员，重定向它在 G 中的每一个后继，以使它们顺着到目标发现的最好路径指向它们的祖先；
(8)按定义的函数值从小到大的顺序重排 OPEN 表；
返回第(3)步
然后有几个问题想问大家
问题1：
这个程序应该是，不论何种初始状态,始终能得到一个从初始状态到目标状态的搜索路径,但是程序运行后，但是这个程序有些还是达不到，比如从
1 2 3
4 5 6
7 8 0
到
1 2 3
4 5 6
8 7 0
说明这个程序算法实现还是有问题的，请高手帮忙解答为什么。
问题2：
对问题1里面出现的问题，我觉得应该是步骤重复了，哪么我怎样避免重复访问一个状态呢！

[此贴子已经被作者于2008-5-30 19:46:57编辑过]


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	62.500ms