この問題をグラフの問題と見なすことができます。つまり、2 つのパーティション (学生、グループ) を尊重し、1 つのパーティション (学生) のカバーを最大化しながら、互いに素なサブグラフのセットで 2 部グラフをカバーします。
私はこのヒューリスティックを考えています：
- 空のソリューションから始める
- 割り当てられていない学生とオープン (メンバーが 6 人未満) のグループがある場合:
- 割り当てられていない学生を空き枠の順に並べ替えます
- リストの一番上から 6 人の生徒を選び (6 人の生徒が参加できるグループが見つかるまでリストを上から読んでください)、それらをグループとして使用します。
- 6 人の生徒を選ぶことができない場合は、できるだけ多くの生徒を選びます。
- グループを形成する 3 人の学生が見つからない場合、2 人はいます。
- そのグループの 3 人目の生徒を見つけて、そのグループで現在あなたが受講できるグループ (3 人以上) に割り当てられており、その生徒を使ってグループを埋めます。割り当てられていないセットから補充できるグループを優先する
- 第三者が見つからない場合は、別の 3 人グループから 1 人を選びます。そのグループでの彼の後任の検索を再帰します (またはあきらめます)。異なる 3 メンバー グループからの削除を並行して試みることができます。
- 生徒が 1 人しかいない場合は、他のグループの他の 2 人で彼のグループを埋めることができるかどうかを確認します。必要に応じて、それらを再帰的に置き換えるか、あきらめてください。
- すべての候補者グループがすでに満員の学生がいる場合は、これらのグループのいずれかで、満員ではないグループに移動できない人を探します。すべての置換グループがすでにいっぱいの場合は、再帰します。
- 割り当てられていない学生を満足させるために人々を移動させる方法が見つからない場合は、終了してください。
これは次のように要約されることに注意してください。
ほとんどの人を満足させる解決策をすばやく見つけます (ここでやめてもかまいません)。次に、次のペアリングのチェーンを見つけて、生徒を挿入してみてください。
- 使用済みと未使用のペアリングを交互に
- 学生から始まる
- クラスで終了
これは、2部グラフで交互パスを見つけることと同形であり、そのように最適化できることに注意してください。
人を満足させるために単一のグループ内の複数の人を置き換えることは決してないため、これでも最適な解決策を見つけることができないことに注意してください。
上記の疑似コードは、各ステップで学生のリストを並べ替えるように指示します。代わりに、このリストへの変更を追跡し、更新中に並べ替え順序を更新することができます。
更新: 教師も割り当てたいと思っていたとは思いませんでした。
この場合、生徒をグループに割り当てるときに、教師をグループに割り当てる必要があります。これにより、一部のグループの作成が妨げられますが、空いている教師がいない場合は、そのグループに別の教師を割り当てることができれば、別のグループから教師を連れて行くことができます。繰り返しになりますが、今回は教師グループのサブグラフで交互グラフを検索しているだけです。教師を解放するために生徒をシャッフルすることは実行可能ではないようです。
カバーするグラフ全体には、生徒、教師、グループの 3 つのパーティションがあります。教師と生徒は交流しないため、生徒 - グループ、グループ - 教師の 2 つの層があります。これら 2 つのレイヤーは、同じグループのセットをカバーする必要があることを除いて、独立しています。