循序渐进，搞懂什么是回溯算法

循序渐进，搞懂什么是回溯算法

回溯算法简介

回溯算法（backtracking algorithm）实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。满足回溯条件的某个状态的点称为“回溯点”。

回溯算法通常用于在候选解的所有可能的情况中搜索并找出满足条件的解。它的基本思路是从问题的某一种状态开始搜索，在搜索过程中不断尝试每一种可能的选择，直到找到满足条件的解或者所有可能的选择都已尝试完毕。如果当前的选择不能得到满足条件的解，就回溯到上一个状态并尝试其他选择。

回溯算法的关键在于定义问题的状态以及如何进行选择和回溯。首先需要为问题定义一个解空间（solution space），这个空间必须至少包含问题的一个解（可能是最优的）。

回溯法从开始结点（根结点）出发，以深度优先的方式搜索整个解空间，这个开始结点就成为一个“回溯点”，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点，这个新结点就成为一个新的“回溯点”，并成为当前扩展结点。如果搜索深度达到最大，扩展结点处不能再向纵深方向移动，应回溯至最近的一个“回溯点”，并使这个“回溯点”成为当前的扩展结点。回溯法以这种工作方式递归地在解空间中搜索，直至找到所求的解或解空间都已尝试完毕。

回溯算法按照深度优先的顺序，穷举所有的可能性，但是回溯算法比暴力穷举法更高明的地方就是回溯算法可以随时判断当前状态是否满足问题的解。一旦不满足，就退回到上一个状态，省去了继续往下搜索的时间，相当于对穷举进行了“剪枝”。

回溯算法的一般求解步骤

回溯算法通常使用递归来实现，每一层表示问题的一个状态，在递归的过程中，不断地重复做“选择”和“回溯”这两种操作。

在问题的初始状态（根结点），会先做出第一次“选择”，如果能选择的选项有N个，这N个选项组成的集合称为选择列表。做选择的过程相当于在一棵N叉树上做搜索，一般情况下，最终会生成一棵深度为N+1的N叉树。

在每做一次选择后，都会判断当前的状态是否满足问题的条件，如果满足，就会对当前状态做相应的处理，如更新选择列表、记录当前状态等，然后递归。如果不满足条件，就撤销做选择时的处理，往回“回溯”。

所以，回溯算法解决问题的一般步骤为：

1. 定义问题的解空间，确定问题的解是什么形式的。

2. 确定状态搜索树的结构，使得能用回溯法搜索整个解空间。

3. 以深度优先的方式搜索解空间，并且在搜索过程中进行剪枝，避免无效搜索。搜索解空间就是全遍历，但是在遍历时可以及时判断当前是否满足问题的条件，不满足就跳过，进行剪枝。

回溯算法实现举例

回溯算法即涉及递归，又涉及多叉树的深度优先遍历，光看前面的概念，多半还是似懂非懂，还是要用具体的案例来与理论进行对照学习，才能加深理解。而回溯算法最经典的一个案例就是八皇后问题，下面就以八皇后问题的求解为例，来看一下回溯算法如何实现。

八皇后问题是指将八个国际象棋中的皇后放在 8*8 的棋盘上，并且使皇后彼此之间不能相互攻击。皇后可以攻击同一行、同一列、对角线方向。要满足8个皇后不互相攻击，那它们都不能在同一行、同一列以及同一条对角线上。

基于以上规则，开始分析如何用回溯算法进行求解。首先，皇后不能存在于同一行，也就是每一行只能有一个皇后，所以求解步骤就是依次在每一行放置一个皇后，枚举皇后所在的列，看是否满足不互相攻击的条件。求解时用一个列表来记录已放置皇后的位置，列表的下标刚好可以表示皇后所在的行，而列表中的每个值表示皇后所在的列，求出八个皇后所在列的组合即可。

根据这个解题思路，得到的每个解是长度为 8 的列表，一开始，可以初始化一个长度为 8 的列表来保存解，这就定好了问题的解空间（对应步骤1）。如果找到多个解，可以把所有解一起保存下来。

