この問題を解決するための良いアルゴリズムは何ですか?
グループ A、グループ B、グループ C の 3 つのグループがあります。各グループの人数は同じです。彼らはそれぞれ、喜んで協力してくれる他のグループのメンバーのリストを持っています。私はこれらすべての人々を 3 つのグループ (A から 1 人、B から 1 人、C から 1 人) にグループ化し、グループ内の全員がグループ内の他の人々と協力したいと思うようにしたいと考えています。
これらのグループをすばやく見つけるにはどうすればよいですか? 全員を幸せにする方法がない場合、アルゴリズムは、最初に、互いに協力したい 3 人を含むグループをできるだけ多く作成し、次に、他のグループのできるだけ多くの人を幸せにする必要があります。
最後のポイント: 人々は誰と一緒に働きたいかについて合意します (もし x が y と働きたいのなら、y も x と働きたいと思うでしょう)。また、アルゴリズムの実行時間の大きな O を与えることができれば、それは素晴らしいことです!
これは安定した結婚の問題に似ていますが、2 つではなく 3 つの当事者がいます。
以前の問題 (二部グラフ マッチング) の効率的な解決策を見て、それらをニーズに合わせて調整してください。
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) = 1a (A の指定されたメンバー) が b (B の指定されたメンバー) と連携する意思がある場合、それ以外の場合は 0
M2 = |A| x |C|M2(a,c) = 1a (A の指定されたメンバー) が c (C の指定されたメンバー) と連携する場合は行列、それ以外の場合は 0
M2 = |B| x |C|行列、ここで
M3(b,c) = 1b (B の指定されたメンバー) が c (C の指定されたメンバー) と連携する意思がある場合、それ以外の場合は 0
ここで、最大化に使用する新しい行列を定義します。
X = |A| x |B| x |C|行列、ここで
X(a,b,c) = 1a、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 と Johnson を参照)。このような問題を合理的な方法で解決するには、何らかの形式の制約、整数、または線形計画法 (他の方法が存在します) を使用する必要がある可能性があります。役に立つかもしれないのは、新しい Microsoft Solver Foundation です。チェックしてみてください。
私は同様の問題に遭遇し、ブルートフォースするスクリプトを書きました... http://grouper.owoga.com/
私の最初の考えは次のとおりでした:総当たりするには大きすぎる大規模なグループの場合、ある種の遺伝的アルゴリズム? N 個のランダム スワップを M 回行います。いくつかの「幸せ」関数によって、それぞれの新しい配置にスコアを付けます。最良の数を取り、繁殖させ、繰り返します。
小さなグループの場合、いくつかのグループをループして、「最高の」スワップ (全体的な「幸福度」が最も高いスワップ) を見つけ、それを繰り返して、より良い結果を得ることができました。
まず、2 つの当事者が 3 番目のグループで協力する相手のリストがばらばらであるという事実を排除できます。次に、ブルートフォースの深さ優先検索を開始し、常に人気の低いものから人気の高いものへと選択します。
または、上記の削除と同等で、可能なすべてのトリオのリストを作成し、代わりにそれを基に作業します。