首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >深度优先搜索

深度优先搜索

作者头像
可爱见见
发布2020-02-25 18:50:00
8520
发布2020-02-25 18:50:00
举报
文章被收录于专栏:卡尼慕卡尼慕

深度优先搜索,简称dfs。我们可以将它跟递归联合在一起。

dfs与递归

先回顾一下递归。

我们使用递归完成斐波那契数列的计算:

int fib(int n){
    if(n == 1 || n == 2){
        return 1;   
    }
    return fib(n - 1) + fib(n - 2);
}

以上递归实现斐波那契实际上就是按照深度优先的方式进行搜索。也就是 “一条路走到黑” 。注意:这里的搜索指的是一种穷举方式,把可行的方案都列举出来,不断尝试,直到找到问题的解。

以上即为Fib(5)的计算过程,我们发现实际上对应着一棵树,这棵树被称为搜索树

深度优先搜索与递归的区别:

  1. 深度优先搜索是一种算法,更注重思想。
  2. 递归是一种基于编程语言的实现方式。
  3. 深度优先搜索可以使用递归实现!当然也就存在非递归的的方式实现搜索。

dfs与迷宫游戏

dfs解法:首先找到起点s,走到每个点时,按照左、下、右、上的顺序尝试。每走到下一个点以后,我们把这个点当作起点s,继续顺序尝试。如果某个点上下左右四个方向都尝试过,便回到走到这个点的之前点,称为回溯。然后继续尝试其他方向,直到所有点都尝试过上下左右四个方向。

代码实现:

  1. 首先要处理好边界条件,即什么时候搜索结束。 if(maze[x][y] == 'T'){//T是终点 return true; }
  2. 另外,为了方式走回头路,我们还需要标记当前点已经走过了,所以需要一个vis数组来做标记。同时为了标记出来路径,我们使用”m“进行地图上的标记。 vis[x][y] = 1; maze[x][y] = 'm';
  3. 前面两步已经完成当前节点的操作了,接下来是要进行走下一步的操作。先往左走看看。 int tx = x - 1, ty = y; if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){ //在地图内,非障碍物,无访问过 if(dfs(tx, ty)){ return true; } }
  4. 向下走。 int tx = x, ty = y - 1; if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){ //在地图内,非障碍物,无访问过 if(dfs(tx, ty)){ return true; } }
  5. 向右走。 int tx = x + 1, ty = y; if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){ //在地图内,非障碍物,无访问过 if(dfs(tx, ty)){ return true; } }
  6. 向上走。 int tx = x, ty = y + 1; if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){ //在地图内,非障碍物,无访问过 if(dfs(tx, ty)){ return true; } }
  7. 如果路走不通的话,一定要取消一下m标记,标记成”.“障碍物。 vis[x][y] = 0; maze[x][y] = '.'; return false;
  8. 最后写一下 in(int x, int y) 函数,来判断是否在地图内。

完整代码

//迷宫
#include<iostream>
using namespace std;
string maze[110];
bool vis[110][110];
int n, m;
bool in(int x, int y){
    return 0 <= x && x < n && 0 <= y && y < m;
}
bool dfs(int x, int y){
    if(maze[x][y] == 'T'){//T是终点 
        return true;
    }
    vis[x][y] = 1;
    maze[x][y] = 'm';
    int tx = x - 1, ty = y;
    if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
        //在地图内,非障碍物,无访问过
         if(dfs(tx, ty)){
            return true;
         }
    }
    int tx = x, ty = y - 1;
    if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
        //在地图内,非障碍物,无访问过
         if(dfs(tx, ty)){
            return true;
         }
    }
    int tx = x + 1, ty = y;
    if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
    //在地图内,非障碍物,无访问过
        if(dfs(tx, ty)){
             return true;
        }
    }
    int tx = x, ty = y + 1;
    if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
        //在地图内,非障碍物,无访问过
        if(dfs(tx, ty)){
            return true;
        }
    }
    vis[x][y] = 0;
    maze[x][y] = '.';
    return false;
} 
int main(){
    //输入地图
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin>>maze[i];
    }
    int x, y;
    //找到起始点 
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(maze[i][j] == 'S'){
                x = i; y = j;
            }
        }
    }
    if(dfs(x, y)){
        //打印
        for(int i = 0; i < n; i++){
            cout << maze[i] <<endl;
        } 
    }else{
        cout<<"No!"<<endl;
    }
    return 0;
}

然而我们发现代码比较长,而且有很多重复的地方比较冗余。重复的地方在于下一步的运行方向。那么我们可以简化一下代码。

  1. 首先有四个方向,每一个方向是使用二维向量表示。因此我们可以建立一个4*2的数据来标记我们要前进的方向。 int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; 这里建议使用逆时针或者顺时针的记录,方便使用向左转向右转的实现。
  2. 然后使用for循环依次考虑四个方向。 for(int i = 0; i < 4; i++){ int tx = x + dir[i][0]; int ty = y + dir[i][1]; if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){ //在地图内,非障碍物,无访问过 if(dfs(tx, ty)){ return true; } } }

从而减少了代码量。

最短路径

前面我们只是寻找了是否有可行的路径,现在需要求最少多少步即可到达。

我们使用一个参数来记录前面参数以及走了多少步:step。

int ans = 10000000000;//结果
void dfs(int x, int y, int step){
    if(maze[x][y] == 'T'){//T是终点 
        if(step < ans){
            ans = step;
        }
        return;
    }
    vis[x][y] = 1;
    maze[x][y] = 'm';
    for(int i = 0; i < 4; i++){
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if(in(tx, ty) && maze[tx][ty] != '*' && !vis[tx][ty]){
            //在地图内,非障碍物,无访问过
            dfs(tx, ty, step + 1)
        }
    }
    vis[x][y] = 0;//取消标记 
} 

ok,明天继续。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-01-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 卡尼慕 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • dfs与递归
  • dfs与迷宫游戏
  • 最短路径
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档