深度宽度优先搜索八数码.docx
- 文档编号:16564580
- 上传时间:2023-07-14
- 格式:DOCX
- 页数:17
- 大小:49.80KB
深度宽度优先搜索八数码.docx
《深度宽度优先搜索八数码.docx》由会员分享,可在线阅读,更多相关《深度宽度优先搜索八数码.docx(17页珍藏版)》请在冰点文库上搜索。
深度宽度优先搜索八数码
八数码问题
具体思路:
宽度优先算法实现过程
(1)把起始节点放到OPEN表中;
(2)如果OPEN是个空表,则没有解,失败退出;否则继续;
(3)把第一个节点从OPEN表中移除,并把它放入CLOSED的扩展节点表中;
(4)扩展节点n。
如果没有后继节点,则转向
(2)
(5)把n的所有后继结点放到OPEN表末端,并提供从这些后继结点回到n的指针;
(6)如果n的任意一个后继结点是目标节点,则找到一个解答,成功退出,否则转向
(2)。
开始
把S放入OPEN表
OPEN表为空
失败
把第一个节点n从把S放入OPEN表移除,放到CLOSED表中
移除
扩展n,把它的后继节点放入OPEN表的末端,提供回到n
的指针
是否任何节点为目标节点
成功
深度优先实现过程
(1)把起始节点S放入未扩展节点OPEN表中。
如果此节点为一目标节点,则得到一个解;
(2)如果OPEN为一空表,则失败退出;
(3)把第一个节点从OPEN表移到CLOSED表;
(4)如果节点n的深度等于最大深度,则转向
(2);
(5)扩展节点n,产生其全部后裔,并把它们放入OPEN表的前头。
如果没有后裔,则转向
(2);
(6)如果后继结点中有任一个目标节点,则得到一个解,成功退出,否则转向
(2)。
开始
把S放入OPEN表
S是否为目标节点
成功
把第一个节点n从把S放入OPEN表移除,放到CLOSED表中
移除
节点n的深度是否等于最深界限
OPEN表为空
失败
扩展n,把它的后继放入OPEN表的前头,提供回到n的指针
是否有任何后继节点为目标节点
成功
方法一:
用C语言实现
#include<>
#include<>
#include<>
typedeflongUINT64;
typedefstruct
{
charx;=0;
move[0].y=1;
move[1].x=0;
move[1].y=3;
return2;
case1:
move[0].x=1;
move[0].y=0;
move[1].x=1;
move[1].y=2;
move[2].x=1;
move[2].y=4;
return3;
case2:
move[0].x=2;
move[0].y=1;
move[1].x=2;
move[1].y=5;
return2;
case3:
move[0].x=3;
move[0].y=0;
move[1].x=3;
move[1].y=6;
move[2].x=3;
move[2].y=4;
return3;
case4:
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;
return4;
case5:
move[0].x=5;
move[0].y=2;
move[1].x=5;
move[1].y=4;
move[2].x=5;
move[2].y=8;
return3;
case6:
move[0].x=6;
move[0].y=3;
move[1].x=6;
move[1].y=7;
return2;
case7:
move[0].x=7;
move[0].y=6;
move[1].x=7;
move[1].y=4;
move[2].x=7;
move[2].y=8;
return3;
case8:
move[0].x=8;
move[0].y=5;
move[1].x=8;
move[1].y=7;
return2;
}
return0;
}
longmov(EP_NODE*n1,EP_MOVE*mv,EP_NODE*n2)
=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];
}
elseif(node->v
{q->small=&m_ar[r];
}
return1;
}
/*得到节点所在深度*/
longget_node_depth(EP_NODE*node)
{longd=0;
while(node->prev)
{d++;
node=node->prev;
}
returnd;
}
/*返回值:
成功-返回搜索节点数,节点数不够-(-1),无解-(-2)*/
longbfs_search(char*begin,char*end)
{longh=0,r=1,c,i,j;
EP_NODEl_end,node,*pnode;
EP_MOVEmv[4];;
TRANS(end,;
m_ar[0].prev=NULL;
m_root=m_ar;
m_root->small=NULL;
m_root->big=NULL;
while((h {c=move_gen(&m_ar[h],mv); for(i=0;i {mov(&m_ar[h],&mv[i],&node); =&m_ar[h]; if== {pnode=&node; j=0; while(pnode->prev) {m_out[j]=*pnode; j++; pnode=pnode->prev; } m_depth=j; returnr; } if(add_node(&node,r))r++;.%9d/%d@%d",h,r,get_node_depth(&m_ar[h])); } if(h==r) {return-2;} else {return-1;} } longcheck_input(char*s,chara,longr) {longi; for(i=0;i {if(s[i]==a-0x30)return0;} return1; } longcheck_possible(char*begin,char*end) {charfs; longf1=0,f2=0; longi,j; for(i=0;i {fs=0; for(j=0;j { if((begin[i]! =0)&&(begin[j]! =0)&&(begin[j] } f1+=fs; fs=0; for(j=0;j {if((end[i]! =0)&&(end[j]! =0)&&(end[j] } f2+=fs; } if((f1&1)==(f2&1))return1; else return0; } voidoutput(void) {longi,j,k; charss[NUM]; for(i=m_depth-1;i>=0;i--) {RTRANS(m_out[i].v,ss); for(j=0;j {for(k=0;k {printf("%2d",ss[SIZE*j+k]); } printf("\n"); } printf("\n"); } } intmain(void) {chars1[NUM]; chars2[NUM]; longr; chara; printf("请输入开始状态: "); r=0; while(r {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 {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(); } elseif(r==-1) {printf("没有找到路径.\n"); } elseif(r==-2) {printf("这种状态变换没有路径到达.\n"); } else {printf("不确定的错误.\n"); } } else {printf("不允许这样移动! \n"); } return0; } 方法二: 用MATLAB实现 program8no_bfs;{八数码的宽度优先搜索算法} Const Dir: array[1..4,1..2]ofinteger{四种移动方向,对应产生式规则} =((1,0),(-1,0),(0,1),(0,-1)); n=10000; Type T8no=array[1..3,1..3]ofinteger; TList=record Father: integer; {父指针} dep: byte; {深度} X0,Y0: byte;{0的位置} State: T8no; {棋盘状态} end; Var Source,Target: T8no; List: array[0..10000]ofTList;{综合数据库} Closed,open,Best: integer{Best表示最优移动次数} Answer: integer;{记录解} Found: Boolean;{解标志} procedureGetInfo;{读入初始和目标节点} vari,j: integer; begin fori: =1to3do forj: =1to3doread(Source[i,j]); fori: =1to3do forj: =1to3doread(Target[i,j]); end; procedureInitialize;{初始化} varx,y: integer; begin Found: =false; Closed: =0;open: =1; withList[1]dobegin State: =Source;dep: =0;Father: =0; Forx: =1to3do Fory: =1to3do ifState[x,y]=0thenBeginx0: =x;y0: =y;End; end; end; FunctionSame(A,B: T8no): Boolean;{判断A,B状态是否相等} Vari,j: integer; Begin Same: =false; Fori: =1to3doforj: =1to3doifA[i,j]<>B[i,j]thenexit; Same: =true; End; Functionnot_Appear(new: tList): boolean;{判断new是否在List中出现} vari: integer; begin not_Appear: =false; fori: =1toopendoifSame,List[i].State)thenexit; not_Appear: =true; end; procedureMove(n: tList;d: integer;varok: boolean;varnew: tList); {将第d条规则作用于n得到new,OK是new是否可行的标志} varx,y: integer; begin X: =+Dir[d,1]; Y: =+Dir[d,2]; {判断new的可行性} ifnot((X>0)and(X<4)and(Y>0)and(Y<4))thenbeginok: =false;exitend; OK: =true; : =;{new=Expand(n,d)} [X,Y]: =0; [,]: =[X,Y]; : =X;: =Y; end; procedureAdd(new: tList);{插入节点new} begin ifnot_Appear(new)thenBegin{如果new没有在List出现} Inc(open);{new加入open表} List[open]: =new; end; end; procedureExpand(Index: integer;varn: tList);{扩展n的子节点} vari: integer; new: tList; OK: boolean; Begin ifSame,Target)thenbegin{如果找到解} Found: =true; Best: =; Answer: =Index; Exit; end; Fori: =1to4dobegin{依次使用4条规则} Move(n,i,OK,new); ifnotokthencontinue; : =Index; : =+1; Add(new); end; end; procedureGetOutInfo;{输出} procedureOutlook(Index: integer);{递归输出每一个解} vari,j: integer; begin ifIndex=0thenexit; Outlook(List[Index].Father); withList[Index]do fori: =1to3dobegin forj: =1to3dowrite(State[i,j],''); writeln; end; writeln; end; begin Writeln('Total=',Best); Outlook(Answer); end; procedureMain;{搜索主过程} begin Repeat Inc(Closed); Expand(Closed,List[Closed]);{扩展Closed} Until(Closed>=open)orFound; ifFoundthenGetOutInfo{存在解} elseWriteln('noanswer');{无解} end; Begin Assign(Input,'');ReSet(Input); Assign(Output,'');ReWrite(Output); GetInfo; Initialize; Main; Close(Input);Close(Output); End. 五、实验结果 六、实验总结 通过实验问题的求解过程就是搜索的过程,采用适合的搜索算法是关键的,因为对求解过程的效率有很大的影响,包括各种规则、过程和算法等推理技术。 八数码问题中,将牌的移动来描述规则,是一种相对较简单的方法。 用广度优先算法实现八数码问题,其实是一种比较费劲的方式;然而深度优先将是一个很好的方法,利用深度优先不但减少了程序实现的时间,是一种不错的方式。 但最好的方式是启发式搜索方式实现,在很大程度上相对于前两种方式是一种非常好的实现方式,不但节省了时间,也节省了空间。 通过这次试验使我对搜索算法有了一定的了解,并对实现这个问题的执行过程有了更一步的认识。 也通过它解决了八数码问题,但在实际的过程中还存在很多问题,也看了一些辅助书籍,以后还要加强学习,加强理论与实际的练习。 总之,这次试验使我受益匪浅。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 深度宽度优先搜索 八数码 深度 宽度 优先 搜索 数码