第6章 回溯算法

回溯算法详解
回溯算法是一种经典问题求解方法，通常被应用于在候选解的搜索空间中，通过深度优先搜索的方式找到所有可行解的问题。

回溯算法的本质是对一棵树的深度优先遍历，因此也被称为树形搜索算法。

回溯算法的基本思想是逐步构建候选解，并试图将其扩展为一个完整的解。

当无法继续扩展解时，则回溯到上一步并尝试其他的扩展，直到找到所有可行的解为止。

在回溯算法中，通常会维护一个状态向量，用于记录当前已经构建的解的情况。

通常情况下，状态向量的长度等于问题的规模。

在搜索过程中，我们尝试在状态向量中改变一个或多个元素，并检查修改后的状态是否合法。

如果合法，则继续搜索；如果不合法，则放弃当前修改并回溯到上一步。

在实际应用中，回溯算法通常用来解决以下类型的问题：
1. 组合问题：从n个元素中选取k个元素的所有组合；
2. 排列问题：从n个元素中选择k个元素，并按照一定顺序排列的所有可能；
3. 子集问题：从n个元素中选择所有可能的子集；
4. 棋盘问题：在一个给定的n x n棋盘上放置n个皇后，并满足彼此之间不会互相攻击的要求。

回溯算法的时间复杂度取决于候选解的规模以及搜索空间中的剪枝效果。

在最坏情况下，回溯算法的时间复杂度与候选解的数量成指数级增长，因此通常会使用剪枝算法来尽可能减少搜索空间的规模，从而提高算法的效率。

总之，回溯算法是一种非常有用的问题求解方法，在实际应用中被广泛使用。

同时，由于其时间复杂度较高，对于大规模的问题，需要慎重考虑是否使用回溯算法以及如何优化算法。

回溯算法原理和几个常用的算法实例回溯算法是一种基于深度优先的算法，用于解决在一组可能的解中找到满足特定条件的解的问题。

其核心思想是按照特定的顺序逐步构造解空间，并通过剪枝策略来避免不必要的。

回溯算法的实现通常通过递归函数来进行，每次递归都尝试一种可能的选择，并在达到目标条件或无法继续时进行回溯。

下面介绍几个常用的回溯算法实例：1.八皇后问题：八皇后问题是一个经典的回溯问题，要求在一个8×8的棋盘上放置8个皇后，使得每个皇后都不能相互攻击。

即每行、每列和对角线上都不能有两个皇后。

通过在每一列中逐行选择合适的位置，并进行剪枝，可以找到所有满足条件的解。

2.0-1背包问题：0-1背包问题是一个经典的组合优化问题，要求在一组物品中选择一些物品放入背包，使得其总重量不超过背包容量，同时价值最大化。

该问题可以通过回溯算法进行求解，每次选择放入或不放入当前物品，并根据剩余物品和背包容量进行递归。

3.数独问题：数独问题是一个经典的逻辑推理问题，要求在一个9×9的网格中填入数字1-9，使得每行、每列和每个3×3的子网格中都没有重复数字。

该问题可以通过回溯算法进行求解，每次选择一个空格，并依次尝试1-9的数字，然后递归地进行。

4.字符串的全排列：给定一个字符串，要求输出其所有可能的排列。

例如，对于字符串"abc"，其所有可能的排列为"abc"、"acb"、"bac"、"bca"、"cab"和"cba"。

可以通过回溯算法进行求解，每次选择一个字符，并递归地求解剩余字符的全排列。

回溯算法的时间复杂度通常比较高，因为其需要遍历所有可能的解空间。

但是通过合理的剪枝策略，可以减少的次数，提高算法效率。

在实际应用中，可以根据具体问题的特点来设计合适的剪枝策略，从而降低算法的时间复杂度。

回溯算法的步骤介绍回溯算法是一种常用于解决组合优化问题的算法。

