Максимизация комбинации ряда ценностей

TL; DR: я думаю, вы предоставляете своим ученикам слишком большой выбор: D

Но у меня все равно была попытка решить эту проблему. На самом деле, довольно забавное упражнение, хотя некоторые ограничения были немного расплывчаты. Прежде всего, мне нужно было угадать, как будет выглядеть фактическое распределение предпочтений студентов. Я использовал равномерно распределенные независимые переменные, хотя это, вероятно, не очень реалистично. Тем не менее, я думаю, что он должен работать с реальными данными так же хорошо, как и с моими случайно сгенерированными данными.

Я считал это грубым форсированием, но грубый анализ дал мне оценку более 10 ^ 65 возможных конфигураций. Это довольно много. А поскольку у нас нет триллиона триллионов лет, чтобы рассмотреть их все, нам понадобится эвристический подход.

Из-за масштабов проблемы я старался не возвращаться. Но это означало, что можно застрять; Возможно, не будет решения, при котором все будут получать только даты, которые они поставили 4 и 5.

В итоге я реализовал обоюдоострый поиск в стиле итеративного углубления, в котором оба лучший случай, на который мы все еще надеемся (т. е. назначить ученикам дату, которую они поставили 5), и наихудший сценарий, который мы готовы принять ( некоторым ученикам, возможно, придется жить с 3), постепенно опускаются до тех пор, пока не будет найдено решение. Если мы застряли, сбросьте настройки, снизьте ожидания и попробуйте еще раз. Задачи A и B назначаются первыми, а C выполняется только после того, как A и B завершены, потому что ограничения на C гораздо менее строгие.

Я также использовал весовой коэффициент, чтобы смоделировать компромисс между максимальным удовлетворением учащихся и соблюдением ограничений на количество презентаций в день.

В настоящее время он, кажется, находит решение практически для каждого случайно сгенерированного набора предпочтений. Я включил метрику оценки; соотношение между суммой значений предпочтений всех назначенных комбинаций ученик / свидание и суммой всех идеальных / трех лучших значений предпочтений ученика. Например, если у ученика X в списке две пятерки, одна четверка и остальные тройки, и ему назначена одна из своих пятерок и две тройки, он получит 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%