寻路算法: 4种寻路算法并比较

好久没搞这些东西了...想了十分钟才勉强回忆起来...
写了 3个钟头...好累啊...
4种算法是DFS,BFS,Heuristic DFS, Heuristic BFS (A*)
用了两张障碍表张是典型迷宫:

char Block[SY][SX]=
{{1,1,1,1,1,1,1,1,1,1,1 },
{1,0,1,0,1,0,0,0,0,0,1 },
{1,0,1,0,0,0,1,0,1,1,1 },
{1,0,0,0,1,0,1,0,0,0,1 },
{1,0,1,1,0,0,1,0,0,1,1 },
{1,0,1,0,1,1,0,1,0,0,1 },
{1,0,0,0,0,0,0,0,1,0,1 },
{1,0,1,0,1,0,1,0,1,0,1 },
{1,0,0,1,0,0,1,0,1,0,1 },
{1,1,1,1,1,1,1,1,1,1,1 }};

第 2张是删掉些障碍后:

char Block[SY][SX]=
{{1,1,1,1,1,1,1,1,1,1,1 },
{1,0,1,0,1,0,0,0,0,0,1 },
{1,0,1,0,0,0,1,0,1,1,1 },
{1,0,0,0,0,0,1,0,0,0,1 },
{1,0,0,1,0,0,1,0,0,1,1 },
{1,0,1,0,0,1,0,1,0,0,1 },
{1,0,0,0,0,0,0,0,1,0,1 },
{1,0,1,0,0,0,1,0,1,0,1 },
{1,0,0,1,0,0,1,0,0,0,1 },
{1,1,1,1,1,1,1,1,1,1,1 }};

结果:
尝试节点数 合法节点数 步数
深度优先 416/133 110/43 19/25
广度优先 190/188 48/49 19/15
深度+启发 283/39 82/22 19/19
广度+启发 189/185 48/49 19/15

所以可以看出深度+启发是最好效率高路径也挺短A*第是不真实 2是慢 3是空间消耗较大

附:dfs+heu源bc 3.1通过


# <iostream.h>
# <memory.h>
# <stdlib.h>

# SX 11 //宽
# SY 10 //长

dx[4]={0,0,-1,1}; // 4种移动方向对x和y坐标影响
dy[4]={-1,1,0,0};

/*char Block[SY][SX]= //障碍表
{{ 1,1,1,1,1,1,1,1,1,1,1 },
{ 1,0,1,0,1,0,0,0,0,0,1 },
{ 1,0,1,0,0,0,1,0,1,1,1 },
{ 1,0,0,0,0,0,1,0,0,0,1 },
{ 1,0,0,1,0,0,1,0,0,1,1 },
{ 1,0,1,0,0,1,0,1,0,0,1 },
{ 1,0,0,0,0,0,0,0,1,0,1 },
{ 1,0,1,0,0,0,1,0,1,0,1 },
{ 1,0,0,1,0,0,1,0,0,0,1 },
{ 1,1,1,1,1,1,1,1,1,1,1 }};*/

char Block[SY][SX]= //障碍表
{{ 1,1,1,1,1,1,1,1,1,1,1 },
{ 1,0,1,0,1,0,0,0,0,0,1 },
{ 1,0,1,0,0,0,1,0,1,1,1 },
{ 1,0,0,0,1,0,1,0,0,0,1 },
{ 1,0,1,1,0,0,1,0,0,1,1 },
{ 1,0,1,0,1,1,0,1,0,0,1 },
{ 1,0,0,0,0,0,0,0,1,0,1 },
{ 1,0,1,0,1,0,1,0,1,0,1 },
{ 1,0,0,1,0,0,1,0,1,0,1 },
{ 1,1,1,1,1,1,1,1,1,1,1 }};

MaxAct=4; //移动方向总数
char Table[SY][SX]; //已到过标记
Level=-1; //第几步
LevelComplete=0; //这步搜索是否完成
AllComplete=0; //全部搜索是否完成
char Act[1000]; //每步移动方向搜索1000步够了吧？
x=1,y=1; //现在x和y坐标
TargetX=9,TargetY=8; //目标x和y坐标
sum1=0,sum2=0;

void Test( );
void Back( );
ActOK( );
GetNextAct( );

void ( )
{
mem(Act,0,(Act)); //清零
mem(Table,0,(Table));
Table[y][x]=1; //做已到过标记
while (!AllComplete) //是否全部搜索完
{
Level;LevelComplete=0; //搜索下步
while (!LevelComplete)
{
Act[Level]=GetNextAct( ); //改变移动方向
(Act[Level]<=MaxAct)
sum1;
(ActOK( )) //移动方向是否合理
{
sum2;
Test( ); //测试是否已到目标
LevelComplete=1; //该步搜索完成
}

{
(Act[Level]>MaxAct) //已搜索完所有方向
Back( ); //回上步
(Level<0) //全部搜索完仍无结果
LevelComplete=AllComplete=1; //退出
}
}
}
}

void Test( )
{
((xTargetX)&&(yTargetY)) //已到目标
{
for ( i=0;i<=Level;i)
cout<<()Act[i]; //输出结果
cout<<endl;
cout<<Level+1<<\" \"<<sum1<<\" \"<<sum2<<endl;
LevelComplete=AllComplete=1; //完成搜索
}
}

ActOK( )
{
tx=x+dx[Act[Level]-1]; //将到点x坐标
ty=y+dy[Act[Level]-1]; //将到点y坐标
(Act[Level]>MaxAct) //方向？
0;
((tx>=SX)||(tx<0)) //x坐标出界？
0;
((ty>=SY)||(ty<0)) //y坐标出界？
0;
(Table[ty][tx]1) //已到过？
0;
(Block[ty][tx]1) //有障碍？
0;
x=tx;
y=ty; //移动
Table[y][x]=1; //做已到过标记
1;
}

void Back( )
{
x-=dx[Act[Level-1]-1];
y-=dy[Act[Level-1]-1]; //退回原来点
Table[y][x]=0; //清除已到过标记
Act[Level]=0; //清除方向
Level--; //回上层
}

GetNextAct( ) //找到下个移动方向这段有些乱
//仔细看!
{
dis[4];
order[4];
t=32767;
tt=2;
for ( i=0;i<4;i)
dis[i]=abs(x+dx[i]-TargetX)+abs(y+dy[i]-TargetY);
for (i=0;i<4;i)
(dis[i]<t)
{
order[0]=i+1;
t=dis[i];
}
(Act[Level]0)
order[0];
order[1]=-1;
for (i=0;i<4;i)
((dis[i]t)&&(i!=(order[0]-1)))
{
order[1]=i+1;
;
}
(order[1]!=-1)
{
for (i=0;i<4;i)
(dis[i]!=t)
{
order[tt]=i+1;
tt;
}
}

{
for (i=0;i<4;i)
(dis[i]!=t)
{
order[tt-1]=i+1;
tt;
}


}

(Act[Level]order[0])
order[1];
(Act[Level]order[1])
order[2];
(Act[Level]order[2])
order[3];
(Act[Level]order[3])
5;
}

延伸阅读

• 2009-2-12-- 寻路算法:A*寻路初探
• 2009-2-12-- 寻路算法:A*寻路算法(For 初学者)