回溯算法详解（python)

2024-07-06 17:04| 来源: 网络整理| 查看: 265

回溯算法详解（python)

从本质上来说，回溯算法就是深度优先搜索（DFS)。而且，回溯算法和动态规划也很像，它们都是“分而治之”的思想，但是动态规划具有重叠子问题的特性，可以通过 dp table 优化，将递归树大幅剪枝。而那些无法大幅剪枝，只能暴力求解的动态规划就是回溯算法了。

对于回溯算法来说，最重要的是“路径”和“选择”，路径就是已经做出来的选择的集合。当回溯算法进行到最后时，如果其满足约束条件，那就把它加入解集，否则，回溯（这也是回溯算法的由来）。

对于回溯算法来说，一般是如下模式：

results = [] def backtrack(路径，选择列表): if 路径结束，满足约束条件： results.append(路径) return if 路径结束，不满足约束条件: return for 选择 in 选择列表：更新路径和选择列表 backtrack（新的路径，新的选择列表）

return results

下面用三个算法题作为示例

leetcode39 组合总和给定一个无重复元素的数组 candidates和一个目标数 target，找出 candidates 中所有可以使数字之和为 target 的组合

说明

所有数字（包括 target)都是正整数解集不能包含重复的组合 candidates 中的数字可以无限制重复被选取示例输入：candidates = [2,3,5].target = 8 输出：[[2,2,2,2],[2,3,3],[3,5]]

def combination(candidate:List[int], target: int)->List[List[int]]: n = len(candidates) candidates.sort() results=[]

# i 和 sum是当前的选择，track 是路径 def backtrack(i,sum,track): # 路径结束，不满足约束条件 if sum > target or i == n: return # 路径结束，满足约束条件 if sum == target: results.append(track) return # 更新选择列表和路径，递归 # 在这个问题中，选择只有两种，是否将当前数字纳入路径 backtrack(i, sum+candidates[i], track+[[candidates[i]]) backtrack(i+1, sum, track) backtrack(0,0,[]) return results leetcode46 全排列给定一个没有重复数字的序列，返回其所有可能的全排列示例：输入：[1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

def permute(nums:List[int]) -> List[List[int]]: nums.sort() results=[]

#nums是选择列表，track 是路径 def backtrack(nums,track): #路径结束满足约束条件 if not nums: results.append(track) return #更新选择列表和路径，递归 #在这个问题中，选择有 n-len(track)这么多种 for i in range(len(nums))： traceback(nums[:i]+nums[i+1:],track+[nums[i]]) backtrack(nums,[]) return results leetcode 51 N 皇后问题在 N*N的棋盘上摆上 N个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，求摆法。说明：

给定一个整数 n，返回所有不同的 n 皇后的问题解决方案每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中’Q’和’.'分别代表了皇后和空位示例输入：4 输出：[[".Q…","…Q",“Q…”,"…Q."],["…Q.",“Q…”,"…Q",".Q…"]] def solveNQueens(n:int)->List[list[str]]:

#首先我们明确一下皇后的位置如何表示，皇后在 track 中的索引代表它所处的列，它的值表示它所在的行 #比如 track[1]=2,表明第二行第一列放置一个皇后 results=[] #track 表示路径，xy_dif 和 xy_sum 用来计算两个皇后是否在同一斜线上 def backtrack(track,xy_dif,xy_sum): p = len(track) if p==n: results.append(track) return for q in range(n): #1. 两个皇后不能处在同一列，则它们的索引必然不同（显然） #2. 两个皇后不能处在同一行，则它们的值必然不同 #3. 两个皇后不能处在左上-右下这种位置，则它们横纵坐标之差必然不同（举例，如(3,4)和（4,5） #4. 两个皇后不能处在右上-左下这种位置，则它们横纵坐标之和必然不同（举例，如(3,4)和（4,3) if (q not in track) and (p-q not in xy_dif) and （p+q not in xy_sum): backtrack(track+[q],xy_dif+[p-q],xy_sum+[p+q]) backtrack([],[],[]) return [['.'*i + 'Q' + '.' *(n-i-1) for i in result] for result in results]

总结总而言之，碰到回溯算法的题目，首先弄清楚回溯的条件（也就是退出条件，得出一个解或者确定无法得出一个解），其次就是在当前状态，选择列表和路径是什么，以及选择完毕，路径和选择列表如何更新。

【本文地址】

公司简介

联系我们