コストの割り当て問題

Question

私は問題に遭遇しています。どこからでも見つけることができないので、私は絶望的にstackoverflowに目を向けています。

この問題は、np-hardがnp-completenessを証明していれば、それがnp-hardか多項式かどうかを知りたければ、アルゴリズムを与えます。

問題は次のとおりです。

n個のモジュールの製品が存在します。いくつかのコスト（c_ij、i：モジュール番号、j：会社番号）で各モジュールを構築できる2つの企業があります。モジュールaとモジュールbが異なる会社によって構築されている場合は、追加コスト（p_ab）もあります。モジュールaおよびbは連続している必要はなく、同じ追加コストがaおよびcにも適用される。期待されているように、問題は、総コストが最小になるように、モジュールを企業に割り当てることを求めています。

Answer 1

これはmin cut問題にまで減らすことができます。これは、max flowアルゴリズムで検出できます。 ネットワークとは何ですか？ モジュールはグラフの頂点になり、2つの新しい頂点のソースとシンクを追加します。 ソースから、容量Ci1のすべてのモジュールiにエッジを追加します。同様に、各モジュールiから、容量Ci2でシンクするためにエッジを追加する。また、任意のモジュールiとjについて、容量pij でエッジを追加します（グラフの向きは2つのエッジ（ij）と（ji）になります）。 min cutの価値が問題の解決であることは容易に分かります（2番目の会社に割り当てられたソースと1番目の会社に残りのモジュールを含むカットの一部のモジュール）