深度宽度优先搜索八数码.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->vv）
{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{依次使用４条规则}
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.
五、实验结果
六、实验总结
通过实验问题的求解过程就是搜索的过程，采用适合的搜索算法是关键的，因为对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。
八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。
用广度优先算法实现八数码问题，其实是一种比较费劲的方式；然而深度优先将是一个很好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。
但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。
通过这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程有了更一步的认识。
也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。
总之，这次试验使我受益匪浅。
升级会员 