December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
260
■
8
章 ネットワークフローアルゴリズム
8.2.3
分析
フォード
-
ファルカーソン法
が必ず停止するのは、流れているユニットの数が非負
整数であるからだ（
Ford-Fulkerson, 1962
）。
深さ優先探索
を用いた
フォード
-
ファ
ルカーソン法
の性能は、
O(E*mf)
となり、これは最大フローの最終値
mf
に基づく。
一見したところ、
1
回の反復ごとに、
1
つのユニットだけが増加道に加えられ、超巨
大容量のネットワークでは、とてつもない回数の反復が必要に見える。しかし、驚
くべきことに、実行時間は問題のサイズ（すなわち、節点または辺の個数）ではなく
て、辺の容量に依存する。
（
エドモンズ
-
カープ法
という名で知られる）
幅優先探索
を用いると性能は
O(V*E
2
)
となる。
幅優先探索
は、最短増加道を
O(V
＋
E)
で見つけるが、これは、連結フロー
ネットワークグラフにおいては節点の個数が辺の個数よりも少ないことから、実際
には
O(E)
となる。コルメンらは、フローの増加回数が
O(V*E)
のオーダーであり、
エドモンズ
-
カープ法
が
O(V*E
2
)
性能を持つという最終結果を証明した（
Cormen
et al., 2009
）。
エドモンズ
-
カープ法
は
幅優先探索
を用い、すべての可能な経路を長
さ順に調べるので、深さ優先のようにシンクへの「競争」による無駄な作業をしない
分だけ、
フォード
-
ファルカーソン法
を上回ることがままある。
8.2.4
最適化
フローネットワーク問題の典型的な実装では情報を配列に貯える。本章では、そ
うせずに、 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.