一、算法思想

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。有时会遇到这样一类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点 再于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。但是，对于可以得出明显的递推公式迭代求解的问题，还是不要用回溯 法，因为它花费的时间比较长

二、算法要素

1、解空间

用回溯法解决实际问题的时候，首先确定解的形式，定义问题解空间

（1）解的组织形式为一个n元组{x1,x2,x3…..,xn}

（2）解的取值范围

例如0-1背包问题：

0-1背包问题可以抽象成一个容量有限（容量设为W）的背包装东西，每个商品都有自己的体积w和价值v，目的就是用这个容量有限的背包装满价值总量最大的东西

例如有3个物品， 解的组织形式为{x1,x2,x3}。它的解分量xi的取值范围很简单，xi=0或者xi=1。xi=0表示第i个物品不放入包，xi=1表示第i个物品放入背包，因此

xiϵ{0,1}

3个物品的0-1背包问题，其所有可能解有：{0,0,0}，{0,0,1}，{0,1,0}，{0,1,1}，{1,0,0}，{1,0,1}，{1,1,0}，{1,1,1}

解空间：所有可能解组成的空间，而我们需要根据问题的约束条件，在解空间中寻找最优解，如下图所示：

解空间越小，搜索效率越高。解空间越大，搜索效率越低

（3）搜索解空间

隐约束指对能否得到问题的可行解或最优解做出的约束

如果不满足隐约束，就说明得不到问题的可行解或最优解，那就没必要在沿着该节点的分支进行搜索了，相当于把这个分支减掉了。因此，隐约束也称为剪枝函数，实质不是减掉分支，而是不再搜索该分支

例如3个物品的0-1背包问题，如果前2个物品放入（x1=1，x2=1）后，背包超重了，那就没必要再考虑第3个物品是否放入背包的问题相当于剪枝了，如下图所示：

隐约束（剪枝函数）包括约束函数和限界函数

解空间的大小和剪枝函数的好坏直接影响搜索效率，因此这两项是搜索算法的关键，在搜索空间时，有几个术语需要说明：

（1）、扩展节点：一个正在生长孩子的节点

（2）、活节点：一个自身已生成，但孩子还没有全部生成的节点

（3）、死节点：一个所有孩子都已经生成的节点

（4）、子孙：节点E的子树所有节点都是E的子孙

（5）、祖宗：从节点E到树根路径上的所有的节点都是E的祖宗

2、解题步骤：

（1）定义解空间

因为解空间的大小对搜索效率有很大影响，因此使用回溯法首先定义合适的解空间，确定解空间包括解的组织形式和显约束

解的组织形式：解的组织形式都规范为一个n元组{x1,x2,…….,xn}，只是具体表达含义不同而已

显约束：对解取值范围的限定，通过显约束可以控制解空间的大小

（2）确定解空间的组织形式

解空间的组织结构通常用解空间树形象的表达，根据解空间的不同，解空间分为子集树、排列树、m叉树

（3）搜索解空间

回溯法是按照深度优先搜索策略，根据约束（约束函数和限界函数），在解空间中搜索问题的可行解或最优解，当发现当前节点不满足求解条件时，就回溯尝试其它路径

如果问题只是要求可行解，则只需设定约束函数即可，如果要求最优解，则需要设定约束函数和限定函数

解的组织形式都是通用的n元组形式，解的组织结构是解空间的形象表达。解空间和隐约束是控制搜索效率的关键。显约束可以控制解空间

三、算法设计过程

以01背包问题为例：假设有n个物品，每个物品i对应的价值为vi，重量为wi，购物车容量为W，每个物品只有1件，要么装入要么不装入不可拆分，如何装入物品的总价值最大？

2、设计过程

（1）定义问题解空间

每个物品有且只有2种状态，要么装入，要么不装入。我们用变量xi表示第i个物品是否被装入购物车的行为，如果用"0"表示不装入背包，用"1"表示装入背包，则xi的取值为0或者1，i=1,2,3,4,5….，第i个物品装入购物车xi=1；不装入购物车xi=0。该问题的解形式是一个n元组,且每个分量的取值为0或1

由此得到问题解空间为{x1,x2,x3,……xi，…..,xn}，其中，显约束xi=0或1，i=1,2,3….n

（2）确定解空间的组织结构

问题的解空间描述了2的n次方可能解，也就是说n个元素组成的集合所有子集个数。例如3个物品的购物车问题，解空间是：{0,0,0}、{0,0,1}、{0,1,0}、{0,1,1}、{1,0,0}、{1,0,1}、{1,1,0}、{1,1,1}。该问题有2的3次方个可能解

