8

教師である私の友人は、1 クラスに 23 人の生徒がいます。彼らは、2 つのペアが 14 週間にわたって繰り返されないように (ペアが 1 週間に割り当てられる)、14 週間にわたって学生を 2 人のグループと 3 人のグループ (奇数の学生を処理する) に割り当てるアルゴリズムを求めています。

力ずくのアプローチでは効率が悪すぎるので、別のアプローチ、魅力的な行列表現、グラフ理論を考えていました。誰にもアイデアはありますか？私が見つけることができた問題は1週間しか対処できず、この答えは私がかなり理解することができました.

4

5 に答える 5

9

ラウンドロビンアルゴリズムは、私が思うトリックを実行します。

残りの生徒を2番目のグループに追加すると、完了です。

First run
1   2   3   4   5   6   7   8   9   10  11  12
23  22  21  20  19  18  17  16  15  14  13

Second run
1   23  2   3   4   5   6   7   8   9   10  11  
22  21  20  19  18  17  16  15  14  13  12

..。

于 2013-03-07T15:29:32.800 に答える
1

もう 1 つの可能性はグラフ マッチングです。14 の異なるグラフ マッチングが必要になります。

于 2013-03-08T14:43:15.057 に答える
-1

これは、14の繰り返されない11ペアの組み合わせのグループを生成するHaskellの例です。値'pairs'は、1から23までのペアのすべての組み合わせです（たとえば、[1,2]、[1,3]など）。次に、プログラムは、各リストが11ペアの14リスト（値「pairs」から選択）であるリストを作成し、11ペアの1つのリストでペアが繰り返されず、単一の数値が繰り返されないようにします。不足している最後の生徒を毎週、適切と思われる場所に配置するのはあなた次第です。（結果の出力を開始する前に計算するのに約3分かかりました）：

import Data.List
import Control.Monad

pairs = nubBy (\x y -> reverse x == y) 
        $ filter (\x -> length (nub x) == length x) $ replicateM 2 [1..23]

solve = solve' [] where
  solve' results =
    if length results == 14
       then return results
       else solveOne [] where
         solveOne result =
           if length result == 11
              then solve' (result:results)
              else do next <- pairs
                      guard (notElem (head next) result' 
                             && notElem (last next) result'
                             && notElem next results')
                      solveOne (next:result)
                         where result' = concat result
                               results' = concat results

出力からの1つのサンプル：

[[[12,17],[10,19],[9,18],[8,22],[7,21],[6,23],[5,11],[4,14],[3,13],[2,16],[1,15]],
[[12,18],[11,19],[9,17],[8,21],[7,23],[6,22],[5,10],[4,15],[3,16],[2,13],[1,14]],
[[12,19],[11,18],[10,17],[8,23],[7,22],[6,21],[5,9],[4,16],[3,15],[2,14],[1,13]],
[[15,23],[14,22],[13,17],[8,18],[7,19],[6,20],[5,16],[4,9],[3,10],[2,11],[1,12]],
[[16,23],[14,21],[13,18],[8,17],[7,20],[6,19],[5,15],[4,10],[3,9],[2,12],[1,11]],
[[16,21],[15,22],[13,19],[8,20],[7,17],[6,18],[5,14],[4,11],[3,12],[2,9],[1,10]],
[[16,22],[15,21],[14,20],[8,19],[7,18],[6,17],[5,13],[4,12],[3,11],[2,10],[1,9]],
[[20,21],[19,22],[18,23],[12,13],[11,14],[10,15],[9,16],[4,5],[3,6],[2,7],[1,8]],
[[20,22],[19,21],[17,23],[12,14],[11,13],[10,16],[9,15],[4,6],[3,5],[2,8],[1,7]],
[[20,23],[18,21],[17,22],[12,15],[11,16],[10,13],[9,14],[4,7],[3,8],[2,5],[1,6]],
[[19,23],[18,22],[17,21],[12,16],[11,15],[10,14],[9,13],[4,8],[3,7],[2,6],[1,5]],
[[22,23],[18,19],[17,20],[14,15],[13,16],[10,11],[9,12],[6,7],[5,8],[2,3],[1,4]],
[[21,23],[18,20],[17,19],[14,16],[13,15],[10,12],[9,11],[6,8],[5,7],[2,4],[1,3]],
[[21,22],[19,20],[17,18],[15,16],[13,14],[11,12],[9,10],[7,8],[5,6],[3,4],[1,2]]]
于 2013-03-07T16:59:19.820 に答える
-1

制約の観点から問題を説明してみてください。

次に、制約を (Eclipse ではなく) ECLiPSe などのツールに渡します。 http://eclipseclp.org/を参照してください。

実際、あなたの問題は、そのサイト ( http://eclipseclp.org/examples/golf.ecl.txt ) の Golf の例と似ているようです。

于 2013-03-07T14:18:23.457 に答える
-1

他のすべての学生が含まれる各学生のセット (メモリ消費を抑えるため、学生へのビットセット マッピングなど) から始めます。パートナーを選ぶ 11 人の学生 (あなたが形成する 11 のグループ) を選ぶたびに、14 回繰り返します。生徒ごとに、まだグループに参加したことのないパートナーを選びます。それらの 11 人のランダムな生徒の 1 人に対して、2 番目のパートナーを選びます。ピックごとに、セットを調整します。

于 2013-03-07T14:18:53.747 に答える