算法(深度优先搜索)

  • 时间:
  • 浏览:
  • 来源:互联网

问题引出:输入一个数n,输出1~n的全排列,在运行时间十分有限的情况下(不能直接暴力枚举),该如何解决这个问题呢?
假设现在有3个号码牌,要将其放入有序地三个盒子中,并且每个盒子有且只能放一个号码牌,问有几种放法?
代码分解:
1.往盒子中放入号码牌的操作:

for(i=1;i<=n;i++)
{
    a[step]=i;//将i号扑克牌放入第step个盒子中。
}

数组a是用来表示盒子的,step表示当前正处在第step个小盒子的前面,a[step]=i表示的就是把i号扑克牌放入到第step个盒子中。同时需要注意的是,如果一张扑克牌已经放到别的盒子中了,这时候就不能再把同样的扑克牌放到当前的小盒子中,所以我们需要一个book数组来标记哪些牌已经使用了。

for(i=1;i<=n;i++)
{
    if(book[i]==0)
    {
        a[step]=i;
        book[i]=1;//表示号码牌已经放到别的盒子中去了。
    }
}

以上被拆解出来的过程表示的只是当前step个盒子的处理方法,那么如何从头处理到尾呢?那就移动到下一个盒子,直到遇到最后一个即可。即step+1.

void dfs(int step)//step表示的是现在执行操作的是第几个盒子
{
    for(i=1;i<=n;i++)
    {
        if(book[i]==0)
        {
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    }
    return ;
}

完整代码如:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
int a[10],book[10],n;
void dfs(int step)//step表示的是现在执行操作的是第几个盒子
{
    int i;
    if(step==n+1)
    {
        for(i=0;i<=n;i++)
        {
            printf("%d",a[i]);
        }
        printf("\n");

        return ;//回到上次执行dfs算法的地方
    }
    //此时执行操作的是step个盒子,要按照1,2,3~n的顺序依次存放
    for(i=1;i<=n;i++)
    {
        if(book[i]==0)
        {
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    dfs(1);
    return 0;
}

这种算法被称为深度优先搜索(depth first search)
其基本模型为

void dfs(int step)
{
    判断边界
    尝试每一种可能 for(i=1;i<=n;i++)
    {
        继续下一步dfs(step+1);
    }
    返回上一次
}

理解深度优先搜索的关键在于解决“当下该如何做”。至于“下一步应该怎么做”则与当下该怎么做是一样的。比如上述的dfs函数的作用就是解决当在第step个盒子的时候应该要做什么,通常的方法就是把所有有可能的答案都尝试一遍,(一般使用for循环来遍历),当前这一步解决了之后就dfs(step+1)直到遇到边界为止。而这正体现了递归的想法,每次执行的方法和上一步都是一致的,即将一个大问题分解成方法一直的若干个小问题。
枚举问题中,对于多次枚举的算法优化。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
int a[10],book[10],n,count=0;

void dfs(int step)
{
    int i;
    if(step==n+1)
    {
        if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9])
        {
            count++;
            printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
        }
        return ;
    }
    for(i=1;i<=9;i++)
    {
        if(book[i]==0)
        {
            a[step]=i;
            book[i]=1;
            dfs(step+1);
            book[i]=0;
        }
    }
    return ;
}
int main()
{
    scanf("%d",&n);
    dfs(1);
    printf("count=%d",count/2);
    return 0;
}

迷宫问题(深度优先算法类型)
现有一个迷宫,有n行m列组成,n<50,m<50,每个单元格要么是空地,要么是障碍物,现在要找到一条从迷宫的起点通往目标位置的最短路径,规定障碍物无法通过,而且人不能走出地图之外。
思路是:只能一个个去尝试,直到走不通的时候再回到这里,对于尝试的方向顺序,我们可以认为规定,按照顺时针的方向来尝试(即右、下、左、上的顺序来尝试),同时需要注意的是,并不是到达目标地点就结束了,而是要把所有可能都尝试一遍,直到找到最短的路径才可以。由此观之,需要三个参数,x,y用来记录人的坐标以及规定边界,step用来记录步数。

void dfs(int x,int y,int step)
{
 return;
}

边界的判定

void dfs(int x,int y,int step)
{
    if(x==p&&y==q)
    {
        if(step<min)
        {
            min=step;
            return ;//返回上一次的地方同时继续尝试新的可能
        }
    }
    return ;
}

dfs主体部分

for(k=0;k<4;k++)
{
    //计算下一个点的坐标
    tx=x+next[k][0];
    ty=y+next[k][1];
    if(tx<1||tx>n||ty<1||ty>m)//判断是否越界了
    {
        continue;
    }
    //判断这个点是不是障碍物,或者已经在路径中了。
    if(a[tx][ty]==0&&book[tx][ty]==0)
    {
        book[tx][ty]=1;
        dfs(tx,ty,step+1);
        book[tx][ty]=0;
        
    }
}

迷宫问题解:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>
int n,m,p,q,min=9999999;
int a[51][51],book[51][51];

void dfs(int x,int y,int step)
{
    int next[4][2]={
    {0,1},//向右走
    {1,0},//向下走
    {0,-1},//向左走
    {-1,0}//向上走
    };
    int tx,ty,k;
    if(x==p&&y==q)
    {
        if(step<min)
        {
            min=step;
        }
        return;//回到上一次调用dfs的地方
    }
    for(k=0;k<4;k++)//枚举四种走法
    {
        tx=x+next[k][0];
        ty=y+next[k][1];
        //接着判断是否越界
        if(tx<1||tx>n||ty<1||ty>m)
        {
            continue;
        }
        if(a[tx][ty]==0&&book[tx][ty]==0)//用来判定这个点是否是障碍物,或者已经在路径中了
        {
            book[tx][ty]=1;
            dfs(tx,ty,step+1);
            book[tx][ty]=0;
        }
    }
    return ;
}
int main()
{
    int i,j,start_x,start_y;
    //读入n,m,n为行,m为列
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d%d%d%d",&start_x,&start_y,&p,&q);
    book[start_x][start_y]=1;//标记起点已经在路径中,避免重走
    dfs(start_x,start_y,0);
    printf("%d",min);
    return 0;
}

本文链接http://www.hatan.cn/news/show-69551.html