algorithm - 集合分区比差分结果更好

Question

Partition problem已知是 NP-hard。根据问题的特定实例，我们可以尝试动态规划或一些启发式算法，如差分(也称为 Karmarkar-Karp 算法)。

后者似乎对具有大数字的实例非常有用(这使得动态编程难以处理)，但并不总是完美的。找到更好的解决方案(随机、禁忌搜索、其他近似)的有效方法是什么？

PS:这个问题背后有一些故事。有挑战Johnny Goes Shopping自 2004 年 7 月起在 SPOJ 上可用。截至目前，该挑战已被 1087 名用户解决，但其中只有 11 人的得分高于正确的 Karmarkar-Karp 算法实现(按照目前的评分，Karmarkar-Karp 给出 11.796614 分)。怎么做更好？ (最想要的已接受提交支持的答案，但请不要透露您的代码。)

Answer 1

无论如何，[Korf88] 中“完整的 Karmarkar Karp”(CKK)搜索过程的一个简单的、未优化的 Python 实现——仅稍作修改以在给定的时间限制(例如，4.95 秒)后退出搜索和返回迄今为止找到的最佳解决方案 -- 足以得分 14.204234 在 SPOJ 问题上，击败了 Karmarkar-Karp 的分数。在撰写本文时，这是 #3 on the rankings ( 参见下面的编辑 #2 )

在 [Mert99] 中可以找到 Korf 的 CKK 算法的更易读的介绍。

编辑 #2 - 我已经实现了 Evgeny Kluev's混合启发式应用 Karmarkar-Karp 直到数字列表低于某个阈值，然后切换到精确的 Horowitz-Sahni 子集枚举方法 [HS74](可在 [Korf88] 中找到简明描述)。正如所怀疑的那样，与他的 C++ 实现相比，我的 Python 实现需要降低切换阈值。通过反复试验，我发现 37 的阈值是允许我的程序在时间限制内完成的最大值。然而，即使在那个较低的阈值下，我也能获得 的分数。 15.265633 ，足够好 second place .

我进一步尝试将这种混合 KK/HS 方法合并到 CKK 树搜索中，基本上是通过使用 HS 作为一种非常积极且昂贵的修剪策略。在普通的 CKK 中，我无法找到与 KK/HS 方法相匹配的切换阈值。然而，使用 CKK 和 HS(阈值为 25)的 ILDS(见下文)搜索策略进行修剪，我能够比之前的分数产生非常小的增益，最高为 15.272802 .在这种情况下，CKK+ILDS 将优于普通 CKK，这可能不足为奇，因为根据设计，它会为 HS 阶段提供更大多样性的输入。

编辑 #1 ——
我尝试了对基本 CKK 算法的两项进一步改进:

“改进的有限差异搜索”(ILDS) [Korf96] 这是搜索树中路径的自然 DFS 排序的替代方法。它倾向于比常规深度优先搜索更早地探索更多不同的解决方案。

“加速 2-Way Number Partitioning” [Cerq12] 这将 CKK 中的修剪标准之一从叶节点的 4 级内的节点推广到叶节点上方 5、6 和 7 级内的节点。

在我的测试案例中，这两种改进通常比原始 CKK 提供了明显的好处，即减少了探索的节点数量(在后者的情况下)和更快地找到更好的解决方案(在前者的情况下)。然而，在 SPOJ 问题结构的范围内，这些都不足以提高我的分数。

鉴于这个 SPOJ 问题的特殊性质(即:5 秒的时间限制和只有一个特定的未公开的问题实例)，很难就什么可以真正提高分数提供建议*。例如，我们是否应该继续追求替代搜索排序策略(例如:Wheeler Ruml 的许多论文 listed here)？或者我们应该尝试将某种形式的局部改进启发式方法结合到 CKK 找到的解决方案中以帮助修剪？或者也许我们应该完全放弃基于 CKK 的方法并尝试使用动态编程方法？ PTAS怎么样？在不了解 SPOJ 问题中使用的实例的具体形状的情况下，很难猜测哪种方法会产生最大的好处。每个实例都有其优点和缺点，具体取决于给定实例的特定属性。

* 除了简单地更快地运行相同的东西之外，例如，通过用 C++ 而不是 Python 实现。

引用

[Cerq12] Cerquides、Jesús 和 Pedro Meseguer。 “加速2路号码分区。”爱奇艺。 2012, doi: 10.3233/978-1-61499-098-7-223

[HS74] 霍洛维茨、埃利斯和 Sartaj Sahni。 “ Computing partitions with applications to the knapsack problem. ” ACM 杂志 (JACM) 21.2 (1974):277-292。

[Korf88] Korf, Richard E. (1998), " A complete anytime algorithm for number partitioning ", 人工智能 106 (2): 181–203, doi: 10.1016/S0004-3702(98)00086-1 ,

[Korf96] Korf, Richard E.“ Improved limited discrepancy search。” AAAI/IAAI，卷。 1. 1996 年。

[Mert99] Mertens, Stephan (1999)，用于平衡数划分的完整时间算法，arXiv: cs/9903011