kirkkmans女子学生のこのバリエーションを解決するには

Question

私はgラボグループのラボに学生を割り当てているアプリを実装しようとしています。制約は次のとおりです。

1：生徒はすべてのラボで新入生と一緒に働きます。 2：すべての生徒は、ラボリーダーでなければなりません。

生徒がラボグループで均等に分割できない場合、解決できません。 「奇妙な」生徒がラボのリーダーになれないのであれば、それは受け入れられます。

私は2つのアプローチを試してみましたが、私はまだ満足していない。：

1. 1を解決したが2の解決の問題があるタブーサーチ、（私は実際には最初の1を解決してから2を解決しようとすると、その可能性があります

2. 私は#labsの学生を配列[0..6] [7..14] [15..21]で分割して回転させる簡単な解決策です行列を転置するには、増分回転（1,2,4）と（2,4,6）で#labs回繰り返す。

   • ラボ1：7のラボ基と3つのラボ21学生のための結果は次のようになり[0、7、14]、[1、8、15]、[2、9、16]、 [3、10、17]、[4、11、18]、[5、12、19]、[6、13、20]
   • ラボ2：6,12、18]、[0、13、 19]、[1、7、20]、[2,8]、[14]、[3、9、15]、[4、10、16]、[5、11、17]
   • ラボ3：[5 、[10,15]、[6,11,16]、[0,12,17]、[1,13,18]、[2,7,19]、[3,8,20]、[4,9 、14]

ラボの指導者が最初にありラボ1、ラボ2のための第二のための列が...

このソリューションは、まともに動作しますが、例えば3つのラボで12人または6つのラボで150人の学生のために失敗しました。助言がありますか？

2例またはそれらの組み合わせの同じ数を処理するようで、たぶん私は一人で

Answer 1

制約＃1 :-)高貴な価格を取得する必要が1に比べ速い雷では通常、社会ゴルファーと呼ばれています問題。 （パラメータgをグループ数、sを各グループのサイズ、wを週数とする。グループ化とは、g * sゴルファーをg個のグループに分割することである。 。

：ゴルファーの各ペアは、社会的なゴルファーの問題は組合せ最適化文献で研究されている）で最も一度一緒にグループ化され、そしてアプローチが（あなたが研究論文を見つけるためにあなたの好みの検索エンジンを使用することができます）の3つのタイプがあり、その

1. ローカル検索。これは、wが最大実現可能値を十分に下回っている場合に有効です。 Dotú and Van Hentenryckには、社会的ゴルファーの問題にタブー検索を適用した論文があります。

2. 完全な検索。これは、wがその最大可能値よりも上か、またはその下にある場合に必要ですが、うまく調整できません。

3. 代数構造。これは、有名なg = 8 s = 4 w = 10インスタンスが解決された方法です。残念なことに、多くのパラメータセットについて、知られている構成はありません。

その学生がその研究室のグループに属している場合、学生や研究室のグループの間にエッジが存在する場合に、学生や研究室のグループ間のmaximum matchingを計算し、ラボの指導者を割り当てます。