TL;DR : あなたは生徒に選択肢を与えすぎていると思います :D
しかし、とにかく私はこの問題に一撃を加えました。いくつかの制約は少しあいまいでしたが、実際にはかなり楽しいエクササイズです。何よりも、実際の学生の選好分布がどのようになるかを推測する必要がありました。おそらくあまり現実的ではありませんが、一様分布の独立変数を使用しました。それでも、ランダムに生成されたデータと同じように、実際のデータでもうまく機能するはずだと思います。
私は総当りを考えましたが、大まかな分析では、10^65 を超える構成が可能であると見積もられました。それはちょっと多いです。そして、それらすべてを検討するのに 1 兆年という余裕はないので、ヒューリスティックなアプローチが必要になります。
問題が大きいため、後戻りを避けるようにしました。しかし、これは行き詰まる可能性があることを意味していました。誰もが 4 と 5 を付けた日付だけを取得するという解決策はないかもしれません。
私は両刃の反復的深化のような検索を実装することになりました。ここでは、私たちがまだ希望を抱いている最良のケース (つまり、生徒が 5 を与えた日付に学生を割り当てる) と、私たちが喜んで行う最悪のケースのシナリオの両方を行います。受け入れる (一部の学生は 3 と一緒に暮らす必要があるかもしれません) は、解決策が見つかるまで徐々に下げられます。行き詰まったら、リセットして、期待値を下げて、もう一度やり直してください。タスク A と B が最初に割り当てられ、A と B が完了してから C が実行されます。これは、C の制約がそれほど厳しくないためです。
また、加重係数を使用して、学生の幸福度を最大化することと、1 日あたりのプレゼンテーションの種類の制限を満たすこととの間のトレードオフをモデル化しました。
現在、ランダムに生成された設定のほとんどすべてのセットに対して解決策を見つけているようです。評価指標を含めました。割り当てられたすべての学生/日付の組み合わせの優先値の合計と、すべての学生の理想/上位 3 つの優先値の合計との比率。たとえば、生徒 X のリストに 2 つの 5、1 つの 4、残りの 3 があり、5 のうちの 1 つと 2 つの 3 に割り当てられている場合、彼は 5+3+3=11 を取得しますが、理想的には 5+5+ を取得できたはずです。 4=14; 彼は 11/14 = 78.6% 満足しています。
いくつかのテストの後、私の実装は、平均して約 95% の学生満足度を生み出す傾向があるようです。これは、私が予想していたよりもはるかに優れています :) しかし、これも偽のデータによるものです。本当の好みはおそらくもっとまとまりがあり、満足するのは難しいでしょう。
以下は、アルゴリズムのコアです。完全なスクリプトは約 250 行で、ここでは少し長すぎると思います。Github で確認してください。
...
# Assign a date for a given task to each student,
# preferring a date that they like and is still free.
def fill(task, lowest_acceptable, spread_weight=0.1, tasks_to_spread="ABC"):
random_order = range(nStudents) # randomize student order, so everyone
random.shuffle(random_order) # has an equal chance to get their first pick
for i in random_order:
student = students[i]
if student.dates[task]: # student is already assigned for this task?
continue
# get available dates ordered by preference and how fully booked they are
preferred = get_favorite_day(student, lowest_acceptable,
spread_weight, tasks_to_spread)
for date_nr in preferred:
date = dates[date_nr]
if date.is_available(task, student.count, lowest_acceptable == 1):
date.set_student(task, student.count)
student.dates[task] = date
break
# attempt to "fill()" the schedule while gradually lowering expectations
start_at = 5
while start_at > 1:
lowest_acceptable = start_at
while lowest_acceptable > 0:
fill("A", lowest_acceptable, spread_weight, "AAB")
fill("B", lowest_acceptable, spread_weight, "ABB")
if lowest_acceptable == 1:
fill("C", lowest_acceptable, spread_weight_C, "C")
lowest_acceptable -= 1
以下は、スクリプトによって出力された結果の例です。
Date
================================================================================
Student | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
================================================================================
1 | | A | B | | C | | | | | | | |
2 | | | | | A | | | | | B | C | |
3 | | | | | B | | | C | | A | | |
4 | | | | A | | C | | | | | | B |
5 | | | C | | | | A | B | | | | |
6 | | C | | | | | | | A | B | | |
7 | | | C | | | | | B | | | | A |
8 | | | A | | C | | B | | | | | |
9 | C | | | | | | | | A | | | B |
10 | A | B | | | | | | | C | | | |
11 | B | | | A | | C | | | | | | |
12 | | | | | | A | C | | | | B | |
13 | A | | | B | | | | | | | | C |
14 | | | | | B | | | | C | | A | |
15 | | | A | C | | B | | | | | | |
16 | | | | | | A | | | | C | B | |
17 | | A | | C | | | B | | | | | |
18 | | | | | | | C | A | B | | | |
================================================================================
Total student satisfaction: 250/261 = 95.00%