美文网首页算法与数据结构
算法之回溯算法详解

算法之回溯算法详解

作者: 阿旭123 | 来源:发表于2020-12-11 20:17 被阅读0次

    回溯算法

    定义

    回溯算法实际上基于DFS(深度优先搜索)的一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回到上一个状态,尝试其他的路径,这种走不通就退回再走的技术为回溯法;满足回溯条件的某个状态的点称为“回溯点”。

    回溯相关问题

    1. DFS 和回溯算法区别

    DFS 是一个劲的往某一个方向搜索,直到到达最底层,而回溯算法建立在 DFS 基础之上的,但不同的是在搜索过程中,达到结束条件后,恢复状态,回溯上一层,再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置

    1. 何时使用回溯算法

    当问题碰到走不通的路径,需要"回头",以此来查找出所有的解的时候,使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通),要撤销选择,回退到上一个状态,继续尝试,直到找出所有解为止。

    1. 回溯算法的基本步骤
    • 找到状态变量(回溯函数的参数)
    • 依据题意定义递归结束条件
    • 找准选择列表(与函数参数相关),与第一步紧密关联
    • 判断是否需要剪枝,即提前将不符合条件的路径排除掉
    • 作出选择,递归调用,进入下一层
    • 撤销选择
    1. 回溯算法类的题型有哪些
    • 子集、组合类问题
    • 排列类问题
    • 搜索、N皇后类问题、

    注意:子集、组合是无关顺序的,而排列是和元素顺序有关的,如 [1,2] 和 [2,1] 是同一个组合(子集),但 [1,2] 和 [2,1] 是两种不一样的排列!!!!

    回溯算法的通用模板

    result = []
    def backtrack(路径, 选择列表):
        if 满足结束条件:
            result.add(路径)
            return
        for 选择 in 选择列表:
            做选择
            backtrack(路径, 选择列表)
            撤销选择
    

    题目举例

    Leetcode78.子集

    问题描述

    给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

    说明:解集不能包含重复的子集。

    示例

    输入: nums = [1,2,3]
    输出:
    [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
    ]

    python代码题解

    套用上述回溯算法的模板,path表示已选择的路径,for i in range(start, len(nums))表示当前能够选择的列表元素,注意对于组合类问题不能够选择前面已经选择过的元素,因为会存在重复结果,因此必须有一个start参数来控制每一轮能够选择的元素[start, len(nums)]

    class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
            def backtrack(nums, path, start):
                # 将path添加到res结果中
                res.append(path.copy())
                # 当前能够选择的参数列表
                for i in range(start, len(nums)):
                    # 做选择
                    path.append(nums[i])
                    backtrack(nums, path, i+1)
                    # 撤销选择
                    path.pop()
            res = []
            backtrack(nums, [], 0)
            return res
    

    Leetcode77.组合

    问题描述

    给定两个整数 nk,返回 1 ... n 中所有可能的 k 个数的组合。

    示例

    输入: n = 4, k = 2
    输出:
    [
    [2,4],
    [3,4],
    [2,3],
    [1,2],
    [1,3],
    [1,4],
    ]

    python代码题解

    本题与上一题基本相同,都是属于组合类问题,只是递归的终止条件不同,本题的终止条件是当路径长度为k时len(track) == k,将结果添加到res中。

    套用上述回溯算法的模板,track表示已选择的路径,for i in range(start, n+1)表示当前能够选择的列表元素,注意start是从1开始的,应为题目中指明能够选择的数为1...n

    class Solution:
        def combine(self, n: int, k: int) -> List[List[int]]:
            # 数的选择范围在1-n
            def backtrack(n,k,start,track):
                if len(track) == k:
                    res.append(track.copy())
                    return
                # 注意i从start开始递增
                for i in range(start, n+1):
                    # 做选择
                    track.append(i)
                    backtrack(n,k,i+1,track)
                    # 撤销选择
                    track.pop()
            res = []
            track = []
            backtrack(n,k,1,track)
            return res
    

    通过上述讲解,读者应该对回溯算法的概念以及模板套路有一个基本的认识,回溯的关键在于选择与撤销选择的过程,读者可以仔细体会一下 ,相信一定会有所收获。后续会继续更新关于回溯算法的相关题解,欢迎持续关注!

    如果喜欢作者,欢迎点赞、收藏及关注,谢谢!

    相关文章

      网友评论

        本文标题:算法之回溯算法详解

        本文链接:https://www.haomeiwen.com/subject/usrsgktx.html