優先パートナーを3つのグループに一致させるアルゴリズム
https://stackoverflow.com/questions/294660
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
この問題を解決するのに適したアルゴリズムは何ですか？
グループA、グループB、グループCの3つのグループがあります。各グループには同じ人数の人々がいます。彼らはそれぞれ、他のグループに所属する人々のリストを持っています。私はこれらのすべての人々を3人のグループ（Aから1人、Bから1人、Cから1人）にグループ化し、グループ内の全員がグループ内の他の人と一緒に働きたいと考えています。
これらのグループをすばやく見つけるにはどうすればよいですか？すべての人を幸せにする方法がない場合、アルゴリズムは最初に多くのグループに互いに協力したい3人の人がいるようにし、次に他のグループの人を幸せにする必要があります。
最後のポイント：人々は誰と仕事をしたいかに同意します（人xが人yと働きたいなら、yもxと働きたい）。アルゴリズムの実行時間の大部分を与えることができれば、それは素晴らしいことです！
解決
これは安定した結婚の問題に似ていますが、2つのパーティではなく3つのパーティがあります。
以前の問題（2部グラフマッチング）の効率的なソリューションを見て、ニーズに合わせて調整してください。
http://en.wikipedia.org/wiki/Stable_marriage_problem
1つの適応策は、最初にグループAとBのみからワーキングペアを構築することです。次に、これらのペアをそれぞれグループCのワーカーとペアにする必要があります。ペアは、ペアの両方のメンバーが同意する（リストが与えられた）ワーカーのみを優先します。これは局所的な最適化のみを提供することに注意してください。
k-partiteマッチングの最適なソリューションは、NPを見つけるのが難しいことです：
http://www.math.tau.ac .il /〜safra / PapersAndTalks / k-DM.ps
k-partiteマッチング問題の最適でない解決策については、このペーパーを参照してください：
検索する用語がわかったので、Googleで他のユーザーを見つけることができると確信しています。 k = 3の最適なソリューションを提供する効率的なアルゴリズムがあるかどうかはわかりません。
他のヒント
これは安定した結婚問題の延長とは異なります。OPの質問を理解しているように、各グループの人々は、ほとんどの人と一緒に働きたい人の順序付けられたリストを持っていないからです。バイナリ関係（意思がある/しない）です。
これは、非常に迅速に解決できる整数計画問題として定式化できます。以下に問題の数学的定式化を示します。 glpkやAMPL / CPLEXなどのパッケージを使用してデータを処理できます。
次のマトリックスを定義します：
M1 = |A| x |B|マトリックス、ここで
M1(a,b) = 1 a（与えられたAのメンバー）がb（与えられたBのメンバー）で作業する意思がある場合、それ以外の場合は0
M2 = |A| x |C|マトリックス。ここで、a（Aの指定されたメンバー）がc（Cの指定されたメンバー）を処理する場合はM2(a,c) = 1、そうでない場合は0
M2 = |B| x |C|マトリックス、ここで
M3(b,c) = 1 b（指定されたBのメンバー）がc（指定されたCのメンバー）で作業する場合、それ以外の場合は0
最大化に使用する新しいマトリックスを定義します。
X = |A| x |B| x |C|マトリックス、ここで
X(a,b,c) = 1 a、b、cを連携させる場合。
今、目的関数を定義します：
//グループの数を最大化
最大化Sum[(all a, all b, all c) X(a,b,c)]
次の制約に従います：
// 2つのグループに誰も配置されないようにする
aのすべての値：Sum[(all j, k) X(a, j, k)] <= 1
bのすべての値：Sum[(all i, k) X(i, b, k)] <= 1
cのすべての値：Sum[(all i, j) X(i, j, c)] <= 1
//すべてのグループが互換性のある個人で構成されていることを確認する
すべてのa、b、c：X(a,b,c) <= M1(a,b)/3 + M2(a,c)/3 + M3(b,c)/3
この問題に対する簡単なメモ。第一に、それは安定した結婚問題の例ではなく、実際にはそれの拡張ではありません（3D安定マッチング問題）。とにかく、NP困難であることが知られている3Dマッチング問題です（Garey and Johnsonを参照）。このような問題を合理的な方法で解決するには、何らかの形式の制約、整数、または線形計画法（他の方法が存在します）を使用する必要がありそうです。役立つ可能性のあるものは、新しいMicrosoft Solver Foundationです。チェックしてください。
最初に、3番目のグループで作業する2人の関係者が互いに素なリストを持っているという事実を排除できます。次に、ブルートフォース、深さ優先検索を開始し、常に人気の低いものから人気の高いものを選択します。
代わりに、上記の削除と同等の、可能なすべてのトリオのリストを作成し、代わりにそれから働きます。
同様の問題に遭遇し、それをブルートフォースするスクリプトを作成しました... http：// grouper。 owoga.com/
最初に考えたのは、ブルートフォースするには大きすぎるグループの場合、ある種の遺伝的アルゴリズムですか？ N回ランダムにM回スワップします。いくつかの「幸福」機能により、それぞれの新しいアレンジメントにスコアを付けます。最高の数匹を選び、繁殖させ、繰り返します。
小さなグループの場合、いくつかのグループをループして、「最高の」スワップ（全体的な「幸福」のゲインが最も高いもの）を見つけ、それを繰り返して、より良い結果を得ました。
