0

最小コスト最大フロー アルゴリズムではどのようなコスト関数を使用できますか?

次のようなコスト関数を持つことは可能ですか?

  • エッジのフローが [1, X] の間の場合、コスト = FixedCost + C1 + フロー * cost_per_flow[C1]
  • エッジのフローが [X + 1, Y] の間の場合、コスト = FixedCost + C2 + フロー * cost_per_flow[C2]
  • 等

これは何らかの形でアルゴリズムを変更しますか?

4

2 に答える 2

1

最小コスト最大フローアルゴリズムは、特定の種類の線形計画法の単なるソルバーです。

線形計画法を効率的に解けるのは凸性です。この場合、2つの実行可能なフローFとGがある場合、[0、1]のすべてのtに対して、フローtF +（1-t）Gは実行可能であり、コストがかかります（ tF +（1-t）G）≤tコスト（F）+（1-t）コスト（G）。あなたの目的のために、これは基本的に[1、X]のFixedCostが0、C1≤C2、[X + 1、Y]のFixedCostが（C1-C2）X≤0であることを意味します。これは次のようになります。

6|        .
5|       .
4|      .
3|     .
2|   .
1| .
0.----------
 0 1   X

おそらく、[1、X]> 0のFixedCostが重要ですが、これにより問題がNP困難になります。グラフのシュタイナー木からの削減は、各エッジの容量を無限にし、最初のユニットのシュタイナー木問題で指定された重みとその後の0のコストをかけることです。k-1シュタイナーターミナルの1つを容量k-1のソースにし、他のターミナルを容量1のシンクにします。k-1ユニットの最も安いフローを要求します。

于 2012-07-10T12:01:23.177 に答える
1

固定費を合計して、方程式から削除できます。次に、各エッジを適切に計算されたコストを持つ 2 つのエッジに分割します。

于 2012-07-10T10:52:50.107 に答える