3

我将使用 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]

当无序时，每个数字的去向并不重要，只要它们之间没有空格即可。

数字可以在连续的块中移动，将它们向左或向右移动任意数量的成本相同，但是存在设置和拆卸成本，这使得移动更大的块并在尽可能少的更新中实现它变得更加有效.

现在我正在使用最简单的解决方案，查找连续数字块并将它们一次移动一个块到最近的左侧，直到它被打包。因此，在示例中，5、6 在一次更新中向左移动了 2 个块，然后在另一个更新中将 10 向左移动了 5 个块。

[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 块来将列表打包到单个更新中：

[None, None, None, None, None, 5, 6, 0, 1, 2, 10]

实际上会有数千个块，但我事先知道每个块的大小和每个间隙。与它们的大小和间隙之间的组合计算所需的计算相比，移动块也非常昂贵，因此找到最佳解决方案是理想的。

这似乎是一种装箱问题，但我真的不知道如何接近它以找到最佳解决方案。有任何想法吗？

4

3 回答 3

3

对于无序的情况，假设有人告诉你最后的连续块应该填充哪些空间。然后一个启发式方法是假设如果您首先将该区域之外的最大块移入该区域，那么一切都会适合并且您不必分解任何块。正如评论中所建议的，您可以使用它运行 A* （或分支和绑定）。然后你的第一个决定是最终的连续块应该在哪里，但这只是 A*/branch and bound 的另一个级别——事实上，在这种启发式下，最有希望的最终连续区域将是当前拥有最多填充数的区域在子区域中，因为您假设您只需要在此之外的子区域中移动。

如果您确实发现这太昂贵了，那么以获得较差答案为代价来加速分支和绑定的一种方法是丢弃可能的答案，对于某些 X，这些答案可能会使迄今为止找到的最佳答案仅提高 X%。

实际上，我认为您可以获得比这更好的下限 - 最大值（目标区域中单独连续间隙的数量，要从源区域移入的单独连续区域的数量）应该稍微好一点，因为一次移动最多可以移动在单个连续的数字区域中并填充目标区域中的单个空白。

获得下限的一种简单方法是忽略对问题的足够约束以使其变得容易。假设未知的正确答案仍然是一个可行的解决方案，这必须给你一个下限，因为弱化问题的最佳解决方案必须至少与未知的正确答案一样好。您可以假装两个更新永远不会相互冲突，从而将其应用于您的更新问题。给定一个指定的目标区域，计算这种启发式方法相当于找到一种将源区域切割成块的最佳方法，每个块都适合目标区域。您可以使用动态程序解决此问题：通过考虑在源区域的最后 k 个单元中复制的所有可能方式，您可以为源区域的前 n+1 个单元计算出最佳答案，然后添加复制源区域的前 n+1-k 个单元的成本，您已经计算过了。不幸的是，我不知道这种启发式方法是否足够强大以至于有用。

于 2012-04-22T04:06:25.227 回答
2

您描述的问题称为压缩问题。在经典的压缩问题（有序和无序变体）中，数据移动的成本并不那么高。因此，可以通过使用辅助存储并在一次线性扫描中将非空条目复制到辅助存储中来轻松解决。新的压缩存储可以简单地替换原始存储或复制到原始存储，具体取决于上下文。现在，所有这些都可以在线性时间内完成，并且只使用线性附加存储。因此，从装箱的意义上说，它不被认为是一个难题。对于豆类包装，无论您是否允许线性数量的额外存储，都绝对没有简单的解决方案。所以，很明显我们在这里处理的不是装箱。

当数据移动成本高昂时，现在有一个额外的限制是最小化非连续数据块的移动次数。可以将此问题视为以下两个问题之一的一个实例：

  1. 二进制数组的就地排序。在这里，您将数组建模为仅包含两种数据——0 和 1。这可以在您的情况下使用谓词 isNull(a) 轻松实现，该谓词对于空数据条目返回 1，对于非空数据条目返回 0。我能想到的最简单的解决方案是使用选择排序 对二进制数组进行排序。在最坏的情况下，它永远不会超过O(n)的数据移动，即使它可以进行O(n 2 )次比较，但您不介意，因为您只想最小化数据移动的数量. 如果没有要移动的数据，它不会做任何事情！一些使事情复杂化的改进可能是：

    • 交换块而不是单个条目。我的意思是，只有当零块更大时，才能交换两个块（一个零，另一个）。您还可以使用贪婪启发式，即下一次交换始终是最小化这两者的绝对差异的交换，即 abs(len(zeroBlock) - len(oneBlock))。这仅适用于您的问题的无序实例。
    • 另外两个优化是做一个预处理来决定天气是升序还是降序。
    • 此外，您可能希望排除列表的连续末端。

  2. 垃圾压缩。本质上，这个想法是将空闲空间视为内存中需要进行垃圾收集的已释放空间。为此，让我向您推荐这个有趣的SO 讨论线程和这个。您可能还会发现这篇研究论文或这篇论文很有用。

祝你好运！

于 2012-04-22T20:00:56.957 回答
1 
#include <stdio.h>
#include <string.h>

#define IS_EMPTY(c) ((c) <= '@')

unsigned moverup(char buff[], unsigned size)
{
unsigned src,dst,cnt;

for (src=dst=cnt=0; src < size; src++ ) {
        if (!IS_EMPTY(buff[src])) { cnt++; continue; }
        if (!cnt) continue;
ugly:
        memmove(buff+dst, buff+src-cnt, cnt );
        dst += cnt;
        cnt = 0;
        }
if (cnt) goto ugly;
return dst;
}

int main(void)
{
unsigned result;
char array[] = "qwe@rty@ui#op";

printf("Before:%s\n", array );

result = moverup (array, strlen (array) );

printf("result:%u\n", result );
// entries beyond result will contain garbage now.
// array[result] = 0;
printf("After:%s\n", array );

return 0;
}
于 2012-04-22T21:37:31.000 回答