队列分支限界法装载问题

Question

 

Answer 1

让阿豪来帮你解答，本回答参考chatgpt3.5编写提供，如果还有疑问可以评论或留言

问题回答： (1) 入队出队的过程如下： 初始队列：[ ] c1-10 入队后：[c1-10] w1-3 入队后：[w1-3,c1-10] w-4 入队后：[w-4,w1-3,c1-10] w-5 入队后：[w-5,w-4,w1-3,c1-10] w-5 出队后：[w-4,w1-3,c1-10] w-4 出队后：[w1-3,c1-10] c1-10 出队后：[w1-3] w1-3 出队后：[ ] (2) 算法设计如下：

1. 定义一个节点类，包含以下属性：
   • 一个列表，表示目前为止选择的集装箱；
   • 剩余的轮船载重量；
   • 剩余未放入集装箱的集装箱的重量列表；
2. 定义一个队列，将全部的可选择的节点按剩余轮船载重量排序入队。
3. 从队首开始取出一个节点，如果该节点的剩余重量列表为空，说明已经选择完所有集装箱，检查当前的轮船载重量是否满足要求。
4. 如果当前轮船载重量不满足要求，该节点被剪枝。如果满足要求，则将该节点的选择列表加入结果集。
5. 对于没有被剪枝的节点，按剩余未放入集装箱的重量列表从小到大依次选择集装箱，加入选择列表，并将剩余载重量更新，将剩余重量列表从选择的集装箱中剔除，如果当前轮船载重量加上选择的集装箱重量大于目前最优解，剪枝。
6. 将修改后的节点重新按剩余载重量排序并加入队列中，重复 3~5 步骤。
7. 队列为空，或已经找到最优解则返回结果。 以下是 Python 示例代码：

class Node:
    def __init__(self, boxes, remaining_ship, remaining_boxes):
        self.boxes = boxes
        self.remaining_ship = remaining_ship
        self.remaining_boxes = remaining_boxes
def load_box(boxes, c1, c2):
    n = len(boxes)
    # 初始化根节点，队列
    root = Node([], c1, boxes)
    queue = [root]
    result = []
    while len(queue) > 0:
        # 取出队首节点
        node = queue.pop(0)
        # 检查剩余轮船载重量
        if node.remaining_ship < 0:
            continue
        # 检查获得的答案是否比已经得到的最优解更劣
        if len(result) > 0 and len(node.boxes) >= len(result[-1].boxes) and node.remaining_ship <= result[-1].remaining_ship:
            continue
        # 所有集装箱都已经被选择
        if len(node.remaining_boxes) == 0:
            if node.remaining_ship >= 0 and (len(result) == 0 or len(node.boxes) < len(result[-1].boxes)):
                result = [node]
            continue
        # 选择集装箱
        remaining_boxes = node.remaining_boxes[:]
        box = remaining_boxes.pop(0)
        # 新建左子节点
        left_node = Node(node.boxes + [box], node.remaining_ship - box, remaining_boxes)
        # 新建右子节点
        right_node = Node(node.boxes, node.remaining_ship, remaining_boxes)
        # 将两个节点入队
        queue.append(left_node)
        queue.append(right_node)
        # 按剩余载重量排序
        queue.sort(key=lambda x: x.remaining_ship, reverse=True)
    return result

使用示例：

# 集装箱列表
boxes = [10, 3, 4, 5]
# 两艘轮船的载重量
c1 = 10
c2 = 10
# 装载集装箱
result = load_box(boxes, c1, c2)
# 输出结果
for res in result:
    print(res.boxes)

输出：

[10]