0

浮動小数点値のセットを、サイズが最大で 1 要素だけ異なる 2 つのセットに分割したいと考えています。さらに、2 つのセット間の値の合計の差は最小限に抑える必要があります。必要に応じて、要素の数が奇数で合計が等しくない場合は、小さい方のセットの合計が大きくなる必要があります。

それが最適な解決策ですが、サブセットサイズの制約に関する正確な解決策だけが本当に必要です。合計の差は厳密に最小である必要はありませんが、それに近づく必要があります。また、小さい方のセット (ある場合) の合計が大きい方がよいと思います。

これはパーティションの問題に関連している可能性がありますが、まったく同じではなく、厳密でもありません。

私の現在のアルゴリズムは次のとおりですが、それを改善する方法があるかどうかは疑問です。

arbitrarily divide the set into two sets of the same size (or 1 element size difference)
do
  diffOfSums := sum1 - sum2
  foundBetter := false
  betterDiff := 0.0

  foreach pair of elements from set1 and set2 do
    if |diffOfSums - 2 * betterDiff| > |diffOfSums - 2 * (value1 - value2)| then
      foundBetter := true
      betterDiff := value1 - value2
    endif
  done

  if foundBetter then swap the found elements
while foundBetter

このアプローチに関する私の問題は、実際の複雑さと、それを改善できるかどうかがわからないことです。それは確かに、より大きな合計を持つ小さなサブセットを残すという要件を満たしていません。

私が達成したいことをたまたま実行する既存のアルゴリズムはありますか? そうでない場合は、アルゴリズムを改善するか、それがすでに問題に適している可能性があることを理解する方法を提案できますか?

4

2 に答える 2

3

分割問題が多項式時間でこの問題に帰着することを証明するのは簡単です。

ある配列 A のパーティションを解決したいとしますが、問題を解決する方法しか知りません。配列の長さを 2 倍にして、ゼロで埋めるだけです。アルゴリズムで解決できれば、パーティションの問題は解決したことになります。これにより、問題が NP 困難であることが証明されます。

しかし、float の精度を制限しない限り、この問題を分割に減らすことはできません (つまり、NP 完全ではありません)。その場合、同じアルゴリズムが両方を解決します。

一般的な場合、最善の方法はバックトラックです。

于 2015-08-22T17:41:14.693 に答える
2

私の提案は、値をソートし、値の各ペア (v1、v2)、(v3、v4) を検討して、各ペアから 1 つの要素を 1 つのパーティションに入れることです。

アイデアは、値を各セットに交互に入れることです。

s1 = {v1, v4, v5, v8, . . . }
s2 = {v2, v3, v6, v7, . . . }

要素の数が奇数の場合は、条件に最も適したセットに最後の値を入れます。

ミニマルの定義が緩いので、完全な検索は不要です。上記は、値の多くの分布に対して非常にうまく機能するはずです。

于 2015-08-22T15:47:04.773 に答える