1

たとえば、doublesのリストがいくつかあり、固定サイズの複数の「バケット」で配布する必要があります（バケットサイズもdouble）。2つの追加の制約があります。

  • 特定のリストの値は、特定の（事前に指定された）バケットにのみ送信できます。

    bucket1 <-\
           |--- list1
          /
         /
bucket2 <--\
bucket3 <---- list2
bucket4 <--/

bucket5 <--- list3

  • 結果として得られる分布は、可能な限り均一である必要があります（たとえば、すべてのバケットの負荷率が0.5）。

このような問題の具体例：複数の電源ユニット（「バケット」）と複数のランプボードがある場合を想像してみてください。各供給ユニットは1つまたは複数のボードに接続され、各供給ユニットの容量は異なり、ランプはさまざまな量のエネルギーを消費します。一部のボードが複数の電源ユニットに接続されている場合は、一部のランプを最初の電源に、一部を2番目の電源に「割り当てる」ことができます。

ブルートフォースでこれを行うと、多数の要素に対してすぐに実行不可能になります。

効率的なアプローチはありますか？

編集：私は次のアプローチを考案しました-それは必要な結果にかなり早く収束するようです。アイデアは次のとおりです。

  • まず、リストごとに、最小負荷のバケットヒューリスティックを使用して、許可されたバケットにアイテムを配布します。
  • 次に、次のことを行います。
    • リストごとに：
      • リストに対応するアイテムをバケットから削除します
      • 同じ最小負荷のヒューリスティックを使用して、それらを再度配布します
      • 最大負荷のバケットサイズと最小負荷のバケットサイズの比率を計算します（許可されたバケットの場合）
    • 比率が一定未満の場合（私が取った1.02）、または通過したステップが多すぎる場合は、ループを終了します。

一般的な考え方は、分布が十分にフラットになるまでバケットを「スムーズ」にすることです。これは通常、必要な目標に到達したことを意味します。

それは良いアルゴリズムですか？

4

2 に答える 2

2

少なくとも特定の負荷率まですべてのバケットを満たすソリューションが必要な、追加の制約 (特定のリストは特定のバケットにしか移動できない) を伴うビン パッキングの問題またはナップザックの問題のように思えます。「効率的」と言えば、あなたが説明することはNP困難であるべきだと思います（NP問題からあなたの特定の問題への削減についてまだ考える時間がなかったので「すべき」ですが、私はかなり確信していますここに一つ）。

試してみること: 最初に制約の問題を解決し、どの行がどのバケットに入ることができるかを判断してから、貪欲にバケットを埋めます。制約が難しい場合は、バックトラックを行うことができます。

于 2012-11-04T15:15:20.597 に答える
1

短い答え：いいえ。NP完全です。詳細については、次のウィキペディアを参照してください。

http://en.wikipedia.org/wiki/Bin_packing_problem

http://en.wikipedia.org/wiki/Knapsack_problem

于 2012-11-04T15:15:03.157 に答える