2

A=(a_1,a_2,...,a_m) と B=(b_1,b_2,...,a_n) の 2 つのセットがあるとします (同じサイズである必要はありません)。関数 F は、集合 A から集合 B までの各リンクに重みを割り当てます: F:A*B->R。したがって、たとえば、F(a_1,b_1)=2 は、a_1 と b_1 の間のリンクの重みが 2 であることを意味します。問題は、集合 A の要素を集合 B の要素に接続して、これらの制約を満たすリンクの重み:

  • セット A の要素は、セット B の 1 つの要素と正確に一致する必要があります。
  • セット B の要素は、0 個以上の一致 (0,1,2...) を持つことができますが、B の要素には重み C_i の合計に対する制約が存在します。つまり、a_1 を b_1 に接続することを選択した場合、および a_2 から b_1 の場合、重みの合計 F(a_1,b_1)+F(a_2,b_1) は C_1 以下でなければなりません。この制約は、B のすべての要素に対して存在します。

私はいくつかのアイデアを探し、代入問題とハンガリーのアルゴリズムを調べました。追加のことは、これらのどれもが私が持っている2番目の制約を考慮していないということです. これを解決する方法について何かアイデアはありますか？

ありがとう

4

1 に答える 1

4

NP困難です。

サブセット和インスタンス{x1 、x 2、...、x n }を取ります。ここで、xi >0および数kです。左の頂点が{ a1、...、a n }、右の頂点が{b 1、b 2 }である2部グラフを作成し、次のようにします。

F（a i、b 1）= x i

F（a i、b 2）= 0

C 1 = k

C 2 = 0

したがって、 aiをb1に接続して数xiを取り、 b2に接続してそのままにしておくことができます。明らかに、サブセット和インスタンスに解がある場合は、重みkが一致します。

于 2012-06-13T21:28:31.297 に答える