它将问题转化为一个搜索树，并使用深度优先搜索的方式遍历整个搜索空间，通过剪枝操作来减少不必要的搜索。

思想回溯算法的思想是不断地试错和回溯。

它通过尝试每一种可能的解决方案，并在发现这条路不可能得到正确解时进行回溯，回退到上一步继续尝试其他的方案。

回溯算法适用于十分灵活的问题，因为它并不局限于特定的解决策略，而是通过搜索整个解空间来找到问题的解。

步骤回溯算法的步骤可以总结为以下几个部分：1. 定义问题的解空间首先需要明确问题的解空间是什么。

解空间是所有可能的解的集合，可以用一个树形结构来表示。

2. 确定搜索的起点确定搜索的起点，通常是空解或者是一个可以快速得到解的初始解。

3. 确定搜索的终点确定搜索的终点，即找到一个满足问题要求的解，或者搜索到整个解空间。

4. 递归地搜索解空间递归地搜索解空间，从起点开始不断地向下搜索，直到找到一个满足条件的解，或者搜索到整个解空间。

5. 对每一个可能的解进行评估对每一个可能的解进行评估，判断是否满足问题的要求。

6. 进行剪枝操作在搜索过程中，如果发现当前的解已经不可能得到满足要求的解，可以进行剪枝操作，直接放弃当前解在解空间的搜索，回溯到上一步继续搜索其他的解。

7. 回溯操作如果当前解满足了问题的要求，可以将其加入到结果集中。

然后进行回溯操作，回退到上一步继续搜索其他的解。

8. 返回解集最后返回所有满足问题要求的解。

实例分析为了更好地理解回溯算法的步骤，我们用一个实例来进行分析。

问题：给定一个数组，求所有可能的子集。

解空间：解空间是所有可能的子集的集合。

起点：空集。

终点：找到所有可能的子集。

步骤： 1. 确定问题的解空间：所有可能的子集的集合，可以用一个树形结构来表示，根节点是空集。

2. 确定搜索的起点：空集。

3. 确定搜索的终点：找到所有可能的子集。

4. 递归地搜索解空间：从起点开始向下搜索，每次可选的操作是向集合添加一个新元素或不添加。

基本算法-回溯法（迷宫问题）作者：翟天保Steven版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处前言本文介绍一种经典算法——回溯法，可作为迷宫问题的一种解法，以下是本篇文章正文内容，包括算法简介、算法应用（迷宫问题）、算法流程和C++代码实现。

一、回溯法简介回溯法（Backtracking）是枚举法的一种，可以找出所有或者一部分的一般性算法，且有效避免枚举不对的解。

当发现某个解的方向不准确时，就不再继续往下进行，而是回溯到上一层，减少算法运行时间，俗称“走不通就回头换路走”。

特点是在搜索过程中寻找问题的解，一旦发现不满足条件便回溯，继续搜索其他路径，提高效率。

二、算法应用（迷宫问题）1.问题描述迷宫问题是回溯法的一种应用。

迷宫问题的描述为：假设主体（人、动物或者飞行器）放在一个迷宫地图入口处，迷宫中有许多墙，使得大多数的路径都被挡住而无法行进。

主体可以通过遍历所有可能到出口的路径来到达出口。

当主体走错路时需要将走错的路径记录下来，避免下次走重复的路径，直到找到出口。

主体需遵从如下三个原则：1.一次步进只能走一格；2.遇到路径堵塞后，退后直到找到另一条路径可行；3.走过的路径记录下来，不会再走第二次。

2.解题思路首先创建一个迷宫图，比如用二维数组人为定义MAZE[row][col]，MAZE[i][j]=1时表示有墙无法通过，MAZE[i][j]=0时表示可行，假设MAZE[1][1]为入口，MAZE[8][10]为出口，创建如下初始迷宫图：图1 初始迷宫图当主体在迷宫中前行时，有东南西北（即右下左上）四个方向可以选择，如下图所示：图2 方向示意图视情况而定，并不是所有位置都可以上下左右前进，只能走MAZE[i][j]=0的地方。

