测试2

回溯法是一种带剪枝的枚举法

回溯法在搜索尝试的过程中得到问题的解，如果当前路径不满足解条件时，则退回到上一层，尝试别的路径，这样就可以达到减少解空间的搜索次数。

回溯法解题步骤（来自百度百科）

  1. 给定问题，确定问题的解空间。
  2. 确定易于搜索的解空间结构，使得回溯法可以方便的搜索整个解空间。
  3. 以深度优先的方式搜索解空间，并在搜索的过程中剪枝避开无效搜索。

哪些问题需要用回溯法来求解？

  1. 排列问题
  2. 求子集问题、组合问题
  3. 迷宫

回溯算法经典问题

问题1:求一个集合的所有子集（不允许重复）leetcode题目：子集

先对数组进行排序，避免[1,2,2]、[2,1,2]这样的重复子集。

回溯法，定义深度优先遍历函数dfs(idx,temp_list)，表示当前遍历到原集合的下标，temp_list表示待加入子集，将dfs(0, [])作为搜索的根节点，进行深度遍历，若当前子集还未加入集合，才进行append操作。

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        res = []
        
        def dfs(idx, temp_list):
            if temp_list not in res:
                res.append(temp_list)
            for i in range(idx,n):
                dfs(i+1, temp_list+[nums[i]])
                
        dfs(0,[])
        return res

进阶：给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。leetcode题目：组合  （组合也是子集的一种）

问题二：全排列（给定一个可包含重复数字的序列，返回所有不重复的全排列）leetcode题目：全排列2

同样，不能有重复的，则需要将原序列排序。

全排列问题，可以用数学方法和回溯法来求解，数学方法时间复杂度小得多。

回溯法求解，全排列中每个排列的长度等于原序列长度，原序列中每个元素只出现一次，所以需要定义一个visit存储当前排列是否已经包含了元素nums[i],如果没有包含nums[i]，则将nums[i]加入当前排列，否则访问下一元素。

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        nums.sort()
        visit = [0]*n
        
        def dfs(temp_list):
            if len(temp_list) == n and temp_list not in res:
                res.append(temp_list)
                return
            for i in range(n):
                if len(temp_list) == 1 and i > 0 and nums[i] ==nums[i-1]:
                    continue   # 重复元素，剪枝，减少搜索，但是这个判断条件只是对树的第一层节点进行了剪枝，应该还可以进行优化
                if not visit[i]:
                    visit[i] = 1
                    dfs(temp_list+[nums[i]])
                    visit[i] = 0
        dfs([])
        return res

数学方法更加简单: 原序列中前i+1个元素的全排列，来源于前i个元素的前排列中的每个排列。

直接上代码：

class Solution:
    def permuteUnique(self, nums):
        nums.sort()
        res = [[]]
        for e in nums:  # 新加一个元素
            temp_res = []
            l = len(res[-1])
            for seq in res: # 对前一步的全排列进行遍历，对每个遍历序列进行插入操作
                for i in range(l, -1, -1):
                    if i < l and seq[i] == e: # 这时插入会导致重复排列，剪枝
                        break  
                    temp_res.append(seq[:i] + [e] + seq[i:])
            res = temp_res
        return res

全排列的生成还有一种交换的方法，“从第一个数字起每个数分别与它后面的数字交换”

算法时间复杂度比较：

下面是数学方法（非递归），上面是回溯法（递归）

问题三：求解数独 leetcode题目：解数独

三个维度约束的排列组合，行，列， 3*3方块，定义三个visit表示约束。从0 ，0 开始验证，寻找未填数的方块，填入数字进行验证，若无法验证，则回溯，直到结束。

