Эвристика случайного поиска и теплоходы
Когда-то давно я уже писал довольно большую статью об использовании эвристик в программировании, но сегодня я хочу привести небольшой практический пример. Этим летом я плавал на теплоходе по маршруту Москва — Ростов-на-Дону — Москва, и заметил, что каждый вечер директор круиза пытается найти оптимальную рассадку туристических групп по автобусам. Задача не такая сложная, но минимум 15 минут в день на её решение тратится. Разумеется, я попробовал автоматизировать этот процесс.
Но, прежде чем описывать моё решение, необходимо более точно сформулировать задачу. В самом начале круиза всех туристов распределили по нескольким экскурсионным группам (в рассматриваемом случае групп было 15), при этом в каждой группе было не более 10 человек. Все группы пронумеровали по порядку, и полученный список групп не изменялся до самого конца круиза. Выглядел этот список примерно так:
1. Группы не разбивать;
2. Заполнять автобусы максимально равномерно;
3. Желательно, чтобы группы, сидящие в одном автобусе, шли подряд. Т.е. первый автобус — группы 1-5, второй автобус 6-10 и т.д.
Первый шаг к автоматизации был сделан с помощью Excel и надстройки «Поиск решения» (к моему удивлению об этой настройке знает очень мало людей, хотя штука безумно полезная).
И тут я вспомнил о эвристике случайного поиска. Если честно, я никогда раньше не использовал её, и был почти уверен, что случайный поиск не приведёт к эффективному решению. Но любопытство взяло верх. В итоге получился следующий алгоритм рассадки:
1. Выбираем случайную группу и случайный автобус
2. Проверяем можем ли мы посадить выбранную группу в выбранный автобус (смотрим, не сидит ли данная группа в другом автобусе, и достаточно ли мест)
2.1. Если не можем, то увеличиваем счётчик неудачных попыток на единицу
2.2. Если можем, обнуляем счётчик неудачных попыток
3. Если количество неудачных попыток превысило 50, выходим из цикла, иначе к п. 1
4. Проверить все ли группы рассажены
4.1. Если все, посчитать максимальную разницу между количеством пустых мест в автобусах (именно это число будет считаться оценкой)
4.2. Если не все, сообщить о неудачной рассадке.
Выполняя эту процедуру сотни раз, мы можем выбрать рассадку с наилучшей оценкой. Это алгоритм сработал на удивление хорошо. По крайней мере и первый, и второй пункты требований были выполнены идеально.
Чтобы выполнить третий пункт, в алгоритм необходимо внести небольшое изменение. Ещё до начала выполнения алгоритма рассадки посадим в каждый автобус по 5 групп (1-5,6-10,11-15), и выполним рассадку. Если она удалась, запоминаем лучшую оценку, а результат выводим. Потом пробуем посадить в каждый автобус по 4 группы (1-4, 5-8,...), и снова выполняем рассадку. Если полученная оценка оказалась лучше, чем была на предыдущем этапе, запоминаем её и снова выводим результат. Потом пробуем посадить в автобус изначально по 3 группы, по 2, по 1, и, наконец, выполняем процедуру рассадки без всякой предварительной информации. Если на каком-то этапе, оценка улучшилась, полученное решение выводится.
Действий, конечно, выполняется больше, но и ценность полученных результатов гораздо выше. На последок приведу небольшой пример работы программы:
Понятно, что большинство из вас и так знает о эвристике случайного поиска, но вдруг этот пост прочитали люди, которые о ней не знают, или в силу каких-то причин боялись ей пользоваться. Надеюсь, теперь, чуть лучше узнав эту эвристику, вы сможете хотя бы немного упростить решение некоторых своих задач.