教師である私の友人は、1 クラスに 23 人の生徒がいます。彼らは、2 つのペアが 14 週間にわたって繰り返されないように (ペアが 1 週間に割り当てられる)、14 週間にわたって学生を 2 人のグループと 3 人のグループ (奇数の学生を処理する) に割り当てるアルゴリズムを求めています。
力ずくのアプローチでは効率が悪すぎるので、別のアプローチ、魅力的な行列表現、グラフ理論を考えていました。誰にもアイデアはありますか？私が見つけることができた問題は1週間しか対処できず、この答えは私がかなり理解することができました.
ラウンドロビンアルゴリズムは、私が思うトリックを実行します。
残りの生徒を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
..。
もう 1 つの可能性はグラフ マッチングです。14 の異なるグラフ マッチングが必要になります。
これは、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]]]
制約の観点から問題を説明してみてください。
次に、制約を (Eclipse ではなく) ECLiPSe などのツールに渡します。 http://eclipseclp.org/を参照してください。
実際、あなたの問題は、そのサイト ( http://eclipseclp.org/examples/golf.ecl.txt ) の Golf の例と似ているようです。
他のすべての学生が含まれる各学生のセット (メモリ消費を抑えるため、学生へのビットセット マッピングなど) から始めます。パートナーを選ぶ 11 人の学生 (あなたが形成する 11 のグループ) を選ぶたびに、14 回繰り返します。生徒ごとに、まだグループに参加したことのないパートナーを選びます。それらの 11 人のランダムな生徒の 1 人に対して、2 番目のパートナーを選びます。ピックごとに、セットを調整します。