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.
8.4
増加道についての考察
■
267
8.3.3
分析
問題帰着方式が効率的であるためには、問題インスタンスと計算された解双方の
間に効率的な対応付けが必要だ。二部マッチング問題
M
＝
(S, T, P)
は、グラフ
G
＝
(V, E)
に
n
＋
m
＋
k
ステップで変換できる。結果として得られるグラフは、
n
＋
m
＋
2
節点と
n
＋
m
＋
k
辺を持ち、サイズは、元の二部マッチング問題より定数分
大きいだけである。構築におけるこの重要な特性から二部マッチング問題に効率的
な解のあることが保証される。最大フローを
フォード
-
ファルカーソン法
で計算でき
れば、フローが
1
のネットワーク内の辺が、二部マッチング問題で計算した対に対
応する。辺の決定に
k
ステップ必要なので、
O(k)
の処理が二部マッチング問題の解
として「読み取る」ために余分に必要となる。
8.4
増加道についての考察
最大フロー問題は、本章の図8-1で論じた他の全問題の解の基盤となる。それぞ
れをフローネットワークで表すためのステップが必要であるが、その後で、フロー
のコストを最小化する問題に帰着できる。ネットワークの各辺
(u, v)
に対して、辺
(u, v)
上で
1
ユニットを輸送するのにかかるコスト
d(u, v)
を付随させれば、目標は、
フローネットワークのすべての辺について
∑
f(u, v)*d(u, v)
を最小化することとなる。
フォード
-
ファルカーソン法
では、ネットワーク上で最大
フローを増加できるような増加道を見つけることの重要性を強調した。探索処理を
修正して、コ
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.