倉庫間の移動品の移動距離を最小限に抑えるにはどうすればよいですか？

Question

第1日にアイテムの数量Q [i]を格納するN個の倉庫があります。第2日には、各倉庫内の数量Q '[i]に対する要件があります。基本的には、制約を満たすためにアイテムを倉庫間で移動する必要があります。倉庫間の距離は既知です。これを解決するアルゴリズムのクラスは何ですか？すべてのポインタ？目標は、移動する商品の移動距離を最小限に抑えることです。

Answer 1

これは、min-cost max-flowアルゴリズムで解決される古典的な問題です。 2つの余分な頂点、すなわちソースとシンクを追加して、グラフを補強します。ソースから元のグラフのすべての頂点まで、Q[i]に等しい容量とゼロコストのエッジを追加します。元のグラフの各頂点から、Q'[i]の容量とゼロコストのシンクにエッジを追加します。元のグラフの頂点間のエッジについては、容量を無限大に、コストを対応する倉庫間の距離に設定し、最小コストの最大フローを計算します。元のグラフの頂点間のフローによって、これらの2つの倉庫間で転送する商品の数がわかります。

いくつかのリンク：最小コスト最大フローについて

1. wikipedia article

2. 非常に良いpresentation（そこにあなたに似ているが同一ではない彼らが持っている問題）

3. がここにありますa great article非常に良い実装の詳細と