1

C または C++ で二部一致アルゴリズム (おそらく max-flow アルゴリズムに基づく) を実装するにはどうすればよいですか?

具体的には、ファイルに次の入力があります: (1,3) (1,5) (2,5)

(M,F) --> ここで、M は MALE の ID を表し、F は FEMALE の ID を表します。

一致の最大数を見つけて、一致したカップルを表示する必要があります。Like: マッチ: 1&3 , 2&5

「ネットワーク内の最大フロー」アルゴリズムに基づいてこの問題を解決できる本をいくつか読んだことがありますが、「この問題は....アルゴリズムで解決できる」という文以外に特定の情報は見つかりませんでした。私はmax-flowについてほとんど知識がなく、それを実装する方法も知りません...

4

5 に答える 5

6

はい、二部マッチングは最大フローまで減らすことができます:

  1. Mノードとのセットが与えられますF。ファイルにペアがある場合は、ノードmインMからノードfインに有向エッジを追加します。F(m, f)

  2. 内のすべてのノードにS有向エッジを持つ単一のノードを追加します (これが「スーパーソース」ノードです)。SM

  3. すべてのノードからT有向エッジを持つ単一のノードを追加します (これが「スーパー シンク」ノードです)。FT

  4. Sここで、 から までの最大フロー (すべての辺の重みが 1 の場合)を見つける必要がありますT。

では、最大流量とは何ですか？からへのフローは、各ノード (とを除く) について、その流入エッジの重みが流出エッジの重みと同じであるエッジのセットです。グラフが一連のパイプであり、 でシステムに水を注ぎ、 で排出していると想像してください。その間のすべてのノードで、入ってくる水の量は出てくる水の量と同じでなければなりません。STSTST

フローが元のセットのマッチングに対応していることを自分自身に納得させてください。(フローが与えられた場合、どのようにマッチングを取得しますか? マッチングが与えられた場合、フローを取得する方法は?)

最後に、グラフ内の最大フローを見つけるには、Ford-Fulkerson アルゴリズムを使用できます。上記のウィキペディアのページでは、疑似コードを使用して適切に説明しています。

于 2009-05-18T17:07:56.927 に答える
3

はい、マックスフロー問題を解決するためのコードが既にある場合は、この講義の最後に示されているように、グラフを変換することで二部マッチングを解決するためにそれを使用できますが、ゼロから始める場合、それはおそらく正しいアプローチではありません。あまり大きくならないサンプルの問題を解決するためにかなり単純なコードを実装したいだけの場合は、ここで概説されている単純な拡張パス アプローチを使用することをお勧めします。これにより、コーディングが非常に簡単で、非常に大きなグラフを除くすべてのグラフに適した O(|V||E|) アプローチが得られます。最悪の場合のパフォーマンスが向上したものが必要な場合は、Hopcraft-Karpを試すことができます一度に複数の拡張パスを見つけ、 O(sqrt(|V|)|E|) 実行時間をバインドするアルゴリズムですが、ウィキペディアの記事では次のように述べています。

何人かの著者が二部マッチングアルゴリズムの実験的比較を行っています。一般に、彼らの結果は、Hopcroft-Karp 法が理論ほど実際には優れていないことを示している傾向があります。拡張パスを見つけるための単純な幅優先および深さ優先の戦略と、プッシュ再ラベル手法の両方によって優れています。 .

いずれにせよ、Hopcraft-Karp またはウィキペディアの記事の参照で言及されているプッシュ関連技術のいずれかに取り組む前に、単純な拡張パス アプローチを確実に理解し、実装できる必要があります。

編集: 何らかの理由で、上記のリンクが正しく表示されません。問題のURLは次のとおりです。/matching.pdf )、および ( http://en.wikipedia.org/wiki/Hopcroft –Karp_algorithm)。

于 2009-05-18T19:19:17.347 に答える
1

QuickGraphライブラリには、2 部構成のマッチング アルゴリズムが含まれています。Edmonds Karp 最大フロー アルゴリズムをラップします。

これまでのところ、アルゴリズムの唯一のドキュメントは、私が追加した単体テストです。単純に maxflow アルゴリズムをラップしない (願わくばもっと速い) 実装を追加したい人がいたら、私に連絡してください。

于 2010-08-11T06:04:01.947 に答える
0

以下は、最大二部マッチングのためのフロー アルゴリズムの実験的研究です。

@article{cherkassky98,
   author = {Boris V. Cherkassky and Andrew V. Goldberg and Paul Martin and Joao C. Setubal and Jorge Stolfi},
   title = {Augment or Push:  A Computational Study of Bipartite Matching and Unit Capacity Flow Algorithms},
   journal = {Journal of Experimental Algorithmics},
   volume = 3,
   number = 8,
   year = 1998
}

勝者は push-relabel アルゴリズムでした。これは、Andrew Goldberg の「BIM」パッケージからの実装であると私は信じています。このパッケージは、次の場所からダウンロードできます。

http://www.avglab.com/andrew/soft.html

解決策を自分でコーディングすることが重要な場合は、Jesse が提案したように、Ford-Fulkerson で解決することをお勧めします。その場合は、深さ優先検索ではなく幅優先検索を使用して、拡張パスを見つけることをお勧めします (上記の記事で説明した理由から)。

于 2009-08-17T03:26:31.540 に答える