2022年深度宽度优先搜索-八数码 .pdf

《2022年深度宽度优先搜索-八数码 .pdf》由会员分享，可在线阅读，更多相关《2022年深度宽度优先搜索-八数码 .pdf（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-1- 八数码问题具体思路：宽度优先算法实现过程（1）把起始节点放到OPEN 表中；（2）如果 OPEN 是个空表，则没有解，失败退出；否则继续；（3）把第一个节点从OPEN 表中移除，并把它放入CLOSED 的扩展节点表中；（4）扩展节点 n。如果没有后继节点，则转向（2）（5）把 n 的所有后继结点放到OPEN 表末端，并提供从这些后继结点回到n 的指针；（6）如果 n 的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转向（2） 。开始把 S放入OPEN 表OPEN 表为空失败把第一个节点n从把 S放入OPEN扩展n，把它的后继节点放入OPEN 表的末端，提供回到n的指针是否任

2、何节点为目标节点成功名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 23 页 - - - - - - - - - -2- 深度优先实现过程（1）把起始节点 S放入未扩展节点 OPEN 表中。如果此节点为一目标节点，则得到一个解；（2）如果 OPEN 为一空表，则失败退出；（3）把第一个节点从OPEN 表移到 CLOSED 表；（4）如果节点 n 的深度等于最大深度，则转向（2） ；（5）扩展节点 n，产生其全部后裔，并把它们放入OPEN 表的前头。如果没有后裔，则转向（2

3、） ；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2） 。方法开始把 S 放入OPEN 表S是否为目标节点成功把第一个节点n 从把 S放入OPEN 表节点 n 的深度是否等于最深界限OPEN 表为空失败扩展 n，把它的后继放入OPEN 表的前头，提供回到n的指针是 否 有 任 何 后 继节点为目标节点成功名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 23 页 - - - - - - - - - -3- 一：用 C语言实现#include #i

4、nclude #include typedef long UINT64; typedef struct char x; /位置 x 和位置 y 上的数字换位 char y; /其中 x 是 0 所在的位置 EP_MOVE; #define SIZE 3 /8数码问题，理论上本程序也可解决15数码问题，#define NUM SIZE * SIZE /但 move_gen需要做很多修改，输入初始和结束状态的部分和check_input也要修改#define MAX_NODE 1000000 #define MAX_DEP 100 #define XCHG(a, b) a=a + b; b=a -

5、 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; /将一个 64位整数 a 转换为数组 b / typedef struct EP_NODE_Tag UINT64 v; /保存状态，每个数字占4 个二进制位，可解决16 数码问题struct EP_NODE_Tag *prev; /父节点struct EP_NODE_Tag *small, *big; EP_NODE; EP_NODE m_arMAX_N

6、ODE; 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) break; /找到 0 的位置名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 23 页

7、- - - - - - - - - -5- 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

8、- - 名师精心整理 - - - - - - - 第 8 页，共 23 页 - - - - - - - - - -9- m_arr.v=node-v; m_arr.prev=node-prev; m_arr.small=NULL; m_arr.big=NULL; if(node-v q-v) q-big= &m_arr; else if(node-v v) q-small= &m_arr; return 1; /* 得到节点所在深度 */ long get_node_depth(EP_NODE *node) long d=0; while(node-prev) d+; node=node-pr

9、ev; return d; /* 返回值：成功返回搜索节点数，节点数不够(-1) ，无解 (-2)*/ long bfs_search(char *begin, char *end) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 23 页 - - - - - - - - - -10- long h=0, r=1, c, i, j; EP_NODE l_end, node, *pnode; EP_MOVE mv4; / 每个局面最多 4 种走法TRANS(begin, m

10、_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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，

11、共 23 页 - - - - - - - - - -11- return r; if(add_node(&node, r) r+; /只能对历史节点中没有的新节点搜索，否则会出现环 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

12、check_possible(char *begin, char *end) char fs; long f1=0, f2=0; long i, j; for(i=0; i NUM; i+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 23 页 - - - - - - - - - -12- fs=0; for(j=0; j i; j+) if(begini != 0) & (beginj != 0) & (beginj begini) fs+; f1+=fs; fs

13、=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+) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 23 页 - - - - - - - - - -13- printf(%2d, ssSIZE * j + k); printf(n); printf(n); int

14、 main(void) char s1NUM; char s2NUM; long r; char a; printf(请输入开始状态 :); r=0; while(r = 0 x30 & a 0 x39 & check_input(s1, a, r) s1r+=a - 0 x30; printf(%c, a); printf(n请输入结束状态 :); r=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 23 页 - - - - - - - - - -14- whi

15、le(r = 0 x30 & a = 0) printf(查找深度 =%d,所有的方式 =%ldn, m_depth, r); output(); else if(r = -1) printf(没有找到路径 .n); else if(r = -2) printf(这种状态变换没有路径到达.n); else printf(不确定的错误 .n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 23 页 - - - - - - - - - -15- else printf(

16、不允许这样移动 !n); return 0; 方法二：用 MATLAB 实现program 8no_bfs; 八数码的宽度优先搜索算法 Const Dir : array1.4,1.2of integer 四种移动方向，对应产生式规则 = (1,0),(-1,0),(0,1),(0,-1); n=10000; Type T8no = array1.3,1.3of integer; TList = record Father : integer; 父指针 dep : byte; 深度 X0,Y0 : byte; 0的位置 State : T8no; 棋盘状态 end; Var Source,Ta

17、rget : T8no; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 23 页 - - - - - - - - - -16- List : array0.10000 of TList; 综合数据库 Closed,open,Best : integer Best表示最优移动次数 Answer : integer; 记录解 Found : Boolean; 解标志 procedure GetInfo; 读入初始和目标节点 var i,j : integer; begin

18、 for i:=1 to 3 do for j:=1 to 3 do read(Sourcei,j); for i:=1 to 3 do for j:=1 to 3 do read(Targeti,j); end; procedure Initialize; 初始化 var x,y : integer; begin Found:=false; Closed:=0;open:=1; with List1 do begin State:=Source;dep:=0;Father:=0; For x:=1 to 3 do For y:=1 to 3 do if Statex,y=0 then Beg

19、in x0:=x;y0:=y; End; end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 23 页 - - - - - - - - - -17- end; Function Same(A,B : T8no):Boolean; 判断 A,B 状态是否相等 Var i,j : integer; Begin Same:=false; For i:=1 to 3 do for j:=1 to 3 do if Ai,jBi,j then exit; Same:=true

20、; End; Function not_Appear(new : tList):boolean;判断 new是否在 List中出现 var i : integer; begin not_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 : integer;var ok : boolean;var new : tList); 将第 d 条规则作用于 n 得到 new,OK是 new是否可行的标志

21、 var x,y : integer; begin X := 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 GetOutInfo 存在解 else Writeln(no answer); 无解 end; Begin Assign(Input,input.txt);ReSet(Input); Assign(Output,Output.txt);ReWrite(Output); GetInfo; Initialize; Mai

22、n; Close(Input);Close(Output); End. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 23 页 - - - - - - - - - -21- 五、实验结果六、实验总结通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。用广度优先算法实现八数码问题，其实是一种比较费劲的方式； 然而深度优先将是一个

23、很好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。通过这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程有了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验使我受益匪浅。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 23 页 - - - - - - - - - -22- 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 22 页，共 23 页 - - - - - - - - - -23- 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 23 页 - - - - - - - - -