【回溯算法】【Python实现】装载问题

本文主要是介绍【回溯算法】【Python实现】装载问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

@[toc]
问题描述
问题转换
回溯算法
`Python`实现
时间复杂性

问题描述

有一批共 $n$ 个集装箱要装上 $2$ 艘载重量分别为 $c_{1}$ 和 $c_{2}$ 的轮船，其中集装箱 $i$ 的重量为 $w_{i}$ ，且 $\displaystyle\sum\limits_{i = 1}^{n}{w_{i}} \leq c_{1} + c_{2}$
是否有一个合理的装载方案可将这 $n$ 个集装箱装上这两艘轮船

问题转换

先将第一艘轮船尽可能装满，然后将剩余的集装箱装上第二艘轮船
装载问题等价于以下特殊的 $0 - 1$ 背包问题

$\begin{cases} \max\displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \\ s.t. \displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq c_{1} \end{cases} \kern{2em} x_{i} \in \set{0 , 1} , \kern{1em} 1 \leq i \leq n$

回溯算法

用子集树表示解空间，根结点为第 $0$ 层
约束函数用于剪去不满足约束条件 $\displaystyle\sum\limits_{i = 1}^{n}{w_{i} x_{i}} \leq c_{1}$ 的子树
- 在子集树的第 $j$ 层的结点 $Z$ 处，用 $c w$ 记为当前的装载重量，即 $\displaystyle\sum\limits_{i = 1}^{j}{w_{i} x_{i}}$
- 当 $cw > c_{1}$ 时，以结点 $Z$ 为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去
限界函数用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率
- 设 $Z$ 是解空间树第 $i$ 层上的当前扩展结点， $c w$ 是当前载重量， $b es tw$ 是当前最优载重量， $r$ 是剩余集装箱的重量，即 $\displaystyle\sum\limits_{j = i + 1}^{n}{w_{j}}$
- 定义限界函数为 $c w + r$ ，在以 $Z$ 为根的子树中任一叶结点所相应的重量均不超过 $c w + r$ ，当 $\leq bestw$ 时，可将 $Z$ 的子树剪去
当 $i = n$ 时，算法搜索至叶结点，其相应的装载重量为 $c w$ ，如果 $c w > b es tw$ ，则表示当前解优于当前最优解，此时更新 $b es tw$
当 $i < n$ 时，当前扩展结点 $Z$ 是子集树中的内部结点
- 该结点的左儿子表示 $x [i + 1] = 1$ 的情形，仅当 $\leq c_{1}$ 时进入左子树，对左子树递归搜索
- 该结点的右儿子表示 $x [i + 1] = 0$ 的情形，由于可行结点的右儿子结点总是可行的，因此进入右子树时不需要检查约束函数，只需要检查限界函数

`Python`实现

def backtrack_loading(weights, capacity):n = len(weights)best_solution = []best_value = 0def constraint(weight):# 约束函数: 检查当前解是否满足容量限制return weight <= capacitydef bound(weight, index):# 限界函数: 计算当前解的重量总和加上剩余物品重量作为上界, 用于剪枝weight += sum(weight for weight in weights[index + 1:])return weightdef backtrack(solution, weight, value, index):nonlocal best_solution, best_valueif index == n:# 已经遍历完所有物品if value > best_value:# 如果当前解的重量更大, 更新最优解best_solution = solutionbest_value = valuereturn# 尝试选择当前物品weight += weights[index]if constraint(weight):# 如果满足约束函数, 继续探索下一个物品backtrack(solution + [weights[index]], weight, value + weights[index], index + 1)# 恢复回溯前状态weight -= weights[index]# 尝试不选择当前物品if bound(weight, index) > best_value:# 如果当前解的上界仍然可能更好, 继续探索下一个物品backtrack(solution, weight, value, index + 1)# 开始回溯搜索backtrack([], 0, 0, 0)return best_solution, best_valueweights = [2, 4, 5, 7]
capacity = 10best_solution, best_value = backtrack_loading(weights, capacity)print(f'最优解: {best_solution}')
print(f'最优值: {best_value}')