回溯算法
1.回溯法的简介
回溯法就是在尝试穷举搜素的同时，当发现某一步走不通时，可以回退到前一步，继续寻找问题的解。
2.回溯法的解题步骤
- 针对问题确定问题的解空间树，问题的解空间树可以包含问题的一个解或者多个可行解。
- 根据题目要求，确定树的扩展搜索规则。
- 用深度搜索的方式搜索解空间树，并在搜索的同时可以采用剪枝函数去避免不必要的搜索，其中，搜索的方式可以采取递归和非递归去回溯
3.回溯的种类
我们大致可以将回溯问题分为两大类问题上，一类是排列树问题，一类是子集树问题。
大多的算法都是这两类，但是千万不可局限这两类树空间，我当时每次做题就非得把这个题架构到这两类树上，看属于哪个用哪个，一定要灵活处理，有其它类的解空间树
接下来我会通过解析几个经典的题目，细细的从空间树，回溯方式，和代码的几个角度去解析回溯法，希望你能坚持看完。
4.回溯的解题框架
空间树是子集树
void backtrack(int leve,int len)
{
//到达了叶子
if (leve > len)
{
...
}
else {
for (j = 下届; j < 上界; j++)
{
if (满足限界条件)
{
backtrack(leve+1, int len)//回溯下一层
}
}
}
}
空间树是排列树
void backtrack(int leve, int len)
{
if (leve > len)
{
...
}
else {
for (j = 下届; j < 上界; j++)
{
swap（data[leve]，data[j]）;
if (满足限界条件)
{
backtrack(leve + 1, len);//回溯下一层
}
swap（data[leve]，data[j]）;
}
}
}
问题1
给一个数列，求该数列的幂级
分析:首先我来帮大家回忆下幂级的概念，我直接举例子吧，我表达可能不清晰，直接举例子写，你就会了。
（1，2，3）的幂级是(),(1),(2),(3),(1,2),(1,3),(2,3),(1,2,3),第一个括号里面是空集的意思。我们仔细分析，这个是回溯的哪个种类?子集树？还是排列树？其它？当然，你肯定可以分析出这个是子集树。
画解空间:
我来分析下我画的子集树，树的左边总是代表选择当前的数字。右边总是代表不选择当前的数字。首先根节点初始是空集，走到第二层，第二层是对数字1的选择，走左边，集合是1，走右边集合还是空的，继续往第三层扩展，集合1走左边选择数字2，集合变(1,2),走右边不选择数字2，集合还是(1),右边同样的道理。继续向下扩展，直到数字3被扩展进去，结束。此时得到的解空间树就是我们的幂级了。是不是很神奇
代码部分
void Get_Power_Set(int *arr1, int *arr2, int len, int index)
{
//回溯到叶子时，直接打印幂集
if (index >= len)
{
printf("( ");
for (int i = 0; i < len; i++)
{
if (arr2[i] != 0)
{
printf("%d ", arr2[i]);
}
}
printf(")\n");
}
else
{
//选择这个数字
arr2[index] = arr1[index];
Get_Power_Set(arr1, arr2, len, index + 1);
//不选择这个数字
arr2[index] = 0;
Get_Power_Set(arr1, arr2, len, index + 1);
}
}
问题2
在象棋算法里，每个棋子都代表0-9中数字，每个棋子代表的数字不一样。有下图的一个算式，请用回溯法推导出兵炮马卒车分别代表哪些数字
hs1.jpg
分析：我们用穷举法很容易计算出这个题，但是我们现在要求用回溯法解决这个题。
首先我们分析问题的空间树是哪一类？每个棋子都要去尝试不同的数字，所以它是一棵子集树。
画解空间树
因为数字太多了，我画了一部分，第二层就是兵的可选择的数字0-9，那么下一层马的就得少一个数字的选择.一直往下到车，一直比上一层少一个数字的选则，总共除去根节点就5层。
代码
//象棋算法
void play_Chess()
{
int temp[10];//代表当前下标对应数字是否使用
for (int i = 0; i < 10; i++)
{
temp[i] = 0;
}
//开始计算
for (int a = 1; a < 10; a++)//----------棋子炮
{
temp[a] = 1;
for (int b = 0; b < 10; b++)//----------棋子马
{
if (temp[b] == 0)
{
temp[b] = 1;
for (int c = 0; c < 10; c++)//----------棋子车
{
if (temp[c] == 0)
{
temp[c] = 1;
int x, y, z;
x = b * 10 + c;
y = c * 10 + a;
z = a * 100 + a * 10 + b;
if (x + y == z)
{
printf("炮:%d 马:%d 车%d\n", a, b, c);
}
}
temp[c] = 0;
}
}
temp[b] = 0;
}
temp[a] = 0;
}
}
问题3
简单0/1背包问题：有n个重量分别为w1,w2,w3..的背包对应的价值分别是v1,v2,v3,..
给定一个容量为W的背包，设计装入物品，使得背包价值最大，注意此处的条件是两个，所选择物品重量恰好等于容量和物品总价值最大。下图是不同物品的价值和重量
| 物品编号 | 重量 | 价值 |
|---|---|---|
| 1 | 5 | 4 |
| 2 | 3 | 4 |
| 3 | 2 | 3 |
| 4 | 1 | 1 |
背包的最大容量设置为6
分析
首先，对于每个物品，我们都是选择与不选择问题，那解空间就是子集树，其次，由于要求容量不能超过背包容量，这个就涉及剪枝函数了，就是当加入某个物品时，超过了背包最大容量，我们就剪枝，停止向下找。其实还存在一个剪枝函数，这个不容易发现，就是当我们考虑某件物品装入时，如果把剩余物品都装入，都不能装满背包，那也要剪枝，因为题目要求的是刚好填满背包。
空间树
首先初始物品总重量是0，总价值也是0。
进入第一层时，走左边代表选择物品1，走右边不选择物品1，当选择了物品1时，对应的总重和价值就是(5,4)进行剪枝函数判断，此时的总重量没有超过背包最大容量，不剪枝，进行第二个剪枝函数的判断，当加入其它所有剩余物品时，可以撑满背包，也不剪枝。当不选择物品1时，对应的总重和价值就是(0，0)进行剪枝函数判断，首席按容量不超过背包，其次加入其它剩余物品，也可以盛满，不剪枝。
接下来就是第二层(5,4)节点的拓展了，向左是选择物品2，此时的总重和总价值是(8,8),我们发现超过了背包容量，进行剪枝，所以左边停止搜素了，右边代表不选择，因此总重和总价这不变，还是(5,4)，搜先容量没超过，其次加上剩余物品总重量也可以超过容量，也不用剪枝。然后是第二层(0,0)节点的扩展了，走左边选择物品2,此时总重量没超过背包容量，同样的，加上剩余物品可以盛满背包，所以不用被剪枝，此时的总重和总价值更新为(3,4),走右边表示不选择物品2，背包容量足够，但是加上剩余物品，不足以撑满背标，剪枝。
因为后面步骤和上面都一样，所以大家按照上图手动推导就行了。
代码
void backpack_01(int *result, int *w, int *v, int sumW, int sumV,int index,int len)
{
//如果扩展到叶子节点
if (index >= len)
{
//如果符合条件，就输出最优解
if (sumW == weight)
{
for (int i = 0; i < len; i++)
{
if (result[i] != -1)
{
printf("物品编号: %d\n", i + 1);
}
}
printf("总重量是: %d,最大价值是: %d\n",sumW, sumV);
}
}
else
{
if (sumW + w[index] <= weight)
{
sumWeight -= w[index];
result[index] = index;
backpack_01(result, w, v, sumW+w[index], sumV+v[index], index + 1, len);
}
if (sumW + sumWeight >= weight)
{
result[index] = -1;//不选择
sumWeight += w[index];
backpack_01(result, w, v, sumW, sumV, index + 1, len);
}
}
}
问题4
有n个集装箱要装入一艘轮船，轮船的载重量为W，现在要从集装箱中选出若干个，使得它们重量和等于W，且要求货物的个数最少。
假设我们题目的W是10，n = 5,每个货物的重量是5,2,6,4,3
分析
这里的每个货物都是选择与不选择问题，所以肯定是解空间是子集树问题。和背包问题一样，左分支的剪枝条件是当前总重量不超过最大载重量，右分枝的剪枝条件是当前剩余物品加上当前选择物品总重量大于载重量。在满足条件里面挑选出集装箱个数最少的就是问题的解了。
解空间树
此处的解空间树，很明显就是子集树，每个物品都权衡在选择与不选择之间，当然注意问题的两个细节，就是要求物品重量恰好等于轮船最大承重，且物品个数最少。这个和上面的背包问题一样，它有两个剪枝条件，一个是当前每加入一件货物，判断是否超重，另一个剪枝条件就是不加入当前货物时，剩下的货物和此时加上去的货物的重量是否能满足货物总重量等于轮船载重量的条件。
代码
void optimal(int *result, int *w, int sumW, int index, int len,int maxWeight)
{
if (index >= len)
{
int count=0;
for (int i = 0; i < len; i++)
{
if (result[i] != 0)
{
count++;
printf("货物%d被选\n", i+1);
}
}
printf("总个数%d\n",count);
}
else
{
if (sumW + w[index] <= maxWeight)
{
result[index] = 1;
optimal(result, w, sumW + w[index], index+1, len, maxWeight);
}
result[index] = 0;
optimal(result, w, sumW, index + 1, len, maxWeight);
}
}
<h3 style="color:red">问题5</h3>
求解任务分配问题
问题描述：
有n个任务需要分配给n个人执行，每个任务只可以分配给一个人，每个人只可以执行一项任务，每个人执行不同任务所花费的成本也不同，求出总成本最小的方案。
| 人员 | 任务1 | 任务2 | 任务3 | 任务4 |
|---|---|---|---|---|
| 1 | 9 | 2 | 7 | 8 |
| 2 | 6 | 4 | 3 | 7 |
| 3 | 5 | 8 | 1 | 8 |
| 4 | 7 | 6 | 9 | 4 |
此时就是4个人，4个任务，求出最小成本的方案。
思路：我们可以把每个人对应的每种方案列举出来，就是按照全排列的方式，假设一种排列是(1,2,3,4),指的是1号人员执行1号任务，2号执行2号任务.....再比如(4,2,1,3)就是1号人员执行4号任务，2号人员执行2号任务....将所有列举出来的计算成本，成本最小的就是我们所求的方案.
空间树
经过上面的分析，大家都知道这个是排列树，我来画画本题的排列树。
代码
void task_Assign(int *data, int len, int index, int (*task)[4])
{
if (index >= len)
{
int sum=0;
//处理排列的数据
for (int i = 0; i < len; i++)
{
sum += task[i][data[i]-1];
}
if (sum < minCost)
{
minCost = sum;
}
}
else {
for (int i = index; i < len; i++)
{
int temp = data[i];
data[i] = data[index];
data[index] = temp;
task_Assign(data, len, index + 1,task);
temp = data[i];
data[i] = data[index];
data[index] = temp;
}
}
}
问题6
n皇后问题
客观莫着急，鄙人在加急code中...更新完毕第一时间发布。
问题7
全排列问题
分析：首先，我们得知道全排列的概念，其实就是数列的排列组合，例如（1，2，3）的全排列有(1,2,3) (1,3,2) (2,1,3) (2,3,1) (3,1,2) (3,2,1)共六种，这个问题其实可以用回溯的第二种空间树思想解决
空间树：
此题对应的空间树就是子集树了，我们直接看看这棵树，然后一步步分析。假设现在求(1,2,3)的全排列。
首先第一层是数列(1,2,3),首先来到第二层的第一个，让a[0]与a[0]交换数列还是(1,2,3),接着是第一层的第二个让a[0]与a[1]交换，数列是(2,1,3),接着让a[0]与a[2]交换数列是(3,2,1)，此时最高就是a[2],结束，到了第三层第一个让a[1]与a[1]交换,数列是(1,2,3),让a[1]与a[2]交换数列是(1,3,2),其它子树依次类推。
代码
void sort_All(int *data,int index, int len)
{
if (index >= len)
{
printf_s("( ");
for (int i = 0; i < len; i++)
{
printf("%d ", data[i]);
}
printf_s(") ");
}
else {
for (int i = index; i < len; i++)
{
//交换数据
int temp = data[i];
data[i] = data[index];
data[index] = temp;
sort_All(data, index + 1, len);
//恢复数据
temp = data[i];
data[i] = data[index];
data[index] = temp;
}
}
}
问题8
活动安排问题
问题
假设现在有一个活动表，里面包含了每个活动的开始时间和结束时间，每一时刻只能有一个活动被执行，问最多可以有多少个活动被安排。
| 活动编号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 开始时间 | 1 | 2 | 4 | 6 |
| 结束时间 | 3 | 5 | 8 | 10 |
分析
看上面的活动表，我们可以得知活动1和活动2不可以同时被选择，因为时间冲突，而活动1和活动3可以被安排。我们可以将所有活动按编号进行排列树的排列，然后对每个序列进行分析，从中找出最多被安排的活动。
空间树
这个空间树和上面的空间树是一个空间树，都是排列树的4层
代码
void plan_Activity(struct task * t, int *data, int index, int len)
{
if (index >= len)
{
int count = 1,last;
//进行活动安排个数的统计,打印每个活动的顺序
last = t[data[0]-1].end;//结束时间
for (int i = 1; i < len; i++)
{
if (t[data[i]-1].begin >= last)
{
count++;
last = t[data[i]-1].end;
}
}
if (count > maxCount)
{
maxCount = count;
}
}
else {
for (int i = index; i < len; i++)
{
int temp = data[index];
data[index] = data[i];
data[i] = temp;
plan_Activity(t, data, index + 1, len);
temp = data[index];
data[index] = data[i];
data[i] = temp;
}
}
}
获取完整代码
我分别用C，C++，JAVA三种主流语言编写了完整代码，请大家指导批正，一起学习。
