欢迎大家来到IT世界,在知识的湖畔探索吧!
回溯算法导读
回溯法(back tracking)(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
回溯算法思路
1:定义问题的解空间(搜索中动态生成)
2:确定搜索的解空间结构(一般为树形结构或图)
3:以深度优先的方式搜索解空间,搜索中用剪枝函数避免无效搜索
剪枝函数:
1:用约束函数在扩展节点处减去不满足约束条件的子树;
2:用限界函数减去不能得到最优解的子树
1.回溯算法之全排列
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
代码实现:
def permute(nums): """ 全排列 :param nums 输入 nums = [1,2,3] :return: 输出[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] """ #保存满足条件的解 #第1步:定义结果集变量 res = [] nums_len = len(nums) #第2步:定义回溯方法 def backtrack(visitedItems,leftNums): """ :param visitedItems: 已遍历的元素 :param leftNums:剩下的数组(待遍历的数组) :return: """ if len(visitedItems) == nums_len: #当遍历的元素数目等于输入nums的数组长度时,寻找到解,添加到res数组 res.append(visitedItems) #递归出口,【注意:递归的结束一定 要有return】 return #递归回溯方法backtrack for i in range(len(leftNums)): """ visitedItems+[leftNums[i]]:已遍历的数组追加 leftNums[:i] + leftNums[i+1:]:表示剩余的数组,即除掉当前的元素 """ backtrack(visitedItems+[leftNums[i]],leftNums[:i] + leftNums[i+1:]) #调用内部回溯算法 backtrack([],nums) #返回结果集 return res
欢迎大家来到IT世界,在知识的湖畔探索吧!
2.回溯算法之数组组合
A = [1, 2, 3, 3] B = [2, 3, 3, 4] C = [2, 3, 3, 4]
集合A,B,C,各取一个元素,获取所有组合
代码实现
欢迎大家来到IT世界,在知识的湖畔探索吧!def combinations(A,B,C): """ 集合A,B,C,各取一个元素,获取所有组合 A = [1, 2, 3, 3] B = [2, 3, 3, 4] C = [2, 3, 3, 4] :param A: :param B: :param C: :return: """ #返回的结果集 res = [] def backtrack(vistedItems): """ :param vistedItems: 已遍历的元素 :return: """ if len(vistedItems) == 3: # 当遍历的元素数目等于3,寻找到解,添加到res数组 res.append(vistedItems) # 递归出口,【注意:递归的结束一定 要有return】 return #获取(A,B,C)接下来需要遍历的数组 candidates = construct_candidates(vistedItems) for candidate in candidates: #vistedItems+[candidate]已遍历的数组追加 backtrack(vistedItems+[candidate]) def construct_candidates(vistedItems): """ 根据已遍历的元素,获取下一个需要遍历的数组 :param vistedItems: 已遍历的元素 :return: """ #默认A数组 array = A #已遍历元素已有一个,则接下来遍历B数组 if len(vistedItems) == 1: array = B #已遍历元素有2个,则接下来遍历C数组 if len(vistedItems) == 2: array = C #返回接下来需要遍历的数组 return array #调用内部回溯算法 backtrack([]) #返回结果集 return res
3.回溯算法之数字组合
数字组合,注意数组的值都是整数
输入: nums = [2,3,6,7], target = 7,
所求解集为: [ [7], [2,2,3] ]
代码实现:
def combinationArray(nums,target): """ 数字组合,注意数组的值都是整数 输入: nums = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ] :param nums: :param target: :return: """ #第1步:定义结果集变量 res = [] def backtrack(visitedNums): """ :param visitedNums: 已遍历元素 :return: """ sumValue = sum(visitedNums) #和值>=target值退出(元素都为正数) if sumValue >= target: if sumValue == target: #满足条件,追加结果集 res.append(visitedNums) # 递归出口,【注意:递归的结束一定 要有return】 return #遍历递归 for num in nums: backtrack(visitedNums+[num]) #调用内部回溯算法 backtrack([]) #返回结果集 return res
4.回溯算法之求数组子集
求数组的子集 [1,2,3]的子集:
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
代码实现:
欢迎大家来到IT世界,在知识的湖畔探索吧!def subsets(nums): """ 求数组的子集 [1,2,3]的子集[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]] :param nums: :return: """ #返回的结果集 res = [] def backtrack(visitedNums,leftNums): """ :param visitedNums: 已遍历的元素 :param leftNums: 剩余还需遍历的元素 :return: """ #追加结果 res.append(visitedNums) #剩余需要访问的数组为空即递归出口,【注意:递归的结束一定 要有return】 if len(leftNums) == 0: return #递归遍历 for i in range(len(leftNums)): """ visitedNums+[leftNums[i]]:已访问的元素追加 leftNums[i+1:]:剩余可访问的数组 """ backtrack(visitedNums+[leftNums[i]],leftNums[i+1:]) #调用内部回溯方法 backtrack([],nums) #返回结果集 return res
最后附上回溯算法代码实现模板
def functionName(params): #第1步:定义返回的结果集 res = [] #第2步:定义回溯方法 def backtrack(visitedNums,leftNums): """ :param visitedNums: 已遍历的元素【必填】 :param leftNums: 剩余还需遍历的元素【非必填】 :return: """ #第3步:追加满足条件的结果集 if conditionA:#约束结果条件 res.append(visitedNums) #第4步:寻找递归出口,【注意:递归的结束一定 要有return】 if conditionB:#退出条件 return #【必须有return】 #第5步:递归遍历 for i in range(arrayA):#具体遍历对象,需根据需求调整 """ visitedNums+[leftNums[i]]:已访问的元素追加 leftNums[i+1:]:剩余可访问的数组 #非必填 """ backtrack(visitedNums+[leftNums[i]],leftNums[i+1:]) #第6步:调用内部回溯方法 backtrack([],nums) #第7步:返回结果集 return res
如有什么不正之处,欢迎留言纠正
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://itzsg.com/31552.html