当前位置: 首页 > news >正文

【算法】(Python)回溯算法

回溯算法:

  • 回溯算法是一种算法思想。
  • 采用“深度优先搜索(dfs,depth first search)”。
  • 采用“尝试”和“回溯”的策略。尝试搜索所有可能的解决方案,遇到不满足条件的撤销选择、回退到回溯点(满足回溯条件的某个状态的点)、尝试其他方法。
  • 基本思想:从一条路往前走,能进则进,不能进则退回来,换条路再试。
  • 类似穷举法,但有剪枝的功能。剪枝:去除不满足约束条件的尝试、提高效率。
  • 通常用递归实现。(也可以用迭代实现,但设计复杂)

回溯算法的伪代码模板:

res = []                                 # 记录所有的最终解def traceback(各参数):if 终止条件:res.append(最终解)                # 保存结果returnfor 方案 in 所有可能的解决方案:          # 遍历所有可能的解决方案if 约束条件:                       # 剪枝做出选择,更新状态traceback(各参数)              # 递归搜索回溯,撤销选择,回退到上一状态traceback(各参数)                          # 执行函数

举例:

1、(难度:简单)【力扣】1863. 找出所有子集的异或总和再求和

解题思路:搜索所有组合,深度优先搜索。遍历给定列表中每个元素,选择该元素并往下递归搜索,再撤销选择,尝试其他搜索。最后所有组合的异或结果求和。

知识点:x ^ y:x和y进行异或运算。异或运算:二进制中各位依次比对,相同为0,不同为1。 

class Solution:def subsetXORSum(self, nums: List[int]) -> int:def traceback(i, xor):# 终止条件:遍历到列表结束if i == n:res.append(xor)      # 最终解保存到结果列表中return# 选择当前元素traceback(i + 1, xor ^ nums[i])# 撤销选择(即不选择当前元素)traceback(i + 1, xor)res = []            # 结果列表,存放所有组合的异或结果xor = 0             # 一个组合的异或结果i = 0               # 目前是列表中哪个元素n = len(nums)       # 列表长度traceback(i, xor)   # 执行函数return sum(res)

2、(难度:中等)【力扣】46. 全排列

 解题思路:全排列:每个元素都有,只是顺序不同。因此,两个列表:结果列表(存放所有组合),存放一个全排列组合的列表。依次往组合中添加元素,给定列表中的每个元素只添加一次。添加元素时,每次从头遍历给定列表,分别选择该元素或不选择该元素。搜索所有组合。

知识点:res.append(alist[:]):往结果列表res中添加列表alist。需使用alist[:],否则回溯时pop撤销选择时,列表alist中会删除最后一个元素,结果列表res中也会删除该元素,最终结果则为空列表。

              alist.pop():删除列表alist中最后一个元素。

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:def traceback(index):# 终止条件:列表遍历结束if index == n:res.append(alist[:])        # 结果列表中保存组合return# 全排列(每个元素都有,只是顺序不同),每次从头遍历for i in range(0, n):# 每个元素在组合中只能出现一次if nums[i] not in alist:# 选择当前元素alist.append(nums[i])traceback(index + 1)     # 递归,往下继续添加元素# 撤销选择(即不选择当前元素)alist.pop()res = []            # 结果列表,存放所有全排列的组合alist = []          # 一个全排列的组合index = 0           # 在组合中添加到哪个元素n = len(nums)       # 列表长度traceback(index)    # 执行函数return res

3、(难度:困难)【力扣】51. N 皇后

(3-1)使用集合

解题思路:皇后所在位置不能同一行、同一列、不能在两个斜线位置(左上到右下,右上到左下)。因此,三个集合:存放皇后所在列号,两个斜线(左上到右下,行号和列号的差相同。右上到左下,行号和列号的和相同)。搜索每一行皇后所在位置,尝试所有可能结果。

知识点: [ ]:空列表。列表:元素可重复的有序、可变的序列。

               列表.append(元素):往列表添加元素。

               列表[下标]:获取或修改列表下标对应的元素。

               "间隔符".join(列表):列表中所有元素按照指定间隔符组合成字符串。间隔符可以为空。

               [元素] * n:列表,列表中有n个相同的指定元素。

               set( ):空集合。集合:元素不重复的无序、可变的序列。

               集合.add(元素):往集合添加元素。

               集合.remove(元素):从集合删除元素。

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def trackback(rowindex):# 终止条件:棋盘所有行遍历结束if rowindex == n:board = []                          # 棋盘列表,存放整个棋盘内容for i in range(n):row[queen[i]] = "Q"             # 各行皇后所在的列下标对应元素为Qboard.append("".join(row))      # 各行加入棋盘row[queen[i]] = "."             # 恢复行初始值res.append(board)                   # 结果列表记录最终整个棋盘return# 遍历棋盘所有列for colindex in range(n):# 判断:不与皇后同一列、斜线(左上到右下,行号与列号的差相同。右上到左下,行号与列号的和相同)if colindex not in columns \and colindex - rowindex not in diagonal_1 \and colindex + rowindex not in diagonal_2:# 选择该位置为皇后queen[rowindex] = colindexcolumns.add(colindex)diagonal_1.add(colindex - rowindex)diagonal_2.add(colindex + rowindex)trackback(rowindex + 1)            # 递归搜索# 撤销选择(即该位置不为皇后)columns.remove(colindex)diagonal_1.remove(colindex - rowindex)diagonal_2.remove(colindex + rowindex)res = []                # 结果列表,存放所有最终棋盘结果columns = set()         # 集合,存放所有皇后所在的列下标diagonal_1 = set()      # 集合,存放所有皇后的斜线(左上到右下)diagonal_2 = set()      # 集合,存放所有皇后的斜线(右上到左下)queen = [-1] * n        # 皇后列表,皇后初始值,存放每行皇后所在的列下标row = ['.'] * n         # 行列表,行初始值rowindex = 0            # 目前在哪一行trackback(rowindex)     # 执行函数return res

