IT评测·应用市场-qidao123.com技术社区

标题: python 回溯算法（Backtracking） [打印本页]
作者: 老婆出轨    时间: 2025-1-4 16:11
标题: python 回溯算法（Backtracking）
回溯算法（Backtracking）是一种通过试错的方式寻找问题的解的算法设计方法。它通常用于办理组合问题，通过递归地实验所有可能的解，并在发现当前路径不可能得到解时回退（回溯）。以下是使用Python实现回溯算法办理几个经典问题的示例：
1. 八皇后问题（N-Queens Problem）

八皇后问题要求在 ( N \times N ) 的棋盘上放置 ( N ) 个皇后，使得它们互不攻击。
  1. def solve_n_queens(n):
  2.     def is_safe(board, row, col):
  3.         # 检查列是否有冲突
  4.         for i in range(row):
  5.             if board[i] == col:
  6.                 return False
  7.             # 检查对角线是否有冲突
  8.             if abs(board[i] - col) == abs(i - row):
  9.                 return False
  10.         return True
  12.     def backtrack(row):
  13.         if row == n:
  14.             solutions.append(board[:])
  15.             return
  16.         for col in range(n):
  17.             if is_safe(board, row, col):
  18.                 board[row] = col
  19.                 backtrack(row + 1)
  20.                 board[row] = -1  # 回溯
  22.     solutions = []
  23.     board = [-1] * n  # 初始化棋盘
  24.     backtrack(0)
  25.     return solutions
  27. # 示例
  28. n = 4
  29. solutions = solve_n_queens(n)
  30. for solution in solutions:
  31.     print(solution)
  32. # 输出:
  33. # [1, 3, 0, 2]
  34. # [2, 0, 3, 1]
复制代码
2. 数独求解（Sudoku Solver）

数独求解问题要求添补一个 ( 9 \times 9 ) 的数独网格，使得每行、每列和每个 ( 3 \times 3 ) 子网格都包罗数字 1 到 9。
  1. def solve_sudoku(board):
  2.     def is_valid(row, col, num):
  3.         # 检查行和列
  4.         for i in range(9):
  5.             if board[row][i] == num or board[i][col] == num:
  6.                 return False
  7.         # 检查 3x3 子网格
  8.         start_row, start_col = 3 * (row // 3), 3 * (col // 3)
  9.         for i in range(3):
  10.             for j in range(3):
  11.                 if board[start_row + i][start_col + j] == num:
  12.                     return False
  13.         return True
  15.     def backtrack():
  16.         for row in range(9):
  17.             for col in range(9):
  18.                 if board[row][col] == 0:  # 找到空白格
  19.                     for num in range(1, 10):
  20.                         if is_valid(row, col, num):
  21.                             board[row][col] = num
  22.                             if backtrack():
  23.                                 return True
  24.                             board[row][col] = 0  # 回溯
  25.                     return False
  26.         return True
  28.     backtrack()
  30. # 示例
  31. board = [
  32.     [5, 3, 0, 0, 7, 0, 0, 0, 0],
  33.     [6, 0, 0, 1, 9, 5, 0, 0, 0],
  34.     [0, 9, 8, 0, 0, 0, 0, 6, 0],
  35.     [8, 0, 0, 0, 6, 0, 0, 0, 3],
  36.     [4, 0, 0, 8, 0, 3, 0, 0, 1],
  37.     [7, 0, 0, 0, 2, 0, 0, 0, 0],
  38.     [0, 6, 0, 0, 0, 0, 2, 8, 0],
  39.     [0, 0, 0, 4, 1, 9, 0, 0, 5],
  40.     [0, 0, 0, 0, 8, 0, 0, 7, 9]
  41. ]
  42. solve_sudoku(board)
  43. for row in board:
  44.     print(row)
  45. # 输出:
  46. # [5, 3, 4, 6, 7, 8, 9, 1, 2]
  47. # [6, 7, 2, 1, 9, 5, 3, 4, 8]
  48. # [1, 9, 8, 3, 4, 2, 5, 6, 7]
  49. # [8, 5, 9, 7, 6, 1, 4, 2, 3]
  50. # [4, 2, 6, 8, 5, 3, 7, 9, 1]
  51. # [7, 1, 3, 9, 2, 4, 8, 5, 6]
  52. # [9, 6, 1, 5, 3, 7, 2, 8, 4]
  53. # [2, 8, 7, 4, 1, 9, 6, 3, 5]
  54. # [3, 4, 5, 2, 8, 6, 1, 7, 9]
复制代码
3. 子集生成（Subset Generation）

生成一个聚集的所有子集。
  1. def subsets(nums):
  2.     def backtrack(start, path):
  3.         result.append(path[:])
  4.         for i in range(start, len(nums)):
  5.             path.append(nums[i])
  6.             backtrack(i + 1, path)
  7.             path.pop()  # 回溯
  9.     result = []
  10.     backtrack(0, [])
  11.     return result
  13. # 示例
  14. nums = [1, 2, 3]
  15. print(subsets(nums))
  16. # 输出: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
复制代码
4. 分列组合（Permutations and Combinations）

生成一个聚集的所有分列或组合。
分列（Permutations）

  1. def permutations(nums):
  2.     def backtrack(path):
  3.         if len(path) == len(nums):
  4.             result.append(path[:])
  5.             return
  6.         for num in nums:
  7.             if num not in path:
  8.                 path.append(num)
  9.                 backtrack(path)
  10.                 path.pop()  # 回溯
  12.     result = []
  13.     backtrack([])
  14.     return result
  16. # 示例
  17. nums = [1, 2, 3]
  18. print(permutations(nums))
  19. # 输出: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
复制代码
组合（Combinations）

  1. def combinations(nums, k):
  2.     def backtrack(start, path):
  3.         if len(path) == k:
  4.             result.append(path[:])
  5.             return
  6.         for i in range(start, len(nums)):
  7.             path.append(nums[i])
  8.             backtrack(i + 1, path)
  9.             path.pop()  # 回溯
  11.     result = []
  12.     backtrack(0, [])
  13.     return result
  15. # 示例
  16. nums = [1, 2, 3, 4]
  17. k = 2
  18. print(combinations(nums, k))
  19. # 输出: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
复制代码
总结

回溯算法通过递归地实验所有可能的解，并在发现当前路径不可能得到解时回退。它实用于组合问题、分列问题、搜索问题等。通过公道地剪枝和回溯，可以高效地找到问题的解。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/) Powered by Discuz! X3.4