回溯简介【自用】

回溯就像尝试不同的路径，当你走到死胡同时，你会回到最后一个选择并尝试不同的路线。在本文中，我们将探讨回溯的基础知识、它是如何工作的，以及它如何帮助解决各种具有挑战性的问题。这就像一种在复杂的选择中找到正确方法的方法。

目录

• 什么是回溯？
• 回溯问题的类型
• 回溯是如何工作的？
• 确定回溯问题
• 回溯伪代码
• 回溯的复杂性分析
• 回溯与递归有何不同？
• 回溯的应用
• 必须做的回溯问题

什么是回溯？

回溯是一种解决问题的算法技术，它涉及通过尝试不同的选项逐步找到解决方案，如果 它们导致死胡同，则撤消它们。它通常用于您需要探索多种可能性来解决问题的情况，例如在迷宫中寻找路径或解决数独等谜题。当到达死胡同时，算法会回溯到前一个决策点并探索不同的路径，直到找到解决方案或用尽所有可能性。

回溯可以定义为一种通用的算法技术，它考虑搜索所有可能的组合以解决计算问题。

回溯简介

基本术语

• 候选项：候选项是可以添加到当前解决方案中的潜在选项或元素。
• 解决方案：该解决方案是满足所有问题约束的有效且完整的配置。
• 部分解决方案：部分解决方案是在回溯过程中构建的中间或不完全配置。
• 决策空间：决策空间是每个决策点上所有可能的候选项或选项的集合。
• 决策点：决策点是算法中的一个特定步骤，其中选择候选项并将其添加到部分解决方案中。
• 可行解决方案：可行解决方案是遵守所有约束的部分或全部解决方案。
• 死胡同：当部分解无法在不违反约束的情况下扩展时，就会出现死胡同。
• 回溯：回溯涉及撤销之前的决策并返回到之前的决策点。
• 搜索空间：搜索空间包括候选项和选项的所有可能组合。
• 最优解：在优化问题中，最优解就是可能的最佳解。

回溯问题的类型

与回溯相关的问题可分为 3 类：

• 决策问题： 在这里，我们寻找可行的解决方案。
• 优化问题：对于此类型，我们寻找最佳解决方案。
• 枚举问题： 我们为此类问题找到了所有可能的可行解决方案。

回溯是如何工作的？

正如我们所知，回溯算法会探索每一条可能的路径以找到有效的解决方案，这种路径的探索可以通过给定的图像轻松理解：

如图所示，“IS” 表示 递归调用开始查找有效解决方案的初始状态。
C ：它表示递归调用的不同 Checkpoint

TN：它表示无法进行进一步递归调用的终端节点，这些节点充当递归的基本情况，我们确定当前解决方案在此状态下是否有效。

在每个 Checkpoint 上，我们的程序都会做出一些决定并移动到其他 checkpoint，直到到达终端节点，在确定解决方案是否有效后，程序开始返回到 checkpoint 并尝试探索其他路径。例如，在上图中，TN1…TN5 是解决方案不可接受的终端节点，而 TN6 是我们找到有效解决方案的状态。

图像中的后退箭头显示了操作中的回溯，其中我们还原了某个检查点所做的更改。

确定回溯问题：

通常，每个约束满足问题都可以使用回溯来解决，但是，每次都使用回溯是最好的吗？事实证明没有，有大量问题可以使用对数或多项式时间复杂度的贪婪或动态规划来解决，这比回溯的指数复杂度要好得多。然而，仍然存在许多问题，只能使用 Backtracking 来解决。

要了解一个问题是否是基于回溯的，让我们看一个简单的问题：
问题：假设你有 3 个封闭的盒子，其中 2 个是空的，1 个是金币。你的任务是获得金币。

为什么动态规划无法解决这个问题：Does 打开或关闭一个盒子对另一个盒子有什么影响？结果是否定的，每个盒子都是彼此独立的，一个盒子的打开/关闭状态无法确定其他盒子的过渡。因此 DP 失败。

为什么贪婪无法解决这个问题：贪婪算法选择一个局部最大值以获得全局最大值，但是在这个问题中，每个盒子都有相等的金币概率，即 1/3，因此没有做出贪婪选择的标准。

为什么回溯有效： 如前所述，回溯算法只是蛮力强制每一个选择，因此我们可以一个一个地选择每个盒子来找到金币，如果发现一个盒子是空的，我们可以将其关闭，这充当回溯步骤。

从技术上讲，对于回溯问题：

• 该算法通过探索问题中的选择创建的所有可能路径来构建解决方案，此解决方案以空集 S={} 开头
• 每个选择都会创建一个新的子树 ‘s’，我们将其添加到 are set 中。
• 现在有两种情况：
  • S+s 是有效集
  • S+s 设置无效
• 如果集合有效，那么我们进一步做出选择并重复该过程，直到找到解决方案，否则我们撤回包含 ‘s’ 的决定并探索其他路径，直到找到解决方案或用尽所有可能的路径。

回溯伪代码

实现回溯的最佳方法是通过递归，所有回溯代码都可以根据给定的伪代码进行总结：

void FIND_SOLUTIONS（ 参数）：

if （有效解）：

存储解决方案

返回

for （all choice）：

if （有效选择）：

APPLY（选择)

FIND_SOLUTIONS （参数）

BACKTRACK （删除选项)

返回

回溯的复杂性分析

由于回溯算法是纯粹的蛮力，因此在时间复杂度方面，它的表现非常糟糕。通常，回溯可以看作具有以下提到的时间复杂性：

• 指数 （O（K^N））
• 阶乘 （O（N！））

这些复杂性是由于这样一个事实：在每种状态下，我们都有多个选择，因此路径的数量会增加，子树会迅速扩展。

回溯与递归有何不同？

递归和回溯是计算机科学和编程中的相关概念，但它们不是一回事。让我们探讨一下它们之间的主要区别：

回溯的应用

• 创建智能机器人来玩棋盘游戏，例如国际象棋。
• 解决迷宫和谜题，例如 N-Queen 问题。
• 网络路由和拥塞控制。
• 解密
• 文本对齐

必须做的回溯问题

• N-Queen 问题
• 解决数独
• M 着色问题
• 迷宫中的老鼠
• 骑士之旅问题
• 给定 String 的排列