(完整word版)八数码问题A算法的实现及性能分析

1、1八数码问题A*算法的实现及性能分析计算机科学与技术学院专业 ：计算机科学与技术161210404 杨凯迪2目录一、8数码问题 .3.1.问题描述 . 32. 八数码问题形式化描述 . 33. 解决方案 . 4二、A*算法.4.1. A* 搜索算法一般介绍 . 42. A* 算法的伪代码 . 53. 建立合适的启发式 . 6三、算法实现及性能比较 .7.四、算法性能分析8.五、结论 .9.六、参考文献.1.0.附录.1.0.3、8数码问题1问题描述八数码问题是指这样一种游戏：将分别标有数字1,2,3,，8的八块正 方形数码牌任意地放在一块3X3的数码盘上。放牌时要求不能重叠。于是，在3X3的数

2、码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码 牌与空格交换的原则，不断移动该空格方块以使其和相邻的方块互换，直至达到 所定义的目标状态。空格方块在中间位置时有上、下、左、右4个方向可移动，在四个角落上有2个方向可移动，在其他位置上有3个方向可移动，问题描述如 图1-1所示2八数码问题形式化描述初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字。把3X3的棋盘按从左到右，从上到下的顺序写成一个一维向量。我们可以设定初始状态：后继函数：按照某种规则移动数字得到的新向量。例如：目标测试：新向量是都是目标状态。即是目标状态？路径耗散函数：每次移动代价为1，每执行一条规则

3、后总代价加1。3. 解决方案该问题是一个搜索问题。 它是一种状态到另一种状态的变换。 要解决这个问 题，必须先把问题转化为数字描述。 由于八数码是一个3*3的矩阵， 但在算法中 不实用矩阵， 而是将这个矩阵转化为一个一维数组， 使用这个一维数组来表示八 数码，但是移动时要遵守相关规则。nant t初始状态过渡状态图 1-1 八数码问题执行过程4(1)可用如下形式的规则来表示数字通过空格进行移动：Va1,a2,a3,a4,a5,a6,a7,a8,a9(2)共24条移动规则，对应与每个位置的移动规则。(3)搜索顺序举例：1)优先移动行数小的棋子(数字)2)同一行中优先移动列数大的棋子(4)约束规则

4、：不使离开既定位置的数字数增加 八数码的节点扩展应当遵循棋子的移动规则。 按规则，每一次可以将一个与空格相邻的棋子移动到空格中， 实际上也可以看做空格的相反方向移动。 空格的 移动方向可以是上下左右， 当然不能出边界。 棋子的位置， 也就是保存状态的数 组元素的下标，空格移动后，相应位置发生变化，在不移出边界的条件下，空格 向右，下，左，上移动后，新位置是原位置分别加上1,3，-1，-3。在这里，空格可以用任意数字表示。操作本文用u(up) r(right) d(down) l(left)分别表示空格 的向上向右向下向左四个操作。经分析，8数码问题的搜索策略共有：1.广度优先搜索、2.深度优先

5、搜索、3.有界深度优先搜索、4.最好优先搜索、5.局部择优搜索，等等。其中广度优先 搜索法是可采纳的， 有界深度优先搜索法是不完备的， 最好优先和局部择优搜索 法是启发式搜索法。本实验采用启发式A*搜索算法来实现。二、A*算法1. A* 搜索算法一般介绍A*算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数 评估每次的的决策的价值，决定先尝试哪一种方案，这样可以极大的优化普通的 广度优先搜索。一般来说，从出发点(A)到目的地(B)的最短距离是固定的，我们 可以写一个函数judge()估计A到B的最短距离，如果程序已经尝试着从出 发点A沿着某条路线移动到了C点,那么我们认为这个方案的

6、A B间的估 计距离为A到C实际已经行走了的距离H加上用judge()估计出的C到B的距离。如此，无论我们的程序搜索展开到哪一步， 都会算出一个评估值， 每一次决 策后，将评估值和等待处理的方案一起排序， 然后挑出待处理的各个方案中最有 可能是最短路线的一部分的方案展开到下一步，一直循环到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的路径则结束。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为:5f(n) = g(n) + h(n)这里，f(n)是估价函数，g(n)是起点到终点的最短路径值，h(n)是n到目标的最 断路经的启发值。由于这个f(n)其实是无法预先知道

7、的，所以我们用前面的估价 函数f(n)做近似。g(n)代替g(n)，但g(n)=g(n)才可(大多数情况下都是满足的， 可以不用考虑)，h(n)代替h(n),但h(n)v=h(n)才可。可以证明应用这样的估价 函数是可以找到最短路径的，也就是可采纳的。2. A* 算法的伪代码创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录 已访问过的节点。算起点的估价值;将起点放入OPEN表;while(OPEN!=NULL)从OPEN表中取估价值f最小的节点n;if(n节点=目标节点)break;for(当前节点n的每个子节点X)算X的估价值;if(X in OPEN)if( X的估

8、价值小于OPEN表的X估价值)把n设置为X的父亲;更新OPEN表中的估价值; /取最小路径的估价值if(X inCLOSE) if( X的估价值小于CLOSE表的X估价值)把n设置为X的父亲；将该节点从close表中除去把X节点放入OPEN /取最小路径的估价值if(X not inboth)把n设置为X的父亲；6求X的估价值；并将X插入OPEN表中；/升序排列open/end for将n节点插入CLOSE表中；按照估价值将OPEN表中的节点排序；/实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。/end while(OPEN!=NULL)保存路径，即从终点开始， 每个节点沿着

