解决6栈6层码头集装箱堆栈翻箱最优解问题

‘’’
con 1
origin_stack = [
[4, 4, 1, 0, 0, 0], # 第一栈
[4, 3, 2, 1, 0, 0], # 第二栈
[4, 2, 2, 1, 0, 0], # 第三栈
[3, 3, 3, 1, 0, 0], # 第四栈
[3, 4, 2, 1, 0, 0], # 第五栈
[4, 2, 3, 2, 0, 0] # 第六栈
]

con 2
origin_stack = [
[4, 4, 3, 0, 0, 0], # 第一栈
[2, 2, 4, 1, 0, 0], # 第二栈
[4, 1, 3, 3, 0, 0], # 第三栈
[1, 4, 2, 1, 0, 0], # 第四栈
[4, 3, 4, 3, 2, 0], # 第五栈
[2, 2, 1, 1, 0, 0] # 第六栈
]

con 3
origin_stack = [
[4, 2, 2, 0, 0, 0], # 第一栈
[1, 1, 1, 0, 0, 0], # 第二栈
[4, 3, 3, 4, 2, 1], # 第三栈
[2, 2, 3, 0, 0, 0], # 第四栈
[2, 3, 4, 1, 0, 0], # 第五栈
[2, 3, 4, 3, 1, 0] # 第六栈
]

con 4
origin_stack = [
[2, 3, 4, 3, 2, 2], # 第一栈
[4, 4, 4, 0, 0, 0], # 第二栈
[2, 1, 1, 3, 0, 0], # 第三栈
[4, 1, 3, 0, 0, 0], # 第四栈
[1, 3, 2, 3, 2, 0], # 第五栈
[1, 1, 4, 0, 0, 0] # 第六栈
]

con 5
origin_stack = [
[3, 2, 1, 4, 0, 0], # 第一栈
[2, 1, 3, 4, 0, 0], # 第二栈
[1, 1, 2, 4, 1, 0], # 第三栈
[2, 1, 2, 0, 0, 0], # 第四栈
[3, 4, 0, 0, 0, 0], # 第五栈
[3, 3, 2, 4, 3, 4] # 第六栈
]

con 6
origin_stack = [
[3, 2, 3, 0, 0, 0], # 第一栈
[2, 1, 3, 4, 0, 0], # 第二栈
[1, 1, 2, 4, 1, 0], # 第三栈
[2, 1, 2, 0, 0, 0], # 第四栈
[3, 4, 0, 0, 0, 0], # 第五栈
[3, 3, 2, 4, 3, 4] # 第六栈
]

con 7
origin_stack = [
[3, 1, 4, 4, 1, 1], # 第一栈
[1, 3, 0, 0, 0, 0], # 第二栈
[2, 2, 4, 0, 0, 0], # 第三栈
[2, 1, 2, 4, 0, 0], # 第四栈
[4, 1, 2, 3, 3, 3], # 第五栈
[4, 3, 2, 0, 0, 0] # 第六栈
]

con 8
origin_stack = [
[3, 1, 1, 3, 0, 0], # 第一栈
[2, 3, 3, 4, 1, 0], # 第二栈
[2, 3, 1, 3, 3, 0], # 第三栈
[4, 4, 2, 0, 0, 0], # 第四栈
[2, 4, 4, 0, 0, 0], # 第五栈
[1, 2, 4, 1, 0, 0] # 第六栈
]

con 9
origin_stack = [
[2, 1, 4, 1, 0, 0], # 表第一栈
[4, 3, 1, 3, 3, 4], # 第二栈
[2, 3, 2, 0, 0, 0], # 第三栈
[1, 2, 4, 4, 3, 2], # 第四栈
[3, 4, 1, 0, 0, 0], # 第五栈
[2, 1, 0, 0, 0, 0] # 第六栈
]

con 10
origin_stack = [
[2, 1, 0, 0, 0, 0], # 第一栈
[4, 3, 1, 0, 0, 0], # 第二栈
[2, 2, 2, 2, 1, 1], # 第三栈
[1, 0, 0, 0, 0, 0], # 第四栈
[3, 3, 3, 3, 3, 2], # 第五栈
[4, 4, 4, 4, 4, 1] # 第六栈
]

‘’’
上面为初始堆栈状态10个

解决6栈6层码头集装箱堆栈翻箱最优解问题

问题描述

码头集装箱堆栈翻箱问题是一个经典的物流优化问题。在这个具体场景中，我们有6栈*6层的集装箱堆栈，需要重新排列这些集装箱，使得：

1. 优先级高的集装箱（数字越小优先级越高）放在上层
2. 同一优先级的集装箱尽量分布在不同的栈中

其中，每个数字代表一个集装箱的优先级，数字越小优先级越高，0表示该位置没有集装箱。

#需求
使用A*算法或其它算法寻找最优解
每次只能移动一个集装箱
优先级高的集装箱应放在上层
同一优先级的集装箱尽量分布在不同的栈
每一步需要打印堆栈状态
计算并输出算法执行的时间

下面是解答：

码头集装箱堆栈翻箱问题解决方案

我将使用A算法来解决这个6栈6层集装箱堆栈翻箱问题。A算法是一种启发式搜索算法，非常适合这种状态空间搜索问题。

解决方案代码

import heapq
import time
from copy import deepcopy
from typing import List, Tuple, Dict, Optional

class ContainerStack:
    def __init__(self, stacks: List[List[int]]):
        self.stacks = stacks
        self.width = len(stacks)
        self.height = len(stacks[0]) if self.width > 0 else 0
    
    def __eq__(self, other):
        return self.stacks == other.stacks
    
    def __hash__(self):
        return hash(tuple(tuple(stack) for stack in self.stacks))
    
    def __str__(self):
        return "\n".join([f"Stack {
     i+1}: {
     stack}" for i, stack in enumerate(self.stacks)])
    
    def is_valid_move(self, from_stack: int, to_stack: int) -> bool:
        # 检查移动是否有效
        if from_stack == to_stack:
            return False
        if not (0 <= from_stack < self.width and 0 <= to_stack < self.width):
            return False
        
        # 找到from_stack最上面的集装箱
        from_top_pos = -1
        for i in range(self.height):
            if self.stacks[from_stack][i] != 0:
                from_top_pos = i
                break
        
        # 如果from_stack为空
        if from_top_pos == -1:
            return False
        
        # 找到to_stack最上面的集装箱位置
        to_top_pos = -1
        for i in range(self.height):
            if self.stacks[to_stack][i] != 0: