首先，溯字：(su:4声)。
所有代码中的i是指：解向量的层数。
学习要点：
- 回溯法概述
- 典型示例
- 效率分析
1.回溯法概述
问题的解空间、两类典型的解空间
解向量：问题的解可以表示成n元(x1, x2, ..., xn)的解向量形式。
而解空间是指：由于xi的不同取值，所有解向量组成的集合。解空间树：若xi有Si种取值，则最后一层（第n层）包含S1*S2*...*Sn个叶结点——和解空间一样，表示问题的所有可能解。
可行解：解空间中，满足约束条件（显约束、隐约束）的解向量（我们应该寻求最优解）。其中显约束：即每个xi的取值范围。隐约束：即每个分量之间的关系。
搜索空间：根据约束条件的不同，可分为回溯法、分支限界法。
解空间描述清楚了，下面是两类典型的解空间：
一般在路径问题、连通性问题、可平面性检验、着色问题和网络优化问题中应用。
子集树空间：
排列数空间：
回溯法的基本思想、算法框架
典型示例：
nQueen算法：
解向量：(x1, ..., xn)，其中xi是棋盘的每一行(i)放置皇后的列号。
约束条件：显约束：1 <= xi <= n
隐约束：1、xi != xj同一列排除(同一行已经排除掉）；2、同斜向|i - j| != |xi - xj|
给出代码：
#include <iostream>
#include <math.h>
using namespace std;
bool check(int k, int *x)
{
int i = 1;
while (i < k)
{
if (x[i] == x[k] || abs(x[i] - x[k]) == abs(i - k))
return false;
i++;
}
return true;
}
void nQueen(int n, int *x)
{
int k = 1; //当前行号
x[1] = 0;
while (k > 0)
{
x[k] = x[k] + 1;
while ((x[k] <= n) && !check(k, x))
x[k] = x[k] + 1;
if (x[k] <= n)
if (k == n)
{
for (int i = 1; i <= n; i++)
cout << x[i] << " ";
cout << "
";
}
else //下一行
{
k = k + 1;
x[k] = 0;
}
else //回溯
k = k - 1;
}
}
int main()
{
int n = 4, *x = new int[n];
nQueen(n, x);
return 0;
}
图的m着色问题：
解向量：(x1, x2, ... , xn)，其中m种颜色用1...m表示，所以xi的值是每一个顶点的颜色。
解空间：高度为n+1的满m叉树。
搜索空间：由算法决定——由我决定。
子集树问题：
解向量的xi为{0，1}，就是子集树问题。遍历子集树需要O(2n)次计算时间。
经典算法：
- 子集和问题
- 0-1背包问题
- 符号三角形问题
子集和问题：
问题实例为<S, t>，其中S={x1, x2, ..., xn}是一个正整数的集合，而c是一个正整数——>而该问题就是要判定是否存在S的一个子集S1，使得∑x∈S1 x = c。
子集和问题的回溯法：
解向量：(
下面给出代码：
#include <iostream> using namespace std; int n, C; int *S, *x; bool check(int i) { long sum = 0; for (int j = 0; j < n; j++) sum += S[j] * x[j]; if (sum != C) return false; return true; } void Backtrace(int i) { if (i == n) { if (check(i)) { for (int j = 0; j < n; j++) if (x[j]) cout << S[j] << " "; cout << endl; } } else { for (int j = 0; j <= 1; j++) { x[i] = j; Backtrace(i + 1); } } } int main() { cin >> n >> C; S = new int[n]; x = new int[n]; for (int i = 0; i < n; i++) cin >> S[i]; Backtrace(0); return 0; } /*测试数据： 输入： 5 10 2 2 6 5 4 输出： 6 4 2 2 6 */
0-1背包问题：
下面给出代码：
#include <iostream> using namespace std; int n, carry, carryWeight = 0, carryPrice = 0, bestValue = 0; //背包容量，当前重量，当前价值，获得的最大价值 int *price, *weight, *x; //选或不选 int *bestX; void OutPut() { for (int j = 0; j < n; j++) cout << bestX[j]; cout << endl; cout << bestValue << endl; } int boundary(int i) //判断这条路以后的能达到的最大价值，如果超过bestValue，继续走才有可能真的超过bestValue（起到了边界的作用） { int tempW = carryWeight + x[i] * weight[i]; int tempP = carryPrice + x[i] * price[i]; int carryLeft = carry - tempW; int maxValue = tempP; int j = 0; for (j = i + 1; j < n && weight[j] <= carryLeft; j++) { maxValue += price[j]; carryLeft -= weight[j]; } if (j < n - 1) //如果某一步实在装不下了，就强行地按照比例装满该物品，能装就装（不用考虑其他物品，因为预估和实际差不多） maxValue += price[j] * carryLeft / weight[i]; return maxValue; } bool check(int i) { if (carryWeight + x[i] * weight[i] > carry || boundary(i) <= bestValue) //!（先看看当前是否可以装&&如果可以，就从当前装完，看是否可用） return false; return true; } void Backtrace(int i) //第i个物品，当前携带的物品重量，物品价值 { if (i == n) { if (carryPrice > bestValue) { bestValue = carryPrice; for (int j = 0; j < n; j++) bestX[j] = x[j]; } } else { for (int j = 0; j <= 1; j++) { x[i] = j; if (check(i)) { carryWeight += weight[i] * x[i]; carryPrice += price[i] * x[i]; Backtrace(i + 1); carryWeight -= weight[i] * x[i]; carryPrice -= price[i] * x[i]; } } } } int main() { cin >> n >> carry; price = new int[n], weight = new int[n]; x = new int[n], bestX = new int[n]; for (int i = 0; i < n; i++) cin >> price[i]; for (int i = 0; i < n; i++) cin >> weight[i]; Backtrace(0); OutPut(); return 0; } /*测试数据： 输入： 5 10 6 3 5 4 6 2 2 6 5 4 输出： 1 1 0 0 1 15 */
符号三角形问题：
问题描述：
有这样的一个三角形：它是由一定数量的符号，"+"和"-"组成的一个倒三角形。其组成规则是同号下面是"+"，而异号下面是"-"（根据这样的规定，只要给出第一行，就可以画出整个三角形）。最后得到的三角形的"+"和"-"个数相同。我们要解决的问题是：给定第一行符号的个数，求出有多少个符号三角形。
问题分析：
代码：