装载问题 ——回溯法（Java）
文章目录
- 装载问题 ——回溯法（Java）
- 1、 问题描述
- 1.1 装载问题
- 1.2 转换问题
- 2、算法设计
- 2.1 可行性约束函数
- 2.2 上界函数
- 2.3 解空间树
- 2.4 剪枝函数
- 2.5 算法设计
- 3、程序代码
- 4、参考资料
1、 问题描述
有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集
装箱i的重量为Wi，且
∑ i = 1 n w i < = C 1 + C 2 \sum_{i=1}^{n} w_i <= C1 + C2 i=1∑nwi<=C1+C2
例如，当n=3,c1=c2=50,且w=[10,40,40]时，可将集装箱1和集装箱2装上一艘轮船，而将集装箱3装在第二艘轮船；如果w=[20,40,40],则无法将这3个集装箱都装上轮船。
1.1 装载问题
装载问题要求
确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。
例如：
6个元素的数组{30,30,30,50,50,60}，容量 C1=100，C2=150.箱子总重量为250，轮船的总容量也为250，如何安排该装载？
-
如果使用贪心算法（按照重量从小到大），会先把30,30,30装到第一艘船，就造成了，10个空间的浪费，导致会有一个箱子不能装上船。
-
如果使用贪心算法（按照装载量尽量最大），会装50+50=100，然后30+30+30+60=150
回溯法因为考虑到了所有的装载顺序，所以一定能找到最优的装载方案。
容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。
(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。
1.2 转换问题
-
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近第一艘轮船的载重量。
-
由此可知，装载问题等价于以下特殊的0-1背包问题。
$$
max\sum_{i=1}^{n} w_ix_i
$$
$$
\sum_{i=1}^{n} w_ix_i \leq C1, x_i \in { 0,1 }, 1 \leq i \leq n
$$
用回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法。
2、算法设计
2.1 可行性约束函数
$$
\sum_{i=1}^{n} w_ix_i \leq C1
$$
在子集树的第j+1层的节点Z处，用
cw记当前的装载重量，即cw=(w1x1+w2x2+…+wjxj)，当cw>c1时，以节点Z为根的子树中所有节点都不满足约束条件，因而该子树中解均为不可行解，故可将该子树剪去。（该约束函数去除不可行解，得到所有可行解）
2.2 上界函数
- 设Z是解空间树第i层上的当前扩展结点。cw是当前载重量；bestw是当前最优载重量；r是剩余集装箱的重量，即
$$
r=\sum_{j=i+1}^{n} w_j
$$
- 定义上界函数为cw+r。在以Z为根的子树中任一叶结点所相应的载重量均不超过cw+r。因此，当cw+r<=bestw时，可将z的右子树剪去。
当前载重量cw+剩余集装箱的重量r≤当前最优载重量bestw
2.3 解空间树
核心代码
public static void backtrack(int t) {
if(t>n) {//到达叶结点
if(cw>bestw)
bestw = cw;
return;
}
if(cw + w[i] <= c) { //搜索左子树
cw += w[i]; //更新装载量
backtrack(i+1);
cw -= w[i]; //回溯到父结点，将装载量还原
}
backtrack(i+1);
}
2.4 剪枝函数
-
约束条件剪去”不可行解”的子树
-
上界条件剪去不含最优解的子树,r为剩余集装箱重量 r = ∑ j = i + 1 n w j r=\sum_{j=i+1}^{n} w_j r=∑j=i+1nwj，
当前装载与r之和为右子树上界
保证算法搜索到的每个叶结点都是迄今为止找到的最优解
2.5 算法设计
-
先考虑装载一艘轮船的情况，依次讨论每个集装箱的装载情况，共分为两种，要么装(1)，要么不装(0)，因此很明显其解空间树可以用子集树来表示。
-
在算法maxLoading中，返回不超过c的最大子集和。
-
在算法maxLoading中，调用递归函数backtrack(1)实现回溯搜索。backtrack(i)搜索子集树中的第i层子树。
-
在算法backtrack中，当i>n时，算法搜索到叶结点，其相应的载重量为cw，如果cw>bestw，则表示当前解优于当前的最优解，此时应该更新bestw。
-
算法backtrack动态地生成问题的解空间树。在每个结点处算法花费O(1)时间。子集树中结点个数为O(2n)，故backtrack所需的时间为O(2n)。另外backtrack还需要额外的O(n)的递归栈空间。
为了构造最优解，需要记录与当前最优值相应的当前最优解。x用于记录从根至当前结点的路径，bestx记录当前最优解。在叶结点处进行修正。
//回溯算法
public static void backtrack(int t) {
if(t>n) {//到达叶结点
if(cw>bestw) {
for(int i=1;i<=n;i++) {
bestx[i] = x[i];
}
bestw = cw;
}
return;
}
r -= w[t]; //当前结点作为扩展结点，求子树剩余集装箱重量
if(cw + w[t] <= c) { //搜索左子树
x[t] = 1;
cw += w[t];
backtrack(t+1);
cw -= w[t]; //回溯到父结点
}
if(cw + r>bestw) { //根据限界函数
x[t] = 0; //搜索右子树
backtrack(t+1);
}
r += w[t];//恢复现场
}
3、程序代码
public class Solution {
// 类数据成员
static int N; // 集装箱数量 - 1
static int[] weight; // 集装箱重量数组
static int[] shipContain; // 第一艘轮船的载重量
static int currWeight; // 当前载重量
static int bestWeight; // 当前最优载重量
static int remain; // 剩余集装箱重量
static int[] solution; // 当前解
static int[] best; // 当前最优解，best[i]表示第i+1个集装箱装载到第best[i]+1艘轮船时最优
public static void main(String[] args) {
// TODO 箱子|轮船总容量都为250
weight = new int[]{30, 30, 30, 50, 50, 60}; // 每个集装箱重量
shipContain = new int[]{100, 150}; // 两艘轮船的载重量分别为C1，C2
// TODO 初始化类数据成员
N = weight.length - 1;
solution = new int[N + 1];
best = new int[N + 1];
currWeight = 0;
bestWeight = 0;
// TODO 初始化remain
for (int i = 1; i <= N; i++) {
remain += weight[i];
}
System.out.println("最优载重量为：" + maxLoading(weight, shipContain[0], best));
System.out.println("最优装载数组：");
for (int i = 0; i < best.length; i++) {
if (i != best.length - 1) {
System.out.print(best[i] + " ");
} else {
System.out.println(best[i]);
}
}
int shipCnt = shipContain.length;
int w = 0;
for (int i = 1; i <= shipCnt; i++) {
System.out.print("第" + i + "艘轮船装载的集装箱分别是：第");
for (int j = 0; j <= N; j++) {
if (best[j] == i - 1) {
System.out.print(j + 1 + ",");
}
}
System.out.println("个");
}
}
public static int maxLoading(int[] weight, int c1, int[] best) {
// TODO 计算最优载重量
backtrack(1, c1);
return bestWeight;
}
private static void backtrack(int level, int c1) {
// TODO 搜素第level层节点
if (level > N) {
// TODO 到达叶节点
if (currWeight > bestWeight) {
for (int i = 1; i <= N; i++) {
best[i] = solution[i];
}
bestWeight = currWeight;
}
return;
}
// TODO 搜索子树
remain -= weight[level];
if (currWeight + weight[level] <= c1) {
// TODO 搜索左子树，即x[level] = 1
solution[level] = 1;
currWeight += weight[level];
backtrack(level + 1, c1);
currWeight -= weight[level];
}
if (currWeight + remain > bestWeight) {
solution[level] = 0;
backtrack(level + 1, c1); // TODO 搜素右子树
}
remain += weight[level];
}
public static int maxLoading1(int[] w, int c, int[] bestx) {
// TODO 迭代回溯法
// 返回最优载重量及其相应解
// 初始化根结点
int curr = 1;
// int n = w.length - 1;
solution = new int[N];
// bestWeight = 0;
// currWeight = 0;
// remain = 0;
for (int j = 1; j <= N; j++) {
remain += w[j];
}
// TODO 搜索子树
while (true) {
while (curr <= N && currWeight + w[curr] <= c) {
// TODO 进入左子树
remain -= w[curr];
currWeight += w[curr];
solution[curr] = 1;
curr++;
}
if (curr > N) {
// TODO 到达叶节点
for (int i = 1; i <= N; i++) {
bestx[i] = solution[i];
}
bestWeight = currWeight;
} else {
// TODO 进入右子树
remain -= w[curr];
solution[curr] = 0;
curr++;
}
while (currWeight + remain <= bestWeight) {
// TODO 剪枝回溯
curr--;
while (curr > 0 && solution[curr] == 0) {
// 从右子树返回
remain += w[curr];
curr--;
}
if (curr == 0) {
return bestWeight;
}
// TODO 进入右子树
solution[curr] = 0;
currWeight -= w[curr];
curr++;
}
}
}
}
运行结果
4、参考资料
- 算法设计与分析（第四版）
结束！
