八數(shù)碼難題Matlab

1、一、實驗目的1、 熟悉和掌握啟發(fā)式搜索的定義、估價函數(shù)和算法過程。2、 利用A*算法求解N數(shù)碼難題，理解求解流程和搜索順序。二、實驗內(nèi)容以八數(shù)碼為例實現(xiàn)A或A*算法 。1、分析算法中的OPEN表CLOSE表的生成過程。1）建立一個隊列，計算初始結(jié)點的估價函數(shù)f，并將初始結(jié)點入隊，設置隊列頭和尾指針。2）取出隊列頭（隊列頭指針所指）的結(jié)點，如果該結(jié)點是目標結(jié)點，則輸出路徑，程序結(jié)束。否則對結(jié)點進行擴展。 3）檢查擴展出的新結(jié)點是否與隊列中的結(jié)點重復，若與不能再擴展的結(jié)點重復（位于隊列頭指針之前），則將它拋棄；若新結(jié)點與待擴展的結(jié)點重復（位于隊列頭指針之后），則比較兩個結(jié)點的估價函數(shù)中g(shù)的大小，保

2、留較小g值的結(jié)點。跳至第五步。4）如果擴展出的新結(jié)點與隊列中的結(jié)點不重復，則按照它的估價函數(shù)f大小將它插入隊列中的頭結(jié)點后待擴展結(jié)點的適當位置，使它們按從小到大的順序排列，最后更新隊列尾指針。5）如果隊列頭的結(jié)點還可以擴展，直接返回第二步。否則將隊列頭指針指向下一結(jié)點，再返回第二步。2、分析估價函數(shù)對搜索算法的影響。3、分析啟發(fā)式搜索算法的特點。 廣度優(yōu)先搜索和雙向廣度優(yōu)先搜索都屬于盲目搜索，這在狀態(tài)空間不大的情況下是很合適的算法，可是當狀態(tài)空間十分龐大時，它們的效率實在太低，往往都是在搜索了大量無關(guān)的狀態(tài)結(jié)點后才碰到解答，甚至更本不能碰到解答。搜索是一種試探性的查尋過程，為了減少搜索的盲目性

3、引，增加試探的準確性，就要采用啟發(fā)式搜索了。所謂啟發(fā)式搜索就是在搜索中要對每一個搜索的位置進行評估，從中選擇最好、可能容易到達目標的位置，再從這個位置向前進行搜索，這樣就可以在搜索中省略大量無關(guān)的結(jié)點，提高了效率。啟發(fā)式函數(shù)選取為：f*(n)=g*(n)+ h*(n)其中：g*(n)是搜索樹中節(jié)點n的深度h*(n)用來計算對應于節(jié)點n的數(shù)據(jù)中錯放的棋子個數(shù)。三、實驗結(jié)果四、程序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=

4、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);%function z=panduan(a)global E;global I;I=2;x,y=size(E);z=1;for i=1:y b=Ei; v=(b

5、-a).2; if sum(sum(v)=0 z=0; break; endend%function y=zhao(a)wan=1 2 3;8 0 4;7 6 5;y=0;b=a-wan;for i=1:3 for j=1:3 if b(i,j)=0 y=y+1; end endend%global Eglobal Ia=2 8 3;1 0 4;7 6 5;b=1 2 3;8 0 4;7 6 5;I=1;E(1)=a;for i=2:20 q=b-Ei; if sum(sum(q.2) E(i)=kaka(Ei-1); celldisp(E(i) else break; endend%func

6、tion a1=kaka(a)global I;global E;c=2 8 3;1 0 4;7 6 5;E(1)=c;x,y=find(a=0);z=9;if x=1 if y=1 x1,y1=xia(a); if y1z if panduan(x1) b=x1; z=y1; end end x2,y2=you(a); if y2z if panduan(x2) b=x2; z=y2; end end a1=b; end if y=2 x1,y1=xia(a); if y1z if panduan(x1) b=x1; z=y1; end end x2,y2=zuo(a); if y2z if

7、 panduan(x2) b=x2; z=y2; end end x3,y3=you(a); if y3z if panduan(x3) b=x3; z=y3; end end a1=b; end if y=3 x1,y1=xia(a); if y1z if panduan(x1) b=x1; z=y1; end end x2,y2=zuo(a); if y2z if panduan(x2) b=x2; z=y2; end end a1=b; endendif x=2 if y=1 x1,y1=shang(a); if y1z if panduan(x1) b=x1; z=y1; end en

8、d x2,y2=xia(a); if y2z if panduan(x2) b=x2; z=y2; end end x3,y3=you(a); if y3z if panduan(x3) b=x3; z=y3; end end a1=b; end if y=2 x1,y1=shang(a); if y1z if panduan(x1); b=x1; z=y1; end end x2,y2=xia(a); if y2z if panduan(x2); b=x2; z=y2; end end x3,y3=zuo(a); if y3z if panduan(x3); b=x3; z=y3; end

9、end x4,y4=you(a); if y4z; if panduan(x4) b=x4; z=y4; end end a1=b; end if y=3 x1,y1=shang(a); if y1z if panduan(x1) b=x1; z=y1; end end x2,y2=xia(a); if y2z if panduan(x2) b=x2; z=y2; end end x3,y3=zuo(a); if y3z if panduan(x3) b=x3; z=y3; end end a1=b; endendif x=3 if y=1 x1,y1=shang(a); if y1z if

10、panduan(x1) b=x1; z=y1; end end x4,y4=you(a); if y4z; if panduan(x4) b=x4; z=y4; end end a1=b; end if y=2 x1,y1=shang(a); if y1z if panduan(x1) b=x1; z=y1; end end x3,y3=zuo(a); if y3z if panduan(x3) b=x3; z=y3; end end x4,y4=you(a); if y4z; if panduan(x4) b=x4; z=y4; end end a1=b; end if y=3 x1,y1=

11、shang(a); if y1z if panduan(x1) b=x1; z=y1; end end x3,y3=zuo(a); if y3z if panduan(x3) b=x3; z=y3; end end a1=b; endendE(I)=a1;五、實驗結(jié)論1、啟發(fā)式搜索算法A*流程圖和算法框圖。算法框圖：算法方法： 利用MATLAB軟件，因為MATLAB是基于矩陣運算的，八數(shù)碼可以看做是一個3*3的矩陣，將八數(shù)碼中的空位可看成矩陣的為0代替，已進行矩陣之間的運算，首先建立了4個函數(shù)，這4個函數(shù)應有在矩陣的上，下，左，右的變換，然后經(jīng)過變換，輸出兩個值，一個為變換后的矩陣，一個為變化

12、后的放錯位置的數(shù)值，然后利用kaka函數(shù)，分別分9中情況來條用這4個函數(shù)，來輸出下一層的矩陣并判斷最小放錯位置的數(shù)值，然后將其矩陣放入全局變量E中的元胞數(shù)組中，記錄下其實的矩陣，然后再每次生成下一層矩陣時，利用panduan函數(shù)來判斷生成的矩陣是否和E元胞數(shù)組中的矩陣相同，防止出現(xiàn)矩陣變化中的內(nèi)部死循環(huán)。然后利用celldisp函數(shù)輸出E元胞數(shù)組中的矩陣，即為起始棋局到目標棋局的路徑。2、分析估價函數(shù)的值對搜索算法速度的影響。考慮到八數(shù)碼問題的特點，在本實驗中使用A*算法求解。A*搜索是一種效的搜索算法，它把到達節(jié)點的耗散g(n)和從該節(jié)點到目標節(jié)點的消耗h(n)結(jié)合起來對節(jié)點進行評價：f(n)=g(n)+h(n