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

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

3、(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)(大多数情况下都 是满足的，可以不用考虑)，且f必须保持单调递增。(2) h必须小于等于 实际的从当前节点到达目标节点的最小耗费h(n)*h'(n)。第二点特别的 重要。可以证明应用这样的估价函数是可以找到最短路径的。*算法的步骤A*算法基本上与广度优先

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

5、队列中的结点不重复，则按照它的估价函数f 大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到 大的顺序排列，最后更新队列尾指针。5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针 指向下一结点，再返回第二步。四、程序框图开始五、实验结果及分析输入初始状态：2 8 3目标状态：12 3送定 CAUsersMinuxkADktop队工百蹴 demo2.exe髓JAW陵2H31G47MS输入目标状态1238 H 4765初始状态，2 8 316 47 0SSWD 1Process exited with return ualuc H Pi*ese any kgy to c

6、ontinue .CLOSE00 10 1 50 15 70 15 7 60 1 5 7 6 9运行结果屏幕打印OPEN 表与 CLOSE 表:OPEN12 3 4234562346723468923489102 3 4 8 11 12 132 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 19114 8 12 13 14 15 16 17 19 2011188 12 13 14 15 16 17 19 21 22111812 13 14 15 16

7、1719212223111812 13 14 15 16 17192122242511184 8 2312 13 14 15 16 17192122242611184 8 23 24发现26为目标节点搜索树:24注释：每个方格中最上面两个数 字分别为编号与启发值，下O 1 832-8 4 231-六、结论对于八数码问题，BFS算法最慢，A*算法较快。八数码问题的一个状态 实际上是09的一个排列，对于任意给定的初始状态和目标，不一定有解， 也就是说从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列 两类，从奇排列不能转化成偶排列。如果一个数字08的随机排列0,用 F(X)表示数字X前面比它

8、小的数的个数，全部数字的F(X)之和为Y=£ (F(X),如果Y为奇数则称原数字的排列是奇排列，如果Y为偶数则称原 数字的排列是偶排列。因此，可以在运行程序前检查初始状态和目标状态 的排序的奇偶行是否相同，相同则问题可解，应当能搜索到路径。否则无 解。七、源程序及注释#include <iostream>#include <ctime>ttinclude <vector>usingnamespacestd;constintROW 二3;constintCOL 二3;constintMAXDISTANCE = 10000;constintMAXNUM

9、 = 10000；int abs(int a)if (a>0) return a;else return -a;typedef struct _Nodeint digitROWCOL;int dist; ist != MAXNUM)return false;return true;igitLi j !=bool isEqual(int index, int digitlCOL) digiti j)return false;return true;)ostream& operator<<(ostream& os, Node& node) for (int

10、 i = 0; i < ROW; i+) for (int j = 0; j < COL; j+)os << ij j ；os << endl;)return os;)void PrintSteps(int index, vector<Node>& rstep_v) ndex;while (index != 0) (node_vindex);index = node_vindex. index;)for (int i = () - 1; i >= 0; i)cout << "Step << () -

11、 i<< endl << rstep-vLi << endl;void Swap(int& a, int& b) igitiLj;)int GetMinNode() ist = MAXNUM) continue;else if (node_vi. dist + node_vLi. dep) < dist) loc = i;dist = node_vi. dist + node_vi. dep;)return loc;)bool isExpandable(Node& node) igit iLj= 0) x 二i; y = j;f

12、lag = true;break;)else flag = false;if(flag)break;Node node_up; ep + 1;(node_up);)Node node_down; ep + 1;(node_down);)Node node_left;ep + 1;(node_left);)Node node_right; ep + 1;(node_right);)node_vindex. dist = MAXNUM;)int main () int number;cout << 输入初始状态： << endl;for (int i = 0; i <

13、 ROW; i+)for (int j = 0; j < COL; j+) cin >> number;Li jj = number;)=0;=1;cout « 输入目标状态 endl;for (int m = 0; m < ROW; m+)for (int n = 0; n < COL; n+) cin >> number;nJ nJ = number;)(src);while (1) if (isEmptyOfOPENQ) cout <<找不到解! << endl;return -1;else (int loc; / the location of the minimize nodeloc = GetMinNode