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

精品文档二、程序运行测试 A*算法求解八数码问题一、 详细设计说明1. 评价函数以当前状态下各将牌到目标位置的距离之和作为节点的评价标准。距离的定义为：“某将牌行下标与目标位置行下标之差的绝对值 + 列下标与目标位置列下标之差的绝对值”。距离越小，该节点的效果越好。某个状态所有将牌到目标位置的距离之和用“h值”表示。2. 主要函数2.1 countH（state & st）;countH函数功能是计算st状态的h值。计算过程中将会用到rightPos数组，数组里记录的是目标状态下，09每个将牌在九宫格里的位置（位置 = 行下标 * 3 + 列下标）。2.2 f（state * p）;f()=h()+level2.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#includeusing namespace std;const int GRID = 3;/Grid表示表格的行数(列数)，这是3*3的九宫格int rightPos9 = 4, 0, 1, 2, 5, 8, 7, 6, 3 ;/目标状态时，若pij=OMG,那么3*i+j = rightPosOMGstruct stateint panelGRIDGRID;int level;/记录深度int h;state * parent;state(int level) :level(level)bool operator = (state & q)/判断两个状态是否完全相等（对应位置元素相等），完全相等返回true,否则返回falsefor (int i = 0; iGRID; i+)for (int j = 0; jGRID; j+)if (panelij != q.panelij)return false;return true;state & operator = (state & p)/以状态p为当前状态赋值，对应位置元素相同for (int i = 0; iGRID; i+)for (int j = 0; jGRID; j+)panelij = p.panelij;return *this;void dump_panel(state * p)/将八数码按3*3矩阵形式输出for (int i = 0; iGRID; i+)for (int j = 0; jGRID; j+)cout panelij ;cout endl;int countH(state & st)/给定状态st，计算它的h值。int h = 0;for (int i = 0; iGRID; i+)for (int j = 0; jGRID; j+)if (st.panelij != 0)h += abs(rightPosst.panelij / GRID - i) +abs(rightPosst.panelij % GRID - j);/h=各个将牌与其目标位置的距离之和.距离定义为：行下标之差的绝对值+列下标之差的绝对值。return h;int findZero(state & st)/找到零值元素，返回其在表中的位置for (int i = 0; iGRID; i+)for (int j = 0; jlevel;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_rlevel + 1;int zeroPos = findZero(*p);int x = zeroPos / 3;/空格的行下标int y = zeroPos % 3;/空格的列下标for (int i = 0; i4; 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= GRID | y + y_offset= GRID)continue;/若移动一步后，将超出上/下/左/右边界，则这个方向不可走，尝试下一个方向state * q = new state(level);/这个方向可走，扩展下一个节点q-parent = p;*q = *p;q-panelxy = q-panelx + x_offsety + y_offset;q-panelx + x_offsety + 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) 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:count tf: f(trace.back() endl endl;trace.pop_back();count+;int main()state p(0);state *q;p.panel00 = 2;/设置初始状态p.panel