0027算法笔记——【回溯法】回溯法与装载问题

1、1、回溯法(1)描述:回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。原理：回溯法在问题的解空间树中，按 深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包 含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回 溯；否则，进入该子树，继续按深度优先策略搜索 。回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的 问题。有许多问题，当需要找出它的解集或者

2、要求回答什么解是满足 某些约束条件的最佳解时，往往要使用回溯法。问题的解空间问题的解向量：回溯法希望一个问题的解能够表示成一个n元式 (x1,x2,xn的形式。显约束：对分量xi的取值限定。隐约束：为满足问题的解而对不同分量之间施加的约束。解空间：对于问题的一个实例，解向量满足显式约束条件的所有 多元组，构成了该实例的一个解空间。注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。例 1: n=3各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城的0 1背包问题的回溯法搜索过程。市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。1

3、0(4)生成问题状态的基本方法扩展结点：一个正在产生儿子的结点称为扩展结点。活结点：一个自身已生成但其儿子还没有全部生成的节点称做活结 点。死结点：一个所有儿子已经产生的结点称做死结点。深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了 它的一个儿子C,就把C当做新的扩展结点。在完成对子树 C (以C 为根的子树)的穷尽搜索之后，将 R重新变成扩展结点，继续生成 R 的下一个儿子(如果存在)。宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点。回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不 断地利用限界函数(bounding function)来处死那些

4、实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回 溯法。(5)回溯法的基本思想基本思想:用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解 空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为0（h（n）。而显式地存储整个解空间则需要0(2h(n)或 0(h(n)!)内存空间。解题步骤:1）针对所给问题，定义问题的 解空间;2）确定易于搜索的解空间结构;3）以深度优先方式搜索解空间，并在搜索过程中用 剪枝函数避免无效搜索。常用剪枝函数：用约束函数在扩展结点处剪

5、去不满足约束的子树；用限界函数剪去得不到最优解的子树。递归回溯:回溯法对解空间作深度优先搜索，因此，在一般情况下用递归方法 实现回溯法。cpp view plain copy..9.10.void backtrack ( int t)if (t>n)out put(x);elsefor ( int i=f(n,t);iv=g(n,t);i+) x【t=h(i);if (constraint(t)&&bound(t) backtrack(t+1);/已到叶子结点，输出结果f(n,t) , g(n,t):表示当前扩展结点处未搜索过的子树的起始编号和

6、终止编号。h(i):表示在当前扩展结点处xt的第i个可选值。迭代回溯:采用树的非递归深度优先遍历算法，可将回溯法表示为一个非递归迭代过程。cpp view plain copy1.2.3.void iterativeBacktrack ()int t=1;4.5.6.while (t>0) if (f(n,t)<=g(n,t)(int i=f(n,t);iv=g(n,t);i+) for7.8.if9.10.(constraint(t)&&bound(t) if (solution(t) output(x); else t+;xt=h(i);11.12.else t

7、-;13.14.15.子集树与排列树:子集树：当所给的问题是从n个元素的集合S中找出满足某种性质25个叶节的子集时，相应的解空间称为 子集树。例如，那个物品的0-1背包问题所相应的解空间树就是一颗子集树。这类子集问题通常有点，其节点总个数为2八(n+1)-1。遍历子集树的任何算法均需要0(2八n)的计算时间。..9.void backtrack ( int t)解空间树称为排列树。排列树通常有n!个叶子节点。因此遍历排列树需用回溯法遍历子集树的一般算法可描述如下:cpp view plain copyif (t>n) output(x);elsefor ( i

8、nt i=0;iv=1;i+) xt=i;if (legal(t) backtrack(t+1);排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的要0(n!)的计算时间。用回溯法遍历排列树的一般算法可描述如下:cpp view plain copy..9.10.void backtrack ( int t)if (t>n) output(x);elsefor ( int i=t;iv=n;i+) swap (xt, xi);if (legal(t) backtrack(t+1);swap (xt, xi);2、装载问题问题描述：有一批共n个集装箱要

9、装上2艘载重量分别为c1和c2的 轮船，其中集装箱i的重量为wi，且台'是否有一个合理的装载方案可将这些集装箱装上这，装载问题要求确定2艘轮船。如果有，找出一种装载方案。例如：当n=3,c仁c2=50,且w二10,40,40时，则可以将集装箱 1和2装到第一艘轮船上，而将集装箱 3装到第二艘轮船上；如果w二20,40,40，则无法将这3个集装箱都装上轮船。基本思路：容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满;(2)将剩余的集装箱装上第二艘轮船。将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接

10、近 C1。由此可知，装载问题等价于以下特 殊的0-1背包问题。ftmax 工 vf. .rr-ls t.工叫M < C/=!心W 0< Z < /P用回溯法设计解装载问题的0（2八n）计算时间算法。在某些情况下该算法优于动态规划算法。算法设计:用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。用可行性约束函数可剪去不满足约束条件工W锻< ClZ的子树。在子 集树的第j+1层的结点z处，用cw记当前的装载重量，即cw=工W曲，则当cw>c1时，以结点z为根的子树中所有结点都不满足=1 约束条件，因而该子树中的解均为不可行解，故可将该子树剪去。（该约束函数去除

11、不可行解，得到所有可行解）。可以引入一个上界函数，用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率。设z是解空间树第i层上的当前扩展结点。cw是当前载重量；bestw是当前最优载重量；r是剩余集装箱的重量，即r=。定义上界函数为cw+r。在以z为根的子树中任一叶结点所相应的载重量均不超过 cw+r。因此，当cw+rv二bestw时，可将z的 右子树剪去。递归回溯具体代码如下:cpp view plain copy11.#include "stdafx.h"2.#include viostream3.using names pace std;4.5.tempi a

12、te < class Type6.class Loading7.8./friend Type MaxLoading(T yp e,T yp e,int,int );9./p rivate:10.public :11.void Backtrack(inti);12.int n,/集装箱数13.*x,/当前解14.*bestx;/当前最优解15.Type *w,/集装箱重量数组16.c,/第一艘轮船的载重量17.cw,/当前载重量18.bestw,/当前最优载重量19.r;/剩余集装箱重量20.；21.22.tempi ate < class Type23.voidLoading vT

13、yp e>:Backtrack (int i);24.25.tempi ate vclass Type26.Type MaxLoading(T ype w, Type c,int n,27.28.intmain()29.30.int n=3,m;31.int c=50,c2=50;int bestx);32.33.int w4=0,10,40,40;34.int bestx4;35.36.m=MaxLoading(w, c, n, bestx);37.38.coutvv"轮船的载重量分别为："vvendl;39.coutvv"c(1)="<&

14、lt;c<< ",c(2)="vvc2vvendl;40.41.coutvv"待装集装箱重量分别为："vvendl;42.coutvv"w(i)="43.for ( int i=1;iv=n;i+)44.45.coutvvwivv""46.47.coutvvendl;48.49.coutvv"回溯选择结果为："vvendl;50.coutvv"m(1)=" vvmvvendl;51.coutvv"x(i)="52.53.for ( int i=

15、1;iv=n;i+)54.55.coutvvbestxivv""56.57.coutvvendl;58.59.int m2=0;60.for ( int j=1;jv=n;j+)61.62.m2=m2+wj*(1-bestxj);63.64.coutvv"m(2)=" vvm2vvendl;65.66.if (m2>c2)67.68.coutvv"因为m(2)大于c(2),所以原问题无解！"69.70.return 0;71.72.73.tempi ate v class Type74.void Loading vTyp e&g

16、t;:Backtrack (int i) /搜索第75.wendl;i层结点76.if (i > n)/到达叶结点77.78.if (cw>bestw)79.80.for (int j=1；jv=n;j+)81.82.bestxj=xj;/更新最优解83.bestw=cw;84.85.86.return ;87.88.89.r-=wi;90.if (cw + wi <= c)/搜索左子树91.92.xi = 1;93.cw += wi;94.Backtrack(i+1);95.cw-=wi;96.97.98.if (cw + r > bestw)99.100.xi =

17、0;/搜索右子树101.Backtrack(i + 1);102.103.叶=wi;104.105.106.tempi ate <class Type107.Type MaxLoading(T ype w, Type c,int n,108.109.LoadingvT yp e>X;110./初始化X111.X.x= new int n+1;112.X.w=w;113.X.c=c;114.X.n=n;115.X.bestx=bestx;116.X.bestw=0;117.X.cw=0;118./初始化rJ119.X.r=0;int bestx) /返回最优载重量120.121.fo

18、r ( int i=i；iv=n;i+)122.123.X+=wi;124.125.126.X.Backtrack(1);127.128.delete X.x; return X.bestw;129.迭代回溯具体代码如下:cpp view plain copy1.#include "stdafx.h"2.#include <iostream>3.using names pace std;4.5.tempi ate <class Type6.Type MaxLoading(T ype w , Type c,int n, int bestx);7.8.intm

19、ain()9.10.intn=3,m;11.intc=50,c2=50;12.intw4=0,10,40,40;13.intbestx4;15.14.m=MaxLoading(w, c, n, bestx);16.17.cout<<"轮船的载重量分别为:"<<endl;18.cout<<"c(1)="<<c<< ",c(2)="<<c2<<endl;19.20.cout<<"待装集装箱重量分别为:"<<end

20、l;21.cout<<"w(i)="22.for (int i=1;i<=n;i+)23.24.cout<<wi<<25.26.coutwendl;28.cout<<"回溯选择结果为：-29.cout<<"m(1)=" <<m<<endl;J30.cout<<"x(i)="27.<<endl;31.32.for ( int i=1;iv=n;i+)33.34.cout<<bestxi<<3

21、5.36.coutwendl;37.38.int m2=0;39.for ( int j=1;jv=n;j+)40.41.m2=m2+wj*(1-bestxj);42.43.coutvv "m(2)=" vvm2vvendl;44.45.if (m2>c2)46.47.cout<<"因为m(2)大于c(2),所以原问题无解！" vvendl;48.49.return 0;3.tempi ate < class Type54.Type MaxLoading(T ype w,T ype c,及其相应解，初始化根结点int n, int bestx) /迭代回溯法，返回最优载重量55.56.int i=1