草庐IT

深度优先搜索算法-dfs讲解

Tstrの小窝 2023-03-28 原文

迷宫问题

有一个迷宫：

S**.
....
***T


（其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。你需要从S出发走到T，每次只能向上下左右相邻的位置移动，不能走出地图，也不能穿过墙壁，每个点只能通过一次。）

现在需要你求出是否可以走出这个迷宫

我们将这个走迷宫过程称为dfs（深度优先搜索）算法。

思路

当我们搜索到了某一个点，有这样3种情况：

1.当前我们所在的格子就是终点。

2.如果不是终点，我们枚举向上、向下、向左、向右四个方向，依次去判断它旁边的四个点是否可以作为下一步合法的目标点，如果可以，那么我们就进行这一步，走到目标点，然后继续进行操作。

3.当然也有可能我们走到了“死胡同”里（上方、下方、左方、右方四个点都不是合法的目标点），那么我们就回退一步，然后从上一步所在的那个格子向其他未尝试的方向继续枚举。

怎样才能算“合法的目标点”？

1.必须在所给定的迷宫范围内

2.不能是迷宫边界或墙。

3.这个点在搜索过程中没有被走过（这样做是因为，如果一个点被允许多次访问，那么肯定会出现死循环的情况——在两个点之间来回走。）

实现代码

#include <iostream>
using namespace std;
int n, m;
string maze[105];
int sx, sy;
bool vis[105][105];
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};//四个方向的方向数组
bool in(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}
bool dfs(int x, int y) {
    vis[x][y] = 1;//点已走过标记
    if (maze[x][y] == 'T') {//到达终点
        return 1;
    }
    for (int i = 0; i < 4; ++i) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (in(tx, ty) && !vis[tx][ty] && maze[tx][ty] != '*') {
            /*
            1.in(tx, ty) : 即将要访问的点在迷宫内
            2.!vis[tx][ty] : 点没有走过
            3.maze[tx][ty] != '*' : 不是墙
            */
            if (dfs(tx, ty)) {
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> maze[i];
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (maze[i][j] == 'S') {
                //记录起点的坐标
                sx = i;
                sy = j;
            }
        }
    }
    if (dfs(sx, sy)) {
        puts("Yes");
    } else {
        puts("No");
    }
    return 0;
}

深搜的剪枝优化

可行性剪枝

剪枝，顾名思义，就是通过一些判断，砍掉搜索树上不必要的子树。有时候，在搜索过程中我们会发现某个结点对应的子树的状态都不是我们要的结果，那么我们其实没必要对这个分支进行搜索，直接“砍掉”这棵子树（直接 return退出），就是"剪枝"。

我们举一个例子：

给定n个整数，要求选出K个数，使得选出来的K个数的和为sum。

 

 

 

如上图，当k=2的时候，如果已经选了2个数，再往后选更多的数是没有意义的。所以我们可以直接减去这个搜索分支，对应上图中的剪刀减去的那棵子树。

又比如，如果所有的数都是正数，如果一旦发现当前和的值都已经大于sum了，那么之后不管怎么选，选择数的和都不可能是sum了，就可以直接终止这个分支的搜索。

例：从1,2,3,⋯,30这30个数中选8个数，使得和为200。

我们可以加如下剪枝

if (数字个数 > 8) return ;
if (总和 > 200) return ;

经过尝逝后发现：

没有剪枝

 

 加剪枝：

 

最优性剪枝

我们再看一个问题：

有一个n×m大小的迷宫。其中字符S表示起点，字符T表示终点，字符*表示墙壁，字符.表示平地。你需要从S出发走到T，每次只能向上下左右相邻的位置移动，并且不能走出地图，也不能走进墙壁。保证迷宫至少存在一种可行的路径，输出S走到T的最少步数。

对于求最优解（从起点到终点的最小步数）这种问题，通常可以用最优性剪枝，比如在求解迷宫最短路的时候，如果发现当前的步数已经超过了当前最优解，那从当前状态开始的搜索都是多余的，因为这样搜索下去永远都搜不到更优的解。通过这样的剪枝，可以省去大量冗余的计算。

