八数码问题C语言A星算法详细实验报告材料含代码

1、、实验容和要求八数码问题：在3X 3的方格棋盘上，摆放着1到8这八个数码，有1个方格是 空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移 和空格下移这四个操作使得棋盘从初始状态到目标状态。例如：28312316484705765(a)初始状态(b)目标状态图1八数码问题示意图请任选一种盲目搜索算法(广度优先搜索或深度优先搜索) 或任选一种启发 式搜索方法(全局择优搜索，加权状态图搜索，A算法或A*算法)编程求解八数码问题(初始状态任选)。选择一个初始状态，画出搜索树，填写相应的OPEN 表和CLOSE表，给出解路径，对实验结果进行分析总结，得出结论。二、实验目的1. 熟悉

2、人工智能系统中的问题求解过程；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

3、) 是从初始结点到节点 n 的实际代价， h(n) 是从结点 n 到目标结点的最 佳路径的估计代价。在这里主要是 h(n) 体现了搜索的启发信息，因为 g(n) 是已 知的。用 f(n) 作为 f'(n) 的近似，也就是用 g(n) 代替 g'(n) ， h(n) 代替 h'(n) 。 这样必须满足两个条件： (1)g(n)>=g'(n) (大多数情况下都是满足的，可以不 用考虑)，且 f 必须保持单调递增。( 2) h 必须小于等于实际的从当前节点到达 目标节点的最小耗费 h(n)<=h'(n) 。第二点特别的重要。可以证明应用这样的估 价

4、函数是可以找到最短路径的。3.A* 算法的步骤A*算法基本上与广度优先算法相同，但是在扩展出一个结点后，要计算它的估价 函数，并根据估价函数对待扩展的结点排序， 从而保证每次扩展的结点都是估价 函数最小的结点。A*算法的步骤如下：1) 建立一个队列，计算初始结点的估价函数f ，并将初始结点入队，设置队列 头和尾指针。2) 取出队列头(队列头指针所指)的结点，如果该结点是目标结点，则输出路 径，程序结束。否则对结点进行扩展。3) 检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复 (位于队列头指针之前) ，则将它抛弃；若新结点与待扩展的结点重复(位于队列头指针之后)，则比较两个结

5、点的估价函数中g的大小，保留较小g值的结点。 跳至第五步。4) 如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f 大小将 它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排 列，最后更新队列尾指针。5) 如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下 一结点，再返回第二步。四、程序框图五、实验结果及分析输入初始状态：2 8 3目标状态：1 2 3运行结果屏幕打印0 1 5 7 6 9 11 2OPEN 表与 CLOSE 表:OPENCLOSE1 2 3 402 3 4 5 60 12 3 4 6 70 1 52 3 4 6 8 90 1 5 7

6、2 3 4 8 9 100 1 5 7 62 3 4 8 11 12 130 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 174 8 12 13 14 15 16 17 19 208 12 13 14 15 16 17 19 21 2212 13 14 15 16 17 19 21 22 2312 13 14 15 16 17 19 21 22 24 2512 13 14 15 16 17 19 21 22 24 26发现26为目标节点0 1 5 7 6 9 11 2 3 180 1 5 7 6 9 11 2 3

7、 18 40 1 5 7 6 9 11 2 3 18 4 80 1 5 7 6 9 11 2 3 18 4 8 230 1 5 7 6 9 11 2 3 18 4 8 23 24搜索树:24.8注释：每个方格中最上面两个数字 分别为编号与启发值，下面 九个数字为八数码。较粗的目标节点14.120 1 382-4-15.143 1 08-2-4-六、结论对于八数码问题，BFS算法最慢，A*算法较快。八数码问题的一个状态实际 上是09的一个排列，对于任意给定的初始状态和目标，不一定有解，也就是说 从初始状态不一定能到达目标状态。 因为排列有奇排列和偶排列两类，从奇排列 不能转化成偶排列。如果一个数

8、字08的随机排列871526340,用F(X)表示数字 X前面比它小的数的个数，全部数字的F(X)之和为Y=E (F(X)，如果丫为奇数则称原数字的排列是奇排列，如果 丫为偶数则称原数字的排列是偶排列。因此， 可以在运行程序前检查初始状态和目标状态的排序的奇偶行是否相同，相同则问题可解，应当能搜索到路径。否则无解。七、源程序及注释#in elude <iostream>#in elude <ctime>#in elude <veetor>using n amespace std;const int ROW = 3;const int COL = 3;cons

9、t int MAXDISTANCE = 10000;const int MAXNUM = 10000;int abs(int a)if (a>0) return a;else return -a;typedef struct _Nodeint digitROWCOL;int dist; /距离int dep; /深度int index; /索引值 Node;Node src, dest;vector<Node> node_v; / 储存节点bool isEmptyOfOPEN() / 判断 Open表是否空 for (int i = 0; i < node_v.size

10、(); i+) if (node_vi.dist != MAXNUM)return false;return true;bool isEqual(int index, int digitCOL) / 值指向的节点相同for (int i = 0; i < ROW; i+)for (int j = 0; j < COL; j+) if (node_vindex.digitij != digitij)return false;return true;ostream& operator<<(ostream& os, Node& node) for (i

11、nt i = 0; i < ROW; i+) for (int j = 0; j < COL; j+)os << node.digitij << ' 'os << endl;return os;void PrintSteps(int index, vector<Node>& rstep_v) / rstep_v.push_back(node_vindex);index = node_vindex.index;判断节点是否与索引输出步骤while (index != 0) rstep_v.push_back(no

12、de_vindex);index = node_vindex.index;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 index) / fo

13、r (int i = 0; i < ROW; i+)for (int j = 0; j < COL; j+)node.digitij = node_vindex.digitij;int GetMinNode() / 获取启发值最小的节点 int dist = MAXNUM;int loc; / the location of minimize nodefor (int i = 0; i < node_v.size(); i+) if (node_vi.dist = MAXNUM)continue;else if (node_vi.dist + node_vi.dep) <

14、; dist) loc = i;dist = node_vi.dist + node_vi.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 digitCOL) /int distance = 0;bool flag = false;for(int i = 0; i &l

15、t; 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;elseflag = false;if (flag)break;return distance;二者取小展开节点int MinDistance(int a, int b) / return (a < b ? a :

16、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_vindex.digitij = 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_

17、up.digitxy, node_up.digitx - 1y); if (isExpandable(node_up) dist_up = Distance(node_up, dest.digit);node_up.index = index;node_up.dist = dist_up;node_up.dep = node_vindex.dep + 1;node_v.push_back(node_up);Node node_down; / 下移操作Assign(node_down, index);int dist_down = MAXDISTANCE;if (x < 2) Swap(n

18、ode_down.digitxy, node_down.digitx + 1y); if (isExpandable(node_down) dist_down = Distance(node_down, dest.digit); node_down.index = index;node_down.dist = dist_down;node_down.dep = node_vindex.dep + 1; node_v.push_back(node_down);Node node_left;/ 左移操作Assign(node_left, index);int dist_left = MAXDIST

19、ANCE;if (y > 0) Swap(node_left.digitxy, node_left.digitxy - 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_vindex.dep + 1;node_v.push_back(node_left);Node node_right; / 右移操作Assign(node_right, index

20、);int dist_right = MAXDISTANCE;if (y < 2) Swap(node_right.digitxy, node_right.digitxy + 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_vindex.dep + 1;node_v.push_back(node_right);node_vindex.dist = MAXNUM;int main() int number;cout << " 输入初始状态 :" << endl;for (int i = 0; i < ROW