За последние два дня я прочитал старый Java-код настольной игры. Хотя игра все еще компилируется и работает (она работает даже на устройстве Zaurus), сам код ужасен: никаких юнит-тестов, проблем с потоками, большого количества статических использований и смешанных обязанностей. Но потом я «заново открыл» мой старый проект TimeFinder , который намного лучше — по крайней мере, он имеет несколько юнит-тестов! Потом я увидел, что даже хочу опубликовать статью о прекрасном открытии, которое я сделал 3 года назад. Но я никогда не публиковал его, так как результаты были слишком разочаровывающими для меня в то время.
Тем не менее, я думаю, что идея все еще стоит распространять (вы можете избежать использования 
). Кстати, теперь вы знаете, почему мой блог начинается с «Find Time …» и почему мой ник в Twitter называется timetabling — это все об истории.
Мой черновик бумаги
Итак, вот моя «статья» « Оптимизация учебных планов с использованием венгерского алгоритма и итеративного локального поиска » со следующим основным результатом:
Алгоритм плох, когда дело доходит до оптимизации softconstraint (хотя он и не был разработан для этого), но он действительно хорош для того, чтобы уменьшить жесткие ограничения проблем с расписанием. Например, это было на порядок быстрее, чем 5-е место ( Мюллер с UniTime ) Международного конкурса Timetabling 2007. Конечно, я еще не сравнивал последнюю версию UniTtime с TimeFinder.
Дайте мне знать, что вы думаете!
Теперь я хотел бы немного поговорить о том, как в общем случае можно использовать алгоритмы присвоения во временном графике.
Использование алгоритмов присваивания во временном графике
В этой статье показано, как алгоритмы присваивания могут применяться в хронометражах. Нам известно лишь несколько работ, в которых используются алгоритмы присваивания, основанные на теории графов [Kin05, Bah04, MD77, TM02].
Алгоритм назначения можно использовать в качестве подпроцедуры эвристики, как это делается в приложении с открытым исходным кодом, которое называется TimeFinder [Kar08]. TimeFinder использует венгерский алгоритм только для назначения местоположения событию, где само решение улучшается с помощью эвристики, основанной на повторном локальном поиске [SLM03], мы назвали эту эвристику NoCollisionPrinciple .
Другая возможность состоит в том, чтобы использовать алгоритмы назначения в качестве «основы» эвристики, как это сделано в [Bah04], где венгерский алгоритм модифицирован, чтобы действовать в качестве алгоритма оптимизации хронометража. Третий подход заключается в использовании алгоритма назначения в качестве предварительный решатель другого алгоритма. Это запланировано для проекта TimeFinder: перед использованием алгоритма UniTime, основанного на ограничениях, будет использоваться алгоритм назначения, чтобы дать хорошую и быструю отправную точку, где все жесткие ограничения действительны.
Во всех случаях хорошая производительность и оптимальные результаты математически обоснованной техники являются причиной их выбора и обещают хороший алгоритм выполнения.
Эвристика пытается добавлять и удалять события в определенные временные интервалы очень часто. Таким образом, проверка наличия места для события E1 во временном интервале должна быть очень быстрой. Но если в этом временном интервале уже много комнат и событий, то простым тестом сложно проверить, существует ли действительная комната для E1. Здесь алгоритмы назначения пришли мне на помощь. Другие алгоритмы, такие как алгоритм аукциона, также могут решить проблему назначения, но здесь они не обсуждаются.
Примером одной матрицы затрат, где мы хотим вычислить минимальное взвешенное соответствие («наилучшее назначение») позже, может быть следующее:
Rooms \ Events | E1 E2 ------------------------ R1 | 12 10 R2 | 16 3
Записи матрицы представляют собой разницу мест для посетителей. Например, (E2, R2) = 3 означает, что будет 3 свободных места, что лучше, чем (E2, R1) = 10 свободных мест.
Чтобы оптимизировать назначения комнаты на событие, необходимо, чтобы назначенная комната имела почти такое же или несколько большее количество мест, что и на событии E1, где присутствуют посетители. Разница не должна быть слишком большой, чтобы места не были «потрачены впустую» (и событие с большим количеством посетителей может быть назначено позже)
Конечно, может оказаться, что запись недействительна (например, слишком много посетителей), тогда значение в матрице + бесконечность.
Лучшее решение (минимальная сумма) здесь будет E1, R1 и E2, R2 с общей суммой 15.
Некоторые сведения о словах в теории графов: эта матрица затрат эквивалентна взвешенному, ненаправленному, двунаправленному, полному графу G. Средневзвешенное означает с числами вместо логических значений; неориентированный означает одно и то же значение для (Ex, Ry) и (Ry, Ex); двухраздельное означает, что график может быть разделен на два набора A и B, где «A и B = пусто» и «A или B = G»; «завершить» означает, что матрица затрат имеет одинаковое количество строк и столбцов, вы всегда можете принудительно задать это с помощью значений + бесконечность.
Алгоритмы назначения
Самый простой способ правильно решить задачу присваивания — это алгоритм грубой силы, который очень медленный для больших n: O (n!).
(Хорошо, это даже медленно для малых n = 10: 10! = 3628800)
Где n в моем случае — количество комнат, доступных в одном временном интервале. Но этот алгоритм всегда верен, потому что он пробует все комбинации назначений и выбирает тот с минимальной общей суммой. Я использовал этот алгоритм для проверки правильности других алгоритмов назначения, которые я реализовал позже.
Теперь приятно знать, что существует еще один очень быстрый и правильный алгоритм, который называется Kuhn-Munkres [1] или венгерский алгоритм . Время работы O (n³) (10³ = 1000), и идеи, используемые в этом алгоритме, основаны на теории графов. Другой оптимизацией, которую можно использовать только в особых случаях, является алгоритм инкрементного назначения с O (n²) (например, «добавить одно назначение» или «удалить одно назначение»)
И есть еще более быстрые алгоритмы, такие как алгоритм Эдмонса и Карпа [2]. Для двудольных графов он работает в O (mn log n).
Интересным подходом являются алгоритмы назначения приближений, которые могут быть намного быстрее: O (n²) с небольшой константой. Но полученные задания не являются лучшими в каждом случае.
Хорошо известный и простой в реализации алгоритм роста траектории от Дрейка и Хугарди [3], который работает следующим образом:
currentMatching = matching0 = empty
matching1 = empty
while edges are not empty
choose a node x from all nodes which has at least one neighbor
while x has a neighbor
find the heaviest edge e={x,y} incident to x
add it to the currentMatching
if(currentMatching == matching1) currentMatching = matching0
else currentMatching = matching1
remove x from the graph
x:=y
end
end
Хорошая вещь этого алгоритма в том, что вы можете сказать, что. о полученном назначении: общая сумма максимальна в два раза выше, чем сумма, полученная с помощью оптимального алгоритма. Есть еще лучшие гарантии, например, Петти и Сандерс (максимум в 3/2 раза выше):
matching is empty repeat k times choose a node x from all nodes at random matching := matching (+) aug(x) end return matching
Ресурсы
Вы можете получить источник TimeFinder (Apache2 лицензирован) через svn:
svn checkout https://timefinder.svn.sourceforge.net/svnroot/timefinder/trunk timefinder
Тогда посмотри в посылку
timefinder-core/src/main/java/de/timefinder/core/algo/
Чтобы построить его, вы должны использовать Maven .
И наконец, вот статья, где идея максимального потока сети уже была представлена:
Джон ван ден Брук, Кор А. Дж. Хюркенс и Герхард Дж. Вёджингер. Проблемы с расписанием в ТУ Эйндховена. Электронные заметки по дискретной математике, 25: 27–28, 2006.
Рекомендации
[1] Кун Мункрес , «Алгоритмы для задач назначения и транспортировки»
[2] Эдмондс и Карп , « Теоретические улучшения алгоритмической эффективности для задач сетевого потока ».
[3] Дрейк и Хугарди. Алгоритм простого приближения для взвешенной задачи согласования, 2002 г.
[4] Петти и Сандерс . Упрощенное линейное время 2/3 — эпсилон-аппроксимация для сопоставления максимального веса , инф. Процесс. Lett. Том 91, № 6, 2004
От http://karussell.wordpress.com/2012/01/22/assignment-algorithms-automated-timetabling/