八数码问题实验报告

1、.八数码问题实验报告一、实验目的：熟练掌握启发式搜索a 算法 。二、实验内容：使用启发式搜索算法求解8 数码问题。编制程序实现求解8 数码问题 a 算法，采用估价函数w nf n d n，p n其中： d n 是搜索树中结点n 的深度； w n 为结点 n 的数据库中错放的棋子个数；p n 为结点 n 的数据库中每个棋子与其目标位置之间的距离总和。三、实验原理：1.问题描述 ：八数码问题也称为九宫问题。在33 的棋盘，摆有八个棋子，每个棋子上标有1 至 8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0 来表示），与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始

2、状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2. 原理描述：启发式搜索（1）原理启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。 在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。（ 2）估价函数计算一个节点的估价函数，可以分成两个部分：1、 已经付出的代价（起始节点到当前节点）；2、 将要付出的代价（当前节点到目

3、标节点）。节点 n 的估价函数f ( n) 定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即 f * (n) =g* (n) + h* (n) 。g* (n) 是从初始节点到达当前节点n 的实际代价；h* (n) 是从节点 n 到目标节点的最佳路径的估计代价。.g* (n) 所占的比重越大，越趋向于宽度优先或等代价搜索；反之，h* (n) 的比重越大，表示启发性能就越强。（3）算法描述：把起始节点 s 放到 open 表中，并计算节点s 的 f ( s) ；如果 open 是空表，则失败退出，无解；从 open 表中选择一个 f 值最小的节点 i 。如果有几个节点值相同，当其

4、中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i ；把节点 i 从 open 表中移出，并把它放入closed 的已扩展节点表中；如果 i 是个目标节点，则成功退出，求得一个解；扩展节点 i ，生成其全部后继节点。对于 i的每一个后继节点j ：计算 f ( j ) ；如果 j既不在 open 表中，又不在cloced 表中，则用估价函数f 把它添入 open 表中。从j 加一指向其父节点i 的指针，以便一旦找到目标节点时记住一个解答路径；如果j 已在 open 表或 closed 表中，则比较刚刚对j 计算过的f 和前面计算过的该节点在表中的f 值。如果新的f 较小，

5、则(i) 以此新值取代旧值。(ii) 从 j 指向 i ，而不是指向他的父节点。(iii) 如果节点j 在 closed 表中，则把它移回open 表中。转向，即goto。（3）算法流程图：.四、实验结果输入矩阵：目标矩阵：283123145804760765五、实验小结通过本次试验， 我对启发式搜索有了更加深入的了解。在实验中， 通过对两种启发式搜索所扩在的节点数来看，p(n) 看来比( n) 更加有效，能在复杂情况下求得更加优质的解，避免不必要的节点的扩展。所以，要更好地定义一个估价函数还有待深入讨论。.源代码：#includestdio.h#define num 3 /宏定义数码的行列数

6、为3/* 显示当前待调整数码矩阵*/void show(int beginnumnum)for(int i = 0; i num; i+)for(int j = 0; j num; j+)printf(%d , beginij);printf(n);printf(n);/* 交换数码中的beginrow_onecolumn_one与 beginrow_twocolumn_two这两个数 */voidexchange(intbeginnumnum,introw_one,intcolumn_one,introw_two,intcolumn_two)int temp;temp = beginrow_

7、twocolumn_two ;beginrow_twocolumn_two = beginrow_onecolumn_one;beginrow_onecolumn_one = temp;/* 判断待调整的数码与最终数码相比正确位置数码的个数*/int judge(int beginnumnum, int endnumnum)int count=0;/count记录数码中正确位置的个数for(int i = 0; i num; i+)/检查当前图形的正确度for(int j = 0; j = 20)return 0;int node; /,node为标记int temp;/存储当前待调整数码正确

8、的个数for(int q=0; qjishu; q+) /检查交换后的end图形是否先前已经遍历过了node = 1;for(int w=0; wnum & node; w+)for(int r=0; rnum & node; r+)if(ji_shuqwr != beginwr)node = 0;if(node = 1)/如果先前遍历过，返回0return 0;for(int i = 0; i num; i+)for(int j = 0; j 0 & biaoji != 0)/存储 0 的位置不是在第一行exchange(begin, row - 1, column, row , colum

9、n); /将 0 与其上面的元素交换存储位置temp = judge(begin, end);if(temp = right)/如果交换后正确数码的个数大于或等于原来正确数码的个数temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 2, row-1, column);if( temp_zhi = 1) /进行下一步的移动return 1;exchange(begin, row - 1, column, row , column); /再将其交换回来if(column 0 & biaoji != 1)exchange(begin, row,

10、column - 1, row , column); /将 0 与其左边的元素交换存储位置.temp = judge(begin, end);if(temp = right)temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu ,3, row, column - 1); if(temp_zhi = 1)return 1;exchange(begin, row, column - 1, row , column);if(row num-1 & biaoji != 2)exchange(begin, row + 1, column, row , c

11、olumn); /将 0 与其下面的元素交换存储位置temp = judge(begin, end);if(temp = right)temp_zhi =yidong(begin, end, temp, jishu+1, ji_shu, 0, row+1, column); if(temp_zhi = 1)return 1;exchange(begin, row + 1, column, row , column);if(column num-1 & biaoji != 3)exchange(begin, row, column + 1, row , column); /将 0 与其右边的元素

12、交换存储位置temp = judge(begin, end);if(temp = right)temp_zhi = yidong(begin, end, temp, jishu+1, ji_shu, 1, row, column+1); if(temp_zhi = 1)return 1;exchange(begin, row, column + 1, row , column);return 0;/移动失败，返回0./* 有用户输入待调整的数码矩阵最初状态的数，并将其存入到begin数组中 */void shuru(int beginnum,int blank)int temp, node,

13、zero = 0;for (int i = 0; i num; i+)for(int j = 0; j num; j+)node = 1;printf(请输入第 %d行，第 %d列的元素的值：, i+1, j+1);scanf(%d, &temp);for (int q = 0; q = i & node = 1; q+) /当输入的值有重复的，提示重新输入for (int w = 0; w j; w+)if(temp = beginqw)printf(输入重复，请重新输入n);node = 0;j-;break;if(temp num*num-1)/当输入的值不是在数码的区间范围内时，提示重

14、新输入printf(请输入从 %d到%d的数 n, zero, num*num-1);node = 0;j-;if(node = 1)/如果输入满足条件if(temp = 0) /如果输入的值为零，由blank0记录行号， blank1记录列号blank0 = i;blank1 = j;beginij = temp;/将满足条件的值存储起来int main()intjishu= 0,ji_shu5033;/jishu存储已经遍历过的八数码图形的个数，jishu存储已经遍历过的八数码图形的形状.int row;/存储数字零的行数int column; /存储数字零的列数int beginnumnum, blank2,count=1;int endnumnum = 1, 2, 3, 8, 0, 4, 7, 6, 5; /给最终状态的数码矩阵赋值printf