回溯算法是五大常用的算法之一，它是一种深度优先搜索策略。下面是一个关于回溯法的例子：
问题描述：从1到n中找出所有和为0的数对。
解题思路：把问题的解空间转化成了图或者树的结构表示，然后使用深度优先搜索策略进行遍历，遍历的过程中记录和寻找所有可行解或者最优解。
详细描述：回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行(即能得到问题的解)。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。问题的关键在于如何定义问题的解空间，转化成树(即解空间树)。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。
回溯法应用：当问题是要求满足某种性质(约束条件)的所有解或最优解时，往往使用回溯法。它有“通用解题法”之美誉。
回溯法实现：回溯法的实现方法有两种：递归和递推(也称迭代)。一般来说，一个问题两种方法都可以实现，只是在算法效率和设计复杂度上有区别。【类比于图深度遍历的递归实现和非递归(递推)实现】
1. 递归
思路简单，设计容易，但效率低。其设计范式如下：
```python
def find_zero_sum_pairs(numbers):
res = []
num_dict = {}
for i in range(len(numbers)):
if (i > 0 and numbers[i] == numbers[i-1]) or (i < len(numbers)-1 and numbers[i] == numbers[i+1]): continue
if not numbers[i] in num_dict:
num_dict[numbers[i]] = [0]
num_dict[numbers[i]].append(i)
for key in num_dict:
temp = sorted([key-j for j in num_dict[key]]) + sorted([key+j for j in num_dict[key]])
for j in temp:
res.append((num_dict[key][j//2], num_dict[key][j//2+1]))
return res
```
针对N叉树的递归回溯方法如下：
```cpp
void backtrack(int t) {
if (t > n) output(x); //叶子节点，输出结果，x是可行解
else {
for (int i = 1; i <= k; i++) { //当前节点的所有子节点
x[t] = value(i); //每个子节点的值赋值给x
if (constraint(t) && bound(t)) {
backtrack(t + 1); //递归下一层
}
}
}
}
```
算法设计相对复杂，但效率高。
// 针对N叉树的迭代回溯方法
void iterativeBacktrack() {
int t = 1;
while (t > 0) {
if (ExistSubNode(t)) { // 当前节点的存在子节点
for (int i = 1; i <= k; i++) { // 遍历当前节点的所有子节点
x[t] = value(i); // 每个子节点的值赋值给x
if (constraint(t) && bound(t)) { // 满足约束条件和限界条件
// solution表示在节点t处得到了一个解
if (solution(t)) output(x); // 得到问题的一个可行解，输出
else t++; // 没有得到解，继续向下搜索
}
}
} else { // 不存在子节点，返回上一层
t--;
}
}
}
```
排列树是一种用于解决n个元素满足某种性质的排列问题的解空间结构。旅行售货员问题是一个典型的例子，要求一个售货员把几个城市旅行一遍，使得走的路程最小。这个问题的解就是城市的排列，对应的解空间就是排列树。回溯法搜索排列树的算法范式如下：
```cpp
void backtrack(int t) {
if (t > n) output(x);
else {
for (int i = t; i <= n; i++) {
swap(x[t], x[i]);
if (constraint(t) && bound(t)) backtrack(t + 1);
swap(x[t], x[i]);
}
}
}
```
经典问题中，0-1背包问题是其中一个例子。给定n种物品和一背包，物品i的重量是wi,其价值为pi,背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？这是一个n个物品中选择部分物品的问题，其解空间是子集树。使用x[i]表示物品i是否放入背包，x[i]=0表示不放，x[i]=1表示放入。回溯搜索过程，如果来到了叶子节点，表示一条搜索路径结束，如果该路径上存在更优的解，则保存下来。如果不是叶子节点，是中点的节点(如B),就遍历其子节点(D和E),如果子节点满足剪枝条件，就继续回溯搜索子节点。以下是代码实现：
```cpp
#include
#define N 3 //物品的数量
#define C 16 //背包的容量
int w[N] = {10, 8, 5}; //每个物品的重量
int v[N] = {5, 4, 1}; //每个物品的价值
int x[N] = {0, 0, 0}; //x[i]=1代表物品i放入背包，0代表不放入
int CurWeight = 0; //当前放入背包的物品总重量
void backtrack() {
if (CurWeight > C) return;
int maxValue = 0;
int maxIndex = 0;
for (int i = 0; i < N; i++) {
if (x[i]) {
CurWeight += w[i];
maxValue = std::max(maxValue, v[i] + x[j]);
CurWeight -= w[i];
}
}
x[maxIndex] = 1;
backtrack();
x[maxIndex] = 0;
}
```
以下是内容重构后的代码：
```cpp
int CurValue = 0; //当前放入背包的物品总价值
int BestValue = 0; //最优值；当前的最大价值，初始化为0
int BestX[N]; //最优解；BestX[i]=1代表物品i放入背包，0代表不放入
//t = 0 to N-1
void backtrack(int t)
{
//叶子节点，输出结果
if(t>N-1)
{
//如果找到了一个更优的解
if(CurValue>BestValue)
{
//保存更优的值和解
BestValue = CurValue;
for(int i=0;i } } else { //遍历当前节点的子节点：0 不放入背包，1放入背包 for(int i=0;i<=1;++i) { x[t]=i; if(i==0) //不放入背包 { backtrack(t+1); } else //放入背包 { //约束条件：放得下并且重量不超过C/w[t] if((CurWeight+w[t])<=C/w[t]) { CurWeight += w[t]; CurValue += v[t]; backtrack(t+1); CurWeight -= w[t]; CurValue -= v[t]; } } } } } int main(int argc, char *argv[]) { backtrack(0); printf("最优值：%d ",BestValue); for(int i=0;i return 0; } ``` 问题：在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。N皇后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。 分析：从n×n个格子中选择n个格子摆放皇后。可见解空间树为子集树。使用Board[N][N]来表示棋盘，Board[i][j]=0 表示(I,j)位置为空，Board[i][j]=1 表示(I,j)位置摆放有一个皇后。全局变量way表示总共的摆放方法数目。使用Queen(t)来摆放第t个皇后。Queen(t) 函数符合子集树时的递归回溯范式。当t>N时，说明所有皇后都已经摆放完成，这是一个可行的摆放方法，输出结果；否则，遍历棋盘，找皇后t所有可行的摆放位置，Feasible(i,j) 判断皇后t能否摆放在位置(i,j)处，如果可以摆放则继续递归摆放皇后t+1,如果不能摆放，则判断下一个位置。 Feasible(row,col)函数首先判断位置(row,col)是否合法，继而判断(row,col)处是否已有皇后，有则冲突，返回0,无则继续判断行、列、斜方向是否冲突。斜方向分为左上角、左下角、右上角、右下角四个方向，每次从(row,col)向四个方向延伸一个格子，判断是否冲突。如果所有方向都没有冲突，则返回1,表示此位置可以摆放一个皇后。 代码： ```python def Queen(t): if t > N: print("Solution #", t, "exists.") return for i in range(N): for j in range(N): if Feasible(i, j): Board[i][j] = 1 Queen(t + 1) Board[i][j] = 0 def Feasible(row, col): if row == col or row + col == N - 1: return False for i in range(row + 1, N): if Board[i][col]: return False for i in range(row - 1, -1, -1): if Board[i][col]: return False for i in range(col + 1, N): if Board[row][i]: return False for i in range(col - 1, -1, -1): if Board[row][i]: return False return True N = int(input()) Board = [[0 for _ in range(N)] for _ in range(N)] Queen(1) ``` ```cpp /*********************************************************************** 2. * 名称：NQueen.cpp 3. * 功 能：回溯算法实例：N皇后问题 4. * 作 者：JarvisChu 5. * 时 间：2013-11-13 6. ********************************************************************8. #include \t\tBoard[i][j]=t+1; //存在冲突 t\t} else { t\tQueen(t+2); //继续递归下一个位置 \t\t}` `}` `}` `}` `way = 0; \t\tQueen(t); //从第t个皇后开始摆放 \t\tprintf("考虑每个皇后都不同，摆放方法：%d\ \",way); //N=8时， way=3709440种 \t\tprintf(\"考虑每个皇后都相同，但是需要除以 N!出去重复的答案(因为相同，则每个皇后可任意调换位置)",way/factorial(n)); //N=8时， way=3709440/8! = 92种 \t\treturn; }` `int main()` `{` `int n = 8; \t\tfactorial(n); //计算阶乘 \t\tQueen(n); //初始化棋盘 \t\treturn 0; }` PS:该问题还有更优的解法。充分利用问题隐藏的约束条件：每个皇后必然在不同的行(列),每个行(列)必然也只有一个皇后。这样我们就可以把N个皇后放到N个行中，使用Pos[i]表示皇后i在i行中的位置(也就是列号)(i = 0 to N-1)。这样代码会大大的简洁，因为节点的子节点数目会减少，判断冲突也更简单。 4. 迷宫问题 问题：给定一个迷宫，找到从入口到出口的所有可行路径，并给出其中最短的路径 分析：用二维数组来表示迷宫，则走迷宫问题用回溯法解决的的思想类似于图的深度遍历。从入口开始，选择下一个可以走的位置，如果位置可走，则继续往前，如果位置不可走，则返回上一个位置，重新选择另一个位置作为下一步位置。N表示迷宫的大小，使用Maze[N][N]表示迷宫，值为0表示通道(可走),值为1表示不可走(墙或者已走过);Point结构体用来记录路径中每一步的坐标(x,y) (ENTER_X,ENTER_Y) 是迷宫入口的坐标 (EXIT_X, EXIT _Y) 是迷宫出口的坐标 Path容器用来存放一条从入口到出口的通路路径 BestPath用来存放所有路径中最短的那条路径 Maze()函数用来递归走迷宫，具体步骤为： 1\. 首先将当前点加入路径，并设置为已走 2\. 判断当前点是否为出口，是则输出路径，保存结果；跳转到4 3\. 依次判断当前点的上、下、左、右四个点是否可走，如果可走则递归走该点 4\. 当前点推出路径，设置[为可] PS:用WPF实现了一个简单的图形化迷宫程序。白色表示通道，红色表示墙，最短的路径用黄色显示。目前实现了一个10*10的迷宫自动搜素最短通路，右侧显示搜索过程中得到的每一个可行通路。由于构造一个迷宫比较复杂，所以暂时“迷宫设置”功能没有做实现，至于手动一步步查看搜素过程的动画也没有做实现。 ```csharp public struct Point { public int X; public int Y; public Point(int x, int y) { X = x; Y = y; } } public class Solution { private static Point[,] maze = new Point[10, 10]; // 用二维数组表示迷宫，值为0表示通道(可走),值为1表示不可走(墙或者已走过) private static Point entrance = new Point(0, 0); // 迷宫入口的坐标 private static Point exit = new Point(9, 9); // 迷宫出口的坐标 private static List private static List public static void Maze() { path.Add(entrance); // 首先将当前点加入路径，并设置为已走 if (path.Contains(exit)) // 如果当前点是出口 { PrintPath(); // 输出路径 PrintBestPath(); // 保存结果 return; // 结束递归 } foreach (var point in GetValidPoints()) // 依次判断当前点的上、下、左、右四个点是否可走 { if (MazeHelper(point)) // 如果可走则递归走该点 { break; // 继续尝试其他点 } } path.RemoveAt(path.Count - 1); // 当前点推出路径，设置为不可走 } private static bool MazeHelper(Point currentPoint) { if (currentPoint.X < 0 || currentPoint.Y < 0 || currentPoint.X >= maze.GetLength(0) || currentPoint.Y >= maze.GetLength(1)) // 如果当前位置越界(出界)或者已经在之前被标记为不可走(墙或者已走过) { return false; // 直接返回false,表示不可走 } if (maze[currentPoint.X, currentPoint.Y] == 1 || IsVisited(currentPoint)) // 如果当前位置已经不可走或者已经被访问过 { return false; // 直接返回false,表示不可走 } path.Add(currentPoint); // 将当前点加入路径，并设置为已走 bestPath.Add(currentPoint); // 将当前点加入最短路径中 if (currentPoint.X == maze.GetLength(0) - 1 && currentPoint.Y == maze.GetLength(1) - 1) // 如果当前点是出口 { return true; // 直接返回true,表示找到了最短路径 } if (IsShortestPath()) // 如果当前点是到最短路径的最近点之一(即不是最后一个点) { bool allSuccess = true; // 先假设所有点都能找到最短路径 for (int i = currentPoint.X + 1; i < maze.GetLength(0); i++) // 从当前点的右边一个点开始尝试向右寻找最短路径 { if (!IsShortestPath()) // 如果不能找到最短路径，说明存在某个点只能沿着这条路走到尽头才能到达出口，那么就不是所有点都能找到最短路径了(因为有部分最短路径需要先经过这些点再回到出口才能形成) { allSuccess = false; // 将allSuccess设为false break; // 直接跳出循环，不再尝试其他点向右寻找最短路径了(因为即使后面的点都找到了最短路径，也无法通过这些点到达出口了) } } for (int i = currentPoint.X - 1; i >= 0; i--) // 从当前点的左边一个点开始尝试向左寻找最短路径 { if (!IsShortestPath()) // 如果不能找到最短路径，说明存在某个点只能沿着这条路走到尽头才能到达出口，那么就不是所有点都能找到最短路径了(因为有部分最短路径需要先经过这些点再回到出口才能形成) { allSuccess = false; // 将allSuccess设为false break; // 直接跳出循环，不再尝试其他点向左寻找最短路径了(因为即使后面的点都找到了最短路径，也无法通过这些点到达出口了) } } for (int i = currentPoint.Y + 1; i < maze.GetLength(1); i++) // 从当前点的下边一个点开始尝试向下寻找最短路径 { if (!IsShortestPath()) // 如果不能找到最短路径，说明存在某个点只能沿着这条路走到尽头才能到达出口，那么就不是所有点都能找到最短路径了(因为有部分最短路径需要先经过这些点再回到出口才能形成) { allSuccess = false; // 将allSuccess设为false break; // 直接跳出循环，不再尝试其他点向下寻找最短路径了(因为即使后面的点都找到了最短路径，也无法通过这些点到达出口了) } } for (int i = currentPoint.Y - 1; i >= 0; i--) // 从当前点的上边一个点开始尝试向上寻找最短路径 { if (!IsShortestPath()) // 如果不能找到最短路径，说明存在某个点只能沿着这条路走到尽头才能到达出口，那么就不是所有点都能找到最�短路径了(因为有部分最短路径需要先经过这些点再回到出口才能形成) { allSuccess = false; // 将allSuccess设为false
