计算机科学论坛--问A*算法解决八数码问题

[size=4]#include <iostream>
#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];//结点数码值
     //用1 2 3等表示数码，0表示空格
int dist;  // 定义一个中间结点与目标节点的距离
int dep;   // 定义中间结点的深度
int index;// 定义一个指针，
} Node;

Node src, dest,bestnode; //定义源节点和目标节点和最优结点

vector<Node> Node_n; // 通过vector容器来存储结点定义一个Node类型

bool NullOPEN() {  //用来判断OPEN表是否为空
for (int i = 0; i < Node_n.size(); i++) {
  if (Node_n[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_n[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_n[index]);
index = Node_n[index].index;
while (index != 0) {
  rstep_v.push_back(Node_n[index]);
  index = Node_n[index].index;
}
for (int i = rstep_v.size() - 1; i >= 0; i--)
{cout << "第 " << rstep_v.size() - i<< "步 "
    <<endl<< rstep_v[i];
cout<<"该结点与目标结点的距离是："<<endl;
cout<<"该结点的深度是"<<endl;
cout<<"该结点的f(n)值为："<<endl<<endl;
}
}

void Swap(int& a, int& b) {//将空格与f(n)值最小数码替换，实现数码移动
int t;
t = a;
a = b;
b = t;
}

void Assign(Node& node, int index) {//
cout<<"ASSIGN"<<endl;for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
node.digit[i][j] = Node_n[index].digit[i][j];
}

int GetMinNode() {//得到最小结点的位置
int dist = MaxNUM;
int loc;  //用来表示最小结点的地点
for (int i = 0; i < Node_n.size(); i++) {
  if (Node_n[i].dist == MaxNUM)
   continue;
  else if ((Node_n[i].dist + Node_n[i].dep) < dist) {
   loc = i;
   dist = Node_n[i].dist + Node_n[i].dep;
  }
}
return loc;
}

bool isExpandable(Node& node) {//判断结点是否扩展过，
for (int i = 0; i < Node_n.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);
      distance=distance+1;
    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_n[index].digit[i][j] == 0) {//找出0结点 0结点表示为空格标记flag为true
    x =i; y = j;
    flag = true;
    break;
   }
   else flag = false;
  }
  if(flag)
   break;
}

Node Node_upProcess;
Assign(Node_upProcess, index);
int dist_up = MaxDistance;
if (x > 0) {
  Swap(Node_upProcess.digit[x][y], Node_upProcess.digit[x - 1][y]);
  if (isExpandable(Node_upProcess)) {
   dist_up = Distance(Node_upProcess, dest.digit);
   Node_upProcess.index = index;
   Node_upProcess.dist = dist_up;
   Node_upProcess.dep = Node_n[index].dep + 1;
   Node_n.push_back(Node_upProcess);
  cout<<"上";cout<<"不同结点个数："<<Node_upProcess.dist<<" "<<"深度："<<Node_upProcess.dep<<endl;}
}

Node Node_downProcess;
Assign(Node_downProcess, index);
int dist_down = MaxDistance;
if (x < 2) {
  Swap(Node_downProcess.digit[x][y], Node_downProcess.digit[x + 1][y]);
  if (isExpandable(Node_downProcess)) {
   dist_down = Distance(Node_downProcess, dest.digit);
   Node_downProcess.index = index;
   Node_downProcess.dist = dist_down;
   Node_downProcess.dep = Node_n[index].dep + 1;
   Node_n.push_back(Node_downProcess);
   cout<<"下";cout<<"不同结点个数："<<Node_downProcess.dist<<" "<<"深度："<<Node_downProcess.dep<<endl;}
}

Node Node_leftProcess;
Assign(Node_leftProcess, index);
int dist_left = MaxDistance;
if (y > 0) {
  Swap(Node_leftProcess.digit[x][y], Node_leftProcess.digit[x][y - 1]);
  if (isExpandable(Node_leftProcess)) {
   dist_left = Distance(Node_leftProcess, dest.digit);
   Node_leftProcess.index = index;
   Node_leftProcess.dist = dist_left;
   Node_leftProcess.dep = Node_n[index].dep + 1;
   Node_n.push_back(Node_leftProcess);

  cout<<"左";cout<<"不同结点个数："<<Node_leftProcess.dist<<" "<<"深度："<<Node_leftProcess.dep<<endl;}
}

Node Node_rightProcess;
Assign(Node_rightProcess, index);
int dist_right = MaxDistance;
if (y < 2) {
  Swap(Node_rightProcess.digit[x][y], Node_rightProcess.digit[x][y + 1]);
  if (isExpandable(Node_rightProcess)) {
   dist_right = Distance(Node_rightProcess, dest.digit);
   Node_rightProcess.index = index;
   Node_rightProcess.dist = dist_right;
   Node_rightProcess.dep = Node_n[index].dep + 1;
   Node_n.push_back(Node_rightProcess);
   cout<<"右";cout<<"不同结点个数："<<Node_rightProcess.dist<<" ";cout<<"深度："<<Node_rightProcess.dep<<endl;}
}

Node_n[index].dist = MaxNUM;
}

int main() { //主函数
int number;

cout << "请输入源数码:" << 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 << "请输入目标数码:" << endl;
for (int m = 0; m < ROW; m++)
  for (int n = 0; n < COL; n++) {
   cin >> number;
   dest.digit[m][n] = number;
  }

Node_n.push_back(src);//进行open表的增加和删减

cout << "正在搜索···" << endl;
while (1) {
  if (NullOPEN()) {
   cout << "失败" << endl;
   return -1;
  }
  else {
   int loc;  // 最小结点的地点
   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;
}

问题1：请问这个函数的作用：
void Assign(Node& node, int index) {
cout<<"ASSIGN"<<endl;for (int i = 0; i < ROW; i++)
  for (int j = 0; j < COL; j++)
   node.digit[i][j] = Node_n[index].digit[i][j];
}
问题2：A*算法中需要一个OPEN 表和一个CLOSE表，请问这个程序里面是如何体现？
问题3：在下面这个函数里面，得到的 loc 说是最小结点的地点，我该如何理解呢!
int GetMinNode() {//得到最小结点的位置
int dist = MaxNUM;
int loc;  //用来表示最小结点的地点
for (int i = 0; i < Node_n.size(); i++) {
  if (Node_n[i].dist == MaxNUM)
   continue;
  else if ((Node_n[i].dist + Node_n[i].dep) < dist) {
   loc = i;
   dist = Node_n[i].dist + Node_n[i].dep;
  }
}
return loc;
}
问题4：下面函数中，distance += abs(i - k) + abs(j - l);是什么意思呢？这也能作为h(n)函数吗？
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);
      distance=distance+1;
    flag = true;
      break;
     }
    else
     flag = false;
    }
  if (flag)
     break;
   }
   return distance;
}
问题5：这个程序总的来说还是有错误的，只能够进行简单的数码移动，一旦搜索树深度过深，数码的移动将会进入死循环。从而得不到结果，请高手帮忙看下，错误在何处！
问题6：这个程序只能够打印出最佳路径，如何打印出其他扩展结点，以及各结点的F(n)值和g(n),及f(n)值？
还请大家帮忙解答！！谢谢！！[/size]
文字


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