（3）搜索解空间

【1】约束条件

解空间包含2的n次方种可能解，存在某种或某些物品无法装入的情况，因此需要设置约束条件，判断装入物品总重量是否超过总容量，如果超出，为不可行解；否则为可行解。搜索过程不再搜索那些导致不可行解的节点及其孩子节点，约束条件为：

w1x1 + w2x2 + w3x3+….<=W

【2】界限条件

可行解可能不止一个，问题的目标是找一个装入购物车的物品总价值最大的可行解，即最优解。因此，需要设置界限条件来加速该最优解的速度

根据解空间的组织结构，对于任何一个中间节点z（中间状态），从根节点到z节点的分支所代表的状态已经确定，从z到其子孙节点的分支的状态是不确定的。也就 是说，如果z在解空间树中所处的层次是t，说明第1种物品到第t-1种物品的状态已经确定了。我们只需要沿着z的分支扩展很容易确定第t种物品的状态。那么前t种物品的状态就确定了。但第t+1种物品到第n种物品的状态还不确定。这样，前t种物品的状态确定后，当前已装入购物车的物品的总价值，用c p表示。已装入物品的价值高不一定就是最优的，因为还有剩余物品未确定

我们还不确定第t+1种物品到第n种物品的实际状态，因此只能用估计值。假设第t+1种物品到第n种物品都装入购物车，第t+1种物品到第n种物品的总价值用rp来表示，因此cp + rp是所有从根出发经过中间节点z的可行解的价值上界，如图：

如果价值上界小于或者等于当前搜索到的最优值（最优值用bestp表示，初始值为0），则说明从中间节点z继续向子孙节点搜索不可能得到一个比当前更优的可行解，没有继续搜索的必要，反之，则继续向z的子孙节点搜索，界限条件为：

cp + rp >bestp

3、搜索过程

从根节点开始，以深度优先地进行搜索。根节点首先成为活节点，也是当前的扩展节点。由于子集树中约定左分支上的值为"1"，因此沿着扩展节点的左分支扩展，则代表装入物品。此时，需要判断是否能够装入该物品，即判断约束条件是否成立，如果成立，即生成左孩子节点，左孩子节点成为活节点，并且成为当前的扩展节点，继续向纵深节点扩展；如果不成立，则剪掉扩展节点的左分支，沿着其右分支扩展，右分支代表物品不装入购物车，肯定有可能导致可行解。但是沿着右分支扩展有没有可能得到最优解呢？这一点需要由界限条件来判断。如果界限条件满足，说明有可能导致最优解，即生成右孩子节点，右孩子节点成为活节点，并成为当前扩展节点，继续向纵深节点扩展；如果不满足限界条件，则剪掉扩展节点的右分支，向最近的祖宗活节点回溯。搜索过程直到所有活节点变成死节点结束

四、算法案例

（一）、案例-1

假设现有4个物品，每个物品的重量w为（2，5，4，2），价值v为（6，3，5，4），只能装入袋子的总容量W为10，问把哪些物品装入袋子，才能获得最大价值？

1、算法设计过程

（1）、初始化

sumw和sumv分别用来统计所有物品的总重量和总价值。sumw = 2 + 5 + 4 +2 =13，

sumv = 6 + 3 + 5 +4 =18 ，sumv > W因此不能全部装完，需要搜索求解。初始化当前放入购物车的物品重量cw = 0；当前放入购物车的物品价值cp = 0；当前最优值bestp = 0

（2）、开始搜索第1层（t = 1）

扩展1号节点，首先判断cw + w[1] = 2 < W，满足约束条件，扩展左分支，

令x[1] = 1 ，cw = cw + w[1] = 2，cp = cp + v[1] = 6，生成2号节点，如图所示：

（3）扩展2号节点（t = 2）

首先判断cw + w[2] = 7 < W，满足约束条件，扩展分支，令x[2] = 1，

cw = cw + w[2] = 7，cp = cp + v[2] = 9，生成3号节点，如图所示：

（4）扩展3号节点（t = 3）

首先判断cw + w[3] = 11 > W，超过了购物车容量，第3个物品不能放入。那么判断bound( t + 1 )是否大于bestp。bound(4)中剩余物品只有第4个，rp = 4，

