3

それぞれ値が 1<=X<=10^6 の N 個の整数を含むセット S があります。問題は、セット 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} です。

最初の質問は、あるパーティションが他のパーティションよりも優れている条件を数学的に表現することです。2番目の質問は、問題を解決する方法です。問題は NP-Hard です。ヒューリスティックはありますか？

N <= (k*logX)^2 を解決しようとしている問題で、K は 2 から 7 まで変化します。

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

他の関連する SO の質問に基づいて、分布を評価するための 2 つの合理的な関数があります。

a) 最大値を持つパーティションの値を最小化します。

よく考えてみると、これは良い指標ではありません。セット {100, 40, 40} を 3 つのサブセットに分割するとします。このメトリックは、次の 2 つの分布を区別しませんが、一方が他方よりも明らかに優れています。

分布 1: {100}、{40}、{40} および分布 2: {100}、{40、40}、{}

b) 特定のパーティション内の任意の 2 つの値の差の最大値を最小化します。つまり、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() は、各 si について sum(s) <= sum(si) となるような s を生成します。

このソリューションは、次のような f (上記で定義されたメトリック) を生成しますf(sol) <= (k-1)*max{S}(ここから、この境界の証明になります)。


claim : 各サブセット 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のペア t テストによると) が、どちらが優れているか選択したメトリックによって定義されますが、驚くべきことに、f() (@Akhil`s) を最小化しようとしたアルゴリズムは、この同じ f ではスコアが低くなりましたが、2 番目のメトリックではスコアが高くなりました。 @Akhil のメトリクス グラフ

@Amit のメトリクス グラフ

于 2011-06-26T21:18:38.420 に答える
1

ヒューリスティックの 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 の結果のパーティション内の任意の 2 つのサブセットです。

分布 D があり、別の要素 x を分布 D に含める必要があるとします。上記のメトリックが最小化されるように、それをサブセット s に追加します。

限界を証明することはできませんでしたが、直観によれば、最適な近似値を適切に近似できますか? 境界を証明するのが得意な人はいますか?

于 2011-06-27T02:23:58.813 に答える