四、实验程序
#include
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
bool isEmptyOfOPEN() //open表是否为空 {
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
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; }
cout << \
for (int i = rstep_v.size() - 1; i >= 0; i--)//输出每一步的探索过程 cout << \ step：\
<< 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); 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); } } 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库人工智能实验报告(2)在线全文阅读。
相关推荐：