通过链表来记录走过的位置，并将其标记为2，把这个位置的信息放入堆栈，再进行下个方向的选择。

若走到死胡同且未到达终点，则退回到上一个岔路口选择另一个方向继续走。

回溯算法学习重点：1、理解回溯法的基本思想；2、掌握回溯法解题的基本算法。

`学习过程:一、回溯法的基本思想回溯法又称试探法。

回溯法的基本做法是深度优先搜索，是一种组织得井井有条的、能避免不必要重复搜索的穷举式搜索算法。

回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

具体说,就是：在搜索(依次用各种方法一一去试探)的过程中，当在P点有N种选择，则从第一种开始尝试，若第K种可行，即这一步搜索成功，打上标记，再向前(即 P+1点)搜索；如在P 点搜索失败(所有的方法都试探过，没有一种可行)，为了摆脱当前的失败，就返回搜索进程中的上一点(即P-1点)，再用第K+1种方法(假设上次在P-1点用第K种方法搜索成功，必须明确以前用过的方法不能再用，否则会陷入死循环)再去搜索，重新寻求解答。

这样搜索回溯，再搜索再回溯，如能搜索到终点，问题有解，如最后回溯到出发点，问题就无解。

这种在搜索的过程中，先对深度大的点进行扩展的算法，叫深度优先搜索法。

设搜索深度指针为P，搜索方法指针为I，可把深度优先搜索算法写成如下形式：P=0：I=0DOI=I+1(搜索到一种方法)IF 搜索方法有效 THEN试探产生临时新结点IF 符合条件 THENP=P+1(深入一步)，新结点记录，I=0，再全方位搜索IF到达终点 THEN 结束搜索，输出结果END IFELSE(搜索的方法无效)I=上次搜索的方法(下一轮将用I的下一方法去搜索)，P=P-1(后退一步返回上结点) END IFL00P UNTIL P=0IF P=0 THEN ’深度指针P为0，表示已退到起始状态，是本题无解的标志无解ELSE输出结果END IFEND二、应用举例1、【问题描述】有一迷宫(如图)，可用一个10行9列的0～1矩阵表示，其中0表示无障碍(白色)，1表示有障碍(黑色)。

设入口位置的坐标为(2，1)，出口为(9，9)，规定每次移动中只能从一个无障碍的单元移到其周围四个方向上任一无障碍的单元。

引言寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。

理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。

不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。

对候选解进行系统检查的方法有多种，其中回溯和分枝定界法是比较常用的两种方法。

按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。

事实上，这些方法可以使我们避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。

因此，这些方法通常能够用来求解规模很大的问题。

算法思想回溯（backtracking）是一种系统地搜索问题解答的方法。

为了实现回溯，首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。

下一步是组织解空间以便它能被容易地搜索。

典型的组织方法是图(迷宫问题)或树(N皇后问题)。

一旦定义了解空间的组织方法，这个空间即可按深度优先的方法从开始节点进行搜索。

回溯方法的步骤如下：1) 定义一个解空间，它包含问题的解。

2) 用适于搜索的方式组织该空间。

3) 用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。

回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。

在搜索期间的任何时刻，仅保留从开始节点到当前节点的路径。

因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。

这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。

所以如果要存储全部解空间的话，再多的空间也不够用。

算法应用回溯算法的求解过程实质上是一个先序遍历一棵"状态树"的过程,只是这棵树不是遍历前预先建立的,而是隐含在遍历过程中<<数据结构>>(严蔚敏).(1) 幂集问题(组合问题) (参见《数据结构》（严蔚敏）)求含N个元素的集合的幂集。

回溯算法的步骤回溯算法的步骤回溯算法是一种通过穷举所有可能的解来求解问题的算法。

它通常用于求解组合优化问题、排列问题和子集问题等。

下面我们将介绍回溯算法的步骤。

1. 定义问题在使用回溯算法之前，需要先定义好要解决的问题。

例如，如果要求解一个排列问题，那么就需要确定排列中元素的个数和范围。

2. 确定状态空间树状态空间树是指所有可能解的集合。

在回溯算法中，状态空间树通常用于表示所有可能的决策路径。

例如，在排列问题中，每一个节点代表一个元素被选中或未被选中。

3. 确定约束条件约束条件是指限制解决方案可行性的条件。

在回溯算法中，必须遵守约束条件才能得到有效的解决方案。

例如，在排列问题中，每个元素只能出现一次。

4. 确定搜索顺序搜索顺序是指按照什么顺序遍历状态空间树。

在回溯算法中，搜索顺序通常有两种：深度优先搜索和广度优先搜索。

5. 编写递归函数递归函数是实现回溯算法最重要的部分。

递归函数的作用是遍历状态空间树，找到所有可行的解决方案。

在编写递归函数时，需要考虑以下几个方面：（1）确定终止条件：当搜索到状态空间树的叶子节点时，需要确定终止条件，返回当前路径是否符合要求。

（2）确定回溯条件：当搜索到某个节点时，如果发现该节点不符合约束条件，则需要回溯到上一个节点。

（3）确定状态变化：在搜索过程中，需要记录每个节点的状态变化。

例如，在排列问题中，需要记录哪些元素已经被选中。

6. 调用递归函数最后一步是调用递归函数，并将初始状态作为参数传入。

在调用递归函数之后，程序会自动遍历状态空间树，并找到所有可行的解决方案。

总结回溯算法是一种常见的求解组合优化问题、排列问题和子集问题等的算法。

它通过穷举所有可能的解来求解问题，在实际应用中有着广泛的应用。

在使用回溯算法时，需要先定义好要解决的问题，并按照上述步骤进行操作。

回溯算法的实施步骤什么是回溯算法回溯算法是一种通过尝试所有可能的解来求解问题的方法。

它适用于各种问题，包括组合优化问题、图问题以及搜索问题等。

回溯算法通过在每一步尝试所有可能的选择，并在不满足条件的情况下回溯到上一步，重新选择其他路径，直到找到满足条件的解或者穷尽所有可能的选择。

回溯算法的实施步骤回溯算法的实施步骤可以分为以下几个关键步骤：1.定义问题的解空间：首先需要明确问题的解空间，也就是问题的输入和可能的解。

根据具体的问题，可以定义解空间为一个数组、一个矩阵或者其他数据结构。

2.定义约束条件：对于问题的解空间，需要明确每个解的可行性条件。

约束条件可以排除一些不符合条件的解，减少搜索空间，提高算法效率。

在回溯算法中，约束条件通常对应于问题的限制条件。

3.定义目标函数：如果问题是优化问题，那么可以定义一个目标函数来评估每个解的优劣。

目标函数可以帮助算法找到最优解。

4.实施回溯搜索：回溯算法是通过深度优先搜索的方式来实施的。

在搜索的过程中，需要对解空间进行遍历，并根据约束条件逐步剪枝。

当找到一个可行解时，可以根据目标函数判断是否要继续搜索其他解。

如果目标函数要求找到所有解，那么需要继续回溯搜索，直到遍历完所有可能的解。

5.实现剪枝操作：在搜索的过程中，可以通过剪枝操作来减少不必要的搜索。

剪枝操作可以根据约束条件来排除某些分支，从而避免搜索无效的解。

6.记录解的搜索路径：在实施回溯算法的过程中，可以记录搜索路径，以便后续分析和回溯操作。

记录搜索路径有助于理解算法的执行过程，并可以用于问题的可视化展示。

7.回溯到上一步：当搜索到达某个状态时，发现没有更多的选择或者找到了一个解时，需要回溯到上一个状态，并选择其他路径继续搜索。

回溯操作可以通过递归实现。

8.终止条件判断：在实施回溯算法的过程中，需要设置终止条件。

终止条件可以是找到一个满足所有约束条件的解，或者遍历完所有可能的解。

示例：回溯算法解决子集问题为了更好地理解回溯算法的实施步骤，我们以一个子集问题为例进行说明。

回溯算法总结对回溯法的理解：回溯法本质就是深搜，对所有可能的结果进⾏搜索匹配，由于很多情况下结果很多，就需要进⾏适当的剪枝和分界限制来加快得到解。

回溯法⽤的最多的就是递归，其实也可⽤递推，但是递归⽐较符合⼈类逻辑。

回溯法的解题通常是有模板的：Void backtrack(){If(到达边界){输出答案/记录答案}Else{ 记录这个点，现存结果更新，递归，现存结果还原，取消该点记录}}回溯法的有三种情况：1）：找所有可能解：通过⼀个结果数组记录搜索得到的解，然后再到达边界时输出2）：寻找其中过⼀个的解：同上；2）：寻找最优（选和不选）在边界点记录/更新最优值 + 在else中除了要对选取这个点的结果进⾏搜索还要对忽略这个点的结果进⾏搜索回溯法的常⽤剪枝：1) :判断该点在之后的所有点组合起来能不能到达最优或者超过当前最优。

不能就剪枝2）当前点是不是访问过，访问过忽略2) 加上当前点是不是会越过限制条件，是的话剪枝3) 如果只要求输出⼀个解，设⽴⼀个flag，有了⼀个答案之后设置flag为1，当flag为1时，全部return⼦集和问题的解空间结构和约束函数：假设给定集合 C = { x1,x2,x3 ……… xn}; 给定正整数P解空间结构 C’ ={ xi,..xk} （1<=i<k<=n）约束函数：1：假设当前的搜索点为 Xi (（1<=i<n）),如果 {Xi+1 ,Xi+2,Xi+3………Xn}的和⼩于P，说明这个这个点取了也没⽤，剪枝；如果⼤于说明接下来的有可能得到P，那就继续搜索2：如果当前点⼤于P，该点不取3: 如果当前点加上当前总和结果⼤于P，不取本章学习遇到的问题:主要是剪枝不充分，导致算法超时问题.结对编程中问题：主要是背包问题的剪枝，要按照严格限界，不然会超时。

这个限界也是之前没有⽤过限界函数.下⾯总结⼀下这个限界函数:⾸先先要把数组进⾏降序排序，预测当前背包剩余容量最⼤可以装下多少价值的物品如果剩余容量能够能够承载的最⼤价值 + 当前的背包价值⼤于当前的最优值，说明这个点可以继续搜索下去。

回溯算法-算法介绍回溯法1、有许多问题，当需要找出它的解集或者要求回答什么解是满⾜某些约束条件的最佳解时，往往要使⽤回溯法。

2、回溯法的基本做法是搜索，或是⼀种组织得井井有条的，能避免不必要搜索的穷举式搜索法。

这种⽅法适⽤于解⼀些组合数相当⼤的问题。

3、回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。

算法搜索⾄解空间树的任意⼀点时，先判断该结点是否包含问题的解。

如果肯定不包含（剪枝过程），则跳过对该结点为根的⼦树的搜索，逐层向其祖先结点回溯；否则，进⼊该⼦树，继续按深度优先策略搜索。

问题的解空间问题的解向量：回溯法希望⼀个问题的解能够表⽰成⼀个n元式(x1,x2,…,xn)的形式。

显约束：对分量xi的取值限定。

隐约束：为满⾜问题的解⽽对不同分量之间施加的约束。

解空间：对于问题的⼀个实例，解向量满⾜显式约束条件的所有多元组，构成了该实例的⼀个解空间。

注意：同⼀个问题可以有多种表⽰，有些表⽰⽅法更简单，所需表⽰的状态空间更⼩（存储量少，搜索⽅法简单）。

下⾯是n=3时的0-1背包问题⽤完全⼆叉树表⽰的解空间：⽣成问题状态的基本⽅法扩展结点:⼀个正在产⽣⼉⼦的结点称为扩展结点活结点:⼀个⾃⾝已⽣成但其⼉⼦还没有全部⽣成的节点称做活结点死结点:⼀个所有⼉⼦已经产⽣的结点称做死结点深度优先的问题状态⽣成法：如果对⼀个扩展结点R，⼀旦产⽣了它的⼀个⼉⼦C，就把C当做新的扩展结点。

在完成对⼦树C（以C为根的⼦树）的穷尽搜索之后，将R重新变成扩展结点，继续⽣成R的下⼀个⼉⼦（如果存在）宽度优先的问题状态⽣成法：在⼀个扩展结点变成死结点之前，它⼀直是扩展结点回溯法：为了避免⽣成那些不可能产⽣最佳解的问题状态，要不断地利⽤限界函数(bounding function)来处死(剪枝)那些实际上不可能产⽣所需解的活结点，以减少问题的计算量。

具有限界函数的深度优先⽣成法称为回溯法。

（回溯法 = 穷举 + 剪枝）回溯法的基本思想(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先⽅式搜索解空间，并在搜索过程中⽤剪枝函数避免⽆效搜索。

Python中的回溯算法详解回溯算法是一种用于解决组合问题的常用算法。

它通过递归地尝试所有可能的解决方案，当遇到不符合条件的情况时，会回溯到上一步进行另外一种尝试。

在本文中，我们将详细介绍Python中的回溯算法及其应用。

一、什么是回溯算法？回溯算法是一种穷举搜索算法，可用于求解在给定约束条件下的所有可能的解决方案。

它通过尝试每一种可能的选择来构建解决方案，并在达到不符合条件的情况时进行回溯，以选择其他可能的路径。

二、回溯算法的应用场景回溯算法适用于以下场景：1. 组合问题：如在一组数中找出所有的组合；2. 排列问题：如求全排列；3. 子集问题：如求目标集合的所有子集；4. 图的遍历问题：如求解图的哈密顿路径。

三、回溯算法的实现步骤回溯算法的实现包括以下步骤：1. 定义问题的解空间：即确定每个节点的选择范围以及约束条件；2. 组织数据结构：使用适当的数据结构来表示问题的解空间以及中间解；3. 确定搜索路径：定义递归函数来搜索问题空间，并处理中间解；4. 剪枝优化：通过剪枝操作来减少搜索空间，提高算法效率；5. 回溯和回退：当达到不符合条件的情况时，回溯到上一步并选择其他可能的路径。

四、回溯算法的示例代码下面是一个在Python中实现回溯算法的示例代码，用于求解全排列问题。

```pythondef backtrack(nums, track, res):# 结束条件，当track中包含了所有的数字if len(track) == len(nums):res.append(track[:])returnfor num in nums:# 排除不合法的选择if num in track:continue# 做出选择track.append(num)# 进入下一层决策树backtrack(nums, track, res)# 撤销选择track.pop()def permute(nums):res = []track = []backtrack(nums, track, res)return res```五、回溯算法的复杂度分析回溯算法的时间复杂度一般是指数级的，因为它需要遍历解空间的所有可能路径。

