1

状況: ユーザーが、プロジェクトの可能なパートナーとして他の複数のユーザーを選択します。ユーザーは、自分が選んだユーザーを別のユーザーより優先することはありません (つまり、リスト内のユーザーはパートナーとして十分です)。例：

| user_id | preferred_partners |
| 1       | 2 4                |
| 2       | 3 1                |
| 3       | 4 2 1              |
| 4       | 1                  |

実際のリストはもっと大きくなります。

私の質問: ユーザーとその優先パートナー (上記のリストなど) の配列が与えられた場合、最終的なパートナー ペアの配列を生成したいと考えています。最終的にパートナーになるペアの数を最大化する必要があります (できるだけ多くの人をペアにしたい)。

これは私が必要だと思うアルゴリズムです: Edmonds's matching algorithmですが、私は数学のバックグラウンドを持っていないため、解釈と実装に問題があります。

どんな助けでも大歓迎です。前もって感謝します。

4

2 に答える 2

0

エドモンズのアルゴリズムはあなたが望むものかもしれませんが、それでもそうではないかもしれません。トリプルを探すつもりはありますか？あなたは今までに好みの強さを欲しがるつもりですか？誰かがより多くの設定を下した場合、それらが一致から不一致に移行できないなど、メカニズムについていくつかの保証が必要になることはありますか？パートナーは相互に優先される必要がありますか？そうでない場合、相互に優先されるパートナーにもっと重みがありますか？

これらのバリアントの一部は、エドモンズのアルゴリズムまたはその加重いとこによって解決できます。これは、ハンガリーのアルゴリズムが2部マッチングアルゴリズムを使用するのとほぼ同じ方法で、エドモンズを使用して「制限付きプライマル」を解決しますが、特に3Dマッチングは困難です。そして、かわいい組み合わせアルゴリズムには従わない。Rubyから整数計画ソルバーを呼び出すと、ポリタイムの場合でも簡単に解ける場合があります。

于 2012-04-21T23:26:08.200 に答える
0

Edmonds のマッチング アルゴリズムはまさにあなたが望むものです。これは詳細な説明を提供する良いリンクです

于 2012-04-21T22:51:06.357 に答える