八数码难题--Matlab

一、实验目的1、熟悉和掌握启发式搜索的定义、估价函数和算法过程。2、利用A*算法求解N数码难题，理解求解流程和搜索顺序。二、实验内容以八数码为例实现A或A*算法。1、分析算法中的OPEN表CLOSE表的生成过程。1）建立一个队列，计算初始结点的估价函数f，并将初始结点入队，设置队列头和尾指针。2）取出队列头（队列头指针所指）的结点，如果该结点是目标结点，则输出路径，程序结束。否则对结点进行扩展。3）检查扩展出的新结点是否与队列中的结点重复，若与不能再扩展的结点重复（位于队列头指针之前），则将它抛弃；若新结点与待扩展的结点重复（位于队列头指针之后），则比较两个结点的估价函数中g的大小，保留较小g值的结点。跳至第五步。4）如果扩展出的新结点与队列中的结点不重复，则按照它的估价函数f大小将它插入队列中的头结点后待扩展结点的适当位置，使它们按从小到大的顺序排列，最后更新队列尾指针。5）如果队列头的结点还可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步。2、分析估价函数对搜索算法的影响。3、分析启发式搜索算法的特点。广度优先搜索和双向广度优先搜索都属于盲目搜索，这在状态空间不大的情况下是很合适的算法，可是当状态空间十分庞大时，它们的效率实在太低，往往都是在搜索了大量无关的状态结点后才碰到解答，甚至更本不能碰到解答。搜索是一种试探性的查寻过程，为了减少搜索的盲目性引，增加试探的准确性，就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估，从中选择最好、可能容易到达目标的位置，再从这个位置向前进行搜索，这样就可以在搜索中省略大量无关的结点，提高了效率。启发式函数选取为：f*(n)=g*(n)+h*(n)其中：g*(n)是搜索树中节点n的深度h*(n)用来计算对应于节点n的数据中错放的棋子个数。三、实验结果四、程序function[a1,b1]=shang(a)[x,y]=find(a==0);a1=a;a1(x,y)=a(x-1,y);a1(x-1,y)=0;b1=zhao(a1);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function[a1,b1]=xia(a)[x,y]=find(a==0);a1=a;a1(x,y)=a(x+1,y);a1(x+1,y)=0;b1=zhao(a1);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function[a1,b1]=zuo(a)[x,y]=find(a==0);a1=a;a1(x,y)=a(x,y-1);a1(x,y-1)=0;b1=zhao(a1);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function[a1,b1]=you(a)[x,y]=find(a==0);a1=a;a1(x,y)=a(x,y+1);a1(x,y+1)=0;b1=zhao(a1);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%functionz=panduan(a)globalE;globalI;I=2;[x,y]=size(E);z=1;fori=1:yb=E{i};v=(b-a).^2;ifsum(sum(v))==0z=0;break;endend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%functiony=zhao(a)wan=[123;804;765];y=0;b=a-wan;fori=1:3forj=1:3ifb(i,j)~=0y=y+1;endendend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%globalEglobalIa=[283;104;765];b=[123;804;765];I=1;E(1)={a};fori=2:20q=b-E{i};ifsum(sum(q.^2))E(i)={kaka(E{i-1})};celldisp(E(i))elsebreak;endend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%function[a1]=kaka(a)globalI;globalE;c=[283;104;765];E(1)={c};[x,y]=find(a==0);z=9;ifx==1ify==1[x1,y1]=xia(a);ify1zifpanduan(x1)b=x1;z=y1;endend[x2,y2]=you(a);ify2zifpanduan(x2)b=x2;z=y2;endenda1=b;endify==2[x1,y1]=xia(a);ify1zifpanduan(x1)b=x1;z=y1;endend[x2,y2]=zuo(a);ify2zifpanduan(x2)b=x2;z=y2;endend[x3,y3]=you(a);ify3zifpanduan(x3)b=x3;z=y3;endenda1=b;endify==3[x1,y1]=xia(a);ify1zifpanduan(x1)b=x1;z=y1;endend[x2,y2]=zuo(a);ify2zifpanduan(x2)b=x2;z=y2;endenda1=b;endendifx==2ify==1[x1,y1]=shang(a);ify1zifpanduan(x1)b=x1;z=y1;endend[x2,y2]=xia(a);ify2zifpanduan(x2)b=x2;z=y2;endend[x3,y3]=you(a);ify3zifpanduan(x3)b=x3;z=y3;endenda1=b;endify==2[x1,y1]=shang(a);ify1zifpanduan(x1);b=x1;z=y1;endend[x2,y2]=xia(a);ify2zifpanduan(x2);b=x2;z=y2;endend[x3,y3]=zuo(a);ify3zifpanduan(x3);b=x3;z=y3;endend[x4,y4]=you(a);ify4z;ifpanduan(x4)b=x4;z=y4;endenda1=b;endify==3[x1,y1]=shang(a);ify1zifpanduan(x1)b=x1;z=y1;endend[x2,y2]=xia(a);ify2zifpanduan(x2)b=x2;z=y2;endend[x3,y3]=zuo(a);ify3zifpanduan(x3)b=x3;z=y3;endenda1=b;endendifx==3ify==1[x1,y1]=shang(a);ify1zifpanduan(x1)b=x1;z=y1;endend[x4,y4]=you(a);ify4z;ifpanduan(x4)b=x4;z=y4;endenda1=b;endify==2[x1,y1]=shang(a);ify1zifpanduan(x1)b=x1;z=y1;endend[x3,y3]=zuo(a);ify3zifpanduan(x3)b=x3;z=y3;endend[x4,y4]=you(a);ify4z;ifpanduan(x4)b=x4;z=y4;endenda1=b;endify==3[x1,y1]=shang(a);ify1zifpanduan(x1)b=x1;z=y1;endend[x3,y3]=zuo(a);ify3zifpanduan(x3)b=x3;z=y3;endenda1=b;endendE(I)={a1};五、实验结论1、启发式搜索算法A*流程图和算法框图。算法框图：算法方法：利用MATLAB软件，因为MATLAB是基于矩阵运算的，八数码可以看做是一个3*3的矩阵，将八数码中的空位可看成矩阵的为0代替，已进行矩阵之间的运算，首先建立了4个函数，这4个函数应有在矩阵的上，下，左，右的变换，然后经过变换，输出两个值，一个为变换后的矩阵，一个为变化后的放错位置的数值，然后利用kaka函数，分别分9中情况来条用这4个函数，来输出下一层的矩阵并判断最小放错位置的数值，然后将其矩阵放入全局变量E中的元胞数组中，记录下其实的矩阵，然后再每次生成下一层矩阵时，利用panduan函数来判断生成的矩阵是否和E元胞数组中的矩阵相同，防止出现矩阵变化中的内部死循环。然后利用celldisp函数输出E元胞数组中的矩阵，即为起始棋局到目标棋局的路径。2、分析估价函数的值对搜索算法速度的影响。考虑到八数码问题的特点，在本实验中使用A*算法求解。A*搜索是一种效的搜索算法，它把到达节点的耗散g(n)和从该节点到目标节点的消耗h(n)结合起来对节点进行评价：f(n)=g(n)+h(n)。当h(n)是可采纳时，使用Tree-Search的A*算法将是最优的。3、根据A*算法分析启发式搜索的特点。启发式搜索是一种试探性的查寻过程，为了减少搜索的盲目性引，增加试探的准确性，就要采用启发式搜索了。所谓启发式搜索就是在搜索中要对每一个搜索的位置进行评估，从中选择最好、可能容易到达目标的位置，再从这个位置向前进行搜索，这样就可以在搜索中省略大量无关的结点，提高了效率。