回溯算法
“不进则退，不喜则忧，不得则亡，此世人之常。”----《邓析子·无后篇》
文章目录
- 回溯算法
- 前言
- 一、回溯和回溯算法
- （1）何为"回溯"？
- (2) 何为"回溯算法"？
- 二、实例展现----0-1背包问题
- （1）问题简述
- (2) 问题分析
- (3) 算法设计
- (4) 模拟过程
- （5） 代码实现
- 总结
- 致谢
前言
回溯法被称为万能解法，更内涵退一步海阔天空的人生哲理。
一、回溯和回溯算法
（1）何为"回溯"？
遗失的美好，你想在重复中找回当时的心动，沿着轨迹回溯，路过的风景却全都已经不是当年的意味。世界上只剩下两种人：像她的和不像她的。
(2) 何为"回溯算法"？
回溯法是一种选优搜索法，按照选优条件深度优先搜索，直至达成目标。当搜索到某一步时，发现原先选择并不是最优或无法达到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态称为“回溯点”。
二、实例展现----0-1背包问题
（1）问题简述
0-1背包问题：提供一个容量（也可以看作是载重量）是W的购物车和n件物品，每个物品 i 对应的价值为Vi，重量为Wi，每个物品只有一件，要么装入要么不装入，不可拆分，如何选择物品，使装入购物车的价值最高。
(2) 问题分析
从n件物品中选择一些物品，相当于从n个物品组成的集合S中找到一个子集，该子集的所有物品的总重量不得超过购物车的容量，并且这些物品在满足条件的情况下总价值最大。
(3) 算法设计
1. 定义问题的解空间
对于每个物品，都只有两种结果，装入和不装入，但是该物品是否装入为未知，所以为方便期间，可以定义变量 Xi 来表示第 i 个物品是否装入，如果装入则使 Xi 的值为1，否则为0，该问题解的形式是一个n元组，且每个分量的取值为 0 或 1.由此可知，问题的解空间为{ X1 ，X2 ，X3，······ ，Xn },其中Xi为0 或 1，i 为1，2，3，4，······ ，n。
2. 确定解空间的组织结构
不难看出该问题的解是 n 个元素组成的集合所有子集个数。
例如 n 的值为3（即物品共有3个），那么解空间是{ 0， 0，0 } ， { 0 ，0 ，1 }， { 0 ， 1， 1 }， { 1 ，1，1 }， { 0 ，1 ，0 }， { 1 ，0 ，0 }， {1 ，0 ，1 }，{ 1 ，1 ，0 }。
可见问题的解空间树的深度为问题的规模 n （也就是物品的总数量）。
3. 搜索解空间
约束条件：
可容易看出 ∑Wi Xi<=W (下界是i=1，上界是n）
限界条件
根据解空间的组织结构，对于任意一个中间结点z，从根节点到z结点的分支所代表的状态（是否装入购物车）已经确定，从z到其子孙结点的分支状态不确定，也就是说，如果z在解空间树中处于第t层，说明第一种物品到第t-1 种物品的状态已经确定，我们只需要沿着z的分支扩展确定第t种物品的状态即可。为方便起见，我们用 CP 表示已经装入购物车的物品的总价值，切记，已装入的价值高并不一定是最优的，因为还有其他情况未确定。
由于我们未确定第t+1种物品到第 n 种物品的实际情况，所以只能估计他们的情况，假设第t+1种物品到第n种物品都装入购物车，第t+1种物品到第n种物品的总价值用 rp 表示，因此 CP+rp是所有从根出发经过中间结点z的可行解的价值上界。
如果价值上界小于或等于当前搜索到的最优值（最优值用bestp表示，初始值为0），则无继续搜索的必要，反之，则继续搜索。
限界条件为： CP+rp>bestp
搜索过程
从根节点开始，深度优先式的搜索，根节点首先成为活结点，也是当前拓展结点。定义左分支为1，即左子树表示该物品放入购物车，右分支为0，表示不放入购物车。起始沿着左分支进行拓展，往后需要判断是否满足限定条件，如果满足则继续沿着左分支拓展，否则沿着右分支拓展，如果不满足则回溯到最近的父亲结点继续拓展其他情况，直到所有情况都被考虑到。
(4) 模拟过程
假设现在有4个物品和一个购物车，每个物品的重量w为（2，5，4，2），价值为（6，3，5，4），购物车重量W是10.
1.初始化
sumw和sumv分别用来统计所有物品的总重量和总价值。sumw=13，sumv=18，sumw>W，因此不能全部装完，需要择优选取。当前放入购物车的重量是cw=0，当前放入购物车的价值为cp=0，当前最优值bestp=0.
2.搜索第一层
扩展 1 号结点，首先判断cw+w[1]=2<W,满足约束条件，扩展左分支，令X[1]=1,cw=cw+w[1]=2,cp=cp+v[1]=6,生成二号节点。
3.扩展2号结点
首先判断cw+w[2]=7<W,满足约束条件，扩展左分支，令x[2]=1,cw=cw+w[2]=7,cp=cp+v[2]=9,生成三号节点。
4. 扩展3号结点
首先判断cw+w[3]=11>W,超过了购物车容量，第三个物品不能放入。那么判断bound(t+1)是否大于bestp。bound（4）中剩余物品只有第四个，rp=4,cp+rp=13,bestp=0,因此满足限界条件，扩展右子树。令x[3]=0,生成四号结点。
5. 扩展4号结点
首先判断cw+w[4]=9<W,满足约束条件，扩展左分支，令x[4]=1,cw=cw+w[4]=9,cp=cp+v[4]=13,生成5号结点。
6. 扩展5号结点
t>n,找到当前一个最优解，用bestx[ ]保存当前最优解{ 1 ，1 ，0， 1 }，保存当前最优值bestp=13，5号结点成为死点。
7. 回溯到4号结点，一直向上回溯到2号结点。
向上回溯到4号结点，回溯时cw=cw-w[4]=7,cp=cp-v[4]=9.如何加上的，如何减去。4号结点右子树还未生成，考察bound（t+1）是否大于bestp，判断可知不满足条件，故不在扩展4号结点的右分支，4号结点为死点。向上继续回溯至3号结点，3号结点左右孩子都已经考察过，为死点。继续回溯至2号结点，回溯时cw=cw-w[2]=2,cp=cp-v[2]=6.
8. 扩展2号结点
2号结点右子树还未生成，考察bound(t+1)是否大于bestp，bound（3）中剩余物品为第3、4个物品，rp=9,cp+rp=15>bestp=13,满足条件，扩展右子树。令x[2]=0,生成6号结点。
9. 扩展6号结点
首先判断cw+w[3]=6<W,满足约束条件，扩展左分支，令x[3]=1,cw=cw+w[3]=6,cp=cp+v[3]=11,生成7号结点。
10. 扩展7号结点
首先判断cw+w[4]=8<W,满足约束条件，扩展左分支，令x[4]=1,cw=cw+w[4]=8,cp=cp+v[4]=15,生成8号结点。
11. 扩展8号结点
t>n,找到一个最优解，用bestx[ ]保存最优解{ 1 ， 0 ，1 ，1 }，保存最优值bestp=10,8号为死点，回溯至7号结点，cw=cw-w[4]=6,cp=cp-v[4]=11.
12. 扩展7号结点
7号右子树还未生成，考察发现不满足限界条件，不再扩展，向上回溯至6号结点，cw=cw-w[3]=2,cp=cp-v[3]=6.
13. 扩展6号结点
6号结点右子树未生成，判断发现不满足限界条件，向上回溯至2号结点，cw=cw-w[1]=0,cp=cp-v[1]=0.
14. 扩展1号结点
1号结点右分支未生成，判断发现不满足限界条件，算法结束。
（5） 代码实现
C++代码
double Bound(int i) //计算上界
{
int rp=0; //剩余物品为第i到n种物品。
while(i<=n) //依次计算剩余物品的价值
{
rp+=v[i];
i++;
}
return cp+rp; //返回上界
}
void Backtrack(int t) //t表示当前扩展结点在第t层
{
if(t>n)
{
for(j=1;j<=n;j++)
{
bestx[j]=x[j];
}
bestrp=cp;
return ;
}
if(cw+w[t]<=W)
{
x[t]=1;
cw+=w[t];
cp+=v[t];
Backtrack(t+1);
cw-=w[t];
cp-=v[t];
}
if(Bound(t+1)>bestp)
{
x[t]=0;
Backtrack(t+1);
}
}
Python代码
def backtrack(i):#global是可以让函数处理函数外的变量
global bestV, curW, curV, x, bestx
if i >= n:
if bestV < curV:
bestV = curV
bestx = x[:]
else:
if curW + w[i] <= c:
x[i] = True
curW += w[i]
curV += v[i]
backtrack(i + 1)
curW -= w[i]
curV -= v[i]
x[i] = False
backtrack(i + 1)
if __name__ == '__main__':
n = 5
c = 10
w = [2, 2, 6, 5, 4]
v = [6, 3, 5, 4, 6]
x = [False for i in range(n)]
backtrack(0)
print(bestV)
print(bestx)
Java代码：引用自CSDN博主：落雪侵越，文章链接：落雪侵越
/**
* 回溯
* @param t
*/
public static void BackTrack(int t) {
if(t>count) {//到达叶结点
if(cp>bestp) {
for(int i = 1;i<=count;i++) {
bestx[i] = cx[i];
}
bestp = cp;
}
return;
}
r -= p[t];
if(cw + w[t] <= c) {//搜索左子树
cx[t] = 1;
cp += p[t];
cw += w[t];
BackTrack(t+1);
cp -= p[t];//恢复现场
cw -= w[t];//恢复现场
}
if(cp + r >bestp) {//剪枝操作
cx[t] = 0;//搜索右子树
BackTrack(t+1);
}
r += p[t];//恢复现场
}
C语言：转自CSDN博主：永远的9，文章地址：永远的9
#include<stdio.h>
#define max 100
int weight[max];
int value[max];
int n,max_weight,max_value;
int best_answer[max],answer[max];
void print()
{
int i,j,k,l;
printf("+++++++++++++%d++++++++++++\n",max_value);
for(i=1;i<=n;i++)
printf("%d ",best_answer[i]);
printf("\n");
}
void DFS(int level,int current_weight,int current_value)
{
if(level>=n+1)
{
if(current_value>max_value)
{
int i;
max_value = current_value;
for(i=1;i<=n;i++)
best_answer[i] = answer[i];
}
}
else
{
if(current_weight>=weight[level+1])
{
current_weight = current_weight - weight[level+1];
current_value = current_value + value[level+1];
answer[level+1] = 1;
DFS(level+1,current_weight,current_value);
answer[level+1] = 0;
current_weight = current_weight + weight[level+1];
current_value = current_value - value[level+1];
}
DFS(level+1,current_weight,current_value);
}
}
void init()
{
int i,j,k,l;
max_value = 0;
for(i=1;i<=n;i++)
answer[i] = 0;
}
int main()
{
int i,j,k,l;
while(scanf("%d%d",&n,&max_weight)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&weight[i]);
for(j=1;j<=n;j++)
scanf("%d",&value[j]);
init();
DFS(0,max_weight,0);
print();
}
return 0;
}
总结
回溯算法本质是一种暴力算法，毕竟在绝对实力的面前，一切花里胡哨都如蝼蚁。本人才疏学浅，出错在所难免，还望各位不吝赐教，多加指正，鄙人先行谢过。最后，送大家一句话：风可以吹灭蜡烛，却能使火越烧越旺！
致谢
感谢CSDN博客专家、2020年博客之星TOP5、蓝桥杯签约作者1_bit对本 人Python和算法学习的建议；
感谢南阳理工学院陈小玉教授的网络远程指导；
感谢滴滴出行的刘景亮学长对本人C++的指导以及数据结构与算法的宝贵建议和资源的分享；
感谢致易王俊学长对本人Python算法实现的调试、建议与帮助；
感谢知某、某Code、某Time上各网友的建议和资源分享。