二部グラフの問題で最大マッチングに行き詰まっています。問題は次のようになります。
m 個の円形の穴があるボードと n 個の円形ディスクのセットが与えられます。穴には h 1、...、h m、ディスクには d 1、...、d nの番号が付けられます。
m 行 n 列の行列 A があります。A[i][j] = 1 は、h iが d jに適合する場合(つまり、h iの直径 ≥ d jの直径)、それ以外の場合は 0 です。
任意の穴に最大 1 つのディスクを含めることができるという条件を考えると、穴ディスクのフィッティングが最大になる構成を見つける必要があります。
この問題はネットワーク フローの問題にモデル化できると読みましたが、その方法を正確に追うことができませんでした。誰かがこれを行う方法を説明できますか? また、私が見ることができるかもしれないこれのためのCコードはありますか?
二部マッチングから最大フローへの削減は、実際には非常に美しいものです。二部グラフが与えられた場合、グラフは、最初の列から 2 番目の列へのエッジで接続されたノードの 2 つの列と考えることができます。
A ----- 1
B --\ 2
C \- 3
... ...
Z n
問題を最大フローに減らすには、フローが左の列から右にのみ移動できるように、最初の列から 2 番目の列にすべてのエッジを向けることから始めます。これを行った後、ソース ノードおよびターミナル ノードとして機能する 2 つの新しいノード s および t を導入します。s を左側のすべてのノードに接続するように配置し、t を右側の各ノードに接続するように配置します。例えば：
A ----- 1
/ B --\ 2 \
s- C \- 3 - t
\ ... ... /
Z n
ここでの考え方は、s から t にたどり着けるパスは、左側の列のノードの 1 つに入り、右側の列のエッジを横切り、そこから t に到達する必要があるということです。したがって、一致するパスと st パスのエッジから簡単な 1 対 1 のマッピングがあります。s からエッジのソースへのパスをたどり、エッジをたどり、端点からノードまでのエッジをたどるだけです。 t。この時点での目標は、s から t へのノード分離パスの数を最大化する方法を見つけることです。次のように maximum-flow を使用してこれを実現できます。最初に、s を残す各エッジの容量を 1 に設定します。これにより、最大 1 ユニットのフローが最初の列の各ノードに入ることが保証されます。同様に、2 つの列を横切る各エッジの容量を 1 に設定し、エッジを選択するか選択しないかのいずれかになります。ある程度の多様性でそれを選ぶのではなく。最後に、2 列目を t に残すエッジの容量も 1 に設定します。これにより、右側の各ノードが一度だけ一致することが保証されます。これは、複数のフロー ユニットを通過させることができないためです。
フロー ネットワークを構築したら、標準アルゴリズムのいずれかを使用して最大フローを計算します。 Ford-Fulkersonは、グラフの最大フローがノード数に等しいため、ここでうまく機能する単純なアルゴリズムです。最悪の場合のパフォーマンスは O(mn) です。あるいは、高度に最適化されたHopcroft-Karp アルゴリズムを使用すると、O(m√n) 時間でこれを実行できます。
C 実装については、Google で Ford-Fulkerson ステップをすばやく検索すると、このリンクが見つかりました。このコードに渡す前にフロー ネットワークを構築する必要がありますが、構築はそれほど複雑ではないので、それほど苦労することはないと思います。
お役に立てれば！