最大流問題とは (サイダイリュウモンダイとは) [単語記事] - ニコニコ大百科

最大流問題単語 サイダイリュウモンダイ 1.1千文字の記事 14 0pt ほめる 掲示板へ 記事編集 概要フロー増加法例最大流最小カット定理関連項目掲示板最大流問題とは、最大の流量を求める問題である。線型計画問題のひとつ。 概要 例えば、ある地点から他の地点に物資を送るとする。このとき、いくつかの地点を経由し、分岐や合流をしながら物資が送られるとする。送られる過程で、それぞれの地点からそれぞれの地点に一度に送ることのできる量の最大値が決まっている際、全体で一度に送れる量の最大値はいくらなのか。これを考えるのが最大流問題である。最大流問題では、送られる量をフロー、出発点をソース、終着点をシンクという。 フロー増加法 最大流問題を解くアルゴリズムのひとつ。 フローをすべて0にする。 残余ネットワーク(後述)を求める。 残余ネットワークにソースからシンクへつながる路がなければ、6へ飛ぶ。あれば、

[totttte]

おお