回溯算法原理和几个常用的算法实例回溯算法是一种通过不断尝试和回退的方式来进行问题求解的算法。

它的基本思想是在过程中，当发现当前的选择并不符合要求时，就进行回退，尝试其他的选择，直到找到符合要求的解或者遍历完所有可能的选择。

回溯算法通常用于问题求解中的和排列组合问题，比如求解八皇后问题、0-1背包问题、数独等。

下面将介绍几个常用的回溯算法实例。

1.八皇后问题：八皇后问题是指在一个8×8的国际象棋棋盘上，放置八个皇后，使得任意两个皇后都不在同一行、同一列或同一斜线上。

可以通过递归的方式依次尝试每一行的位置，并判断当前位置是否满足条件。

如果满足条件，则进入下一行尝试；否则回溯到上一行，并尝试其他的位置，直到找到解或遍历完所有的可能。

2.0-1背包问题：0-1背包问题是指在给定一组物品和一个容量为C的背包，每个物品都有自己的重量和价值，求解在不超过背包容量时，如何选择物品使得背包中物品的总价值最大。

可以通过递归的方式依次考察每个物品，并判断是否选择当前物品放入背包。

如果放入当前物品，则背包容量减小，继续递归考察下一个物品；如果不放入当前物品，则直接递归考察下一个物品。