此外，在搜索是否有可行解的过程中，一旦找到了一组可行解，后面所有的搜索都不必再进行了，这算是最优性剪枝的一个特例。

现在我们考虑用dfs来解决这个问题，第一个搜到的答案res并不一定是正解，但是正解一定小于等于res。于是如果当前步数大于等于res就直接剪枝。

在dfs函数内加入如下代码

if (目前步数 >= res) return ;
if (目前所处的位置字符 == 'T') {
    答案 = 目前步数;//因为我们在刚才已经进行了一次剪枝，所以我们现在是可以保证目前答案大于之前答案的
    return ;
}

好啦，到这里就结束了捏~

求赞qwq

dfs深度优先spanclasscolor算法与数据结构

有关深度优先搜索算法-dfs讲解的更多相关文章

  1. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  2. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD

  3. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  4. 深度学习部署：Windows安装pycocotools报错解决方法 - 2

    深度学习部署：Windows安装pycocotools报错解决方法1.pycocotools库的简介2.pycocotools安装的坑3.解决办法更多Ai资讯：公主号AiCharm本系列是作者在跑一些深度学习实例时，遇到的各种各样的问题及解决办法，希望能够帮助到大家。ERROR:Commanderroredoutwithexitstatus1:'D:\Anaconda3\python.exe'-u-c'importsys,setuptools,tokenize;sys.argv[0]='"'"'C:\\Users\\46653\\AppData\\Local\\Temp\\pip-instal

  5. ruby - 如何搜索有用的 ruby - 2

    寻找有用的ruby的好网站是什么？ 最佳答案 AgileWebDevelopment列出插件(虽然不是ruby​​gems，我不确定为什么)，并允许人们对它们进行评级。RubyToolbox按类别列出gem并比较它们的受欢迎程度。Rubygems有一个搜索框。StackOverflow对最有用的rails插件和ruby​​gems有疑问。 关于ruby-如何搜索有用的ruby，我们在StackOverflow上找到一个类似的问题： https://stacko

  6. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  7. ruby - Ruby 中的必应搜索 API - 2

    我读了"BingSearchAPI-QuickStart"但我不知道如何在Ruby中发出这个http请求(Weary)如何在Ruby中翻译“Stream_context_create()”？这是什么意思？"BingSearchAPI-QuickStart"我想使用RubySDK，但我发现那些已被弃用前(Rbing)https://github.com/mikedemers/rbing您知道Bing搜索API的最新包装器(仅限Web的结果)吗？ 最佳答案 好吧，经过一个小时的挫折，我想出了一个办法来做到这一点。这段代码很糟糕，因为它是

  8. Ruby#index 方法 VS 二进制搜索 - 2

    给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

  9. ruby - 使用 Ransack 搜索枚举字段 - 2

    我有一个表，'jobs'和一个枚举字段'status'。status具有以下枚举集:enumstatus:[:draft,:active,:archived]使用ransack，我如何过滤表，比如说，所有事件记录？ 最佳答案 你可以像这样在模型中声明自己的掠夺者:ransacker:status,formatter:proc{|v|statuses[v]}do|parent|parent.table[:status]end然后您可以使用默认的搜索语法_eq来检查相等性，如下所示:Model.ransack(status_eq:'ac

  10. ruby-on-rails - Rails 4 postgres 全文搜索错误(范围) - 2

    我一直在使用postgres关注railscast的全文搜索，但我不断收到以下错误#的未定义局部变量或方法“作用域”我关注了railscast确切地。我安装了所有正确的gem。(pg_search，pg)。这是我的代码文章Controller(我在这里也使用acts_as_taggable)defindex@articles=Article.text_search(params[:query]).page(params[:page]).per_page(3)ifparams[:tag]@articles=Article.tagged_with(params[:tag])else@art

随机推荐