四种寻路算法并比较

四种算法是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 }};

第二张是删掉一些障碍后的:

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*第一是不真实二是慢三是空间消耗较大。

附：dfs+heu的源程序，bc++ 3.1通过

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

#define SX 11 //宽

#define SY 10 //长


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

int 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 }};

int MaxAct=4; //移动方向总数

char Table[SY][SX]; //已到过标记

int Level=-1; //第几步

int LevelComplete=0; //这一步的搜索是否完成

int AllComplete=0; //全部搜索是否完成

char Act[1000]; //每一步的移动方向，搜索1000步，够了吧？

int x=1,y=1; //现在的x和y坐标

int TargetX=9,TargetY=8; //目标x和y坐标

int sum1=0,sum2=0;

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

void main( )
{
    memset(Act,0,sizeof(Act)); //清零

    memset(Table,0,sizeof(Table));
    Table[y][x]=1; //做已到过标记

    while (!AllComplete) //是否全部搜索完

    {
        Level++;LevelComplete=0; //搜索下一步

        while (!LevelComplete)
        {
            Act[Level]=GetNextAct( ); //改变移动方向

            if (Act[Level]<=MaxAct)
                sum1++;
            if (ActOK( )) //移动方向是否合理

            {
                sum2++;
                Test( ); //测试是否已到目标

                LevelComplete=1; //该步搜索完成

            }
            else
            {
                if (Act[Level]>MaxAct) //已搜索完所有方向

                    Back( ); //回上一步

                if (Level<0) //全部搜索完仍无结果

                    LevelComplete=AllComplete=1; //退出

            }
        }
    }
}

void Test( )
{
    if ((x==TargetX)&&(y==TargetY)) //已到目标

    {
        for (int i=0;i<=Level;i++)
            cout<<(int)Act[i]; //输出结果

        cout<<endl;
        cout<<Level+1<<" "<<sum1<<" "<<sum2<<endl;
        LevelComplete=AllComplete=1; //完成搜索

    }
}

int ActOK( )
{
    int tx=x+dx[Act[Level]-1]; //将到点的x坐标

    int ty=y+dy[Act[Level]-1]; //将到点的y坐标

    if (Act[Level]>MaxAct) //方向错误？

        return 0;
    if ((tx>=SX)||(tx<0)) //x坐标出界？

        return 0;
    if ((ty>=SY)||(ty<0)) //y坐标出界？

        return 0;
    if (Table[ty][tx]==1) //已到过？

        return 0;
    if (Block[ty][tx]==1) //有障碍？

        return 0;
    x=tx;
    y=ty; //移动

    Table[y][x]=1; //做已到过标记

    return 1;
}

void Back( )
{
    x-=dx[Act[Level-1]-1];
    y-=dy[Act[Level-1]-1]; //退回原来的点

    Table[y][x]=0; //清除已到过标记

    Act[Level]=0; //清除方向

    Level--; //回上一层

}

int GetNextAct( ) //找到下一个移动方向。这一段程序有些乱，

//仔细看!

{
    int dis[4];
    int order[4];
    int t=32767;
    int tt=2;
    for (int i=0;i<4;i++)
    dis[i]=abs(x+dx[i]-TargetX)+abs(y+dy[i]-TargetY);
    for (i=0;i<4;i++)
    if (dis[i]<t)
    {
        order[0]=i+1;
        t=dis[i];
    }
    if (Act[Level]==0)
        return order[0];
    order[1]=-1;
    for (i=0;i<4;i++)
    if ((dis[i]==t)&&(i!=(order[0]-1)))
    {
        order[1]=i+1;
        break;
    }
    if (order[1]!=-1)
    {
        for (i=0;i<4;i++)
            if (dis[i]!=t)
            {
                order[tt]=i+1;
                tt++;
            }
    }
    else
    {
        for (i=0;i<4;i++)
        if (dis[i]!=t)
        {
            order[tt-1]=i+1;
            tt++;
        }
    }

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