0

私は立ち往生している問題があり、どこから始めても見つからないので、どうしようもなくスタックオーバーフローに目を向けています。

この問題は、それが np-hard か多項式かを調べ、np-hard が np-completeness を証明する場合、そうでない場合はアルゴリズムを提供することを求めています。

問題は次のとおりです。

n 個のモジュールからなる製品が存在します。各モジュールを構築できる会社が 2 つありますが、費用はかかります (c_ij、i: モジュール番号、j: 会社番号)。モジュール a と b が別の会社によって構築されている場合は、追加コスト (p_ab) もかかります。モジュール a と b は連続している必要はありません。a と c にも同じ追加コストが適用されます。予想どおり、この問題は、総コストが最小になるように、企業へのモジュールの割り当てを見つけることを望んでいます。

何か案は ？

4

1 に答える 1

1

これは、任意の最大フロー アルゴリズムで見つけることができる最小カット問題に減らすことができます。では、ネットワークとは何ですか？モジュールはグラフの頂点になり、ソースとシンクの 2 つの新しい頂点も追加します。ソースから、容量 Ci1 のすべてのモジュール i にエッジを追加します。同様に、すべてのモジュール i からエッジからシンクに容量 Ci2 を追加します。また、任意のモジュール i および j に対して、容量 pij のエッジを追加します (グラフ指向であるため、2 つのエッジ (ij) および (ji) が存在します)。最小カットの値が問題の解決策であることは簡単にわかります (ソースを持つカットの一部のモジュールは 2 番目の会社に割り当てられ、残りのモジュールは最初の会社に割り当てられます)。

于 2010-11-29T01:16:31.653 に答える