3

有一个包含 N 个整数的集合 S，每个整数的值 1<=X<=10^6。问题是将集合 S 划分为 k 个分区。分区的值是其中存在的元素的总和。分区是以这样的方式完成的，集合 S 的总值在 k 个分区中公平分布。还需要定义公平的数学含义（例如，目标可以是最小化分区值与集合 S 的平均值的标准偏差（即 sum(S)/k)）

例如 S = {10, 15, 12, 13, 30, 5}, k=3

一个好的分区是 {30}, {10, 15}, {12, 13, 5}

一个坏的分区是 {30, 5}, {10, 15}, {12, 13}

第一个问题是在数学上表达一个分区优于另一个分区的条件。第二个问题是如何解决问题。问题是NP-Hard。有什么启发式方法吗？

在我试图解决 N <= (k*logX)^2 的问题中，K 从 2 到 7 不等。

==================================================== =================================

基于其他相关的 SO 问题，评估分布有两个合理的函数：

a) 最小化具有最大值的分区的值。

再想一想，这不是一个好的指标。考虑，一组 {100, 40, 40} 被划分为三个子集。该指标不区分以下两种分布，即使其中一种明显优于另一种。

分布 1：{100}、{40}、{40} 和分布 2：{100}、{40、40}、{}

b) 最小化给定分区中任意两个值之差的最大值，即最小化 max|AB| 对于任何 A、B

4

3 回答 3

6

我认为一个好的指标是：

let the result set be s1,s2,...,sk
let MAX be max{sum(si) for each i}
f({s1,...,sk}) = Sigma(MAX-sum(si)) for each i)

好处：完美的分布将始终产生 0！
缺点：如果没有完美的解决方案，最好的结果不会产生 0。

这个问题的贪婪启发式将是：

sorted<-sort(S) (let's say sorted[0] is the highest)
s1=s2=...=sk= {}
for each x in sorted:
   s <- find_min() (*)
   s.add(x)

其中 find_min() 产生 s，使得每个 si 的 sum(s) <= sum(si)。

这个解决方案将产生 f（上面定义的度量）使得f(sol) <= (k-1)*max{S}（从这里它是这个界限的证明）：


声明：对于每个子集，通过归纳MAX- sum(s) <= max{S}
证明：在每一步，声明对于临时解决方案都是正确的。
在每一步中，让 MAX 在迭代开始时（加法之前）为 max{sum(si)}！

base: the set of subsets at start is {},{},.. MAX=sum(si)=0 for each si. 
step: assume the assumption is true for iteration i, we'll show it is also true for iteration i+1:
let s be the set that x was added to, then MAX-sum(s) <= max{S} (induction assumption).
if sum(s) + x <= MAX: we are done, MAX was not changed.
else: we sorted the elements at start, so x <= max{S}, and thus if s was chosen
   (sum(si) >= sum(s) for each si) and sum(s) + x > MAX then: for each si, sum(si) + x >=
   sum(s) + x, so sum(s)+x - sum(si) <= x <= max{S}. since sum(s)+x will be the MAX next 
   iteration, we are done.

因为对于每个集合MAX-sum(si) <= max{S}（显然，对于最大集合MAX-sum(si)=0），总体而言 Sigma(MAX-sum(si)) <= (k-1)*max{S}，正如所承诺的那样。

编辑：
我有一些空闲时间，所以我编写了我和@Akhil 建议的启发式方法，并且这两个指标首先，两个结果都是决定性的（根据Wilcoxon的 pair-t 测试），但更好的是由您选择的指标定义，令人惊讶的是，试图最小化 f() (@Akhil`s) 的算法在相同的 f 上得分较低，但在第二个指标上得分更高。 @Akhil 的指标图

@Amit 的指标图

于 2011-06-26T21:18:38.420 回答
1

一种启发式方法是将较大的权重尽可能均匀地分布在袋子之间，留下足够小的权重，以便您现在留下一个具有大量自由度的子问题。如有必要，重复到子子问题。这种启发式假设您的分布不是太几何，例如 {1000} and {100, 10, 1}，并稍微假设您的惩罚函数将惩罚零赋值或非常大的异常值。

例如：

distributeFairly(numbers, bins):
    distributeFairlySubproblem(numbers, bins):
        n = len(numbers)
        numElementsToDefer = min(-n//3,20*k)  # modify as appropriate, e.g. to avoid len(toPlace)<len(toDefer)

        toDefer = numbers[-numElementsToDefer:]
        toPlace = numbers[:-numElementsToDefer]

        newBins = shoveThemIn(toPlace, copy(bins))
        return distributeFairlySubproblem(toDefer, newBins)

    initialGuess = distributeFairlySubproblem(sorted(numbers,reverse=True), [[]]*k)
    return anneal(initialGuess)
于 2011-06-23T14:34:47.650 回答
1

让度量最小化 max(sum(si) - sum(sj))，其中 si 和 sj 是集合 S 的结果分区中的任意两个子集。

假设我们有一个分布 D，我们需要在分布 D 中包含另一个元素 x。将其添加到子集 s 中，以使上述度量最小化。

无法证明任何界限，但直觉说它会很好地逼近最优值？有谁擅长证明界限？

于 2011-06-27T02:23:58.813 回答