《2022年八数码问题C语言A星算法详细实验报告含代码.pdf》由会员分享，可在线阅读，更多相关《2022年八数码问题C语言A星算法详细实验报告含代码.pdf（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、八数码问题C语言 A星算法详细实验报告含代码一、实验内容与要求八数码问题 : 在33的方格棋盘上 , 摆放着1到8这八个数码 , 有1个方格就是空的, 其初始状态如图 1所示, 要求对空格执行空格左移、空格右移、空格上移与空格下移这四个操作使得棋盘从初始状态到目标状态。例如: 2 8 3 1 2 3 1 6 4 8 4 7 0 5 7 6 5 (a) 初始状态 (b) 目标状态图 1 八数码问题示意图请任选一种盲目搜索算法 ( 广度优先搜索或深度优先搜索) 或任选一种启发式搜索方法 (全局择优搜索 , 加权状态图搜索 , A 算法或 A* 算法) 编程求解八数码问题 ( 初始状态任选 )。选择
2、一个初始状态 , 画出搜索树 , 填写相应的 OPEN 表与CLOSED表, 给出解路径 , 对实验结果进行分析总结, 得出结论。二、实验目的1、 熟悉人工智能系统中的问题求解过程; 2、 熟悉状态空间的盲目搜索与启发式搜索算法的应用; 3、 熟悉对八数码问题的建模、求解及编程语言的应用。三、实验算法A*算法就是一种常用的启发式搜索算法。在 A*算法中 , 一个结点位置的好坏用估价函数来对它进行评估。A*算法的估价函数可表示为 : f(n) = g(n) + h(n) 这里,f(n)就是估价函数 ,g(n)就是起点到终点的最短路径值(也称为最小耗费或最小代价 ),h(n)就是 n 到目标的最短
3、路经的启发值。由于这个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)。这样必须满足两个条件:(1)g(n)=g(n)(大多数情况下都就是满足的,精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - -
4、- - - - - - -第 1 页，共 10 页 - - - - - - - - - - 八数码问题C语言 A星算法详细实验报告含代码可以不用考虑 ), 且 f 必须保持单调递增。 (2)h 必须小于等于实际的从当前节点到达目标节点的最小耗费h(n)=h(n)。第二点特别的重要。可以证明应用这样的估价函数就是可以找到最短路径的。3、A*算法的步骤A*算法基本上与广度优先算法相同, 但就是在扩展出一个结点后, 要计算它的估价函数 , 并根据估价函数对待扩展的结点排序, 从而保证每次扩展的结点都就是估价函数最小的结点。A*算法的步骤如下 : 1) 建立一个队列 , 计算初始结点的估价函数f, 并
5、将初始结点入队 , 设置队列头与尾指针。2) 取出队列头 ( 队列头指针所指 ) 的结点 , 如果该结点就是目标结点, 则输出路径 ,程序结束。否则对结点进行扩展。3) 检查扩展出的新结点就是否与队列中的结点重复, 若与不能再扩展的结点重复( 位于队列头指针之前 ), 则将它抛弃 ; 若新结点与待扩展的结点重复( 位于队列头指针之后 ), 则比较两个结点的估价函数中g 的大小 , 保留较小 g 值的结点。跳至第五步。4) 如果扩展出的新结点与队列中的结点不重复, 则按照它的估价函数f 大小将它插入队列中的头结点后待扩展结点的适当位置, 使它们按从小到大的顺序排列,最后更新队列尾指针。5) 如果
6、队列头的结点还可以扩展, 直接返回第二步。否则将队列头指针指向下一结点, 再返回第二步。四、程序框图精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 10 页 - - - - - - - - - - 八数码问题C语言 A星算法详细实验报告含代码五、实验结果及分析输入初始状态 :2 8 3 目标状态 : 1 2 3 1 6 4 8 0 4 7 0 5 7 6 5 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第
7、 3 页，共 10 页 - - - - - - - - - - 八数码问题C语言 A星算法详细实验报告含代码运行结果屏幕打印OPEN 表与 CLOSE 表: OPEN CLOSE 1 2 3 4 0 2 3 4 5 6 0 1 2 3 4 6 7 0 1 5 2 3 4 6 8 9 0 1 5 7 2 3 4 8 9 10 0 1 5 7 6 2 3 4 8 11 12 13 0 1 5 7 6 9 2 3 4 8 12 13 14 15 0 1 5 7 6 9 11 3 4 8 12 13 14 15 16 17 0 1 5 7 6 9 11 2 4 8 12 13 14 15 16 17
8、18 19 0 1 5 7 6 9 11 2 3 4 8 12 13 14 15 16 17 19 20 0 1 5 7 6 9 11 2 3 18 8 12 13 14 15 16 17 19 21 22 0 1 5 7 6 9 11 2 3 18 4 12 13 14 15 16 17 19 21 22 23 0 1 5 7 6 9 11 2 3 18 4 8 12 13 14 15 16 17 19 21 22 24 25 0 1 5 7 6 9 11 2 3 18 4 8 23 12 13 14 15 16 17 19 21 22 24 26 0 1 5 7 6 9 11 2 3 18
9、 4 8 23 24 发现 26 为目标节点搜索树 :072 8 3 1 0 4 7 6 5 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 10 页 - - - - - - - - - - 八数码问题C语言 A星算法详细实验报告含代码六、结论对于八数码问题 ,BFS 算法最慢 ,A* 算法较快。八数码问题的一个状态实际上就是 09 的一个排列 , 对于任意给定的初始状态与目标, 不一定有解 , 也就就是说从初始状态不一定能到达目标状态。因为排列有奇排列与偶排列两类, 从奇排列不能转化成偶排列
10、。如果一个数字08 的随机排列 871526340,用 F(X)表示数字X 前面比它小的数的个数 , 全部数字的 F(X) 之与为 Y=(F(X),如果 Y 为奇数则称原数字的排列就是奇排列, 如果 Y为偶数则称原数字的排列就是偶排列。因此,可以在运行程序前检查初始状态与目标状态的排序的奇偶行就是否相同, 相同则问题可解 , 应当能搜索到路径。否则无解。七、源程序及注释#include #include #include using namespace std; const int ROW = 3; const int COL = 3; 18 、10 0 8 3 2 1 4 7 6 5 172
11、 0 3 1 8 4 7 6 5 2 、 、11 2 8 3 1 6 4 7 0 5 3 、 、11 2 8 3 0 1 4 7 6 5 4 、11 2 8 3 1 4 0 7 6 5 580 2 3 1 8 4 7 6 5 692 3 0 1 8 4 7 6 5 10 、14 2 8 3 1 6 4 7 0 5 11 、14 2 8 3 1 6 4 7 5 0 19 、12 2 8 3 7 1 4 0 6 5 21 、12 2 8 3 1 4 3 7 6 5 22 、14 2 8 3 1 4 5 7 6 0 20 、11 8 0 3 2 1 4 7 6 5 791 2 3 0 8 4 7 6
12、 5 10 、11 2 3 4 1 8 0 7 6 5 13 、13 1 2 3 8 4 0 7 6 5 11、 、9 1 0 3 8 2 4 7 6 5 12 、13 1 2 3 8 6 4 7 0 5 8 、12 1 2 3 7 8 4 0 6 5 9 、 、10 1 2 3 8 0 4 7 6 5 23、 、9 1 2 3 7 8 4 6 0 5 24、 、8 1 2 3 7 0 4 6 8 5 25 、12 1 2 3 7 8 4 6 5 0 15 、14 3 1 0 8 2 4 7 6 5 14 、12 0 1 3 8 2 4 7 6 5 目标节点注释: 每个方格中最上面两个数字分别
13、为编号与启发值,下面九个数字为八数码。较粗的箭头为解路径精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 10 页 - - - - - - - - - - 八数码问题C语言 A星算法详细实验报告含代码const int MAXDISTANCE = 10000; const int MAXNUM = 10000; int abs(int a) if (a0) return a; else return -a; typedef struct _Node int digitROWCOL; int di
14、st; / 距离int dep; / 深度int index; / 索引值 Node; Node src, dest; vector node_v; / 储存节点bool isEmptyOfOPEN() /判断 Open表就是否空for (int i = 0; i node_v、size(); 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
15、j = 0; j COL; j+) if (node_vindex、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 index, vector& rstep_v) /输出步骤rstep_v 、push_back(node_vindex); in
16、dex = node_vindex、index; while (index != 0) rstep_v、push_back(node_vindex); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 10 页 - - - - - - - - - - 八数码问题C语言 A星算法详细实验报告含代码 index = node_vindex、index; for (int i = rstep_v、size() - 1; i = 0; i-) cout Step rstep_v、size() - i e
17、ndl rstep_vi endl; void S 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、digitij = node_vindex、digitij; int GetMinNode() /获取启发值最小的节点int dist = MAXNUM; int loc; / the location of minimize node for (int i = 0
18、; i node_v、size(); i+) if (node_vi、dist = MAXNUM) continue; else if (node_vi、dist + node_vi、dep) 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 Distanc
19、e(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+) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 10 页 - - - - - - - - - - 八数码问题C语言 A星算法详细实验报告含代码
20、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 index) /展开节点int x, y; bool flag; for (int i = 0; i ROW; i+) for (int j = 0; j 0) Sxy
21、, 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); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 10 页 - - - - - - - - - -
22、八数码问题C语言 A星算法详细实验报告含代码Node node_down; / 下移操作Assign(node_down, index); int dist_down = MAXDISTANCE; if (x 0) Sxy, 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;
23、node_v、push_back(node_left); Node node_right; /右移操作Assign(node_right, index); int dist_right = MAXDISTANCE; if (y 2) Sxy, 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
24、_vindex、dep + 1; node_v、push_back(node_right); node_vindex 、dist = MAXNUM; int main() int number; cout 输入初始状态 : endl; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 10 页 - - - - - - - - - - 八数码问题C语言 A星算法详细实验报告含代码for (int i = 0; i ROW; i+) for (int j = 0; j number; src、dig
25、itij = number; src 、index = 0; src 、dep = 1; cout 输入目标状态 endl; for (int m = 0; m ROW; m+) for (int n = 0; n 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 rstep_v; cout 初始状态 : endl; cout src endl; PrintSteps(loc, rstep_v); cout 成功! endl; break; else ProcessNode(loc); return 0; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 10 页 - - - - - - - - - -