查看: 543|回复: 3
收起左侧

[转CS-自学] 请教backtracking, dfs, bfs,dp具体算法实现

|只看干货
nanoice | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   82% (5217)
 
 
17% (1126)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 nanoice 于 2022-8-10 10:09 编辑

这个帖子主要是从具体代码角度来看这几种算法,不是数学角度,本人CS小白,有几个问题想问一下大家:先简单确认一下概念,dfs就是深度优先BST里直接一条叉搜索到头然后一点一点往回,backtracking就是dfs里加一些constraint,不满足直接prune branches然后break,bfs就是广度优先BST里先看最顶部node之下能分叉到哪几种选择,然后看每个node都有哪几种选择,一点一点往下延伸,dfs,backtracking,bfs一般是罗列所有可能性,而dp主要是用于优化,大部分题目中都是create一个true false dp array,遍历满足条件就true不然就是default false,return dp[-1]一般就是结果。我其实主要想问的是backtracking和dfs的具体区别,我看网上有人说backtracking是dfs的一种,有人说dfs是backtracking的一种,所以我很混乱。-baidu 1point3acres

这样,我拿一道比较经典的recursive题目来举个例子:
比如给定一个array = [1,2,3]
要求return所有subset的可能性:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 不限定先后这样. Χ
我想出了三种解法,用python简单写一下,都是按照我认为的文字概念写出来的哈:
1. 我认为的bfs:         
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:. Waral dи,
        ans = []
        def bfs(n, cur_index, cur_list):


            if n == len(cur_list):
                ans.append(cur_list.copy())
. 1point3acres.com
            for i in range(cur_index,len(nums)):
                cur_list.append(nums)
                bfs(n,i+1,cur_list)
                cur_list.pop()
        for i in range(len(nums)+1):
            bfs(i,0,[])
        return ans

. 1point3acres
由于我前面加了一个限制n 就是每次循环中只append和i保持一样长度的array,这样得到的结果就是[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]],然后遍历到头就pop(),不知道这算bfs还是dfs,我有个朋友说这个也是dfs。。。但我觉得这是bfs吧,return结果先把len = 1的subset列进去了,然后是len = 2,最后是3。。。所以这是dfs还是bfs请大神解答下。

2. 我认为真正的dfs解法:
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans=[]
        def dfs(l,cur):
            ans.append(l)
            for i in range(cur, len(nums)):
                temp = l.copy()
                temp.append(nums)
                dfs(temp,i+1)
        dfs([],0)
        return ans
每次都在遍历中通过新定义一个temporary array来进行接下来的递归,这样return出来的结果是[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]],每次都是把最长的可能性append之后才回到之前一步的原始状态的array “l”。

3. 我认为的backtracking:.
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def backtracking(cur,s):. ----
.
            ans.append(cur.copy())
            for i in range(s, len(nums)):
                cur.append(nums)
                backtracking(cur, i+1). Waral dи,
                cur.pop()
-baidu 1point3acres
        backtracking([],0)
        return ans. Χ
整体思路和上面的dfs差不多,但是这个相当于直接用方法2中的l不新定义temporary list来直接进行每一次递归,但是递归至最深后通过pop()来prune tree回归到之前状态的未append新数字的current_list,这样return出来的结果也是[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]],和dfs得到的subarray的顺序是一样的。
请问我这么理解的对吗?单纯想求大佬从代码角度来解释一下定义,谢谢!

上一篇:艺术生转码/去美发展求指点
下一篇:转码之前你应该知道的: Job-Oriented Programming面向就业转码思路
阵雨 2022-8-11 03:31:25 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (2117)
 
 
5% (129)    👎
1 本身的确就是个 dfs,因为你还没有 breath first 就往下走了。。

参考 https://www.techiedelight.com/breadth-first-search/ 有 iterative 和 recursive 的 bfs
回复

使用道具 举报

 楼主| nanoice 2022-8-11 03:48:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   82% (5217)
 
 
17% (1126)    👎
阵雨 发表于 2022-8-10 12:31
1 本身的确就是个 dfs,因为你还没有 breath first 就往下走了。。

参考 https://www.techiedelight.com ...

另外请问一下2和3里dfs和backtracking有区别吗?我上面的理解对吗?就是backtracking一般会有pop()或者del 之类的,而普通dfs不需要通过prune吗?还是说backtracking和dfs就是包含和被包含的关系呢?🤔
回复

使用道具 举报

阵雨 2022-8-11 04:12:20 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (2117)
 
 
5% (129)    👎
nanoice 发表于 2022-8-10 12:48
另外请问一下2和3里dfs和backtracking有区别吗?我上面的理解对吗?就是backtracking一般会有pop()或者de ...

不用太纠结。。一般普遍认为 backtracking 是 dfs 的一个特例而已。。

pop 和 del 不一定必须,因为可以通过 idx+1, cur+nums 这种来实现。。。
.--
一般 backtrack 就是 dfs 加上一些返回条件然后继续测试其他。。所以可以认为是 dfs 的一个特例
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表