直到遍历完所有物品或背包容量为0时，返回当前总价值。

3.数独问题：数独是一种通过填充数字的方式使得每一行、每一列和每一个九宫格内的数字都满足一定条件的谜题。

可以通过递归的方式依次尝试填充每一个空格，并判断当前填充是否符合条件。

如果符合条件，则继续递归填充下一个空格；如果不符合条件，则回溯到上一个空格，并尝试其他的数字，直到找到解或遍历完所有的可能。

回溯算法的时间复杂度一般较高，通常为指数级别。

因此，在实际应用中，可以结合剪枝等优化策略来提高算法的效率。

此外，回溯算法也可以通过非递归的方式进行实现，使用栈来存储当前的状态，从而避免递归带来的额外开销。

总之，回溯算法是一种非常有效的问题求解方法，通过不断尝试和回退，可以在复杂的空间中找到符合要求的解。

算法——回溯法回溯法回溯法有“通⽤的解题法”之称。

⽤它可以系统地搜索⼀个问题的所有解或任⼀解。

回溯法是⼀种即带有系统性⼜带有跳跃性的搜索算法。

它在问题的解空间树中，按深度优先策略，从根节点出发搜索解空间树。

算法搜索⾄解空间树的任⼀结点时，先判断该节点是否包含问题的解。