9、父节点移动直至起点， 这就是你的路 径；3. 建立合适的启发式A*算法有个计算公式f(x) = g(x)+h(x)其中g(x)为从起始状态到当前状态所消耗的步数，h(x)为一个启发值，估算 从当前状态到目标状态所需的步数， 一般h(x)小于等于实际需要步数为好，这样 不会将最优解忽略，因为h(x)和解空间有一些关系，如果h(x)设置的比实际需要 的步数多， 那么解空间就有可能将最优解忽略。举个例子吧，宽度优先搜索就是h(x)=0带来的效果，深度优先搜索就是g(x)=0带来的效果，不过h(x)距离h*(x)实 际需要的步数的程度不能过大，否则h(x)就没有过强的区分能力，算法效率并 不会很高。对

10、一个好的h(x)的评价是：h(x)在h*(n)实际需要的步数的下界之下， 并且尽量接近h*(n)实际需要的步数.那么8数码问题g(x)为经过上下左右移动空格附近的数字来得到新状态所 需步数，h(x)为当前状态与目标状态的距离，就是所有不在目标位置的数字总和， 必然小于h*(x)三、算法实现及性能比较这里通过C+语言来实现各种排序算法（源码见附录），程序运行环境为windows 7，所用编译器为vs2013o实验分别以不同的初始棋盘和相同的目标棋盘为例进行测试。初始数码棋盘1：2 0 3 1 4 6 7 5 8初始数码棋盘2：2 4 3 0 6 8 1 7 5初始数码棋盘3：2 3 7 6 4

11、8 1 0 5初始数码棋盘4：3 2 4 5 0 7 8 1 6初始数码棋盘5：4 0 3 2 6 8 1 7 5初始数码棋盘6：1 4 3 5 7 0 2 6 8初始数码棋盘7：4 6 3 2 8 5 1 0 7目标数码棋盘：1 2 3 4 5 6 7 8 0实验部分结果如图3-1：78-g:ABB法实现/ 5 玛可题D e bu gA垂箕法实现/戯碍间益exe2 4 31 6 B7 5 ft-第11步- :231 t M7 5ft* 第12步-:2 4 31 R t7 5 B第姑步:2 0 31 4 &7 5 B-第曲步-:0 2 314b- 第- :12 34 5b? 0 6第佣

12、步I12 34 5 6? 8 B图 3-1.测试结果四、算法性能分析在测试中我们根据不同的初始数码状态相同的目标数码状态， 产生不同的移 动步骤，并给出了其步数和运行时间（单位ms）。表1为不同的初始数码状态相 同的目标数码状态测试后得到的运行时间数据。 表2为不同的初始数码状态相同 的目标数码状态能否的到正确的步骤与否的数据。 g:ABM法实现/啟玛问题Debu0A星管法实现/戯码问题心e匸回1请输入初始数码棋盘狀态丄代表空格:-第站步一-:步-4 0 t7 5 89初始数据棋盘 1棋盘 2棋盘 3棋盘 4棋盘 5棋盘 6棋盘 7步数51121013017时间（ms）52.531507.69

13、18220134.4202815.83表 1 步数和运行时间（单位 ms）初始数据、棋盘 1棋盘 2棋盘 3棋盘 4棋盘 5棋盘 6棋盘 7正确与否TTTFTFT表 2 能否得到正确步骤为了直观起见，根据实验数据画出不同的初始数码状态相同的目标数码状态 下时间随步数的变化趋势图如图3-2所示：图 3-2 时间随步数的变化趋势图根据实验数据表2,我们可得到该算法得到正确步骤路径的概率为：71.42%五、结论最后我们得出结论：时间性能上，算法所需时间随步数的增加而逐渐呈增加趋势，但并不是线性增长。部分时10间不随移动步数变化该算法能得到正确的解概率约为71.42%六、参考文献1Artificial

14、 intelligence :;a modern approach人工智能:一种现代方法 作者：Russell, Stuart J.出版社：清华大学出版社附录#include #include #include #include #include using namespacestd;struct nodeint a33;/ 存放矩阵int father;/ 父节点的位置int gone;/ 是否遍历过 ,1 为是 ,0 为否int fn;/ 评价函数的值int x,y;/ 空格的坐标int deep;/ 节点深度;vector store; / 存放路径节点int mx4=-1,0,1,0;

15、bool check( int num) / 判断 storenum 节点与目标节点是否相同 , 目标节点储存在 store0 中int my4=0,-1,0,1;/ 上下左右移int top;/ 当前节点在 store 中的位置11for ( int i=0;i3;i+)for (int j=0;j3;j+)if (storenum.aij!=store0.aij) return false ;return true ;bool search( int num)/ 判断 storenum 节点是否已经扩展过 , 没有扩展返回 trueint pre=storenum.father; /pre

