Максимизация комбинации ряда значений
Это сложный вопрос, но я подозреваю, что есть какой-то принцип, который я могу применить, чтобы упростить его - я просто не знаю, что это такое.
Мне нужно разделить презентационные слоты в классе, полном студентов на семестр. Существует несколько возможных дат и несколько типов презентаций. Я провел опрос, где студенты могли оценить свой интерес к различным темам. Что я хотел бы сделать, так это получить лучшее (или, по крайней мере, хорошее) распределение слотов для презентаций среди студентов.
Итак, что я имею:
- Список 12 дат
- Список 18 студентов
- CSV-файл, где каждый студент (строка) имеет оценку 1-5 для каждой даты
Что бы я хотел получить:
- Каждый студент должен иметь одну из презентаций типа А (
intro), один из типа представления B (figures) и 3 презентации типа С (aims) - Каждая дата должна иметь как минимум 1 презентацию каждого типа
- Каждая дата должна содержать не более 2-х типов А или В
- Попробуйте дать студентам презентации, которые они высоко оценили (4 или 5)
Должен заметить, что я понимаю, что это похоже на домашнее задание, но это настоящая жизнь:-). Я думал, что я мог бы сделать Student класс для каждого студента, который содержит даты для каждого типа презентации, но я не был уверен, каков будет лучший способ его заполнения. На самом деле, я даже не уверен, с чего начать.
1 ответ
TL; DR: я думаю, что вы предоставляете своим студентам слишком большой выбор:D
Но я все равно попытался решить эту проблему. Довольно забавное упражнение на самом деле, хотя некоторые ограничения были немного расплывчаты. Больше всего мне пришлось угадывать, как будет выглядеть фактическое распределение предпочтений студентов. Я пошел с равномерно распределенными, независимыми переменными, хотя это, вероятно, не очень реалистично. Тем не менее, я думаю, что он должен работать так же хорошо, как и с моими случайно сгенерированными данными.
Я подумал о грубом форсировании, но приблизительный анализ дал мне оценку более 10^65 возможных конфигураций. Это довольно много. И поскольку у нас нет триллиона триллионов лет, чтобы рассмотреть все из них, нам понадобится эвристический подход.
Из-за масштабов проблемы я старался не возвращаться назад. Но это означало, что вы могли застрять; не может быть решения, в котором все получают только даты, которые они дали 4 и 5.
Я закончил тем, что реализовал двусторонний Итеративный Поиск, подобный углубленному, где и лучший вариант, на который мы все еще надеемся (т. Е. Назначаем студентам дату, которую они дали 5), и сценарий наихудшего случая, на который мы готовы принять (некоторые студенты, возможно, придется жить с 3) постепенно снижаются, пока не будет найдено решение. Если мы застряли, перезагрузите, понизьте ожидания и попробуйте снова. Задачи A и B назначаются первыми, а C выполняется только после того, как A и B завершены, поскольку ограничения на C гораздо менее строгие.
Я также использовал весовой коэффициент, чтобы смоделировать компромисс между максимизацией счастья учащихся и соблюдением ограничений на количество презентаций в день.
В настоящее время кажется, что можно найти решение практически для каждого случайного набора предпочтений. Я включил оценку метрики; соотношение между суммой значений предпочтений всех назначенных комбинаций "студент / дата" и суммой всех значений "идеал студента / топ-3". Например, если у студента 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%