:hover{text-decoration:none;}/*pc样式*/.pgc-card{box-sizing:border-box;height:164px;border:1pxsolide8e8e8;height:120px;position:absolute;right:76px;top:20px;}.pgc-cover{position:absolute;width:162px;height:162px;top:0;left:0;background-size:cover;}.pgc-content{overflow:hidden;position:relative;top:50%;-webkit-transform:translateY(-50%);transform:translateY(-50%);}.pgc-content-title{font-size:18px;color:444;overflow:hidden;text-overflow:ellipsis;padding-top:9px;overflow:hidden;line-height:1.2em;display:-webkit-inline-box;-webkit-line-clamp:2;-webkit-box-orient:vertical;}.pgc-content-price{font-size:22px;color:406599;font-size:14px;text-align:center;}.pgc-buy-text{padding-top:10px;}.pgc-icon-buy{height:23px;width:20px;display:inline-block;background:url();}

算法：数据科学基础

￥69.8

购买

一、算法思想

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

二、算法要素

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种物品的状态确定后，当前已装入购物车的物品的总价值，用cp表示。已装入物品的价值高不一定就是最优的，因为还有剩余物品未确定

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

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

cp+rpbestp

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，sumvW因此不能全部装完，需要搜索求解。初始化当前放入购物车的物品重量cw=0；当前放入购物车的物品价值cp=0；当前最优值bestp=0

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

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

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

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

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

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

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

首先判断cw+w[3]=11W，超过了购物车容量，第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]=9W，满足约束条件，扩展左分支，令x[4]=1，令

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

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

tn，找到一个当前最优解，用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]=6W，满足约束条件，扩展左分支，令x[3]=1，

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

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

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

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

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

tn（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，剩余物品我们不确定要装入哪些，我们按照假设都装入的情况估算，即按最大值计算（剩余物品总价值），因此得到的值是可装入物品价值的上界

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

doublebound(inti)

{

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

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

{

rp+=v[i];

i++;

}

returncp+rp;//返回上界

}

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

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

如果tn表示已经到达叶子节点，记录最优值最优解，返回。否则，判断满足约束条件，满足则搜索左子树，因为左子树表示放入该物品，所以令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层

voidbackTrack(intt)

{

if(tn)//已经到达叶子节点

{

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

}

}

完整程序代码如下：

includestring

defineM105

usingnamespacestd;

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

inti,j,n,W;

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

doublew[M],v[M];

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

boolx[M];

//当前重量

doublecw;

//当前价值

doublecp;

//当前最优价值

doublebestp;

//当前最优解

boolbestx[M];

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

doublebound(inti)

{

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

intrp=0;

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

while(i=n)

{

rp+=v[i];

i++;

}

returncp+rp;

}

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

voidbackTrack(intt)

{

if(tn)//已经到达叶子节点

{

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

}

}

voiddemo(doubleW,intn)

{

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

cw=0;

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

cp=0;

//初始化当前最优解

bestp=0;

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

doublesumw=0.0;

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

doublesumv=0.0;

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

{

sumv+=v[i];

sumw+=w[i];

}

if(sumw=W)

{

bestp=sumv;

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

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

return;

}

backTrack(1);

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

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

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

{

if(bestx[i]==1)

couti"";

}

coutl;

}

intmain()

{

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

cinn;

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

cinW;

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

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

{

cinw[i]v[i];

}

demo(W,n);

return0;

}

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

（1）时间复杂度

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

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

【1】总的结点个数：

【2】左右孩子结点个数

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

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

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

有

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

（2）空间复杂度

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

六、算法优化

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

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

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

includestring

defineM105

usingnamespacestd;

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

inti,j,n,W;

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

doublew[M],v[M];

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

boolx[M];

doublecw;//当前重量

doublecp;//当前价值

doublebestp;//当前最优值

doublebestx[M];//当前最优解

/**

*计算上界：

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

*/

doublebound(inti)

{

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

doublecleft=W-cw;//剩余容量

doublebrp=0.0;

while(i=nw[i]cleft)

{

cleft-=w[i];

brp+=v[i];

i++;

}

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

if(i=n)

{

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

}

returncp+brp;

}

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

voidbackTrack(intn)

{

if(tn)//已经到达叶子节点

{

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

}

}

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

structObject

{

intid;//物品序号

doubled;//单位重量价值

};

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

boolcmp(Objecta1,Objecta2)

{

;

}

voiddemo(intW,intn)

{

//初始化

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

cw=0;

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

cp=0;

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

bestp=0;

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

doublesumw=0;

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

doublesumv=0;

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

ObjectQ[n];

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

doublea[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"放入物品最大价值为："bestpl;

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"放入的物品最大价值为："bestpl;

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

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

{

if(bestx[i]==1)

coutQ[i-1].id"";

}

coutl;

}

intmain()

{

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

cinn;

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

cinW;

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

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

{

cinw[i]v[i];

}

demo(W,n);

return0;

}

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

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