8. gw_min_cost_flow.exe の使用法
- アルゴリズムの名称:Min Cost Flow
- 内容:ネットワークにて、その系の流量を最大にし、且つ、コストを最小にする経路を求める
【概要】
ネットワークにて、その系の流量を最大にし、且つ、コストを最小にする経路を求める
- gw_min_cost_flow_new.cpp は、gw_min_cost_flow.cpp を少し改善しました。
修正前は、エッジの値の表示としては、flow の値だけでしたが、修正後は、各エッジの側に、次の2つの情報を表示するようにした。
flow = 29 .... そのエッジを流れる流量
cost = 75 .... そのエッジに対するコスト
gw_min_cost_flow_new.exe を起動すると、25個 (5行5列) のノードを持ったグラフが自動的に生成されるので、メニューの "Graph-> Clear" を選ぶ。
以下の手順で、9個のノードを持つグラフを作成する。
1. 左下端の画面上で、クリックすると1つのノード「N0」が生成される。
2. さらに、右方向に順に2個のノード N1, N2 を追加する
3. 少し上方に、前と同様の手順で3個のノード N3, N4, N5 を追加する
4. その上方に、前と同様の手順で3個のノード N6, N7, N8 を追加する
- 9個のノードの上下左右を接続する。
・ノード「N0」をクリックして、選択状態にする
・マウスポインタを移動して、ノード「N1」をクリックすると、エッジ (N0 --> N1) が生成される
・同様にして、N1 --> N2, N3 --> N4, N4 --> N5, N6 --> N7, N7 --> N8 を作成する
・次に、縦方向の6個のエッジを作成する
N0 --> N3, N3 --> N6, N1 --> N4, N4 --> N7, N2 --> N5, N5 --> N8
- 上記の操作を完了すると、"9 nodes, 12 edges" のグラフが生成される。
グラフの各エッジには2つの情報が表示されている。例えば、"N7 --> N8" は次のようです。
・"N7 --> N8":
flow = 29 .... そのエッジを流れる流量
cost = 75 .... そのエッジに対するコスト
・"N5 --> N8":
flow = 23 .... そのエッジを流れる流量
cost = 37 .... そのエッジに対するコスト
「N0」がスタート・ノード "S" で、「N8」がターゲット・ノード "T" です。
ターゲット・ノード "T" に流入する流量は2つのエッジから流入する flow の和となります。
この系の最大流量 = 29 + 23 = 52
この系の総コストは、各エッジの (flow * cost) の和です。
- 例えば、エッジ「N3 --> N6」のコストを 53 --> 29 に減少させてみます。
すると、下図のように4つのエッジの流量が変化します。
"N3 --> N4": flow= 12 --> flow= 0
"N4 --> N7": flow= 29 --> flow= 17
"N3 --> N6": flow= 0 --> flow= 12
"N6 --> N7": flow= 0 --> flow= 12
即ち、2つの経路で次のように流量が変化しました。
経路:"N3 --> N4 --> N7" にて、flow= -12,
削減されたコスト 12*33 + 12*33 = 792
経路:"N3 --> N6 --> N7" にて、flow= +12
増加されたコスト 12*36 + 12*29 = 780
従って、上記の流量の変化によって 792 - 780 = 12 のコストが削減されました。