cp + rp = 13，bestp = 0，因此满足界限条件，扩展右子树。令x[3] = 0，生成4号节点，如图所示：

（5）扩展4号节点（t = 4）

首先判断cw + w[4] = 9 < W，满足约束条件，扩展左分支，令x[4] = 1，令

cw = cw + w[4] = 9 ，cp = cp + v[4] = 13，生成5号节点

（6）扩展5号节点（t = 5）

t > n ，找到一个当前最优解，用bestx[]保存当前最优解{1,1,0,1}，保存当前最优解bestp = cp = 13，5号节点成为死节点

（7）回溯到4号节点（t =4），一直回溯到2号节点

向上回溯到4号节点，回溯时cw = cw – w[4] = 7，cp = cp – v[4] = 9，怎么加上的，怎么减回去。4号节点右子树还没生成，考察bound(t+1)是否大于bestp，bound(5)中没有剩余物品，rp = 0，cp + rp = 9，bestp = 13，因此不满足界限条件，不能在扩展4号右子树节点。4号节点成为死节点

向上回溯，回溯到3号节点，3号节点的左右孩子均已考察过，是死节点

向上回溯到2号节点，回溯时cw = cw – w[2] = 2，cp = cp – v[2] =6。怎么加上去怎么减去

如下图所示：

（8）扩展节点2（t = 2）

2号节点右子树还未生成，考察bound（t + 1）是否大于bestp，bound(3)中剩余物品为第3、第4个，rp = 9 ， cp + rp =15 ，bestp = 13，因此满足界限条件，扩展右子树。令x2 = 0生成6号节点

（9）扩展6号节点（t = 3）

首先判断cw + w[3] = 6 <W，满足约束条件，扩展左分支，令x[3] =1，

Cw= cw + w[3] = 6，cp = cp + v[3] =11，生成7号节点，如图所示：

（10）扩展7号节点（t = 4）

首先判断 cw + w[4] = 8 < W，满足约束条件，扩展左分支，令x[4] =1，

cw = cw + w[4] = 8，cp = cp + v[4] = 15，生成8号节点，如图：

（11）扩展8号节点（t =5）

t > n（n=4），找到当前个最优解，用bestx[]保存当前最优解{1，0，1，1}，保存当前最优解值bestp = cp = 15 ， 8号节点成为死节点

向上回溯到7号节点，回溯时cw = cw – w[4] = 6、cp = cp –v[4] =11，怎么加的怎么减去

（12）扩展7号节点（t =4）

7号节点的右孩子树还没有生成，考察bound(t + 1)是否大于bestp，bound(5)中没有剩余产品, rp =0、 cp + rp =11，bestp = 15，因此不满足界限条件，不再扩展7号节点的右子树。7号节点成为死节点

向上回溯，回溯到6号节点，回溯时cw = cw – w[3] = 2、cp=cp-v[3]=6怎么加的怎么减

（13）扩展6号节点（t =3）

6号节点的右子树还未生成，考察bound(t+1)是否大于bestp，bound(4)中剩余物品是第4个，rp = 4、cp + rp = 10，bestp=15因此不满足界限条件，不再扩展6号节点的右子树

向上回溯，回溯到2号节点，2号节点的左右孩子均已考察过，是死节点

向上回溯1号节点，回溯时cw=cw-w[1]=0、cp=cp-v[1]=0，怎么加的，怎么减

（14）扩展1号节点（t = 1）

1号节点的右子树还未生成，考察bound(t+1)是否大于bestp，bound(2)中剩余物品为第2、3、4个，rp =12、cp+rp=12、bestp=15，因此不满足限界条件，不再扩展1号节点的右子树，1号节点为死节点，所有节点都是死节点，算法结束。如图所示：

2、代码实现

（1）伪代码

【1】计算上界的函数：

计算上界是指计算已装入物品价值cp与剩余物品的总价值rp之和。我们已经知道已装入物品价值cp，剩余物品我们不确定要装入哪些，我们按照假设都装入的情况估算，即按最大值计算（剩余物品总价值），因此得到的值是可装入物品价值的上界

//计算上界：已装入物品价值+剩余物品总价值

double bound(int i )

{

int rp = 0;//剩余物品为第i- n种物品

while( i <= n )//依次计算剩余物品的价值

{

rp + = v[i];

i++ ;

}

return cp + rp ;//返回上界

}

【2】按约束条件和限界条件搜索求解函数

t表示当前扩展节点在第t层，cw表示当前已放入物品的重量，cp表示当前已放入物品的价值

