回溯算法
陈莎拉
什么是回溯算法？
回溯是一种寻找可能的组合来解决的算法 计算问题。它会逐步构建候选方案并删除那些不满足给定约束的方案。这种技术在您必须在多个可能结果中选择一个可行解决方案的情况下非常有用。
该算法被认为比蛮力法更好、更高效。与尝试所有可能解决方案的蛮力法不同，回溯法专注于根据给定的条件仅找到一个最终解决方案 约束。它还可以通过撤消最后一步（回溯）并在到达死胡同后尝试另一种选择来节省时间和内存。此外，一旦找到有效的解决方案，它就会停止。
回溯是一种广泛使用的技术，因为它可以解决复杂问题而无需耗费大量资源。它对于必须满足许多约束的问题特别有用，例如数独、n 皇后问题和调度。通过智能地浏览潜在解决方案，回溯可以找到满足所有条件的答案。这使得它对于需要精确性和效率的任务非常有用。
回溯算法如何工作？
回溯算法是一种解决问题的技术，涉及逐步寻找有效的解决方案。如果某一步骤的约束不满足某些条件，算法将返回上一步。
然后，它继续寻找满足给定约束的其他可能组合。由于存在许多可能的组合，它会选择最令人满意的选项之一并按顺序解决问题。当您需要解决一个或多个可能的选项时，这种算法技术很有用。撤回意味着当出现无法产生有效解决方案的情况时，取消您的选择。
回溯算法解决一个问题一般有以下步骤：
步骤1）初始化： 从初始的空/部分解决方案开始。
步骤2）选择：根据特定的标准和约束，选择一个选项来扩展当前的解决方案。
步骤 3）探索：通过考虑所选的候选方案并在解决问题的过程中向前推进，以递归方式解决问题。
步骤4）约束检查：检查当前的部分解决方案是否在每一步都违反了任何约束。如果是，则回溯到上一步并尝试不同的候选方案。
步骤5）终止：当找到有效的解决方案或所有组合都已用尽时，回溯过程将停止。
步骤 6）回溯：如果当前选项不能解决给定的问题，它将返回到之前的状态。然后它会考虑新的选项来解决给定的问题。
步骤 7）重复：继续执行这些步骤，直到问题解决或所有选项都试遍为止。
回溯算法的递归性质
回溯算法本质上是递归的。这意味着算法使用不同的参数调用自身，直到找到解决方案或测试了所有可能性：
def find_solutions(n, other_params):
if found_a_solution():
increment_solutions_found()
display_solution()
if solutions_found >= solution_target:
exit_program()
return
for val in range(first, last+1):
if is_valid(val, n):
apply_value(val, n)
find_solutions(n + 1, other_params)
remove_value(val, n)
与回溯问题相关的常用术语
以下是与回溯技术相关的一些基本术语：
- 解向量： 将解决方案表示为 n 元组，如 (X1, X2, ..., Xn)。
- 限制：限制X值的规则，隐式和显式。
- 解决方案空间：满足明确约束的所有有效 X 值。
- 状态空间树：用树来表示解空间。
- 状态空间：描述状态空间树中的路径。
- 问题状态：搜索树中代表部分解决方案的节点。
- 解决方案状态：在 S 中形成有效解元组的状态。
- 答案状态：满足隐含约束并产生所需的解决方案。
- 有前途的节点：导致期望的解决方案并且仍然可行。
- 无前途的节点：导致不可行的状态，不再进一步探索。
- 活跃节点：由未探索的子代生成。
- E节点：活跃节点，并且正在生成子节点。
- 死亡节点：不再扩大所有子代的生成。
- 深度优先节点生成：使用最新的活动节点作为下一个 E 节点。
- 边界函数：最大化或最小化 B(x1, x2, …, Xa) 以进行优化。
- 静态树：与问题实例无关的树公式。
- 动态树：树的公式随着问题实例的不同而变化。
何时使用回溯算法？
在以下情况下，我们可以选择回溯技术来解决复杂问题：
- 存在多种选择： 如果问题解决过程的每个步骤都存在许多选项，则回溯法是合适的。这些选项可能与项目和动作的选择有关。
- 没有明确的最佳选择：当没有足够的信息来确定可用选项中的最佳选择时，可以使用回溯算法。
- 这个决定带来了更多的选择： 你可以选择 回溯技术来系统地审查选择。
- 需要探索所有可能的解决方案：回溯通过做出一系列相互关联的决策来系统地探索所有的解决方案。
回溯问题的类型
回溯算法中的问题类型主要有三类：决策问题、优化问题、枚举问题。下面我们来了解一下。
- 决策问题： 在这种类型的问题中，目标是确定是否存在可行解决方案。我们检查“是”和“否”答案。例如，n 皇后问题。这是一个决策问题，用于检查在 n × n 棋盘上放置 n 个皇后而不互相攻击的可能性。
- 优化问题：在优化问题中，目标是在众多选项中找到最佳解决方案。这可能涉及确定某个函数或变量的最大值和最小值。例如，考虑背包问题，其目标是在遵守背包重量限制的同时最大化背包中物品的总价值。
- 枚举问题：其目标是找到给定问题的所有可能解决方案。我们列出所有有效选项，不遗漏任何选项。例如，从给定的一组字符中生成所有可能的字母组合。
回溯的应用和示例
回溯有多种应用。下面通过伪代码解释其中一些应用。
- Sudoku Solver: 此问题包含一个 3×3 子网格，其中有重复的数字。回溯技术将显示解决方案返回 false，这表明需要不同的数字放置。
- N皇后问题：回溯方法确定如何在 N×N 棋盘上展示皇后，使得它们之间不会互相威胁。
- 子集和问题：它用于从给定集合中找出加起来达到特定目标总和的数字子集。
- 哈密顿循环问题：回溯法可用于在图中寻找一条只访问每个顶点一次的封闭路径。
- 老鼠走迷宫问题：使用回溯技术寻找老鼠从迷宫起点到出口的路径。
function solveSudoku(board):
if no empty cells:
return true # Sudoku is solved
for each empty cell (row, col):
for num from 1 to 9:
if num is valid in (row, col):
place num in (row, col)
if solveSudoku(board):
return true
remove num from (row, col)
return false # No valid solution
function solveNQueens(board, col):
if col >= N:
return true # All queens are placed
for each row in the column col:
if isSafe(board, row, col):
place queen at (row, col)
if solveNQueens(board, col + 1):
return true
remove queen from (row, col)
return false # No valid solution in this branch
function subsetSum(nums, target, index, currentSubset):
if target == 0:
print(currentSubset) # Subset with the target sum found
return
if index >= len(nums) or target < 0:
return
currentSubset.add(nums[index])
subsetSum(nums, target - nums[index], index + 1, currentSubset)
currentSubset.remove(nums[index])
subsetSum(nums, target, index + 1, currentSubset)
回溯算法的优点和缺点
回溯算法的优点
回溯技术用于解决复杂问题。它有许多优点，例如：
- 回溯技术对于处理约束非常有效。
- 该方法有利于解决优化问题。
- 该技术可以解决各种类型的问题。
- 此程序可以帮助审查所有可能的解决方案。
- 由于它采用回溯方法，因此比暴力破解技术节省更多内存。
回溯算法的缺点
回溯技术也有一些局限性，例如时间复杂度。该技术有以下缺点：
- 没有保证的解决方案。
- 由于组合方式较多，所以比较慢。
- 由于可能性较多，时间复杂度较高。
- 它不适合实时约束，因为找到最佳解决方案可能需要很长时间。
- 效率取决于问题的复杂程度。
回溯和递归之间的区别
| 递归 | 回溯 |
|---|---|
| 调用自身直到达到基本情况。 | 使用递归来审查所有可能性，直到找到最佳可行结果。 |
| 自下而上的方法。 | 自上而下的方法。 |
| 没有任何值被丢弃。 | 不可行的解决方案被拒绝。 |
结语
回溯是一种有用的算法策略，通过系统地探索可行的解决方案并在必要时回溯来解决复杂问题。我们可以预期，随着计算能力和算法效率的提高，回溯技术将得到增强。这些进步将使它们能够有效地解决更大、更复杂的问题。
此外，机器学习模型可以根据先前学习的模式指导回溯决策。
所有这些技术创新将彻底改变回溯算法，使其成为解决各个领域复杂问题的强大而多功能的工具。
