A star 算法 八数码问题 C++ 报告+代码+详细注释

二、程序运行测试 A*算法求解八数码问题 一、 详细设计说明 1. 评价函数 以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。距离的定义为：“某将牌行下标与目标位置行下标之差的绝对值 + 列下标与目标位置列下标之差的绝对值”。距离越小，该节点的效果越好。某个状态所有将牌到目标位置的距离之和用“h值”表示。

2. 主要函数 2.1 countH（state & st）; countH函数功能是计算st状态的h值。 计算过程中将会用到rightPos数组，数组里记录的是目标状态下，0~9每个将牌在九宫格里的位置（位置 = 行下标 * 3 + 列下标）。 2.2 f（state * p）; f()=h()+level 2.3 look_up_dup(vector & vec, state * p); 在open表或close表中，是否存在指定状态p，当找到与p完全相等的节点时，退出函数。 2.4 search(state & start)； 在open表不为空时，按f值由小到大对open表中元素进行排序。 调用findZero()函数找到0值元素的位置。空格可以向上下左右四个方向移动，前提是移动后不能越过九宫格的边界线。确定某方向可走后，空格移动一步，生成状态p’。 此时，检查open表中是否已有p’，若有，更新p’数据；检查close表中是否已有p’，若有，将p’从close表中删除，添加到open表中。 重复的执行这个过程，直到某状态的h值为零。 2.5 dump_solution(state * q)； 在终端输出解路径。

// A*算法 八数码问题 #include "stdafx.h" #include #include #include #include using namespace std;

const int GRID = 3; //Grid表示表格的行数(列数)，这是3*3的九宫格 int rightPos[9] = { 4, 0, 1, 2, 5, 8, 7, 6, 3 }; //目标状态时，若p[i][j]=OMG,那么3*i+j = rightPos[OMG]

struct state{ int panel[GRID][GRID]; int level; //记录深度 int h; state * parent;

state(int level) :level(level){} bool operator == (state & q){ //判断两个状态是否完全相等（对应位置元素相等），完全相等返回true,否则返回false for (int i = 0; ifor (int j = 0; jif (panel[i][j] != q.panel[i][j]) return false; } } return true; }

state & operator = (state & p){ //以状态p为当前状态赋值，对应位置元素相同 for (int i = 0; ifor (int j = 0; jpanel[i][j] = p.panel[i][j]; } } return *this; } };

void dump_panel(state * p){ //将八数码按3*3矩阵形式输出 for (int i = 0; ifor (int j = 0; jcout << p->panel[i][j] << " "; cout << endl; } }

int countH(state & st){ //给定状态st，计算它的h值。 int h = 0; for (int i = 0; ifor (int j = 0; jif (st.panel[i][j] != 0) h += abs(rightPos[st.panel[i][j]] / GRID - i) + abs(rightPos[st.panel[i][j]] % GRID - j); //h=各个将牌与其目标位置的距离之和.距离定义为：行下标之差的绝对值+列下标之差的绝对值。 } } return h; }

int findZero(state & st){ //找到零值元素，返回其在表中的位置 for (int i = 0; ifor (int j = 0; jif (st.panel[i][j] == 0) return i * 3 + j; } } }

int f(state * p){ //计算并返回f()值，即h值+level return countH(*p) + p->level; }

bool compare_state(state * p, state * q){ //比较两个状态的f值 return f(p) > f(q); }

vector open_table; //open表 vector close_table; //close表

vector::iterator look_up_dup(vector & vec, state * p){ vector::iterator it_r = vec.begin(); for (; it_rif ((*(*it_r)) == *p){ break; } } return it_r; } state * search(state & start){ //A*算法进行搜索 int level = 0; open_table.push_back(&start); int count = 0;

while (!open_table.empty()){ sort(open_table.begin(), open_table.end(), compare_state); //对open表中的元素进行排序

state * p = open_table.back(); open_table.pop_back();

if (countH(*p) == 0) return p; //所有将牌到达目标位置，搜索过程结束 level = p->level + 1;

int zeroPos = findZero(*p); int x = zeroPos / 3; //空格的行下标 int y = zeroPos % 3; //空格的列下标 for (int i = 0; i<4; i++){ //上下左右四个方向 int x_offset = 0, y_offset = 0; switch (i){ case 0:x_offset = 0, y_offset = 1; break; //右 case 1:x_offset = 0, y_offset = -1; break;//左 case 2:x_offset = 1, y_offset = 0; break;//上 case 3:x_offset = -1, y_offset = 0; break;//下 };

if (x + x_offset<0 || x + x_offset >= GRID || y + y_offset<0 || y + y_offset >= GRID){ continue; //若移动一步后，将超出上/下/左/右边界，则这个方向不可走，尝试下一个方向 } state * q = new state(level); //这个方向可走，扩展下一个节点 q->parent = p; *q = *p; q->panel[x][y] = q->panel[x + x_offset][y + y_offset]; q->panel[x + x_offset][y + y_offset] = 0;//空格沿这个方向移一步

bool skip = false; vector::iterator dup = look_up_dup(open_table, q); //若q已在open表中，则对open表中的信息进行更新 if (dup != open_table.end()){ if (f(q) < f(*dup)){ (*dup)->level = q->level; (*dup)->parent = q->parent; } skip = true; }

dup = look_up_dup(close_table, q); if (dup != close_table.end()){ //若q已在close表中，且f值比原值小， if (f(q) < f(*dup)){ //则将q从close表清除，加入open表 delete *dup; close_table.erase(dup); open_table.push_back(q); skip = true; } }

if (!skip){ open_table.push_back(q); } }

close_table.push_back(p); } }

void dump_solution(state * q) //输出解路径 { vector trace; while (q){ trace.push_back(q); q = q->parent; }

int count = 0; while (!trace.empty()){ cout << "Step " << count << " :^-^=^-^=^-^=^-^=^ ^=^-^=^-^=^-^=^-^=^-^=^@\n"; dump_panel(trace.back()); cout << "h: " << countH(*trace.back()) <<"\tg:"<