これはどのようなアルゴリズム（安定した結婚のバリエーション）ですか？

Question

私はオブジェクトのセットを持っています（1〜約500）。各オブジェクトは、同じセットの特定の（ゼロ以上の）他のオブジェクトと互換性があります。

誰も私にセットのオブジェクトのほとんどがペアになるようにお互いに互換性のあるオブジェクトのペアを作成する最良の方法を決定する方法についてのいくつかのポインタを教えてくれますか？

Answer 1

一般的なグラフで最大一致を探しています。あなたが慣れ親しんでいる安定した結婚問題とは対照的に、最大一致問題では、入力グラフは必ずしも二者であるとは限りません。安定性の概念はありません（頂点は互換性のあるオプションをランク付けしません）。あなたが探しているのは、2つのエッジが共通の頂点（a.k.a.、マッチング）を共有しないようなグラフのエッジのサブセットです。可能な最大数のエッジを含むマッチングを作成しようとしています。

幸いにも、一般グラフの最大マッチングを見つける問題は、（また、ので、それは単一の頂点に花（奇数サイクル）契約方法の花アルゴリズムとしても知られる）Edmond's matching algorithmを用いて多項式時間で解くことができます。エドモンドのマッチングアルゴリズムの時間複雑度はO（E・V^2）です。あまり効率的ではありませんが、これはあなたが扱っている比較的小さなグラフには十分だと思います。 Java implementation of Edmond's algorithmオープンソースがあるので、自分で最初から実装する必要はありません。ただし、最新の技術に興味がある場合は、O（E•sqrt（V））で実行される問題についてはmost efficient algorithmを使用することができます。

入力の頂点の互換性が2分法でない場合（つまり、各頂点にその隣人の間で優先度を指定するランク付けがある場合）、対応する重みをエッジに追加して優先プロファイルに対応し、variation of Edmond's algorithm for weighted graphsを使用できます。