Когда-то давно я уже писал довольно большую статью об использовании эвристик в программировании, но сегодня я хочу привести небольшой практический пример. Этим летом я плавал на теплоходе по маршруту Москва — Ростов-на-Дону — Москва, и заметил, что каждый вечер директор круиза пытается найти оптимальную рассадку туристических групп по автобусам. Задача не такая сложная, но минимум 15 минут в день на её решение тратится. Разумеется, я попробовал автоматизировать этот процесс.
Но, прежде чем описывать моё решение, необходимо более точно сформулировать задачу. В самом начале круиза всех туристов распределили по нескольким экскурсионным группам (в рассматриваемом случае групп было 15), при этом в каждой группе было не более 10 человек. Все группы пронумеровали по порядку, и полученный список групп не изменялся до самого конца круиза. Выглядел этот список примерно так:
Каждый день туристы оповещают директора круиза о том, на какие экскурсии они планируют пойти. Всех, кто не планирует идти на основную экскурсию, из этого списка вычёркивают. Именно с модифицированным списком нам и предстоит работать. Директор круиза считает сколько человек идёт на экскурсию (обычно 100-120 человек) и делает соответствующий заказ на автобусы. Турфирмы на берегу этот заказ принимают и сообщают следующие сведения: «На причале вас будет ждать три автобуса на 48, 48 и 50 мест». В итоге задача получается следующей: необходимо рассадить туристов в автобусы, соблюдая следующие требования (в порядке важности):
1. Группы не разбивать;
2. Заполнять автобусы максимально равномерно;
3. Желательно, чтобы группы, сидящие в одном автобусе, шли подряд. Т.е. первый автобус — группы 1-5, второй автобус 6-10 и т.д.
Первый шаг к автоматизации был сделан с помощью Excel и надстройки «Поиск решения» (к моему удивлению об этой настройке знает очень мало людей, хотя штука безумно полезная).
Первое требование, конечно, выполнялось, но о втором и третьем требовании пришлось забыть. Учитывая, что поиск решения занимал на стареньком ноутбуке около 15 секунд, было принято решение писать свой велосипед. Но тут опять стал вопрос, каким образом всё это делать: симплекс-метод, динамическое программирование, метод ветвей и границ, эвристики? Наверняка есть какой-то сложный алгоритм, который поможет в решении этой задачи, но писать что-то сложное на отдыхе, да потом отлаживать на ноутбуке с маленьким экраном? Я решил попробовать какую-нибудь эвристику. Восхождение на холм я сразу отложил после небольших раздумий, равно как и эвристики минимальной стоимости и сбалансированной прибыли.
И тут я вспомнил о эвристике случайного поиска. Если честно, я никогда раньше не использовал её, и был почти уверен, что случайный поиск не приведёт к эффективному решению. Но любопытство взяло верх. В итоге получился следующий алгоритм рассадки:
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, и, наконец, выполняем процедуру рассадки без всякой предварительной информации. Если на каком-то этапе, оценка улучшилась, полученное решение выводится.
Действий, конечно, выполняется больше, но и ценность полученных результатов гораздо выше. На последок приведу небольшой пример работы программы:
Понятно, что большинство из вас и так знает о эвристике случайного поиска, но вдруг этот пост прочитали люди, которые о ней не знают, или в силу каких-то причин боялись ей пользоваться. Надеюсь, теперь, чуть лучше узнав эту эвристику, вы сможете хотя бы немного упростить решение некоторых своих задач.
Но, прежде чем описывать моё решение, необходимо более точно сформулировать задачу. В самом начале круиза всех туристов распределили по нескольким экскурсионным группам (в рассматриваемом случае групп было 15), при этом в каждой группе было не более 10 человек. Все группы пронумеровали по порядку, и полученный список групп не изменялся до самого конца круиза. Выглядел этот список примерно так:
Каждый день туристы оповещают директора круиза о том, на какие экскурсии они планируют пойти. Всех, кто не планирует идти на основную экскурсию, из этого списка вычёркивают. Именно с модифицированным списком нам и предстоит работать. Директор круиза считает сколько человек идёт на экскурсию (обычно 100-120 человек) и делает соответствующий заказ на автобусы. Турфирмы на берегу этот заказ принимают и сообщают следующие сведения: «На причале вас будет ждать три автобуса на 48, 48 и 50 мест». В итоге задача получается следующей: необходимо рассадить туристов в автобусы, соблюдая следующие требования (в порядке важности):1. Группы не разбивать;
2. Заполнять автобусы максимально равномерно;
3. Желательно, чтобы группы, сидящие в одном автобусе, шли подряд. Т.е. первый автобус — группы 1-5, второй автобус 6-10 и т.д.
Первый шаг к автоматизации был сделан с помощью Excel и надстройки «Поиск решения» (к моему удивлению об этой настройке знает очень мало людей, хотя штука безумно полезная).
Первое требование, конечно, выполнялось, но о втором и третьем требовании пришлось забыть. Учитывая, что поиск решения занимал на стареньком ноутбуке около 15 секунд, было принято решение писать свой велосипед. Но тут опять стал вопрос, каким образом всё это делать: симплекс-метод, динамическое программирование, метод ветвей и границ, эвристики? Наверняка есть какой-то сложный алгоритм, который поможет в решении этой задачи, но писать что-то сложное на отдыхе, да потом отлаживать на ноутбуке с маленьким экраном? Я решил попробовать какую-нибудь эвристику. Восхождение на холм я сразу отложил после небольших раздумий, равно как и эвристики минимальной стоимости и сбалансированной прибыли.И тут я вспомнил о эвристике случайного поиска. Если честно, я никогда раньше не использовал её, и был почти уверен, что случайный поиск не приведёт к эффективному решению. Но любопытство взяло верх. В итоге получился следующий алгоритм рассадки:
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, и, наконец, выполняем процедуру рассадки без всякой предварительной информации. Если на каком-то этапе, оценка улучшилась, полученное решение выводится.
Действий, конечно, выполняется больше, но и ценность полученных результатов гораздо выше. На последок приведу небольшой пример работы программы:
Понятно, что большинство из вас и так знает о эвристике случайного поиска, но вдруг этот пост прочитали люди, которые о ней не знают, или в силу каких-то причин боялись ей пользоваться. Надеюсь, теперь, чуть лучше узнав эту эвристику, вы сможете хотя бы немного упростить решение некоторых своих задач.
