八数码问题c语言a星算法详细实验报告含代码.doc
-一、实验内容和要求八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。例如：28312316484705765(a) 初始状态 (b) 目标状态图1 八数码问题示意图请任选一种盲目搜索算法广度优先搜索或深度优先搜索或任选一种启发式搜索方法全局择优搜索，加权状态图搜索，A 算法或A* 算法编程求解八数码问题初始状态任选。选择一个初始状态，画出搜索树，填写相应的OPEN表和CLOSED表，给出解路径，对实验结果进展分析总结，得出结论。二、实验目的1. 熟悉人工智能系统中的问题求解过程；2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；3. 熟悉对八数码问题的建模、求解及编程语言的应用。三、实验算法A*算法是一种常用的启发式搜索算法。在A*算法中，一个结点位置的好坏用估价函数来对它进展评估。A*算法的估价函数可表示为：f'(n) = g'(n) + h'(n) 这里，f'(n)是估价函数，g'(n)是起点到终点的最短路径值也称为最小消耗或最小代价，h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以实际上使用的是下面的估价函数：f(n) = g(n) + h(n) 其中g(n)是从初始结点到节点n的实际代价，h(n)是从结点n到目标结点的最正确路径的估计代价。在这里主要是h(n)表达了搜索的启发信息，因为g(n)是的。用f(n)作为f'(n)的近似，也就是用g(n)代替g'(n)，h(n)代替h'(n)。这样必须满足两个条件：1g(n)>=g'(n)大多数情况下都是满足的，可以不用考虑，且f必须保持单调递增。2h必须小于等于实际的从当前节点到达目标节点的最小消耗h(n)<=h'(n)。第二点特别的重要。可以证明应用这样的估价函数是可以找到最短路径的。3.A*算法的步骤A*算法根本上与广度优先算法一样，但是在扩展出一个结点后，要计算它的估价函数，并根据估价函数对待扩展的结点排序，从而保证每次扩展的结点都是估价函数最小的结点。A*算法的步骤如下：1建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。2取出队列头队列头指针所指的结点，如果该结点是目标结点，则输出路径，程序完毕。否则对结点进展扩展。3检查扩展出的新结点是否与队列中的结点重复，假设与不能再扩展的结点重复位于队列头指针之前，则将它抛弃；假设新结点与待扩展的结点重复位于队列头指针之后，则比拟两个结点的估价函数中g的大小，保存较小g值的结点。跳至第五步。4如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。5如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。四、程序框图五、实验结果及分析输入初始状态：2 8 3目标状态：1 2 31 6 48 0 47 0 57 6 5运行结果屏幕打印OPEN表与CLOSE表：OPENCLOSE1 2 3 4 02 3 4 5 60 12 3 4 6 70 1 52 3 4 6 8 90 1 5 72 3 4 8 9 100 1 5 7 62 3 4 8 11 12 13 0 1 5 7 6 92 3 4 8 12 13 14 150 1 5 7 6 9 113 4 8 12 13 14 15 16 170 1 5 7 6 9 11 24 8 12 13 14 15 16 17 18 190 1 5 7 6 9 11 2 34 8 12 13 14 15 16 17 19 200 1 5 7 6 9 11 2 3 188 12 13 14 15 16 17 19 21 220 1 5 7 6 9 11 2 3 18 412 13 14 15 16 17 19 21 22 230 1 5 7 6 9 11 2 3 18 4 812 13 14 15 16 17 19 21 22 24 250 1 5 7 6 9 11 2 3 18 4 8 2312 13 14 15 16 17 19 21 22 24 260 1 5 7 6 9 11 2 3 18 4 8 23 24发现26为目标节点072 8 31 0 47 6 5搜索树：2.112 8 31 6 47 0 5172 0 31 8 47 6 54.112 8 31 4 07 6 53.112 8 30 1 47 6 52 8 31 4 57 6 02 8 37 1 40 6 52 8 31 4 37 6 50 8 32 1 47 6 52 8 31 6 47 5 02 8 31 6 47 0 5692 3 01 8 47 6 5580 2 31 8 47 6 5791 2 30 8 47 6 52 3 41 8 07 6 58 0 32 1 47 6 5注释：每个方格中最上面两个数字分别为编号与启发值，下面九个数字为八数码。较粗的箭头为解路径8.121 2 37 8 40 6 59.101 2 38 0 47 6 511.91 0 38 2 47 6 523.91 2 37 8 46 0 51 2 38 4 07 6 51 2 38 6 47 0 524.81 2 37 0 46 8 51 2 37 8 46 5 00 1 38 2 47 6 53 1 08 2 47 6 5目标节点六、结论对于八数码问题，BFS算法最慢，A*算法较快。八数码问题的一个状态实际上是09的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类，从奇排列不能转化成偶排列。如果一个数字08的随机排列871526340，用F(*)表示数字*前面比它小的数的个数，全部数字的F(*)之和为Y=(F(*)，如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原数字的排列是偶排列。因此，可以在运行程序前检查初始状态和目标状态的排序的奇偶行是否一样，一样则问题可解，应当能搜索到路径。否则无解。七、源程序及注释#include <iostream>#include <ctime>#include <vector>using namespace std;const int ROW = 3;const int COL = 3;const int MA*DISTANCE = 10000;const int MA*NUM = 10000;int abs(int a)if (a>0) return a;else return -a;typedef struct _Nodeint digitROWCOL;int dist; / 距离int dep; / 深度int inde*; / 索引值 Node;Node src, dest;vector<Node> node_v; / 储存节点bool isEmptyOfOPEN() /判断Open表是否空for (int i = 0; i < node_v.size(); i+) if (node_vi.dist != MA*NUM) return false;return true;bool isEqual(int inde*, int digitCOL) /判断节点是否与索引值指向的节点一样for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) if (node_vinde*.digitij != digitij) 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.digitij << ' ' os << endl;return os;void PrintSteps(int inde*, vector<Node>& rstep_v) /输出步骤rstep_v.push_back(node_vinde*);inde* = node_vinde*.inde*;while (inde* != 0) rstep_v.push_back(node_vinde*); inde* = node_vinde*.inde*;for (int i = rstep_v.size() - 1; i >= 0; i-) cout << "Step " << rstep_v.size() - i << endl << rstep_vi << endl;void Swap(int& a, int& b) /交换int t;t = a;a = b;b = t;void Assign(Node& node, int inde*) /获取节点for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) node.digitij = node_vinde*.digitij;int GetMinNode() /获取启发值最小的节点int dist = MA*NUM;int loc; / the location of minimize nodefor (int i = 0; i < node_v.size(); i+) if (node_vi.dist = MA*NUM) continue; else if (node_vi.dist + node_vi.dep) < dist) loc = i; dist = node_vi.dist + node_vi.dep; return loc;bool isE*pandable(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 digitCOL) /计算距离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.digitij = digitkl) 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 inde*) /展开节点int *, y;bool flag;for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) if (node_vinde*.digitij = 0) * =i; y = j; flag = true; break; else flag = false; if(flag) break;Node node_up; /上移操作Assign(node_up, inde*);int dist_up = MA*DISTANCE;if (* > 0) Swap(node_up.digit*y, node_up.digit* - 1y); if (isE*pandable(node_up) dist_up = Distance(node_up, dest.digit); node_up.inde* = inde*; node_up.dist = dist_up; node_up.dep = node_vinde*.dep + 1; node_v.push_back(node_up); Node node_down; /下移操作Assign(node_down, inde*);int dist_down = MA*DISTANCE;if (* < 2) Swap(node_down.digit*y, node_down.digit* + 1y); if (isE*pandable(node_down) dist_down = Distance(node_down, dest.digit); node_down.inde* = inde*; node_down.dist = dist_down; node_down.dep = node_vinde*.dep + 1; node_v.push_back(node_down); Node node_left;/左移操作Assign(node_left, inde*);int dist_left = MA*DISTANCE;if (y > 0) Swap(node_left.digit*y, node_left.digit*y - 1); if (isE*pandable(node_left) dist_left = Distance(node_left, dest.digit); node_left.inde* = inde*; node_left.dist = dist_left; node_left.dep = node_vinde*.dep + 1; node_v.push_back(node_left); Node node_right; /右移操作Assign(node_right, inde*);int dist_right = MA*DISTANCE;if (y < 2) Swap(node_right.digit*y, node_right.digit*y + 1); if (isE*pandable(node_right) dist_right = Distance(node_right, dest.digit); node_right.inde* = inde*; node_right.dist = dist_right; node_right.dep = node_vinde*.dep + 1; node_v.push_back(node_right); node_vinde*.dist = MA*NUM;int main() int number;cout << "输入初始状态:" << endl;for (int i = 0; i < ROW; i+) for (int j = 0; j < COL; j+) cin >> number; src.digitij = number; src.inde* = 0;src.dep = 1;cout << "输入目标状态" << endl;for (int m = 0; m < ROW; m+) for (int n = 0; n < COL; n+) cin >> number; dest.digitmn = number; node_v.push_back(src);while (1) if (isEmptyOfOPEN() cout << "找不到解!" << endl; return -1; else int loc; / the location of the minimize node 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;. z.
