これが状況です。市内の固定された場所に住んでいる番号 1、2...x の x 人の学生がいるとします。1 、 2 、 3 ...y の番号が付けられた y の試験センターがあり、それぞれの収容人数は「i-can-hold[y]」です。生徒 i から試験センター j までの距離は 'i-have-to-walk[i][j]' です。
総移動距離が最小になるようにするアルゴリズムを提案できますか? (つまり、各学生の試験センターからの距離の合計)
明らかに i-can-hold[1]+i-can-hold[2]+...+i-can-hold[y]>x
そのようなプログラムを作成して、試験を実施する手間を最小限に抑えることを考えています。googlemap の助けを借りて実用的な実装が可能です。
一般に、距離と容量に制約がない場合、これは最小コスト最大フローの問題です。
i-can-hold各都市は、コスト 0 の容量を持つシンクに接続されています。i-have-to-walkます。Ford–Fulkerson アルゴリズムを使用して最大フローを見つけることができますが、コストは考慮されません。より簡単な例でフローネットワークについて学ぶことは、それを学ぶのに役立つかもしれません.
コストを最小化するためのさまざまなアルゴリズムがあります。一つは「連続する最短経路」です。アイデアは、残差ネットワークでソースからシンクへの最小コスト パスを繰り返し見つけ、それ以上のパスが見つからなくなるまで、このパスに沿ってフローを追加することです。
例えば：
a) 各頂点にラベルが付けられたフロー ネットワーク (コスト、容量)。2 つのセンターの列に接続された 3 人の学生の列が含まれています。
b) 残留ネットワーク内の最短経路 (Bellman-Ford で検出可能) に沿って追加されたフロー。残差ネットワークは、使用可能な容量 (容量から各方向のフローを差し引いたもの) から作成されたグラフです。
c) 別のパスに沿って追加されたフロー。
d) 最適な流れ。既に追加されたフローを変更するパスに沿ってフローが追加されました。これが許されるのは、残りのネットワークがフローの反対方向に容量を持っているからです。
以下も参照してください。