2

問題

N 個の実数 A = {x_1, x_2, ..., x_N}のセットがあるとします。

目標は、このセットをA_1、A_2、...、A_Lサブセットに分割し、 sum( A_i ) <= Tの制限とこの項を最小化することです。

コスト := sum( abs( sum(A_i) - T ) )

ここで、sum(A_i)はA_iの数値の合計を表し、Tは特定のしきい値です。

非進化的最適アルゴリズムを探しています。

更新: x_iは正の実数であり、T ( 0 < x_i <= T ) 以下です。

更新 2:コスト関数が修正されました。

がんばれ、貪欲アルゴリズム！

簡単なアイデアは、貪欲なアプローチを使用して問題を解決することです。擬似コードは次のとおりです。

 1. create subset A_1 and set i=1.
 2. remove the largest number x from A.
 3. If sum(A_i) + x <= T
  * put x into A_i
 4. Else
  * create a new subset A_i+1, 
  * put x into A_i+1 
  * set i=i+1
 5. If A is non-empty
  * goto step 2.
 6. Else
  * return all created A_i s

問題は、このソリューションが最適ではないことです。たとえば、最初のサブセットA_1に 2 つの最大数x1とx2を入れないほうがよい場合があります。これは、そのセットに追加して作成できる * x_i * が他にないためです。その合計はTに近くなります。一方、x1とx2を別々のセットに入れておけば、より良い解 ( Cost値が小さい解) を見つけることができます。

可能な解決策

最適な解を見つけることができるバックトラッキングアルゴリズムを使用することも考えましたが、この問題の複雑さは高いと思います。

ウィキペディアでビン パッキング問題(NP-hard [ため息...] ) やカッティング ストックの問題などの記事を読んだことがありますが、どうやら私の問題はこの標準的な問題と非常によく似ていますが、どれが私のケースに一致するかわかりません。

4

1 に答える 1

2

更新: 修正されたコスト関数では、A_i <= T として sum(A_i) - T は常に負になることに注意してください。

sum(abs(sum(A_i)-T)) = sum(T-sum(A_i)) = L*T-sum(A)

sum(A) は定数なので、タスクは使用されるビンの数を最小限に抑えることです。したがって、あなたの問題は古典的なビンパッキングと同等です。

これを解決するには、このようなビン パッキング ソルバーを使用できます。

于 2012-06-02T13:19:59.280 に答える