如果t > n表示已经到达叶子节点，记录最优值最优解，返回。否则，判断满足约束条件，满足则搜索左子树，因为左子树表示放入该物品，所以令x[t]=1，表示放入第t个该物品。cw + = w[t]，表示当前已放入该物品的重量增加w[t]。cp + = v[t]，表示当前已放入物品的价值增加v[t]。backTrack(t+1)表示递推，深度优先搜索第t+1层。回归时即向上回溯时，要把增加的值减去，cw- =w[t]，cp-=v[t]

判断是否满足限界条件，满足则搜索右子树。因为右子树表示不放入该物品，所以令x[t]=0。当前已放入物品的重量、价值均不改变。backTrack(t+1)表示递推，深度优先搜索第t+1层

//表示当前扩展节点在第t层

void backTrack(int t)

{

if(t > n)//已经到达叶子节点

{

for(j = 1 ; j < = n ; j++)

{

bestx[j]=x[j];

}

//保存当前最优解

bestp = 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);

}

}

完整程序代码如下：

#include <iostream>

#include <string>

#include <algorithm>

#define M 105

using namespace std;

//n表示n个物品，W表示购物车的容量

int i , j , n , W;

//w[i]表示第i个物品的重量，v[i]表示第i个物品的价值

double w[M] , v[M];

//表示第i个物品是否放入购物车

bool x[M];

//当前重量

double cw;

//当前价值

double cp;

//当前最优价值

double bestp;

//当前最优解

bool bestx[M];

//计算上界，即剩余物品总价值

double bound (int i )

{

//剩余物品为i--n种物品

int rp = 0;

//以物品为单位重量价值重量价值递减的顺序装入物品

while(i <= n )

{

rp + = v[i];

i ++;

}

return cp + rp;

}

//用于搜索空间数，t表示当前扩展节点在第t层

void backTrack( int t )

{

if( t > n )//已经到达叶子节点

{

for(j = 1;j < = n; j++)

{

//保存当前最优解

bestx[j] = x[j];

}

bestp = 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);

}

}

void demo(double W , int n)

{

//初始化当前放入购物车的物品重量为0

cw = 0;

//初始化当前放入购物车的物品价值为0

cp = 0;

//初始化当前最优解

bestp = 0;

//用来统计所有物品的总重量

double sumw = 0.0;

//用来统计所有物品的总价值

double sumv = 0.0;

for(i = 1; i <= n;i++)

{

sumv + = v[i];

sumw + = w[i];

}

if(sumw <= W)

{

bestp = sumv;

count << "放入购物车的物品最大价值为：" <<bestp<<endl;

cout <<"所有的物品均放入购物车";

return;

}

backTrack(1);

cout <<"放入购物车的物品最大价值为："<<bestp<<endl;

cout <<"放入购物车的物品序号为：";

for(i = 1;i < = n; i ++)

{

if(bestx[i] ==1)

cout <<i<<" ";

}

cout<<endl;

}

int main()

{

cout<<"请输入物品的个数n：";

cin>>n;

cout<<"请输入购物车的容量W：";

cin>>W;

cout<<"请依次输入每个物品的重量w和价值v,用空格分开" ;

for(i = 1;i <= n;i++)

{

cin>>w[i]>>v[i];

}

demo(W,n);

return 0;

}

五、算法时间复杂度和空间复杂度分析

（1）时间复杂度

回溯法的运行时间取决于它在搜索过程中生成的节点数。而限界函数可以大大减少所生成的节点个数，避免无效搜索，加快搜索速度

左节点需要判断约束函数，右节点需要判断限界函数，那么最坏有多少个左节点和右节点呢？我们看规模为n的子集树，最坏情况下的状态如图：

【1】总的结点个数：

【2】左右孩子结点个数

总的结点个数减去根节点再除2就得到左右孩子结点的个数，左右孩子结点的个数为：

约束函数的时间复杂度为O(1)，限界函数时间复杂度为O(n)。最坏情况下有

个左孩子结点调用约束函数

有

个右孩子结点调用限界函数，故回溯法的时间复杂度为

（2）空间复杂度

回溯法会产生解空间，在搜索的任何时刻，仅保留从开始结点到当前扩展结点的路径，从开始结点起最长的路径为n。程序中我们使用bestp[]数组记录最长路径作为最优解，所以该算法的空间复杂度为O(n)

六、算法优化

