我将使用 Python 语法和对象来表示问题，但实际上它适用于 SQL 数据库中的模型，具有 Python API 和 ORM。
我有一个这样的数字列表:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
有时，一些数字会被删除，而空空格仍然存在:
[0, 1, 2, None, None, 5, 6, None, None, None, 10]
我需要做的是在定期执行的维护步骤中以有序和无序的方式有效地打包这组数字，以便数字之间没有空空格:
因此，按照有序的方式，我需要将该列表变为:
[0, 1, 2, 5, 6, 10, None, None, None, None, None]
当无序时，每个数字的去向并不重要，只要它们之间没有空空格即可。
数字可以在连续的 block 中移动，并且将它们向左或向右移动任意数量的位置成本相同，但是有一个设置和拆卸成本使得移动更大的 block 并在尽可能少的时间内实现它更加有效尽可能更新。
现在我正在使用最简单的解决方案，找到连续数字 block 并将它们一次移动到最近的左边一个 block ，直到它被打包。因此，在示例中，5、6 在一次更新中向左移动了 2 个 block ，然后 10 在另一个更新中向左移动了 5 个 block 。
[0, 1, 2, None, None, 5, 6, None, None, None, 10]
[0, 1, 2, 5, 6, None, None, None, None, None, 10]
[0, 1, 2, 5, 6, 10, None, None, None, None, None]
当顺序很重要时，这种简单的方法似乎是最有效的，但实际上我的大部分操作都是无序的，我认为应该有更好的方法。例如，在这种情况下，可以通过在 6 和 10 之间移动 0、1、2 block 来将列表打包在单个更新中:
[None, None, None, None, None, 5, 6, 0, 1, 2, 10]
现实中会有上千个 block ，但我事先知道每个 block 的大小和每个间隙。与 block 的大小和间隙之间的组合所需的计算相比，移动 block 的成本也非常高，因此找到最优解是理想的。
这似乎是一种装箱问题，但我真的不知道如何处理它才能找到最佳解决方案。有什么想法吗？
最佳答案
对于无序的情况，假设有人告诉你最后的连续 block 应该填充哪些空间。然后一种启发式假设，如果您首先将该区域以外的最大块移动到该区域中，那么一切都会适合并且您不必分解任何 block 。正如评论中所建议的，您可以使用它运行 A*(或分支定界)。然后你的第一个决定是最终的连续 block 应该在哪里，但这只是 A*/分支定界的另一个级别 - 事实上在这种启发式下，最有希望的最终连续区域将是当前拥有最多填充数的区域在子区域中，因为您假设您只需要在此之外的子区域中移动。
如果您确实发现这太昂贵了，加速分支定界的一种方法是以得到较差答案为代价的一种方法是丢弃可能的答案，这些答案可能会将目前找到的最佳答案提高 X%，对某些人来说X.
实际上，我认为您可以获得比这稍微好一点的下限 - max(目标区域中单独的连续间隙的数量，要从源区域移入的单独的连续区域的数量)应该稍微好一点，因为一步可以充其量只能在一个连续的数字区域中移动并填补目标区域中的一个空白。
获得下限的一种简单方法是忽略对问题的足够限制以使其变得简单。假设未知的正确答案仍然是一个可行的解决方案，这必须给你一个下限，因为弱化问题的最佳解决方案必须至少与未知的正确答案一样好。您可以假装两个更新永远不会相互冲突，从而将其应用于间隙更新的问题。给定一个指定的目标区域，计算这种启发式算法相当于找到一种最佳方法，将源区域切割成 block ，每个 block 都适合目标区域。您可以使用动态程序解决此问题:通过考虑在源区域的最后 k 个单元格中复制的所有可能方式，然后添加复制成本，您可以为源区域的前 n+1 个单元格计算出最佳答案在源区域的前 n+1-k 个单元格中，您已经计算过了。不幸的是，我不知道这种启发式是否足够强大以至于有用。
关于algorithm - 有效地删除一组数字中的空格，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10264767/