(3-2)使用二进制

解题思路:将棋盘每行视为一串二进制,尝试所有可能的位置。第一行从最右边(低位)开始搜索,获取皇后所在位置在棋盘上该行的列下标。下一行,新皇后不能同一列,不能斜线(即可能位置为左侧斜线右移一位,右侧斜线左移一位),继续搜索,搜索所有行的皇后位置。再新一轮搜索第一行下一个可能位置,依次类推,深度优先搜索,搜索所有可能结果。

知识点:1 << n:1左移n位。若n=4,则二进制10000。

             (1 << n)-1:若n=4,则结果为二进制1111。即棋盘中一行4位均为可能位置。

             (~(columns | diagonal_1 | diagonal_2):“|”即or,“~”为取反。即不与已有皇后同一列、两个斜线位置。

              may_pos & (-may_pos) : 获取二进制may_pos中最右边为1的位置,即皇后可能位置。

              may_pos & (may_pos - 1) :将二进制may_pos最右边的1置为0,即剩余可能位置。

              bin(...).count("1"):统计二进制中1的个数。以次获取列下标。

class Solution:def solveNQueens(self, n: int) -> List[List[str]]:def trackback(rowindex, columns, diagonal_1, diagonal_2):# 终止条件:遍历棋盘所有行if rowindex == n:board = []                      # 保存整个棋盘内容for i in range(n):row[queen[i]] = "Q"         # 皇后所在位置元素为Qboard.append("".join(row))  # 保存各行row[queen[i]] = "."         # 行恢复初始值res.append(board)               # 结果列表中保存最终整个棋盘return# 所有可能的位置may_pos = ((1 << n) - 1) & (~(columns | diagonal_1 | diagonal_2))# 遍历所有可能的位置while may_pos:pos = may_pos & (-may_pos)            # 获取最右边为1的位置colindex = bin(pos - 1).count("1")    # 最右边1的位置转为在棋盘中的列下标queen[rowindex] = colindex            # 保存该行皇后的列下标may_pos = may_pos & (may_pos - 1)     # 将最右边的1置为0,剩余可能位置# 递归搜索trackback(rowindex + 1, columns | pos, (diagonal_1 | pos) << 1, (diagonal_2 | pos) >> 1)res = []                # 结果列表,保存所有的最终棋盘queen = [-1] * n        # 存放各行皇后所在的列下标row = ["."] * n         # 行初始值# 目前所在行号、列号、两个斜线位置rowindex, columns, diagonal_1, diagonal_2 = 0, 0, 0, 0trackback(rowindex, columns, diagonal_1, diagonal_2)return res


http://www.mrgr.cn/news/61913.html

相关文章:

  • LiveQing视频点播流媒体RTMP推流服务常见问题-如何查看无人推流RTMP推流OBS推流的远端IP?
  • 浏览器HTTP缓存解读(HTTP Status:200 304)
  • HarmonyOS开发 - 本地持久化之实现LocalStorage支持多实例
  • No.23 笔记 | WEB安全 - 任意文件漏洞 part 5
  • Linux 应用领域
  • 【SQL Server】解决因使用 varchar 类型存储 Unicode 字符串导致的中文显示乱码问题
  • Spring Cloud Ribbon:负载均衡的服务调用
  • Java 泛型和反射(15/30)
  • 软件工程经验详细总结
  • 进程线程、同步异步、并发并行
  • 小游戏发展迅速,游戏平台如何从技术方向加速业务转化?
  • 如何进行Java的时间序列分析与算法优化,应该从何入手?
  • 大模型:索引构建、预检索与检索阶段、检索后与生成阶段
  • 自动批量生成图片代码
  • Apache Hive 通过Docker快速入门
  • 深入解析Sysmon日志:增强网络安全与威胁应对的关键一环
  • Leetcode—3216. 交换后字典序最小的字符串【简单】
  • 先验概率、似然概率、后验概率
  • Qt5 读写共享内存,已验证,支持汉字的正确写入和读取
  • Java 中 InputStream 的使用:try-with-resources 与传统方式的比较
  • 解密自闭症全托寄宿肇庆:专业照顾与培养一站式服务
  • node学习记录-os
  • 比较24个结构的迭代次数
  • 量化与知识蒸馏的区别
  • 加密软件有什么功能?
  • flume系列之:flume机器做条带划分提高磁盘性能和吞吐量的详细步骤