八数码难题Matlab八数码难题Matlab八数码难题Matlab一、实验目的熟悉和掌握启发式搜索的定义、估价函数和算法过程。利用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）;ify1<zifpanduan(x1）b=x1；z=y1;endend