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 回答