class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        visit_a = [[0]*9 for _ in range(9)]
        visit_b = [[0]*9 for _ in range(9)]
        visit_c = [[0]*9 for _ in range(9)]
        
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = int(board[i][j])
                    visit_a[i][num-1] = 1
                    visit_b[j][num-1] = 1
                    visit_c[(i//3) * 3 + (j//3)][num-1] = 1
        
        def dfs(row,col):
            while board[row][col] != '.':
                if col == 8:
                    row, col = row+1, 0
                else:
                    col += 1
                if row == 9: return True
            for k in range(9):
                if not visit_a[row][k] and not visit_b[col][k] and not visit_c[(row//3) * 3 + (col//3)][k]:
                    visit_a[row][k] = 1
                    visit_b[col][k] = 1
                    visit_c[(row//3) * 3 + (col//3)][k] = 1
                    board[row][col] = str(k+1)
                    if dfs(row, col):
                        return True
                    else: # 回溯
                        visit_a[row][k] = 0
                        visit_b[col][k] = 0
                        visit_c[(row//3) * 3 + (col//3)][k] = 0 
                        board[row][col] = '.'
            return False
        dfs(0,0)
View Code

 

进阶：求出所有可能的数独解。

问题四：迷宫问题   leetcode题目：单词搜索

目前碰到过两种迷宫问题

  1. 从[0,0]出发，能否搜到到目标。
  2. 从迷宫任意位置出发，是否能搜索到目标。单词搜索属于这种。相对于1直接调用递归，2需要遍历迷宫的每个元素，找到即立刻返回结果。

单词搜索，题目种要求网格中的单词不能重复使用，因此定义visit[rows][cols]，用于标记。

  • dfs结束条件：找到搜索单词 或 未找到自然退出
  • dfs递归调用条件：
    • 当前节点未被访问
    • 当前节点元素值等于 word[idx]
    • 当前节点下表合法
  • 依次递归调用当前节点的上下左右节点。
class Solution:
    found = False
    def exist(self, board: List[List[str]], word: str) -> bool:
        rows = len(board)
        cols = len(board[0])
        
        def dfs(visit,i,j,idx):
            if idx == len(word):
                self.found = True
                return
            if not self.found and i>=0 and i<rows and j>=0 and j<cols and not visit[i][j] and board[i][j] == word[idx]:
                visit[i][j] = 1
                dfs(visit, i-1, j, idx+1)
                dfs(visit, i+1, j, idx+1)
                dfs(visit, i, j-1, idx+1)
                dfs(visit, i, j+1, idx+1)
                visit[i][j] = 0

        for i in range(rows):
            for j in range(cols):
                visit = [[0]*cols for _ in range(rows)]
                dfs(visit,i,j,0)
                if self.found:    
                    return True
        return self.found
View Code

 

问题五：N皇后    leetcode题目：N皇后

解N皇后问题，网上很多博客都写得很清楚了，这里我主要是用回溯法来求解N皇后。

以8皇后为例，由于8皇后每行有且仅有一个皇后，我们可以用一个数组A来表示8皇后的一个解，A[i] 表示在第i行第的A[i]列放了一个皇后。有了这种表示方法，我们在每次递归时，只需要检查当前节点cur(第cur行的皇后)是否和前面已放好的皇后有冲突。

class Solution:
    count = 0
    def solveNQueens(self, n):
        def change(temp,n):
            result = []
            for e in temp:
                base = ['.']*n
                base[e] = 'Q'
                result.append(''.join(base))
            return result
        res = []
        def queen(A, cur=0):
            self.count += 1
            if cur == len(A):
                res.append(change(A, n))
                return 0
            for col in range(len(A)):
                A[cur], flag = col, True
                for row in range(cur):
                    if A[row] == col or abs(col - A[row]) == cur - row:
                        flag = False
                        break
                if flag:
                    queen(A, cur+1)
        queen([None]*n)
        return res
View Code

 

内容来源于网络如有侵权请私信删除
标签： 算法 数据结构
你还没有登录，请先登录或注册！
  • 还没有人评论，欢迎说说您的想法！

相关课程

六天机器学习入门
3972 98元
英特尔 OpenCV 初级认证课程
8312 0元 限免