如果不包含，则跳过对以该节点为根的⼦树的搜索，逐层向其它祖先节点回溯。

否则，进⼊该⼦树，继续按照深度优先策略搜索。

回溯法求问题的所有解时，要回溯到根，且根节点的所有⼦树都已被搜索遍才结束。

回溯法求问题的⼀个解时，只要搜索到问题的⼀个解就可结束。

这种以深度优先⽅式系统搜索问题的算法称为回溯法，它是⽤于解组合数⼤的问题。

问题的解空间⽤回溯法解问题时，应明确定义问题的解空间。

问题的解空间⾄少包含问题的⼀个（最优）解。

例如对于有n种可选择物品的0-1背包问题，其解空间由长度为n的0-1向量组成。

该解空间包含对变量的所有可能的0-1赋值。

例如n=3时，其解空间是{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}定义了问题的解空间后，还应该将解空间很好地组织起来，使得能⽤回溯法⽅便地搜索整个解空间。

通常将解空间组织成树或者图的形式。

例如，对于n=3时的0-1背包问题，可⽤⼀颗完全的⼆叉树表⽰其解空间，如下图。

解空间树的第i层到第i+1层边上的标号给出了变量的值。

从树根到叶⼦的任⼀路径表⽰解空间中的⼀个元素。

例如，从根节点到节点H的路径相当与解空间中的元素(1,1,1)。

回溯法的基本思想确定了解空间的组织结构后，回溯法从根节点出发，以深度优先搜索⽅式搜索整个解空间。

回溯法以这种⼯作⽅式递归地在解空间中搜索，直到找到所要求的解或解空间所有解都被遍历过为⽌。

回溯法搜索解空间树时，通常采⽤两种策略避免⽆效搜索，提⾼回溯法的搜索效率。

其⼀是⽤约束函数在当前节点（扩展节点）处剪去不满⾜约束的⼦树；其⼆是⽤限界函数剪去得不到最优解的⼦树。