フォードファルカーソン法をRubyで実装 - yasuhisa's blog
グラフに対する基本的な問題として 最小全域木 最短路問題 最大フロー の3つがあると思う。で、最小全域木は離散最適の課題としてPrim法を使って解いてみたし、最短路問題はベルマンフォードのアルゴリズムをRubyとC++で解いてみた。となったら、最大フローを実装しないわけにはいかないな、ということでフォードファルカーソン法を実装してみました。上の3つの問題では一番ややこしかった気がする。というわけでコードと実行結果。 繰り返しの中で残余ネットワークを更新していって、残余ネットワークにおいて始点から終点へのパスが存在するかを幅優先探索を使って探索していくという流れ。 # -*- coding: utf-8 -*- require "pp" class DirectedGraph attr_reader :nodes attr_reader :weights attr_reader :edges
Network Flow
ネットワーク 定義 G：有向グラフ V：点の集合 E(G)={e=(u,v)|u,v∈V}：Gにおける辺の集合 cap(e)：各辺eの容量 s：湧出点、入口, t：流入点、出口 (s,t∈V) N=(G,cap,s,t)：ネットワーク f:E(G)→R+（辺集合E(G)から非負実数集合への関数） δ-(v)：vを終点とするNの辺の集合 δ+(v)：vを始点とするNの辺の集合 ただし、fは次の二つを満たす
点と線の部屋
平成１６年２月２３日 第一部 第五十四章 「アフィン平面と射影平面」 新規公開 平成１６年１月４日 第一部 第五十二章 第三節 「4次のアフィン平面」 追加 第一部 第五十三章 「麻雀の組合せの問題（ラテン方陣とアフィン平面）」 新規公開 第二部 第三十三章 「有限体クラスの拡張」 新規公開 平成１５年２月１１日 第二部 第三十二章 「有限体クラス」 新規公開 平成１５年２月３日 第一部 第五十二章 「体とアフィン平面」 新規公開 平成１５年１月１３日 第一部 第三十一章 第三節を不備訂正のため大幅に変更し、また一部を第四節に分離独立させた 平成１４年１１月３日 第一部 第五十一章 「再構成問題 その１」 新規公開 平成１４年７月１５日 第一部 第五十章 「最短経路問題」 新規公開 平成１４年５月１３日 第一部 第四十九章 「弦グラフ その１」 新規公開 平成１４年２月４日
Graph Classes and Algorithms
[概要] 計算機で扱う問題は，多くの場合グラフ上の問題として定式化できる． 計算量の理論により，これまで多くの問題が``手に負えない''ことが示されてきた． 一方でこうした問題に対する現実的なアプローチがいくつか提案されてきた． 本稿ではグラフに制限を加えるアプローチについて解説する．DNA の切片間の関係などは， モデル化すると特別なグラフになる．こうしたグラフ上では， これまで手に負えないとされてきた問題が効率良く解けることがある． 本稿では，代表的なグラフクラスと，関連したアルゴリズムの最近の研究動向を解説する． [キーワード] アルゴリズム，グラフクラス，計算の複雑さ，理想グラフ [お断り] このページは，電子情報通信学会に掲載予定の同名の解説論文を加筆修正したものです． せっかく書いたので，より広く公開して，かつ，ときどきは更新して行こうかと思っています． リンクも少しずつ充実さ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
