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

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

文章目录

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

问题描述

• 有一批共$n$个集装箱要装上$2$艘载重量分别为$c_1$和$c_2$的轮船，其中集装箱$i$的重量为$w_i$，且$\sum _{i=1}^n{w}_i\le c_1+c_2$
• 是否有一个合理的装载方案可将这$n$个集装箱装上这两艘轮船

---

问题转换

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

{ max ⁡ ∑ i = 1 n w i x i s . t . ∑ i = 1 n w i x i ≤ c 1 x i ∈ { 0 , 1 } , 1 ≤ i ≤ n \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 ⎩ ⎨ ⎧​maxi=1∑n​wi​xi​s.t.i=1∑n​wi​xi​≤c1​​xi​∈{0,1},1≤i≤n

---

回溯算法

• 用子集树表示解空间，根结点为第$0$层
• 约束函数用于剪去不满足约束条件$\sum _{i=1}^n{w}_i{x}_i\le c_1$的子树
  • 在子集树的第$j$层的结点$Z$处，用$cw$记为当前的装载重量，即$cw=\sum _{i=1}^j{w}_i{x}_i$
  • 当$cw>c_1$时，以结点$Z$为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去
• 限界函数用于剪去不含最优解的子树，从而改进算法在平均情况下的运行效率
  • 设$Z$是解空间树第$i$层上的当前扩展结点，$cw$是当前载重量，$bestw$是当前最优载重量，$r$是剩余集装箱的重量，即$r=\sum _{j=i+1}^n{w}_j$
  • 定义限界函数为$cw+r$，在以$Z$为根的子树中任一叶结点所相应的重量均不超过$cw+r$，当$cw+r\le bestw$时，可将$Z$的子树剪去
• 当$i=n$时，算法搜索至叶结点，其相应的装载重量为$cw$，如果$cw>bestw$，则表示当前解优于当前最优解，此时更新$bestw$
• 当$i<n$时，当前扩展结点$Z$是子集树中的内部结点
  • 该结点的左儿子表示$x[i+1]=1$的情形，仅当$cw+w[i+1]\le 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}')

最优解: [2, 7]
最优值: 9

---

时间复杂性

• 计算上界需要$O(n)$时间，在最坏情况下有$O(2^n)$个右儿子结点需要计算上界
• 所以解装载问题的回溯算法所需的计算时间为$O(n{2}^n)$

---

这篇关于【回溯算法】【Python实现】装载问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---