スピードランナースマートフォン用の表示で見る遥かへのスピードランナーシリコンバレーでAndroidアプリの開発してます。コンピュータービジョン・3D・アルゴリズム界隈にもたまに出現します。この広告は、90日以上更新していないブログに表示しています。グラフ理論PRMLの8.3節では、マルコフ確率場を応用した事例として画像のノイズ除去がでてきますが、PRMLで紹介されている「グラフカットアルゴリズム」を試すには最大流問題を解く必要があるのでアルゴリズムの勉強もかねて実装してみました。最大フロー問題または最大流問題とは、各枝に容量(capacity)と流量(flow)が設定された有効グラフにおいて、ある始点(ソース)から終点(シンク)へのフローで最大となるフローを求める問題です。この問題を解くアルゴリズムとしてフォード・ファルカーソンのアルゴリズムが一般的に良く知られていて、僕の持っているアルゴリズムC・新版—基礎・データ構造・整列・探索にも載っています。アルゴリズムCから引用すると、フォード・ファルカーソンのアルゴリズムは「辺の流量がすべてゼロである状態から開始し、ソースからシンクに向かう道で、飽和した前向きの辺や流量ゼロの後ろ向きの辺を含まないものに沿って流量を増やし、ネットワークにそのような道がなくなるまで繰り返す」というように要約できます。「後ろ向きの辺」が何かというと、元の向きと逆向きの辺を考えて、その辺を流れるときは逆に流量を減らすというものです。この逆向きの辺を考えないと、最初に変な道の選び方をしてしまうと、もう最大フローにはたどり着かなくなってしまいます。フォード・ファルカーソンのアルゴリズム自体は「ソースからシンクに向かう道で、飽和した前向きの辺や流量ゼロの後ろ向きの辺を含まないもの」を探すアルゴリズム自体を規定しているわけではないので、このアルゴリズムは自分で探索アルゴリズムを組む必要があります。アルゴリズムCでは最良優先探索を使用しています。以下では、アルゴリズムCにならって最良優先検索で最大流および最小切断を求めてみます。対象となる最大流問題は、アルゴリズムCの図33.2のネットワークを対象としています。(図がダウンロードできなかったので、貼付けられず。//NodeとEdgeで相互参照するため、あらかじめ宣言しておく。}}//全ノードvecNodesを順位優先で検索して、流量の増加の最も多い経路を見つける。//ソースからシンクまでの流量が増加する経路が発見された場合、シンクから逆に発見された経路をたどり、流量を増加させる。mincutacというわけで、最小切断がa,cだということが分かりました。PFS内で、流量最大のノードを探索している箇所をヒープソートにしたりすれば多分もっと早くなります。ちなみにですが、石川先生のグラフカットのサーベイ論文によれば、最大流問題を解くアルゴリズムとして、フォード・ファルカーソンのアルゴリズム以外にpush-relabelアルゴリズム(PDF)が知られていて、フォード・ファルカーソンが計算量O(n^3)に対し、push-relabelはO(nmlog(n^2/m))(nは頂点の数、mは辺の数)で、push-relabelの方が速いそうです。次回はとりあえずこのままフォード・ファルカーソンのアルゴリズムで、グラフカットによるエネルギー最小化問題を解いてみることにします。(1)はてなブログをはじめよう!thorikawaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。