2

フォードフルカーソンアルゴリズムを使用して最大フローを計算しましたが、最大を計算する必要があるプロジェクト選択問題を実装したいと考えています。番号。実行可能なプロジェクトの.i を含む min.cut を見つける必要があります。最大の利益をもたらす実行可能なプロジェクトの。分を見つけるためのアルゴリズムはどうあるべきですか。カット *グラフでmax.flowを知った後。*最大フローを使用して、ie noを含むカットを決定するにはどうすればよいですか 最大フローに貢献するノードの数。収益が最大化されるように、最適なノードのセットを選択する必要があります。私のアプリケーションでは、各ノードは収益に関連付けられており、正にも負にもなり得ます。また、優先順位の制約もあります。たとえば、a が選択されている場合は b&c も選択する必要があります。これを実装する方法を誰か教えてもらえますか?

次のように最大フロー グラフに変換しました: if Revenue(node)>0 source->node からエッジを追加します。それ以外の場合は node->sink からエッジを追加し、優先順位の制約のために無限容量のエッジを作成しました

4

2 に答える 2

0

Ford Fulkerson は、いくつかの異なる方法で実装できるという点で、ややメタアルゴリズムです (Edmonds-Karp は FF アルゴリズムのインスタンス化です)。あなたの質問は、どのように実装したか、またはどのような情報を持っているかを知らずに答えるのは困難です.

理想的には、ある種の残差グラフを使用して、アルゴリズムである種の幅優先探索を行っています。これを行っているとき、BFS がシンクを見つけられない場合、アルゴリズムは停止するはずです。これが発生すると、カットの最初のセットは BFS で見つけることができたすべてのノードであり、もう 1 つのセットは見つけることができなかったすべてのノードです。

アルゴリズムのラベル付けバージョンを使用している場合、カットを形成するセットは、ラベル付けされたセットとラベル付けされていないセットです。

これが役立つことを願っています。あなたの質問は、確かに私が解析するのが少し難しかったです。ここで十分なヘルプが見つからない場合は、matcheek と同じ推奨事項があります (Wikipedia または CLRS が利用可能な場合は参照してください)。

于 2012-07-06T18:14:52.687 に答える
0

ソース頂点から dfs/bfs を実行して min.cut (A,B) を計算し、最終的な残差グラフで飽和エッジを見つけることができます。

于 2012-07-11T18:18:44.427 に答える