深度宽度优先搜索八数码

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

2、ED表；（4）如果节点n的深度等于最大深度，则转向（2）；（5）扩展节点n,产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）o方法一：用C语言实现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;/*得到节点所在深度*/long get_node_depth(EP_NODE *node) long d=0;while(node-prev)( d+;node=node-prev;return d;/*返回值：成功一返回搜索节点数，节点数不够一 (-1),无解一 (-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请输入开始状态

9、:)；r=0;while(r = 0 x30 & a 0 x39 & check_input(si, a, r) slr+=a - 0 x30;printf (%c，a);printf (n请输入结束状态：);r=0;while(r = 0 x30 & a = 0) printf C查找深度二%d,所有的方式二%ldn，m_depth, r);output ();else if (r = -1)( printf (/z没有找到路径.n)；else if (r = -2)(printf C这种状态变换没有路径到达.n)；elseprintf C不确定的错误.n”);else( printf 不允

10、许这样移动！n)；return 0;方法二：用MATLAB实现program 8no_bfs;八数码的宽度优先搜索算法ConstDir : array 1. 4, 1. 2of integer 四种移动方向,对应产生式规则=(1,0), (-1,0), (0,1), (0,-1);n=10000;TypeT8no = array1. . 3, 1. . 3of integer;TList = record父指针深度(0的位置棋盘状态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综合数据库( Best表示最优移动次数记录解解标志读入初始和目标节点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 状态是否相等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 中出现)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条规则作用

14、于n得到new, OK是new是否可行的标志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.五、实验结果六、实验总结通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键 的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理 技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。用广度优先算法实现八数码问题，其实是一种比较费劲