在上面程序中上界函数是当前价值cp与剩余物品总价值rp之和，这个估值过高了，因为剩余物品的重量很可能是超过购物车容量的。因此我们可以缩小上界，从而加快剪枝速度，提高搜索效率

上界函数bound()：当前价值cp+剩余容量可容纳的剩余物品的最大值brp

为了更好地计算和运用上界函数剪枝，先将物品按照其单位重量价值（价值/重量）从大到小排序，然后按照排序后的顺序考察各个物品

#include <iostream>

#include <string>

#include <algorithm>

#define M 105

using namespace std;

//n表示物品个数，W表示购物车容量

int i , j , n , W;

//w[i]表示第i个物品重量，v[i]表示第i个物品价值

double w[M] , v[M];

//x[i]=1表示第i个物品放入购物车

bool x[M];

double cw;//当前重量

double cp;//当前价值

double bestp;//当前最优值

double bestx[M];//当前最优解

/**

*计算上界：

*将剩余物品装满剩余的背包容量时所能获得的最大价值

*/

double bound(int i)

{

//剩余物品为第i--n种物品

double cleft = W - cw;//剩余容量

double brp =0.0;

while(i <= n && w[i] < cleft)

{

cleft -=w[i];

brp +=v[i];

i++;

}

//采用切割的方式装满背包，这里是求上界，求解时不允许切割

if(i <=n)

{

brp+=v[i]/w[i]*cleft;

}

return cp + brp;

}

//用于搜索空间数，t表示当前扩展结点在第t层

void backTrack(int n)

{

if(t > n)//已经到达叶子节点

{

for(j = 1;j <=n;j++)

{

bestx[j]=x[j];

}

bestp=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);

}

}

//定义物品结构，包括序号和单位重量价值

struct Object

{

int id; //物品序号

double d;//单位重量价值

};

//按物品单位重量价值由大到小排序

bool cmp(Object a1,Object a2)

{

return a1.d>a2.d;

}

void demo(int W,int n)

{

//初始化

//初始化放入物品重量为0

cw=0;

//初始化放入物品价值为0

cp=0;

//初始化当前最优值为0

bestp=0;

//用来统计所有物品总重量

double sumw = 0;

//用来统计所有物品总价值

double sumv=0;

//物品结构体类型，用于按单位重量价值（价值/重量比）排序

Object Q[n];

//辅助数组，用于把排序后的重量和价值传递给原来的重量价值数组

double a[n+1] , b[n+1];

for(i = 1;i <=n ;i++)

{

Q[i-1].id = i;

Q[i-1].d = 1.0*v[i]/w[i];

sumv+=v[i];

sumw+=w[i];

}

if(sumw <= W )

{

bestp = sumv;

cout<<"放入物品最大价值为："<<bestp<<endl;

cout<<"所有物品均放入";

return;

}

//按单位重量价值（价值/重量比）从大到小排序

sort(Q ,Q + n,cmp);

for(i=1;i<=n;i++)

{

//把排序后的数据传递给辅助数组

a[i]=w[Q[i-1].id];

b[i]=v[Q[i-1].id];

}

for(i=1;i<=n;i++)

{

//把排序后的数据传递给w[i]

w[i] = a[i];

v[i] = b[i];

}

backTrack(1);

cout<<"放入的物品最大价值为："<<bestp<<endl;

cout<<"放入购物车的物品序号为";

for(i =1;i <= n;i++)

{

if(bestx[i]==1)

cout<<Q[i-1].id<<"";

}

cout<<endl;

}

int main()

{

cout<<"请输入物品的个数n：";

cin >>n;

cout<<"请输入购物车的容量W：";

cin >>W;

cout<<"请依次输入每个物品的重量w和价值v，用空格分开";

for(i=1;i<=n;i++)

{

cin>>w[i]>>v[i];

}

demo(W,n);

return 0;

}

（1）时间复杂度：约束函数时间复杂度为O(1)，限界函数时间复杂度为O(n)。最坏情况下有O(2的n次方)个左孩子调用约束函数，有O(2的n次方)个右孩子调用界限函数，回溯算法backTrack需要计算时间为O(n*2的n次方)。排序函数时间复杂度为O(n Log n)，这是考虑最坏情况。实际上，经过上界函数优化后，剪枝速度很快，根本不需要生成所有节点

（2）空间复杂度：除了记录最优解数组外，还是用一个结构体数组用于排序，两个辅助数组传递排序后的结果，这些数组的规模都是n，因此空间复杂度仍为O(n)