依次在每一行枚举可能的解，就是在解空间里面进行深度优先搜索（对应步骤2）。搜索用递归来实现，在递归代码中，需要做以下事情，如果放置了一个皇后，则要更新存在冲突的信息，然后递归，继续在下一行进行搜索。如果在当前这一行中找不到满足条件的位置，则要回溯到上一行，撤销上一行的选择和冲突信息，重新选择上一行。如果 8 个皇后全部放置完毕，则找到了一个可行解。

在每一次选择之后，立即判断当前位置是否满足条件，如果在某一行找不到满足条件的位置，就立即回溯，这个过程就会对搜索进行“剪枝”，降低问题的时间复杂度（对应步骤3）。

根据题目规则，不满足条件的情况（相互攻击）可以分成三种：

1.当前列已经放置了皇后。在代码中用一个集合 columns 记录已经有皇后的列，每放置或撤回一个皇后，都更新 columns 。

2.从左上到右下的斜线上已经放置了皇后。经过分析，同一条斜线上的行列数之差相等，并且不同斜线的行列数之差不相等。见下图中绿色的斜线，如(0, 0)，(1,1)，(2, 2)…这条斜线的行列之差都是0。(4, 0)，(5, 1)，(6, 2)，(7, 3)这条斜线的行列之差都是4。在代码中用一个集合 diagonal_left 记录行列数之差，每放置或撤回一个皇后，都更新 diagonal_left 。

3.从右上到左下的斜线上已经放置了皇后。经过分析，同一条斜线上的行列数之和相等，并且不同斜线的行列数之和不相等，见下图黄绿色斜线。同理维护一个集合 diagonal_right 记录行列数之和，每放置或撤回一个皇后，都更新 diagonal_right 。

分析完成后，就可以开始实现代码了，下面的代码中写了详细注释，可以结合分析一起对照着看。

def solve8queens(n=8):
    solutions = []  # 保存所有解
    columns = set()  # 存在冲突的列
    diagonal_left = set()  # 存在冲突的对角线（方向左上到右下）
    diagonal_right = set()  # 存在冲突的对角线（方向右上到左下）
    result = [-1] * n  # 可行解的列表，初始化成长度为n，初始值全设为-1
    def backtrack(row):  # 回溯函数，传入行的下标row
        if row == n:  # 如果row已经与n相等，说明已经找到了一个可行解
            # python的列表是可变对象，保存当前找到的解时，先转换成元组
            solutions.append(tuple(result))  
            return
        else:
            for i in range(n):
                # 遍历每一列，判断是否存在位置冲突，存在冲突则跳过，“剪枝”
                if i in columns or row-i in diagonal_left or row+i in diagonal_right:
                    continue
                # 保存满足条件的值，并更新存在冲突的信息
                result[row] = i
                columns.add(i)
                diagonal_left.add(row - i)
                diagonal_right.add(row + i)
                # 递归调用回溯函数
                backtrack(row + 1)
                # 回溯时删除对应的冲突信息
                columns.remove(i)
                diagonal_left.remove(row - i)
                diagonal_right.remove(row + i)
    backtrack(0)  # 选择一个初始状态，触发回溯函数
    return solutions


print("可行解个数：", len(solve8queens()))
print(solve8queens()[0])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Output:

可行解个数： 92
(0, 4, 7, 5, 2, 6, 1, 3)
1
2

根据代码运行结果，可以看到八皇后问题一共有92种可行解，如果靠人工暴力求解，根本不可能。回溯算法是类似枚举的搜索算法，时间复杂度为 O(N!)，问题规模每增加1，时间复杂度都会明显变大，即使回溯算法中有“剪枝”的效果，也仅仅是稍微缓解。

回溯算法的实现代码中，在函数的内部还定义了一个递归的函数，而且是在for循环下进行递归，虽然代码不多，但也不易理解，所以要结合理论和解题步骤进行理解。

本文的代码还可以扩展到求解 N 皇后问题，即求将N个皇后放置在 N*N 的棋盘上，不互相攻击，代码可以直接使用。

要加深对回溯算法的理解，可以多看一些相关的文章，看不同的人从不同的角度分析可能会加深理解，还可以多看代码实现方式和多看案例。

---

相关阅读：

循序渐进，搞懂什么是动态规划