深度宽度优先搜索八数码

《深度宽度优先搜索八数码》由会员分享，可在线阅读，更多相关《深度宽度优先搜索八数码（19页珍藏版）》请在装配图网上搜索。

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

2、表移到CLOSED表；(4) 如果节点n的深度等于最大深度，则转向(2)；(5) 扩展节点n，产生其全部后裔，并把它们放入 OPEN表的前头。如果没有后裔，则转 向(2 )；(6) 如果后继结点中有任一个目标节点，贝U得到一个解，成功退出，否则转向(2 )。是否有任何后继节点为目标节点f1*成功方法:用C 语言实现#include #include #includetypedef long UINT64;typedef structchar x; / 位置 x 和位置 y 上的数字换位char y; / 其中 x 是 0 所在的位置 EP_MOVE;#define SIZE 3 /8数码问题，

3、理论上本程序也可解决 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 - b; a=a - b; #define TRANS(a, b)/* long iii; (b)=0; for(iii=0; iii NUM; iii+) (b)=(b) = 0; iii-) biii=ttt & 0xf; ttt=4; / 将一个 64 位整

4、数 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_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 的位置UIN

5、T64 t=0xf;for(pz=NUM - 1; pz = 0; pz-)if(node-v & t) = 0) 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=nod

6、e-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-prev;return d;/* 返回值：成功返回搜索节点数，节点数不够 (-1) ，无解 (-2)*/ long bfs_search(char *begin, c

7、har *end) long h=0, r=1, c, i, j;EP_NODE l_end, node, *pnode;EP_MOVE mv4; / 每个局面最多 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_d

8、epth=j;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; elsereturn -1; long check_input(char *s, char a, long r) long i;for(i=0; i r; i+) if(si = a - 0x30) return 0; return 1;long check_possible(char *begin,

9、char *end) char fs;long f1=0, f2=0;long i, j;for(i=0; i 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

10、* j + k); printf(n); printf(n);int main(void) char s1NUM; char s2NUM;long r;char a;printf( 请输入开始状态 :);r=0; while(r = 0x30 & a 0x39 & check_input(s1, a, r) s1r+=a - 0x30;printf(%c, a);printf(n 请输入结束状态 :);r=0;while(r = 0x30 & a = 0) printf( 查找深度 =%d, 所有的方式 =%ldn, m_depth, r); output();else if(r = -1)

11、printf( 没有找到路径 .n);else if(r = -2)printf( 这种状态变换没有路径到达 .n);elseprintf( 不确定的错误 .n);else printf( 不允许这样移动 !n);return 0;方法二：用 MATLAB 实现program 8no_bfs;八数码的宽度优先搜索算法 ConstDir : array1.4,1.2of integer 四种移动方向，对应产生式规则 = (1,0),(-1,0),(0,1),(0,-1);n=10000;TypeT8no = array1.3,1.3of integer;TList = recordFather

12、: integer; dep : byte;X0,Y0 : byte;State : T8no;end;VarSource,Target : T8no;List : array0.10000 of TList; Closed,open,Best : integer Answer : integer;Found : Boolean; procedure GetInfo; var i,j : integer;父指针深度0 的位置 棋盘状态 综合数据库 Best 表示最优移动次数 记录解解标志 读入初始和目标节点 beginfor i:=1 to 3 dofor j:=1 to 3 do read(

13、Sourcei,j);for i:=1 to 3 dofor j:=1 to 3 do read(Targeti,j); end;procedure Initialize;初始化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;end;Function Same(A,B : T8no)

14、:Boolean;判断 A,B 状态是否相等 Var i,j : integer;BeginSame:=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 中出现 var i : integer;beginnot_Appear:=false;for i:=1 to open do if Same(new.State,Listi.State) then exit; not_Appea

15、r:=true;end;procedure Move(n : tList;d : integer;var ok : boolean;var new : tList);将第 d 条规则作用于 n 得到 new,OK 是 new 是否可行的标志 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;Begin

16、Assign(Input,input.txt);ReSet(Input); Assign(Output,Output.txt);ReWrite(Output);Getl nfo;In itialize;Main;Close(l nput);Close(Output);End.五、实验结果六、实验总结通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键 的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理 技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。用广度优先算法实现八数码问题， 其实是一种比较费劲的方式；然而深度 优先将是一个很好的方法，利用深度优先不但减少了程序实现的时间，是一种 不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两 种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。通过这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执 行过程有了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还 存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的 练习。总之，这次试验使我受益匪浅。