深度寬度優(yōu)先搜索

1、八數(shù)碼問題具體思路:寬度優(yōu)先算法實(shí)現(xiàn)過程（1）把起始節(jié)點(diǎn)放到OPEN表中；（2）如果OPEN是個(gè)空表，則沒有解，失敗退出；否則繼續(xù)；（3）把第一個(gè)節(jié)點(diǎn)從OPEN表中移除，并把它放入CLOSED的擴(kuò)展節(jié)點(diǎn)表中；（4）擴(kuò)展節(jié)點(diǎn)n。如果沒有后繼節(jié)點(diǎn)，則轉(zhuǎn)向（2）（5）把n的所有后繼結(jié)點(diǎn)放到OPEN表末端，并提供從這些后繼結(jié)點(diǎn)回到n的指針；（6）如果n的任意一個(gè)后繼結(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)，則找到一個(gè)解答，成功退出，否則轉(zhuǎn)向（2）。深度優(yōu)先實(shí)現(xiàn)過程（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表的前頭。如果沒有后裔，則轉(zhuǎn)向（2）；（6）如果后繼結(jié)點(diǎn)中有任一個(gè)目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解，成功退出，否則轉(zhuǎn)向（2）。方法:用C語言實(shí)現(xiàn)#include #include #includetypedef long UINT64;typedef struct(char x; 位置x和位置y上的數(shù)字換位char y; 其中x是0所在的位置 EP_MOVE;#define SIZE 3 /8數(shù)碼問題，理論上本程序也可解決15數(shù)碼問題，#define NUM SIZE * SIZE /但mov

3、e_gen需要做很多修改，輸入初始和結(jié)束狀態(tài)的部分和check_input也要修改#define MAX_NODE 1000000#define MAX_DEP 100#define XCHG(a, b) ( a=a + b; b=a - b; a=a - b; #define TRANS(a, b)/*( long iii; (b)=0; for(iii=0; iii NUM; iii+) (b) = (b) = 0; iii-) ( biii=ttt & 0 xf; ttt=4; /將一個(gè)64位整數(shù)a轉(zhuǎn)換為數(shù)組b/typedef struct EP_NODE_Tag( UINT64 v;

4、保存狀態(tài)，每個(gè)數(shù)字占4個(gè)二進(jìn)制位，可解決16數(shù)碼問題struct EP_NODE_Tag *prev; /父節(jié)點(diǎn)struct EP_NODE_Tag *small, *big; EP_NODE;EP_NODE m_arMAX_NODE;EP_NODE *m_root;long m_depth; 搜索深度EP_NODE m_outMAX_DEP; 輸出路徑/long move_gen(EP_NODE *node, EP_MOVE *move)(long pz; /0 的位置UINT64 t=0 xf;for(pz=NUM - 1; pz = 0; pz-)(if(node-v & t) = 0)

5、 (break; /找到0的位置tv, ss);XCHG(ssmv-x, ssmv-y);TRANS(ss, n2-v);return 0;long add_node(EP_NODE *node, long r)(EP_NODE *p=m_root;EP_NODE *q;while(p)( q=p;if(p-v = node-v) return 0;else if(node-v p-v) p=p-big;else if(node-v v) p=p-small;m_arr.v=node-v;m_arr.prev=node-prev;m_arr.small=NULL;m_arr.big=NULL;

6、if(node-v q-v)( q-big= &m_arr;else if(node-v v)( q-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)，無解一(-2)*/long bfs_search(char *begin, char *end)( long h=0, r=1, c, i, j；EP_NODE l_end, node, *p

7、node;EP_MOVE mv4; /每個(gè)局面最多4種走法TRANS(begin, m_ar0.v);TRANS(end, l_end.v);m_ar0.prev二NULL;m_root=m_ar;m_root-small=NULL;m_root-big=NULL;while(h r) & (r MAX_NODE - 4)( c=move_gen(&m_arh, mv);for(i=0; i prev)( m_outj=*pnode;j+;pnode二pnode-prev; m_depth=j;return r;if(add_node(&node, r) r+; 只能對(duì)歷史節(jié)點(diǎn)中沒有的新節(jié)點(diǎn)搜

8、索，否則會(huì)出現(xiàn)環(huán)h+;printf(rSearch.%9d/%d %d, h, r, get_node_depth(&m_arh);if(h = r)( return -2; else(return -1; 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 f1=0, f2=0;long i, j;for(i=0; i

9、NUM; i+)( fs=0;for(j=0; j i; j+)(if(begini != 0) & (beginj != 0) & (beginj begini) fs+;f1+=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);printf(n)；printf(n)；int main(void)( char s

10、1NUM;char s2NUM;long r;char a;printf(請(qǐng)輸入開始狀態(tài):)；r=0;while(r = 0 x30 & a 0 x39 & check_input(s1, a, r)( s1r+=a - 0 x30;printf(%c, a);printf(n請(qǐng)輸入結(jié)束狀態(tài):)；while(r = 0 x30 & a = 0)( printf(查找深度二%d,所有的方式二%ldn”, m_depth, r);output();else if(r = -1) printf(沒有找到路徑.n);else if(r = -2)(printf(-這種狀態(tài)變換沒有路徑到達(dá).n)；els

11、e printf（不確定的錯(cuò)誤.n）;else printf(不允許這樣移動(dòng)！n);return 0;方法二：用MATLAB實(shí)現(xiàn)program 8no_bfs;八數(shù)碼的寬度優(yōu)先搜索算法ConstDir : array1.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 = recordFather : integer;父指針dep : byte;深度X0,Y0 : byte;0 的位置State : T8no;棋盤狀態(tài)end;VarSo

12、urce,Target : T8no;Closed,open,Best : integer( Best表示最優(yōu)移動(dòng)次數(shù)Answer : integer;記錄解Found : Boolean;解標(biāo)志procedure GetInfo;讀入初始和目標(biāo)節(jié)點(diǎn)讀入初始和目標(biāo)節(jié)點(diǎn)var i,j : integer;beginfor i:=1 to 3dofor j:=1 to 3 do read(Sourcei,j);for j:=1 to3 dofor i:=1 to 3dofor j:=1 to 3 do read(Targeti,j);for j:=1 to3 doend;procedure Ini

13、tialize;初始化List : array0.10000 of TList; 綜合數(shù)據(jù)庫(kù)var x,y : integer;beginFound:=false;Closed:=0;open:=1;with List1 do beginState:二Source;dep:=0;Father:=0;For x:=1 to 3 doFor y:=1 to 3 doif Statex,y=0 then Begin x0:=x;y0:=y; End;end;Function Same(A,B : T8no):Boolean; 判斷 A,B 狀態(tài)是否相等Var i,j : integer;BeginS

14、ame:=false;For i:=1 to 3 do for j: = 1 to 3 do if Ai,jBi,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(new.State,Listi.State) then exit;not_Appear:二true;end;procedure Move(n : tList;d : inte

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