2022年八数码问题A算法的实现及性能分析 .pdf

1 八数码问题A* 算法的实现及性能分析计算机科学与技术学院专业：计算机科学与技术161210404 杨凯迪名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - 2 目录一、8 数码问题 . 31.问题描述 . 32. 八数码问题形式化描述. 33. 解决方案 . 4二、A* 算法. 41. A* 搜索算法一般介绍. 42. A* 算法的伪代码. 53. 建立合适的启发式. 6三、算法实现及性能比较 . 7四、算法性能分析 . 8五、结论 . 9六、参考文献 . 10附录 . 10名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - 3 一、 8 数码问题1.问题描述八数码问题是指这样一种游戏：将分别标有数字1，2，3，8 的八块正方形数码牌任意地放在一块33 的数码盘上。放牌时要求不能重叠。于是，在33 的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则， 不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右4 个方向可移动，在四个角落上有 2 个方向可移动， 在其他位置上有 3 个方向可移动， 问题描述如图 1-1 所示初始状态过渡状态最终状态图 1-1 八数码问题执行过程2. 八数码问题形式化描述初始状态：初始状态向量：规定向量中各分量对应的位置，各位置上的数字。把33的棋盘按从左到右，从上到下的顺序写成一个一维向量。 我们可以设定初始状态： 后继函数：按照某种规则移动数字得到的新向量。例如： 目标测试：新向量是都是目标状态。即 是目标状态？路径耗散函数：每次移动代价为 1，每执行一条规则后总代价加1。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 17 页 - - - - - - - - - 4 3. 解决方案该问题是一个搜索问题。 它是一种状态到另一种状态的变换。要解决这个问题，必须先把问题转化为数字描述。由于八数码是一个3*3 的矩阵，但在算法中不实用矩阵， 而是将这个矩阵转化为一个一维数组，使用这个一维数组来表示八数码，但是移动时要遵守相关规则。(1) 可用如下形式的规则来表示数字通过空格进行移动： (2)共 24 条移动规则，对应与每个位置的移动规则。(3)搜索顺序举例：1) 优先移动行数小的棋子 (数字) 2) 同一行中优先移动列数大的棋子(4)约束规则：不使离开既定位置的数字数增加八数码的节点扩展应当遵循棋子的移动规则。按规则，每一次可以将一个与空格相邻的棋子移动到空格中， 实际上也可以看做空格的相反方向移动。空格的移动方向可以是上下左右， 当然不能出边界。 棋子的位置， 也就是保存状态的数组元素的下标，空格移动后，相应位置发生变化，在不移出边界的条件下，空格向右，下，左，上移动后，新位置是原位置分别加上1,3，-1，-3。在这里，空格可以用任意数字表示。操作本文用u(up) r(right) d(down) l(left) 分别表示空格的向上向右向下向左四个操作。经分析， 8 数码问题的搜索策略共有：1.广度优先搜索、 2.深度优先搜索、3.有界深度优先搜索、 4.最好优先搜索、 5.局部择优搜索，等等。其中广度优先搜索法是可采纳的， 有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。本实验采用启发式A* 搜索算法来实现。二、 A* 算法1. A*搜索算法一般介绍A* 算法实际是一种启发式搜索，所谓启发式搜索，就是利用一个估价函数评估每次的的决策的价值， 决定先尝试哪一种方案， 这样可以极大的优化普通的广度优先搜索。一般来说，从出发点(A)到目的地 (B)的最短距离是固定的，我们可以写一个函数judge() 估计 A 到 B 的最短距离，如果程序已经尝试着从出发点 A 沿着某条路线移动到了C 点, 那么我们认为这个方案的A B 间的估名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - 5 计距离为A 到 C 实际已经行走了的距离H 加上用judge() 估计出的C 到B 的距离。如此，无论我们的程序搜索展开到哪一步，都会算出一个评估值， 每一次决策后，将评估值和等待处理的方案一起排序，然后挑出待处理的各个方案中最有可能是最短路线的一部分的方案展开到下一步，一直循环到对象移动到目的地，或所有方案都尝试过却没有找到一条通向目的地的路径则结束。A*算法是一个可采纳的最好优先算法。A* 算法的估价函数可表示为：f(n) = g(n) + h(n) 这里， f(n)是估价函数， g(n)是起点到终点的最短路径值，h(n)是 n 到目标的最断路经的启发值。 由于这个 f(n)其实是无法预先知道的， 所以我们用前面的估价函数 f(n)做近似。g(n)代替 g(n)，但 g(n)=g(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替 h(n)，但 h(n)=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 的估价值小于 OPEN 表的 X 估价值 ) 把 n 设置为 X 的父亲 ; 更新 OPEN 表中的估价值 ; /取最小路径的估价值 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - 6 if(X inCLOSE) if( X 的估价值小于 CLOSE 表的 X 估价值 ) 把 n 设置为 X 的父亲 ; 将该节点从 close表中除去把 X 节点放入 OPEN /取最小路径的估价值 if(X not inboth) 把 n 设置为 X 的父亲 ; 求 X 的估价值 ; 并将 X 插入 OPEN 表中; /升序排列 open /end for 将 n 节点插入 CLOSE 表中; 按照估价值将 OPEN表中的节点排序 ; /实际上是比较 OPEN 表内节点 f的大小，从最小路径的节点向下进行。/end while(OPEN!=NULL) 保存路径，即从终点开始， 每个节点沿着父节点移动直至起点，这就是你的路径；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)就没有过强的区分能力，算法效率并不会很高。对一个好的 h(x)的评价是：h(x)在 h*(n)实际需要的步数 的下界之下，并且尽量接近 h*(n) 实际需要的步数 . 那么 8 数码问题 g(x) 为经过上下左右移动空格附近的数字来得到新状态所需步数，h(x)为当前状态与目标状态的距离， 就是所有不在目标位置的数字总和，必然小于 h*(x) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 17 页 - - - - - - - - - 7 三、算法实现及性能比较这里通过c+语言来实现各种排序算法（源码见附录），程序运行环境为windows 7，所用编译器为vs2013。实验分别以不同的初始棋盘和相同的目标棋盘为例进行测试。初始数码棋盘 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 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：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - 8 图 3-1.测试结果四、算法性能分析在测试中我们根据不同的初始数码状态相同的目标数码状态，产生不同的移动步骤，并给出了其步数和运行时间（单位ms） 。表 1 为不同的初始数码状态相同的目标数码状态测试后得到的运行时间数据。表 2 为不同的初始数码状态相同的目标数码状态能否的到正确的步骤与否的数据。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - 9 初始数据棋盘 1 棋盘 2 棋盘 3 棋盘 4 棋盘 5 棋盘 6 棋盘 7 步数5 11 21 0 13 0 17 时间 (ms) 52.531 507.69 1822 0 134.42 0 2815.83 表 1 步数和运行时间（单位ms）初始数据棋盘 1 棋盘 2 棋盘 3 棋盘 4 棋盘 5 棋盘 6 棋盘 7 正确与否T T T F T F T 表 2 能否得到正确步骤为了直观起见， 根据实验数据画出不同的初始数码状态相同的目标数码状态下时间随步数的变化趋势图如图3-2 所示：46810121416182022050010001500200025003000Time(ms)Steps Time(ms)图 3-2 时间随步数的变化趋势图根据实验数据表 2， 我们可得到该算法得到正确步骤路径的概率为：71.42%。五、结论最后我们得出结论：时间性能上，算法所需时间随步数的增加而逐渐呈增加趋势，但并不是线性增长。部分时名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - 10 间不随移动步数变化。该算法能得到正确的解概率约为71.42% 六、参考文献1Artificial intelligence :;a modern approach 人工智能: 一种现代方法 作者：Russell, Stuart J. 出版社：清华大学出版社附录#include #include #include #include #include usingnamespace std; struct node int a33; / 存放矩阵int father; / 父节点的位置int gone; / 是否遍历过 ,1 为是,0 为否int fn; / 评价函数的值int x,y; / 空格的坐标int deep; / 节点深度; vector store; / 存放路径节点int mx4=-1,0,1,0; int my4=0,-1,0,1; / 上下左右移动数组int top; / 当前节点在 store 中的位置bool check( int num) / 判断 storenum 节点与目标节点是否相同, 目标节点储存在 store0中名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - 11 for ( int i=0;i3;i+) for ( int j=0;j3;j+) if (storenum.aij!=store0.aij) returnfalse ; returntrue ; bool search(int num) / 判断storenum 节点是否已经扩展过 , 没有扩展返回 true int pre=storenum.father; /pre 指向 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 ) returnfalse ; pre=storepre.father; /pre 继续指向 storepre父节点位置 returntrue ; void print(int num) / 打印路径 ,storenum为目标节点 vector temp; / 存放路径int pre=storenum.father; temp.push_back(num); while (pre!=0) / 从目标节点回溯到初始节点temp.push_back(pre); pre=storepre.father; coutendl; cout *数码移动步骤 *=0;m-) cout-第 mm 步- ：endl; for ( int i=0;i3;i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 17 页 - - - - - - - - - 12 for ( int j=0;j3;j+) coutstoretempm.aij ; coutendl; mm+; coutendl; cout 所需步数为 : storenum.deependl; return ; int get_fn(int num) / 返回storenum 的评价函数值 int fn_temp=0; / 评价函数值bool test= true ; for ( int i=0;i3;i+) / 当找到一个值后 , 计算这个值位置与目标位置的距离差,test置为false 后继续寻找下一个值for ( int j=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) /寻值时排除空格位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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - 13 return ; int main() cout -A*算法解决 8数码问题 -endl; while ( true ) store.clear(); / 清空 store vector open; / 建立 open表int i,j,m,n,f; int min; /storemin储存fn 值最小的节点int temp; bool test; top=1; / 当前节点在 store 的位置 , 初始节点在 store1 int target9; int begin9; / 储存初始状态和目标状态, 用于判断奇偶int t1=0,t2=0; / 初始状态和目标状态的奇偶序数node node_temp; store.push_back(node_temp); store.push_back(node_temp); / 用于创建 store0和store1,以便下面使用cout 请输入初始数码棋盘状态,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 ; break ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 17 页 - - - - - - - - - 14 if (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 (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 ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 17 页 - - - - - - - - - 15 if (test= false ) break; if (test= false ) cout 输入与初始状态不匹配, 请重新输入 : 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); QueryPerformanceCounter(&Count1);/ 获取时间 Count1double d; store1.father=0; / 初始化参数store1.gone=0; store1.deep=0; / 初始节点的父节点为 0 store1.fn=get_fn(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - 16 if (check(1) / 判断初始状态与目标状态是否相同print(1); /system(pause);/return 0;coutendl; continue ; open.push_back(1); / 把初始状态在 store 中的位置数压入 open表中while (!open.empty() / 当open表不为空时 , 开始寻找路径if (check(top) break ; min=top; int i_min=0; for (i=0;iopen.size();i+) / 遍历open表中元素 , 找出store 中fn 值最小的节点if (storeopeni.fn=storemin.fn&storeopeni.gone=0) min=openi; i_min=i; storemin.gone=1; open.erase(open.begin()+i_min); / 把最小节点标记遍历过, 并从 open表中删除m=storemin.x; n=storemin.y; / 空格坐标for (f=0;f=0&i=0&j=2) / 当变换后的空格坐标在矩阵中时, 开始移动top+; store.push_back(storemin); / 把storemin压入store 中成为新增节点, 位置为 storetop storetop.father=min; / 新增节点的父节点为 min storetop.gone=0; / 新增节点未被访问storetop.deep=storemin.deep+1; / 新增节点的深度为父节点深度+1 temp=storetop.amn; / 交换空格与相邻数字storetop.amn=storetop.aij; storetop.aij=temp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - 17 storetop.x=i; / 移动后的空格坐标storetop.y=j; storetop.fn=get_fn(top); / 移动后的 fn 值open.push_back(top); / 把top压入 open表中if (check(top) / 检查是否到达目标print(top); /system(pause);/return 0;break ; if (search(top)=false ) / 检查新增节点是否被访问过, 若访问过 ,则删除此节点top-; store.pop_back(); open.pop_back(); QueryPerformanceCounter(&Count2);/ 获取时间 Count2d=(double )(Count2.QuadPart-Count1.QuadPart)/(double )Freg.QuadPart*1000.0;/ 计算时间差， d的单位为 ms.cout 算法时间为为 d ms. endl; coutendl; return 0; system( pause ); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -