Оптимизация распределения студентов по комнатам
Сегодня мы решим задачу о распределении студентов по комнатам в общежитии с учетом их основного и альтернативного пожеланий. Хотя формулировка довольно специфична, ее можно легко обобщить на похожие задачи, – тот же самый код годится для распределения игроков по столам в онлайновой карточной игре, для распределения ошибок между разработчиками в большом программном проекте и даже для распределения работы по дому между прислугой. Как и раньше, наша цель – собрать информацию об отдельных людях и найти такое сочетание, которое приводит к оптимальному результату.
В нашем примере будет пять двухместных комнат и десять претендующих на них студентов. У каждого студента есть основное и альтернативное пожелание.
# Двухместные комнаты
dorms = ['Zeus','Athena','Hercules','Bacchus','Pluto']
# Люди и два пожелания у каждого (основное, второстепенное)
prefs = [('Toby', ('Bacchus', 'Hercules')),
('Steve', ('Zeus', 'Pluto')),
('Karen', ('Athena', 'Zeus')),
('Sarah', ('Zeus', 'Pluto')),
('Dave', ('Athena', 'Bacchus')),
('Jeff', ('Hercules', 'Pluto')),
('Fred', ('Pluto', 'Athena')),
('Suzie', ('Bacchus', 'Hercules')),
('Laura', ('Bacchus', 'Hercules')),
('James', ('Hercules', 'Athena'))]
Сразу видно, что удовлетворить основное пожелание каждого человека не удастся, так как на два места в комнате Bacchus имеется три претендента. Поместить любого из этих трех в ту комнату, которую он указал в качестве альтернативы, тоже невозможно, так как в комнате Hercules всего два места.
В приведенном примере общее число вариантов порядка 100 000, то можно перебрать их все и найти оптимальный. Но если комнаты будут четырехместными, то количество вариантов будет исчислять триллионами.
Представление решения
# [9, 8, 7, 6,..., 1]
domain = [i for i in xrange(9, 0, -1)]
Целевая функция
Целевая функция работает следующим образом. Создается начальный список отсеков, и уже использованные отсеки из него удаляются. Стоимость вычисляется путем сравнения комнаты, в которую студент помещен, с двумя его пожеланиями. Стоимость не изменяется, если студенту досталась та комната, в которую он больше всего хотел поселиться; увеличивается на 1, если это второе из его пожеланий; и увеличивается на 3, если он вообще не хотел жить в этой комнате.
def dorm_cost(vec):
cost=0
# Создаем список отсеков, т.е. первые 2 места - 0 отсек и т.д.
slots = [0, 0, 1, 1, 2, 2, 3, 3, 4, 4]
# Цикл по студентам, i - порядковый номер студента
for i in xrange(len(vec)):
x = int(vec[i])
dorm = dorms[slots[x]]
pref = prefs[i][1]
print x, '->', slots[x],'->', prefs[i][0], pref, '->', dorm
# Стоимость основного пожелания равна 0, альтернативного – 1
# Если комната не входит в список пожеланий, стоимость увеличивается на 3
if pref[0] == dorm: cost += 0
elif pref[1] == dorm: cost += 1
else: cost += 3
# Удалить выбранны й отсек
# Это самое важное действие тут,
# прошу особо обратить на него внимание и учесть, что элементы сдвигаются
del slots[x]
return cost
При конструировании целевой функции полезно стремиться к тому, чтобы стоимость идеального решения (в данном случае каждый студент заселился в комнату, которую поставил на первое место в своем списке предпочтений) была равна нулю. В рассматриваемом примере мы уже убедились, что идеальное решение недостижимо, но, зная о том, что его стоимость равна нулю, можно оценить, насколько мы к нему приблизились. У этого правила есть еще одно достоинство – алгоритм оптимизации может прекратить поиск, если уже найдено идеальное решение.
Оптимизация
result, score = genetic_optimize(domain, dorm_cost)
print result, score
7 -> 3 -> Toby (‘Bacchus’, ‘Hercules’) -> Bacchus
1 -> 0 -> Steve (‘Zeus’, ‘Pluto’) -> Zeus
2 -> 1 -> Karen (‘Athena’, ‘Zeus’) -> Athena
0 -> 0 -> Sarah (‘Zeus’, ‘Pluto’) -> Zeus
0 -> 1 -> Dave (‘Athena’, ‘Bacchus’) -> Athena
1 -> 2 -> Jeff (‘Hercules’, ‘Pluto’) -> Hercules
2 -> 4 -> Fred (‘Pluto’, ‘Athena’) -> Pluto
1 -> 3 -> Suzie (‘Bacchus’, ‘Hercules’) -> Bacchus
0 -> 2 -> Laura (‘Bacchus’, ‘Hercules’) -> Hercules
Вместо вывода
Автор: Pavel Petropavlov
