深度寬度優(yōu)先搜索八數(shù)碼

1、八數(shù)碼問(wèn)題具體思路：寬度優(yōu)先算法實(shí)現(xiàn)過(guò)程（1）把起始節(jié)點(diǎn)放到OPEN表中；（2）如果OPEN是個(gè)空表，則沒(méi)有解，失敗退出；否則繼續(xù)；（3）把第一個(gè)節(jié)點(diǎn)從OPEN表中移除，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中;（4）擴(kuò)展節(jié)點(diǎn)n。如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向（2）的指針；否則轉(zhuǎn)向（2）o（5）把n的所有后繼結(jié)點(diǎn)放到OPEN表末端，并提供從這些后繼結(jié)點(diǎn)回到n（6）如果n的任意一個(gè)后繼結(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出，深度優(yōu)先實(shí)現(xiàn)過(guò)程（1）把起始節(jié)點(diǎn)S放入未擴(kuò)展節(jié)點(diǎn)OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解；（2）如果OPEN為一空表，則失敗退出；（3）把第一個(gè)節(jié)點(diǎn)從OPEN表移到CLOS

2、ED表；（4）如果節(jié)點(diǎn)n的深度等于最大深度，則轉(zhuǎn)向（2）；（5）擴(kuò)展節(jié)點(diǎn)n,產(chǎn)生其全部后裔，并把它們放入OPEN表的前頭。如果沒(méi)有后裔，則轉(zhuǎn)向（2）；（6）如果后繼結(jié)點(diǎn)中有任一個(gè)目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解，成功退出，否則轉(zhuǎn)向（2）o方法一：用C語(yǔ)言實(shí)現(xiàn)include include ttincludeOtypedef long UINT64;typedef struct(char x; =0;move0. y=l;movel. x=0;movel.y=3;return 2;case 1:move0. x=l;move0. y=0;movel. x=l;movel. y=2;move 2. x=l;

3、move 2. y=4;return 3;case 2: move0. x=2;move0. y=l;movel. x=2;movel. y=5;return 2;case 3:move 0. x=3;move0. y=0;movel. x=3;movel. y=6; move 2.x=3: move 2. y=4;return 3;case 4:move 0. x=4;move0. y=l;movel. x=4;movel.y=3;move 2. x=4;move2. y=5;move 3.x=4;move 3. y=7;return 4;case 5:move0. x=5;move0. y

4、=2;movel. x=5;movel. y=4;move 2.x=5;move 2. y=8;return 3;case 6:move 0. x=6;move0. y=3;movel. x=6;movel. y=7;return 2;case 7:move0. x=7;move0. y=6;movel. x=7;movel. y=4;move 2. x=7;move 2. y=8;return 3;case 8:move 0. x=8;move0. y=5;movel. x=8;movel. y=7;return 2;return 0;long mov（EP_NODE *nl, EP_MOV

5、E *mv, EP_NODE *n2）=node-v;m_ar r. prev=node-prev;m_arr. small=NULL;m_arr. big=NULL;if （node-v q-v） q-big= &m_arr;else if （node-v small= &m_arr;return 1;/*得到節(jié)點(diǎn)所在深度*/long get_node_depth(EP_NODE *node) long d=0;while(node-prev)( d+;node=node-prev;return d;/*返回值：成功一返回搜索節(jié)點(diǎn)數(shù)，節(jié)點(diǎn)數(shù)不夠一 (-1),無(wú)解一 (-2)*/long bf

6、s_search(char *begin, char *end) long h=0, r=l, c, i, j;EP_NODE l_end, node, *pnode;EP_MOVE mv4;TRANS (end,;m_ar0. prev=NULL;m root=m ar;m root-smal1=NULL;m_root-b i g=NULL;while(h r) & (r MAX_NODE - 4)c=move_gen(&m_arh, mv);for(i=0; i prev;m_depth=j;return r;if(add_node(&node, r) r+; . %9d/%d %d，h,

7、 r, get_node_depth(&m_arh);if(h = r) return -2; elsereturn T; long check_input (char *s, char a, long r) long i;for(i=0; i r; i+) if(si = a - 0 x30) return 0; return 1;long check_possible(char *begin, char *end) char fs;long fl=0, f2=0;long i, j；for(i=0; i NUM; i+)( fs=0;for(j=0; j i; j+)(if(begini

8、!= 0) & (beginj != 0) & (beginfj begini) fs+;fl+=fs;fs=0;for(j=0; j i; j+) if(endi != 0) & (endj != 0) & (endj = 0; i-) RTRANS(m_outi. v, ss);for(j=0; j SIZE; j+)( for(k=0; k SIZE; k+)( printf (%2d, ssSIZE * j + k);printfCn);printfCn);int main(void) char s1NUM;char s2NUM;long r;char a;printfC請(qǐng)輸入開(kāi)始狀態(tài)

9、:)；r=0;while(r = 0 x30 & a 0 x39 & check_input(si, a, r) slr+=a - 0 x30;printf (%c，a);printf (n請(qǐng)輸入結(jié)束狀態(tài)：);r=0;while(r = 0 x30 & a = 0) printf C查找深度二%d,所有的方式二%ldn，m_depth, r);output ();else if (r = -1)( printf (/z沒(méi)有找到路徑.n)；else if (r = -2)(printf C這種狀態(tài)變換沒(méi)有路徑到達(dá).n)；elseprintf C不確定的錯(cuò)誤.n”);else( printf 不允

10、許這樣移動(dòng)！n)；return 0;方法二：用MATLAB實(shí)現(xiàn)program 8no_bfs;八數(shù)碼的寬度優(yōu)先搜索算法ConstDir : array 1. 4, 1. 2of integer 四種移動(dòng)方向,對(duì)應(yīng)產(chǎn)生式規(guī)則=(1,0), (-1,0), (0,1), (0,-1);n=10000;TypeT8no = array1. . 3, 1. . 3of integer;TList = record父指針深度(0的位置棋盤狀態(tài)Father : integer;dep : byte;X0, Y0 : byte;State : T8no;end;VarSource, Target : T8n

11、o;List : array0. . 10000 of TList;Closed,open, Best : integerAnswer : integer;Found : Boolean;procedure Getlnfo;var i, j : integer;begin綜合數(shù)據(jù)庫(kù)( Best表示最優(yōu)移動(dòng)次數(shù)記錄解解標(biāo)志讀入初始和目標(biāo)節(jié)點(diǎn)for i:=1 to 3 dofor j:=1 to 3 do read (Sourcei,j);for i:=1 to 3 dofor j:=1 to 3 do read (Targeti,j);end;procedure Initialize;初始化va

12、r x, y : integer;beginFound:=false;Closed:=0;open:=l;with List 1 do beginState:=Source;dep:=0;Father:=0;For x:=l to 3 doFor y:=l to 3 doif Statex,y=0 then Begin x0:=x;y0:=y; End;end;end;Function Same (A, B : T8no) :Boolean; 判斷 A, B 狀態(tài)是否相等Var i, j : integer;BeginSame:=false;For i :=1 to 3 do for j :=

13、1 to 3 do if Ai,j then exit;Same:=true;End;Function not_Appear (new : tList) :boolean; (判斷 new 是否在 List 中出現(xiàn))var i : integer;beginnot_Appear:=false;for i:=1 to open do if Same, Listi. State) then exit;not_Appear:=true;end;procedure Move(n : tList;d : integer;var ok : boolean;var new : tList);將第d條規(guī)則作用

14、于n得到new, OK是new是否可行的標(biāo)志var x, y : integer;beginX := 4- Dird, 1;Y := 4- Dird, 2;判斷new的可行性if not (X 0) and ( X 0 ) and ( Y =open) or Found;if Found then GetOutlnfoelse Writeinno answer);end;BeginAssign (Input,);ReSet (Input);Assign(Output,);ReWrite (Output);Getlnfo;Initialize;Main;Close(Input);Close(Output);End.五、實(shí)驗(yàn)結(jié)果六、實(shí)驗(yàn)總結(jié)通過(guò)實(shí)驗(yàn)問(wèn)題的求解過(guò)程就是搜索的過(guò)程，采用適合的搜索算法是關(guān)鍵 的，因?yàn)閷?duì)求解過(guò)程的效率有很大的影響，包括各種規(guī)則、過(guò)程和算法等推理 技術(shù)。八數(shù)碼問(wèn)題中，將牌的移動(dòng)來(lái)描述規(guī)則，是一種相對(duì)較簡(jiǎn)單的方法。用廣度優(yōu)先算法實(shí)現(xiàn)八數(shù)碼問(wèn)題，其實(shí)是一種比較費(fèi)勁