Y-----WORD格式--可编辑--专业资料-----八数码问题具体思路：宽度优先算法实现过程（1）把起始节点放到OPEN表中；（2）如果OPEN是个空表，则没有解，失败退出；否则继续；（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；（4）扩展节点n。
如果没有后继节点，则转向（2）（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转向（2）。
深度优先实现过程（1）把起始节点S放入未扩展节点OPEN表中。
如果此节点为一目标节点，则得到一个解；（2）如果OPEN为一空表，则失败退出；（3）把第一个节点从OPEN表移到CLOSED表；（4）如果节点n的深度等于最大深度，则转向（2）；（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。
如果没有后裔，则转向（2）；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。
方法一：用C语言实现#include <stdio.h>#include <string.h>#include<stdlib.h>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 - b; a=a - b; }#define TRANS(a, b)/*{ long iii; (b)=0; for(iii=0; iii < NUM; iii++) (b)=((b) << 4) + a[iii]; }*/ //将数组a转换为一个64位的整数b#define RTRANS(a, b) \{ \long iii; \UINT64 ttt=(a); \for(iii=NUM - 1; iii >= 0; iii--) \{ \b[iii]=ttt & 0xf; \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_ar[MAX_NODE];EP_NODE *m_root;long m_depth; //搜索深度EP_NODE m_out[MAX_DEP]; //输出路径//long move_gen(EP_NODE *node, EP_MOVE *move){long pz; //0的位置UINT64 t=0xf;for(pz=NUM - 1; pz >= 0; pz--){if((node->v & t) == 0){ break; //找到0的位置}t<<=4;}switch(pz){case 0:move[0].x=0;move[0].y=1;move[1].x=0;move[1].y=3;return 2;case 1:move[0].x=1;move[0].y=0;move[1].x=1;move[1].y=2;move[2].x=1;move[2].y=4;return 3;case 2:move[0].x=2;move[0].y=1;move[1].x=2;move[1].y=5;return 2;case 3:move[0].x=3;move[0].y=0;move[1].x=3;move[1].y=6;move[2].x=3;move[2].y=4;return 3;case 4:move[0].x=4;move[0].y=1;move[1].x=4;move[1].y=3;move[2].x=4;move[2].y=5;move[3].x=4;move[3].y=7;return 4;case 5:move[0].x=5;move[0].y=2;move[1].x=5;move[1].y=4;move[2].x=5;move[2].y=8;return 3;case 6:move[0].x=6;move[0].y=3;move[1].x=6;move[1].y=7;return 2;case 7:move[0].x=7;move[0].y=6;move[1].x=7;move[1].y=4;move[2].x=7;move[2].y=8;return 3;case 8:move[0].x=8;move[0].y=5;move[1].x=8;move[1].y=7;return 2;}return 0;}long mov(EP_NODE *n1, EP_MOVE *mv, EP_NODE *n2) //走一步，返回走一步后的结果{char ss[NUM];RTRANS(n1->v, ss);XCHG(ss[mv->x], ss[mv->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 < p->v) p=p->small;}m_ar[r].v=node->v;m_ar[r].prev=node->prev;m_ar[r].small=NULL;m_ar[r].big=NULL;if(node->v > q->v){ q->big= &m_ar[r];}else if(node->v < q->v){ q->small= &m_ar[r];}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, char *end){ long h=0, r=1, c, i, j;EP_NODE l_end, node, *pnode;EP_MOVE mv[4]; //每个局面最多4种走法TRANS(begin, m_ar[0].v);TRANS(end, l_end.v);m_ar[0].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_ar[h], mv);for(i=0; i < c; i++){ mov(&m_ar[h], &mv[i], &node);node.prev= &m_ar[h];if(node.v == l_end.v){ pnode= &node;j=0;while(pnode->prev){ m_out[j]=*pnode;j++;pnode=pnode->prev;}m_depth=j;return r;}if(add_node(&node, r)) r++; //只能对历史节点中没有的新节点搜索，否则会出现环}h++;printf("\rSearch...%9d/%d @ %d", h, r, get_node_depth(&m_ar[h]));}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(s[i] == a - 0x30) 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 < NUM; i++){ fs=0;for(j=0; j < i; j++){if((begin[i] != 0) && (begin[j] != 0) && (begin[j] < begin[i])) fs++;}f1+=fs;fs=0;for(j=0; j < i; j++){ if((end[i] != 0) && (end[j] != 0) && (end[j] < end[i])) fs++;}f2+=fs;}if((f1 & 1) == (f2 & 1)) return 1;elsereturn 0;}void output(void){ long i, j, k;char ss[NUM];for(i=m_depth - 1; i >= 0; i--){ RTRANS(m_out[i].v, ss);for(j=0; j < SIZE; j++){ for(k=0; k < SIZE; k++){ printf("%2d", ss[SIZE * j + k]);}printf("\n");}printf("\n");}}int main(void){ char s1[NUM];char s2[NUM];long r;char a;printf("请输入开始状态:");r=0;while(r < NUM){ a=getchar();if(a >= 0x30 && a < 0x39 && check_input(s1, a, r)) { s1[r++]=a - 0x30;printf("%c", a);}}printf("\n请输入结束状态:");r=0;while(r < NUM){ a=getchar();if(a >= 0x30 && a < 0x39 && check_input(s2, a, r)) { s2[r++]=a - 0x30;printf("%c", a);}}printf("\n");if(check_possible(s1, s2)){ r=bfs_search(s1, s2);printf("\n");if(r >= 0){ printf("查找深度=%d,所有的方式=%ld\n", m_depth, r); output();}else if(r == -1){ printf("没有找到路径.\n");}else if(r == -2){printf("这种状态变换没有路径到达.\n");}else{printf("不确定的错误.\n");}}else{ printf("不允许这样移动!\n");}return 0;}方法二：用MATLAB实现program 8no_bfs; {八数码的宽度优先搜索算法} ConstDir : array[1..4,1..2]of integer {四种移动方向，对应产生式规则} = ((1,0),(-1,0),(0,1),(0,-1));n=10000;TypeT8no = array[1..3,1..3]of integer;TList = recordFather : integer; {父指针}dep : byte; {深度}X0,Y0 : byte; {0的位置}State : T8no; {棋盘状态 }end;VarSource,Target : T8no;List : array[0..10000] of TList; {综合数据库 }Closed,open,Best : integer { Best表示最优移动次数}Answer : integer; {记录解}Found : Boolean; {解标志}procedure GetInfo; {读入初始和目标节点}var i,j : integer;beginfor i:=1 to 3 dofor j:=1 to 3 do read(Source[i,j]);for i:=1 to 3 dofor j:=1 to 3 do read(Target[i,j]);end;procedure Initialize; {初始化}var x,y : integer;beginFound:=false;Closed:=0;open:=1;with List[1] do beginState:=Source;dep:=0;Father:=0;For x:=1 to 3 doFor y:=1 to 3 doif State[x,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:=1 to 3 do if A[i,j]<>B[i,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,List[i].State) then exit;not_Appear:=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 + Dir[d,1];Y := n.y0 + Dir[d,2];{判断new的可行性}if not ((X > 0) and ( X < 4 ) and ( Y > 0 ) and ( Y < 4 )) then begin ok:=false;exit end;OK:=true;new.State:=n.State; {new=Expand(n,d)}new.State[X,Y]:=0;new.State[n.x0,n.y0]:=n.State[X,Y];new.X0:=X;new.Y0:=Y;end;procedure Add(new : tList); {插入节点new}beginif not_Appear(new) then Begin {如果new没有在List出现 }Inc(open); {new加入open表 }List[open] := new;end;end;procedure Expand(Index : integer; var n : tList); {扩展n的子节点}var i : integer;new : tList;OK : boolean;Beginif Same(n.State , Target) then begin {如果找到解}Found := true;Best :=n.Dep;Answer:=Index;Exit;end;For i := 1 to 4 do begin {依次使用４条规则} Move(n,i,OK,new);if not ok then continue;new.Father := Index;new.Dep :=n.dep + 1;Add(new);end;end;procedure GetOutInfo; {输出}procedure Outlook(Index : integer); {递归输出每一个解} var i,j : integer;beginif Index=0 then exit;Outlook(List[Index].Father);with List[Index] dofor i:=1 to 3 do beginfor j:=1 to 3 do write(State[i,j],' ');writeln;end;writeln;end;beginWriteln('Total = ',Best);Outlook(Answer);end;procedure Main; {搜索主过程}beginRepeatInc(Closed);Expand(Closed,List[Closed]); {扩展Closed}Until (Closed>=open) or Found;if Found then GetOutInfo {存在解}else Writeln('no answer'); {无解}end;BeginAssign(Input,'input.txt');ReSet(Input);Assign(Output,'Output.txt');ReWrite(Output);GetInfo;Initialize;Main;Close(Input);Close(Output);End.五、实验结果六、实验总结通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。
