【回溯】装载问题Python实现

发布时间:2023年12月25日

因上努力

个人主页:丷从心

系列专栏:回溯法

果上随缘


问题描述

  • 有一批共 n n n个集装箱要装上 2 2 2艘载重量分别为 c 1 c_{1} c1? c 2 c_{2} c2?的轮船,其中集装箱 i i i的重量为 w i w_{i} wi?,且 ∑ i = 1 n w i ≤ c 1 + c 2 \displaystyle\sum\limits_{i = 1}^{n}{w_{i}} \leq c_{1} + c_{2} i=1n?wi?c1?+c2?
  • 是否有一个合理的装载方案可将这 n n n个集装箱装上这两艘轮船

问题转换

  • 先将第一艘轮船尽可能装满,然后将剩余的集装箱装上第二艘轮船
  • 装载问题等价于以下特殊的 0 ? 1 0-1 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} , 1 \leq i \leq n ? ? ??maxi=1n?wi?xi?s.t.i=1n?wi?xi?c1??xi?{0,1},1in


回溯法

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

时间复杂性

  • 在每个结点处算法花费 O ( n ) O(n) O(n)时间,子集树中结点个数为 O ( 2 n ) O(2^{n}) O(2n),故时间复杂性为 O ( n 2 n ) O(n 2^{n}) O(n2n)

Python实现

def backtrack_loading(weights, capacity):
    n = len(weights)
    best_solution = []
    best_value = 0

    def constraint(solution):
        # 约束函数: 检查当前解是否满足容量限制
        total_weight = sum(item for item in solution)

        return total_weight <= capacity

    def bound(solution, index):
        # 限界函数: 计算当前解的重量总和加上剩余物品重量作为上界, 用于剪枝
        total_weight = sum(item for item in solution) + sum(weight for weight in weights[index + 1:])

        return total_weight

    def backtrack(solution, value, index):
        nonlocal best_solution, best_value

        if index == n:
            # 已经遍历完所有物品
            if value > best_value:
                # 如果当前解的重量更大, 更新最优解
                best_solution = solution
                best_value = value

            return

        # 尝试选择当前物品
        weight = weights[index]
        if constraint(solution + [weight]) and bound(solution + [weight], index) >= best_value:
            # 如果满足约束函数, 继续探索下一个物品
            backtrack(solution + [weight], value + weight, index + 1)

        # 尝试不选择当前物品
        if bound(solution, index) >= best_value:
            # 如果当前解的上界仍然可能更好, 继续探索下一个物品
            backtrack(solution, value, index + 1)

    # 开始回溯搜索
    backtrack([], 0, 0)

    return best_solution, best_value


weights = [2, 4, 5, 7]
capacity = 10

best_solution, best_value = backtrack_loading(weights, capacity)

print(f'最优解: {best_solution}')
print(f'最优值: {best_value}')
最优解: [2, 7]
最优值: 9

文章来源:https://blog.csdn.net/from__2023_11_28/article/details/135203024
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。