algorithm - 调度：将一组整数划分为 K 个子集

Question

我正在研究任务调度程序并面临以下问题（处理器之间的任务分配）：

有一组 N 个整数。如何将它们划分为 K 个不相交的子集，它们的总和相差很小？

我正在寻找一种简单的启发式算法，它对于 N=100-500 和 K=10-20 具有合理的计算复杂度。不需要最优解（即总和的最小可能差异），粗略的近似就足够了。

提前致谢。

score 2 · Accepted Answer

构造启发式First Fit或First Fit Decreasing效果很好。

对于 First fit Decreasing，首先按尺寸递减对零件进行排序（在下面的示例中：A、B、C、D），然后将它们一个一个地放在剩余的最佳位置（X 或 Y）中。在下面的示例中，忽略 2 个维度中的 1 个（例如，忽略 CPU）。

CloudBalance 上的首次拟合减少

score 1 · Accepted Answer

这是您正在寻找的论文，我认为：

多路数分区
Richard E. Korf 加利福尼亚大学洛杉矶分校
计算机科学系 Los Angeles, CA 90095 korf@cs.ucla.edu

score 1 · Accepted Answer

即使划分为 2 也是 NP 完全的。尽管您可以使用伪多项式时间算法。在 Wikipedia上提到，假设您有数字总和的上限。

score 0 · Accepted Answer

0

事实证明，简单的贪心算法在这种情况下效果很好。

于 2012-08-19T16:56:17.107 回答

4 回答 4