最大流量と最大流量の違いは何ですか？

Question

最大流量と最大流量の違いは何ですか。私はフォードFulkersonアルゴリズムに取り組んでいる間、私はこれらの言葉を読んでいます、そして彼らは非常に混乱しています。私はインターネットで試しましたが、合理的な答えを得ることができませんでした。私は最大の流れがネットワーク内のソースからシンクされるべき最大量のフローを意味するので、最大の流れは非常に明確ですが、正確に最大のフローです。

可能であれば、LAYMAN用語で答えてください。

ありがとう。

Answer 1

短回答：

山の頂上について考えてください、 それらのそれぞれは最大の解です。 それらより高い近くの場所はありません、 しかし、エベレスト山の上部だけが最大の高さを持っています それゆえ最大解。

長い回答：

幾何学的な用語で説明しましょう： 飛行機について考えてください（例えば、紙の大きな平和です）。 平面上の各点は問題の可能な解決策です。 各点の高さは、その点に対応する解の品質です。 最適化において、我々は最適な解決策、すなわち平面上の最も高い点を見つけたい。 最適な解決策を見つけるための1つの考えは、平面内の可能な解決策から始めることです。 少しずつそれを改善する： その近くにある点から1つずつ移動するたびに移動します。 これは局所検索アルゴリズムと呼ばれます。 このプロセスは、その近くのすべての点よりも高い点に達すると停止します。 そのような点は局所最適値と呼ばれる。 それに対応する解決策は最大の解決策に近いどんな解決策に移動することによって、解の品質を高めることはできません。 ただし、最大の解は最適な解決策である必要はありません。 その隣人と比較して最適です。

満足している場合は一般的な条件がある 世界的に最適化されていない平面上に局所的な最適化はありません。 そのような状況では、最適な解決策を見つけるために局所検索アルゴリズムを使用することができます。 そのような条件の1つは、ソリューションの平面が凸である場合です。 2点ごとに直感的に、私たちはそれらを接続するすべてのポイントを持っています 溶液空間でも それらのそれぞれの品質はから決定することができます 2つのエンドポイントへのポイントの相対距離 2つのエンドポイントの品質。 凸スペースを介した最適化は、凸状最適化

で検討されています。

今、最大フローの問題に戻ることができます。 グラフを入力として固定します。 流れの容量と保存を満たす各フローについて考える ポイントとしての要件 これらの有効なフローを呼び出します。 最大の流れを見つけたいです。 2つの点は互いに近くにあります。 ソースからシンクへの経路を通る流れ。

すべてのエッジの流れがゼロの流れから始めることができます （これは有効なフローです）。 各ステップで、更新された残り容量グラフのソースからシンクへのパスがあります（各エッジの重みは使用されていない容量の量です）。 どういうわけか（例えばBFSを使用）およびこれを追加することによって流れを増加させる。 これにより、ローカル検索アルゴリズムが得られます。 問題は解決策のスペースが凸でないことです。 私達は流れに終わるかもしれません もっと増やすことはできませんが、最大の流れではありません。

私たちは何ができる？ 1つの考えは、解決策のスペースを凸のものに変更することです。 直感のために飛行機の上の星について考える。 星の中の点は凸スペースを作らない しかし、私たちは解決策のスペースのより多くの点を含めることによってそれを凸スペースに変えることができます そしてそれをペンタゴンに変える

これは本質的に私たちが既存の流れを考慮して グラフの元のエッジ 新しいエッジとして（残差エッジと呼ばれる） それらの上の流れが元のエッジ上の既存の流れを減らすことに対応します。 これにより、スペースの凸面が凸のため、私たちの地域検索アルゴリズムは解決策に立ち往生していない これは地域的に最適であるがグローバルに最適ではない。