algorithm - 最も満足できるように人々をチームに分けます

Question

ただの好奇心の質問。クラスのグループワークで、教授が人々を特定の数のグループに分割したことを覚えていますか（n）？

私の教授の何人かは、n一緒に働きたい人と一緒に働きたくない人のリストを各学生から取り、次に、学生が好きな人と一致し、一緒に働くことを避ける場所nのグループを魔法のように見つけますn彼らが好まない人々。

私には、このアルゴリズムはナップサック問題によく似ていますが、この種の問題に対するあなたのアプローチについて質問したいと思います。

編集：私の質問とまったく同じようなものを説明しているACMの記事を見つけました。既視感の2番目の段落を読んでください。

score 5 · Accepted Answer

私には、それはある種のクリーク問題のように聞こえます。

頂点は学生になります
次の両方が当てはまる場合、2人の生徒はエッジで接続されます。
1. 2人の学生のうち少なくとも1人は、もう1人と一緒に働きたいと思っています。
2. 二人の生徒はどちらももう一人と一緒に働きたくない。

次に、グラフをサイズnのクリークに分割します。（学生の数がnで割り切れると仮定します）

これが不可能な場合は、エッジの最初の制約をスリップさせ、どちらも相手と一緒に作業したくないと明示的に言っていない限り、2人の間にエッジを設定します。

これを効率的に解決するためのアプローチについては、私にはわかりませんが、これにより、問題に対する洞察に近づくことができれば幸いです。

score 3 · Accepted Answer

これをクラスタリングの問題として非常に簡単にモデル化でき、実際に空間を定義する必要さえなく、実際には距離を定義するだけで済みます。

2 人が一緒に仕事をしたい場合は、2 人を非常に親密にします。一方が他方と連携したい場合は閉じます。無関心なら中距離。どちらか一方が他方と連携したくない場合は、遠く離れてください。

その後、クラスターを見つけることができます。次に、サイズが大きすぎるクラスターを分割します。クラスター内のすべての人が一緒に問題なく作業できるという確信が持てます。

score 1 · Accepted Answer

この問題はブルートフォースになる可能性があるため、私のアプローチでは、まずブルートフォースを行い、より良いアイデアが得られたら修正します。

score 0 · Accepted Answer

使用できるアルゴリズムがいくつかあります。良い例は、いわゆる「安定した結婚問題」で、これには完全な解決策があります。詳細については、こちらをご覧ください。

安定した結婚の問題は、2 つのグループの人々 (結婚の場合は男性/女性) でのみ機能します。ペアを形成したい場合は、バリエーション、安定したルームメイトの問題を使用できます。この場合、ペアを作成しますが、全員が 1 つのプールから来ます。

しかし、あなたはチームを要求しました (チームごとに 2 人以上に翻訳します)。この場合、全員に最高から最低の一致を記入させてから、

4 に答える 4