重み付けされたバイパータイトマッチング

Question

私はそこに似たような話題がたくさんあることを知っています。しかし、私の場合、ほとんどの人が私に疑念を残しました。私がしたいのは、完璧なマッチングを見つけることです（もちろん、完璧なマッチングができない場合にはできる限り完璧に近づけてください）。そして、n個の頂点のうちkをマッチさせることができるすべてのマッチングから）、私は可能な限り高い総重量を選択したい。ほとんどの場合（非加重）最大マッチングがあいまいなので、私は最大のを持っているものを選択したい

できるだけ多くの頂点として

1. マッチ： だから単純に追従しているものを私は言って置く優先順位エッジ上の重みの合計。同じ重量のものがいくつかある場合は、どちらを選択するかは関係ありません。

私はFord-Fulkersonアルゴリズムについて聞いたことがあります。それは私がそれを記述する方法で動作しているか、他のアルゴリズムが必要ですか？

Answer 1

これを自分で実装する場合は、おそらくHungarian algorithmを使用します。より高速のアルゴリズムは存在しますが、理解や実装が容易ではありません。

Ford-Fulkersonは最大フローアルゴリズムです。重みのないマッチングを簡単に解決することができます。加重マッチングアルゴリズムに変換するには追加のトリックが必要です。そのトリックで、あなたはハンガリーのアルゴリズムを思いついた。

また、最小コストのフローアルゴリズムを使用して加重二者間マッチングを行うこともできますが、同様にうまく機能しない可能性があります。ネットワークシンプレックス法もありますが、それは主に歴史的関心事のようです。