1

ナップザックの崩壊問題は、通常のナップザック問題の一般化であり、ナップザックの容量は含まれるアイテムの数の非増加関数です。

アイテムの数ではなく、選択したアイテムに応じてナップザックの容量が変化するバリアント (つまり、ドメインはアイテムのパワーセット) について何か (名前、文献、アルゴリズムなど) を知っている人はいますか?

4

1 に答える 1

0

「容量」の一般的な値については、セット要素に対して何らかの列挙を行う必要があると思います。私の理解が正しければ、サブセットが実行可能かどうか (その要素の重みの合計がその容量よりも小さいかどうか) を示す任意のブール値に多かれ少なかれ対応します。

ナップザック問題の「容量」は、制約の右側に現れるものです。つまり、

sum p_i x_i <= C

古典的なナップザックと

sum p_i x_i <= C (sum x_i)

崩壊するナップザックの中で。

これらは線形制約であるため、ある程度予測可能な方法で動作し、問題を解決するためにすべての可能な組み合わせ (べき乗セットの要素) を調べることを回避します。

パワーセットの各要素に任意の容量値がある場合C_J、容量はベクトルの予測可能な関数ではないxため、調査する必要があるリストからサブセットを削除する唯一の方法Jは、その値 ( sum_J a_i x_i) がすでに実行可能であることがわかっているサブセットの 1 つの値よりも低い(容量からの情報はまったくありません)。

これは特に、これを整数プログラムでモデル化する方法がないことを意味します。これは、それぞれに少なくとも 1 つの制約が必要になるためですC_J(実行可能なサブセットごとにコストを計算するだけでより効率的になります)。

列挙アルゴリズムを使用して、検索ツリーをできるだけ削減しようとします。

増加しない値で項目を並べてみましょうa_0 >= a_1 >= ... >= a_n。

カーディナリティを減らすことで、すべての可能なサブセットを調べることができます。これは、いくつかの基数 について、基数kが最大でも可能な最良のサブセットkの値がM_k = sum_{i=0}^k a_iであることを知っているためです。そのため、すべてのサブセットを調べる前に検索を停止することができます (カットする別の方法は考えられません)。検索ツリー)。

アルゴリズムは次のようになります。

M := 0とから始めk=nます。

繰り返す：

  • kその値Aがよりも優れている場合、カーディナリティで最適なサブセットを見つけるM
  • M := max (A, M): これまでに見つかった最良のサブセットの値
  • if M >= M_{k-1}, stop: 最適なものを見つけました
  • そうしないとk := k-1

カーディナリティ の最適なサブセットを検索するkには、次の順序を使用できますa_i。

  • から開始し、カーディナリティのサブセットを持つサブセットを{0, ..., k}再帰的に調べます。{0} U J'J'k-1{1, ..., n}
  • 次に、カーディナリティのサブセットなどを{1} U J'持つフォームのすべてのサブセットを調べます。J'k-1{2, ..., n}

実行可能なサブセットが見つかったらすぐに、bound を更新しMます。

これもまた、 をk含まないカーディナリティのサブセットがa_0, ..., a_iによって境界付けられているためa_{i+1} + ... + a_{i+k+1}であり、これが現在の境界より低くなるとすぐに停止できますM。

注: 容量に関する仮説は想定していませんC_J。容量が集合論の意味で増加しているかどうか、つまり、含意Iに含まれているかどうかを知ることは、確かに興味深いことです。JC_I <= C_J

于 2013-10-10T19:49:16.980 に答える