如我在评论中所述，查找是否存在任何解决方案的问题被称为Bin Packing且是NP完全问题。因此，任何解决方案都有可能无法找到答案，或者会变得可能呈指数级缓慢。
明确的偏好是有时找不到答案。 因此，我会做出合理的决策以实现此目标。
请注意，这需要我花费几天时间才能实现。 您可以自己尝试一下，但如果需要，您可以发送电子邮件至btilly@gmail.com与我们讨论合同（我已经在上面花费了太长时间了）。
接下来，对最短路径的请求意味着进行广度优先搜索。 因此，我们将通过“路径的合理性”进行广度优先搜索。 基本上，我们将首先尝试贪婪策略，然后如果时间过长就截断它。 因此，我们可能会找到错误的答案（如果贪婪错误），或放弃（如果时间太长）。 但总体而言，我们会做得比较好。
那么什么是合理的路径呢？对于装箱问题，一个好的贪心解决方案总是先放最重的物品，并将其放在最满的箱子中。这对于一次性放置一堆物品非常有用，但它不能直接帮助您移动物品。
因此，我们将优先考虑创建大空洞的移动。因此，我们尝试的第一件事情的规则变成了：
- 始终首先放置最重的物品。
- 如果可能，将其放置在离容器最满的地方。
- 尝试移动物品以创建大空间而不是小空间。
- 尽早去重。
弄清楚这一点将涉及到很多“选择最接近满箱的地方，我适合在哪里”和“选择让我适合的箱子中最小的东西”。您希望在查看很多“我们做了X、Y和Z……”然后查看“……或者可能是X、Y和W……”时完成此操作。
幸运的是，我碰巧有一个非常适合这种情况的完美数据结构。https://dev59.com/h38QtIcB2Jgan1zn5X4k#75453554 展示了如何拥有一个平衡的二叉树，保持排序顺序，并且可以轻松克隆并尝试一些操作而不影响原始树。我在那里做了一些让你可以迭代旧树的操作。但是你也可以使用它来创建一个克隆版本，尝试一些后来可能会放弃的操作。
我没有将其作为多集合（能够多次添加元素）或添加 next_biggest 方法。可以通过向节点添加 count 来实现多集合。现在 contains 可以返回计数（可能为 0），而不是布尔值。添加 next_biggest 相当容易。
我们需要为此添加一个 hash 函数以进行去重。我们可以递归地定义如下：
node.hash = some_hash(some_hash(node.value) + some_hash(node.left.hash) + some_hash(node.right.hash))
(如果node.left或node.right是None，请插入适当的默认哈希)
如果我们在创建节点时将其存储起来，那么查找它以进行去重很快。
如果你有许多容器和许多对象，你可以按照大小的顺序存储对象，并按照剩余空间和bin.hash的顺序存储容器。现在的想法是按照以下方式将一个新对象添加到容器中：
new_bin = old_bin.add(object)
new_bins = old_bins.remove(old_bin).add(new_bin)
并且类似地移除：
new_bin = old_bin.remove(object)
new_bins = old_bins.remove(old_bin).add(new_bin)
在有
n 个对象分布在
m 个容器的情况下，每次构建新状态只使用
O(log(n) + log(m)) 的新数据。我们可以轻松地判断是否已经访问过这些状态。
现在，我们创建由以下部分解对象组成：
prev_solution (the solution we came from, may be None)
current_state (our data for bins and objects in bins)
creation_id (ascending id for partial solutions)
last_move (object, from_bin, to_bin)
future_move_bins (list of bins in order of largest movable object)
future_bins_idx (which one we last looked at)
priority (what order to look at these in)
moves (how many moves we've actually used)
move_priority (at what priority we started emptying the from_bin)
部分解决方案应该基于priority和creation_id进行比较。它们应该基于(solution.state.hash, solution.last_move.move_to.hash, future_bins_idx)进行哈希。
需要有一个名为next_solutions的方法。它将返回下一组要考虑的未来解决方案。(这些可能共享)
第一个部分解决方案将具有prev_solution = None，creation_id=1，last_move=None和priority = moves = move_priority = 0。 future_move_bins将是按最大可移动元素降序排序的箱子列表。而future_move_bins_idx将是0
当我们创建一个新的部分解决方案时，我们必须：
clone old solution into self
self.prev_solution = old solution
self.creation_id = next_creation_id
next_creation_id += 1
set self.last_move
remove object from self.state.from_bin
add object to self.state.to_bin
(fixing future_move_bins left to caller)
self.moves += 1
if the new from_bin matches the previous:
self.priority = max(self.moves, self.move_priority)
else:
self.priority += 1
self.move_priority = self.priority
好的，这是很多设置。我们快要完成了。（除了关键字future_moves的部分。）
接下来我们需要的是优先队列的概念。在 Python 中，可以通过 heapq 实现。
现在，这里是搜索的逻辑：
best_solution_hash_moves = {}
best_space_by_moves = {}
construct initial_solution
queue = []
add initial_solution.next_solutions() to queue
while len(queue) and not_time_to_stop():
solution = heapq.heappop(queue)
if can add target object to solution.state:
walk prev_solution backwards to get the moves we want
return reverse of the moves we found.
if solution.hash() not in best_solution_hash:
best_solution_hash[solution.hash()] = solution
elif solution.moves < best_solution_hash[solution.hash()].moves:
solution.priority = min(solution.priority, best_solution_hash[solution.hash()].priority - 0.01)
best_solution_hash[solution.hash()] = solution
if best_solution_hash[solution.hash()] == solution:
for next_solution in solution.next_solutions():
if solution.moves not in best_space_by_moves or
best_space_by_moves[solution.moves] <=
space left in solution.last_move.from_bin:
best_space_by_moves[solution.moves] =
space left in solution.last_move.from_bin:
solution.priority = solution.move_priority = solution.moves
add next_solution to queue
return None
所以这个想法是，我们采用最好的解决方案，考虑几个相关方案，然后将它们添加回队列中，通常具有更高的优先级。因此，如果某个相当贪婪的东西有效，我们会很快尝试它。随着时间的推移，我们会走向不太光明的路。如果其中一个让我们感到惊喜，我们就会将其优先级设置为
moves（从而使我们集中注意力），并更加强烈地探索这条路。
那么
next_solutions 是做什么的呢？大致如下：
def next_solutions(solution):
if solution.last_move is None:
if future_bins is not empty:
yield result of moving largest movable in future_bins[0] to first bin it can go into (ie enough space)
else:
if can do this from solution:
yield result of moving largest movable...
in future_bins[bin_idx]...
to smallest bin it can go in...
...at least as big as last_move.to_bin
if can move smaller object from same bin in prev_solution:
yield that with priority solution.priority+2
if can move same object to later to_bin in prev_solution:
yield that with priority solution.priority+2
if can move object from next bin_idx in prev_solution:
yield result of moving that with priority solution.priority+1
请注意，首先尝试移动小物体或将物体移动到比所需更空的箱子中是可能的，但不太可能是一个好主意。因此，我对此进行了更严厉的惩罚，以便优先队列专注于更好的想法。这导致分支因子约为2.7。
因此，如果明显的贪婪方法在少于7步的情况下成功，队列在找到它之前很可能会达到1000左右的大小。如果您有几个次优选择，队列很可能会找到它。
即使需要做出一些不寻常的选择，您仍然可以快速获得答案。您可能找不到最佳解决方案，但通常会找到相当不错的解决方案。
具有大量数据的十几个移动的解决方案将需要队列增长到约10万个项目，并且应该需要50-500 MB的内存。这可能是这种方法的极限。
如果箱子已经装满，没有太多的移动要做，那么所有这些都可能更快（很多）。
