首页 > 代码库 > 回溯法——装载问题
回溯法——装载问题
问题描述：
有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量是wi，且不能超，即Σwi<=c1+c2。
算法思想：
——在给定的装载问题有解的情况下
最优装载方案： 首先将第一艘轮船尽可能的装满；
然后将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能的装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。
算法设计：
先考虑装载一艘轮船的情况，依次讨论每个集装箱的装载情况，共分为两种，要么装(1)，要么不装(0)，因此很明显其解空间树可以用子集树来表示。
在算法Maxloading中，返回不超过c的最大子集和，但是并没有给出到达这个最大子集和的相应子集，稍后完善。
在算法Maxloading中，调用递归函数Backtrack(1)实现回溯搜索。Backtrack(i)搜索子集树中的第i层子树。
在算法Backtrack中，当i>n时，算法搜索到叶结点，其相应的载重量为cw，如果cw>bestw，则表示当前解优于当前的最优解，此时应该更新bestw。
算法Backtrack动态地生成问题的解空间树。在每个结点处算法花费O(1)时间。子集树中结点个数为O(2^n)，故Backtrack所需的时间为O(2^n)。另外Backtrack还需要额外的O(n)的递归栈空间。
算法描述：
1 template <class Type> 2 class Loading 3 { 4 friend Type MaxLoading(Type [],Type,int); 5 private: 6 void Backtrack(int i); 7 int n; //集装箱数目 8 Type * w, //集装箱重量数组 9 c, //第一艘轮船的载重量 10 cw, //当前载重量 11 bestw; //当前最优载重量 12 }; 13 14 template <class Type> 15 void Loading<Type>::Backtrack(int i) //回溯搜索 16 { //搜索第i层结点 17 if(i>n) //到达叶结点 18 { 19 if(cw>bestw) 20 bestw = cw; 21 return; 22 } 23 if(cw+w[i] <= c) //搜索子树 24 { 25 cw += w[i]; //当前载重量增加正考虑对象的重量 26 Backtrack(i+1); 27 cw -= w[i]; //递归返回上一层时，记得减去刚考虑对象的集装箱重量 28 } 29 Backtrack(i+1); //递归搜索第i+1层 30 } 31 32 template <class Type> 33 Type MaxLoading(Type w[],Type c,int n) //返回最优载重量 34 { 35 Loading<Type> X; //初始化 36 X.w = w; 37 X.c = c; 38 X.n = n; 39 X.bestw = 0; //当前最优载重量的初值赋为0 40 X.cw = 0; 41 X.Backtrack(1); //计算最优载重量————调用递归函数，实现回溯搜索 42 return X.bestw; 43 }
上界函数：
引入剪枝函数，用于剪去不含最优解的子树：即当cw(当前载重量)+r(未考察对象的总重量)<bestw(当前的最优载重量)时当前子树不可能包含最优解，直接减掉。
1 template <class Type> 2 class Loading 3 { 4 friend Type MaxLoading(Type [],Type,int); 5 private: 6 void Backtrack(int i); 7 int n; 8 Type * w, 9 c, 10 cw, 11 bestw, 12 r;//剩余集装箱重量————未考察过的集装箱的重量，并非没有装载的集装箱重量 13 }; 14 template <class Type> 15 void Loading<Type>::Backtrack(int i) 16 { 17 if(i>n) 18 { 19 if(cw>bestw) 20 bestw = cw; 21 return; 22 } 23 r-=w[i]; //计算剩余（未考察）的集装箱的重量，减去当前考察过的对象的重量 24 if(cw+w[i] <= c) 25 { 26 cw += w[i]; 27 Backtrack(i+1); 28 cw -= w[i]; 29 } 30 Backtrack(i+1); 31 r+=w[i]; //递归回退返回上一层时，记得修改r的当前值，如果得不到最优解，再取消当前考察的集装箱，标记为未选，因此剩余容量要再加上当前集装箱重量 32 } 33 template <class Type> 34 Type MaxLoading(Type w[],Type c,int n) 35 { 36 Loading<Type> X; //初始化 37 X.w = w; 38 X.c = c; 39 X.n = n; 40 X.bestw = 0; 41 X.cw = 0; 42 X.r = 0; //初始化r 43 for(int i=1;i<=n;i++) //计算总共的剩余（当前为考察过的）集装箱重量 44 X.r += w[i]; 45 X.Backtrack(1); 46 return X.bestw; 47 }
构造最优解：
为了构造最优解，必须在算法中保存最优解的记录。因此需要两个成员数组 x ,bestx，一个用于记录当前的选择，一个用于记录最优记录。
改进后的算法描述如下：
1 template <class Type> 2 class Loading 3 { 4 friend Type MaxLoading(Type [],Type,int); 5 private: 6 void Backtrack(int i); 7 int n, 8 * x, //当前解 9 * bestx; //当前最优解 10 Type * w, //集装箱重量数组 11 c, //第一艘轮船的载重量 12 cw, //当前载重量 13 bestw, //当前最优载重量 14 r; //剩余集装箱重量————未考虑过的集装箱重量，并非没有装载的集装箱重量 15 }; 16 template <class Type> 17 void Loading<Type>::Backtrack(int i) 18 { //搜索第i层结点 19 if(i>n) //到达叶子结点 20 { 21 if(cw>bestw) 22 { 23 for(j=1;j<=n;j++) 24 bestx[j] = x[j]; 25 bestw = cw; 26 } 27 return; 28 } //搜索子树 29 r-=w[i]; //计算剩余（未考虑过）集装箱的重量，减去当前考虑过的集装箱重量 30 if(cw+w[i] <= c) //搜索左子树 31 { 32 x[i] =1; 33 cw += w[i]; 34 Backtrack(i+1); 35 cw -= w[i]; 36 } 37 if(cw+r > bestw) //搜索右子树——————剪枝函数 38 { 39 x[i] = 0; 40 Backtrack(i+1); 41 } 42 r+=w[i]; //递归返回上一层时，记得修改r的值，如果取不到最优解，再取消当前考虑的集装箱，标记为未选，因此剩余容量要再加上当前集装箱重量 43 } 44 template <class Type> 45 Type MaxLoading(Type w[],Type c,int n) 46 { 47 Loading<Type> X; 48 X.w = w; 49 X.c = c; 50 X.n = n; 51 X.bestx = bestx; 52 X.bestw = 0; 53 X.cw = 0; 54 X.r = 0; 55 for(int i=1;i<=n;i++) //计算总共的剩余(当前为考察过的)集装箱重量 56 X.r += w[i]; 57 X.Backtrack(1); 58 delete []X,x; 59 return X.bestw; 60 }
构造最优解的另一种经典方法：
1 void backtrack(int t) 2 { 3 if(t>n) 4 output(x); 5 else 6 { 7 for(i-0;i<=1;i++) 8 { 9 x[t]=i; 10 if(cw+i*wt<=c) 11 { 12 cw=cw+i*wt; 13 backtrack(t+1); 14 } 15 } 16 } 17 }
迭代回溯方式：
利用数组x所含的信息，可将上面方法表示成非递归的形式。省去O(n)递归栈空间。非递归迭代回溯法描述如下：
1 template <class Type> 2 Type MaxLoading(Type w[],Type c,int n,int bestx[]) 3 { 4 //迭代回溯法，返回最优装载量及其相应解，初始化根节点 5 int i =1; //当前层 x[1:i-1]为当前路径 6 int *x = new int[n+1]; 7 Type bestw = 0, //当前最优载重量 8 cw = 0, //当前载重量 9 r = 0; //剩余（未考虑过的）集装箱重量 10 for(int j=1;j<=n;j++) 11 r+=w[j]; 12 while(true) 13 { //进入子树 14 while(i<=n && cw+w[i]<=c) 15 { //搜索左子树 16 r -= w[i]; 17 cw +=w[i]; 18 x[i] =1; 19 i++; 20 } 21 if(i>n) //到达叶子结点 22 { 23 for(int j=1;j<=n;j++) 24 bestx[j] = x[j]; 25 bestw = cw; 26 } 27 else //进入右子树 28 { 29 r -= w[i]; 30 x[i] = 0; 31 i++; 32 } 33 while(cw+w[i] <= bestw) 34 { //剪枝回溯 35 i--; 36 while(i>0 && !x[i]) 37 { //从右子树返回 38 r+=w[i]; 39 i--; 40 } 41 if(i == 0) 42 { 43 delete[] x; 44 return bestw; 45 } //进入右子树 46 x[i] =0; 47 cw -= w[i]; 48 i++; 49 } 50 } 51 }
注：上面的解法实际上就是针对一艘轮船的最优转载
针对于多艘轮船就不一定是最优解了。。。。。
如果是多艘轮船的装载问题：
同样选择回溯法解决——子集树，只是每个集装箱的选择范围不再仅仅是装否两种考虑情况，而变为不装抑或是装载到某个编号的轮船上等多种考虑范围。
例如：n=3，c1=c2=50，w=[10,40,40]，所以对于3个集装箱中的任何一个都有3种选择，不装、转载到1号轮船和转载到2号轮船。
1 void backtrack (int t) //t:代表待考察的对象 2 { 3 if (t>n) output(x); //n:考察对象的个数 4 else 5 for (int i=0;i<=2;i++) { //控制分支的数目，此处只有3个分支，0、1、2分别代表不装，装载到1号轮船，转载到2号轮船 6 x[t]=i; 7 if (constraint(t)&&bound(t)) backtrack(t+1); //剪枝函数：约束函数+限界函数 ————> 递归 8 } 9 }
约束函数为:
cw1+wt*i/i<=c1&&cw2+wt*i/i<=c2;
1 void backtrack (int t) //t:代表待考察的对象 2 { 3 if (t>n) output(x); //n:考察对象的个数 4 else 5 for (int i=0;i<=2;i++) { 6 x[t]=i; 7 //剪枝函数：约束函数+限界函数 ————> 递归 8 if (cw1+wt*i/i<=c1&&cw2+wt*i/i<=c2;) { 9 cw1=cw1+i*wt/i; 10 cw2=cw2+i*wt/i; 11 backtrack(t+1); 12 } 13 } 14 } 15