16、 指向 storenum 的父节点位置bool test= true ;while (!pre) / 循环直到 pre 为 0, 既初始节点 for (int i=0;i3;i+)for ( int j=0;j3;j+)if (storepre.aij!=storenum.aij) test= false ; break ;if (test= false ) break ;if (test= true ) return falsepre=storepre.father;return true ;coutendl;cout * 数码移动步骤 * =0;m-)cout- 第vvmm步-:endl;

17、for (int i=0;i3;i+)for (int j=0;j3;j+) coutstoretempm.aijcoutendl;mm+; coutendl;cout 所需步数为 : storenum.deependl; return ;/pre 继续指向 storepre 父节点位置void print( int num)vector temp;int pre=storenum.father;temp.push_back(num);while(pre!=0) temp.push_back(pre); pre=storepre.father;/ 打印路径 ,storenum 为目标节点/ 存

18、放路径/ 从目标节点回溯到初始节点12int get_fn( int num)int fn_temp=0; bool test=true ;for ( int i=0;i3;i+)/ 返回 storenum 的评价函数值/ 评价函数值/ 当找到一个值后 , 计算这个值位置与目标位置的距离差 ,test 置为 false 后继续寻找下一个值for (intj=0;j3;j+) test= true ;for (int k=0;k3;k+)for (int l=0;l3;l+)if (storenum.x!=i|storenum.y!=j)&storenum.aij=store0.akl)

19、 /寻值时排除空格位fn_temp=fn_temp+abs(i-k)+abs(j-l);test= false ;if (test= false ) break ;if (test= false ) break ;fn_temp=fn_temp+storenum.deep; / 加上节点深度 return fn_temp;void kongxy( int num) / 获得空格坐标for ( int i=0;i3;i+) for (int j=0;j3;j+)if (storenum.aij=0) storenum.x=i; storenum.y=j;returnint main()cout

20、- A*算法解决 8 数码问题 - endl;while (true )store.clear();/ 清空 storevector open;/建立 open 表int i,j,m,n,f;int min;/storemin储存 fn 值最小的节点int temp;bool test;top=1;/ 当前节点在 store 的位置,初始节点在 store1int target9;int begin9;/ 储存初始状态和目标状态 , 用于判断奇偶int t1=0,t2=0;/ 初始状态和目标状态的奇偶序数13node node_temp;store.push_back(node_temp);s

21、tore.push_back(node_temp);/用于创建 store0和 store1,以便下面使用coutvv请输入初始数码棋盘状态,0 代表空格：endl; /输入初始状态，储存在 store1 中test= false ;while (test= false )f=0;for (i=0;i3;i+)for (j=0;jtemp;store1.aij=temp; beginf+=temp;test= true ;for (i=0;i8;i+)/ 检查是否有重复输入 , 若有则重新输入for (j=i+1;j9;j+) if (begini=beginj)test= false ;br

22、eak;14if (test= false ) break ;if (test= false ) cout 输入重复 , 请重新输入 : endl;kongxy(1); / 找出空格的坐标cout 请输入目标数码棋盘状态 ,0 代表空格： endl; / 输入目标状态 ,储存在 store0 中test= false ;while (test= false )f=0;for (i=0;i3;i+)for (j=0;jtemp; store0.aij=temp; targetf+=temp;test= true ;for (i=0;i8;i+) / 检查是否有重复输入 , 若有则重新输入 for

23、 (j=i+1;j9;j+)if (targeti=targetj)test= false ; break ;if (test= false ) break ;if (test= false ) cout输入重复，请重新输入:endl; continue ;/ 若重复 , 重新输入for (i=0;i9;i+)/ 检查目标状态与初始状态是否匹配test= false ;for (j=0;j9;j+)if (begini=targetj)test= true ;break;15if (test= false ) break ;if (test= false ) cout 输入与初始状态不匹配 ,

24、 请重新输入 : endl;for (i=1;i=0;j+)if (beginibegini-j) if (begini-j!=0) t1+;for (i=1;i=0;j+) if (targetitargeti-j)if (targeti-j!=0) t2+;if (!(t1%2=t2%2)cout 无法找到路径 . endl; coutendl;/system(pause);/return 0; continue ;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);Quer

25、yPerformanceCounter(&Count1); / 获取时间 Count1 double d;store1.fn=get_fn(1);store1.father=0;store1.gone=0;store1.deep=0;/ 初始化参数/ 初始节点的父节点为 0+116if (check(1)print(1);/system(pause);/return 0;coutendl;continue ;/ 判断初始状态与目标状态是否相同open.push_back(1);while(!open.empty() if(check(top)/当 open 表不为空时，开始寻找路径break ;/把初始状态在 store 中的位置数压入 open 表中min=top;int i_min=0;/遍历 open 表中元素，找岀 store 中 fn 值最小的节for (i=0;iopen.size();i+)点八、if(storeopeni.fn=storemin.fn&storeopeni.gone=0) min=openi; i_min=i;storemin.gone=1;open.erase(open.begin()