0

假设我有一组对象，S. 有一种算法f，给定一个集合在其上S构建一定的数据结构D：f(S) = D. 如果S很大和/或包含非常不同的对象，则会D变得很大，以至于无法使用（即不适合分配的内存）。为了克服这个问题，我分成S几个不相交的子集：S = S1 + S2 + ... + Sn并为每个子集构建Di。使用n结构比使用结构效率低，但至少这样我可以适应内存限制。由于大小的f(S)增长速度比S自身快，组合大小Di远小于大小D。

然而，仍然希望减少n，即子集的数量；或减小 的组合大小Di。为此，我需要以S每个Si包含“相似”对象的方式进行拆分，因为f如果输入对象彼此“足够相似”，则会产生较小的输出结构。

问题是，虽然对象的“相似性”S和 do 的大小f(S)相关，但除了评估之外，没有办法计算后者f(S)，而且f速度不是很快。

我目前拥有的算法是迭代地将每个下一个对象从 中添加S到其中一个中Si，这样就可以尽可能少地（在这个阶段）增加组合Di大小：

for x in S:
    i = such i that
             size(f(Si + {x})) - size(f(Si))
             is min
    Si = Si + {x}

这给出了实际有用的结果，但肯定远非最佳（即最小可能的组合大小）。另外，这很慢。为了加快速度，我只计算size(f(Si + {x})) - size(f(Si))那些i与.xSi

这类问题有什么标准方法吗？

我知道分支和边界算法系列，但它不能在这里应用，因为它会非常慢。我的猜测是，根本不可能在合理的时间内计算S出in 的最佳分布。Si但是有一些常见的迭代改进算法吗？

编辑：

正如评论所指出的，我从未定义过“相似性”。事实上，我想要的只是分割成Si组合大小Di = f(Si)最小或至少足够小的子集。“相似度”仅被定义为这一点，不幸的是，它根本无法轻松计算。我确实有一个简单的近似值，但仅此而已——一个近似值。

所以，我需要的是一个（可能是启发式的）算法，sum f(Si)考虑到没有简单的方法来计算后者——我只需要一个近似值来丢弃不太可能给出好的结果的情况。

4

1 回答 1

0

关于速度慢，我发现在类似问题中，一个足够好的解决方案是仅通过选择固定数量的随机候选者来计算匹配。

诚然，结果不会是最好的（通常比你实施的完整的“贪婪”解决方案更糟糕），但根据我的经验，它还不错，你可以决定速度......它甚至可以以规定的数量实施时间（即您继续搜索，直到分配的时间到期）。

我使用的另一个选择是继续搜索，直到我暂时看不到任何改进。

为了克服贪婪的逻辑，您可以保留一个包含 N 个“x”元素的队列，并尝试将它们同时打包成“k”组（k < N）。在这种情况下，我发现保留队列中元素的“年龄”并将其用作结果的“奖品”也很重要，以避免将“坏”元素永远保留在队列中，因为其他元素总是匹配得更好（这会使队列搜索无用，结果与贪心方法基本相同）。

于 2010-06-12T19:48:15.807 回答