Эвристика случайного поиска и теплоходы

    Когда-то давно я уже писал довольно большую статью об использовании эвристик в программировании, но сегодня я хочу привести небольшой практический пример. Этим летом я плавал на теплоходе по маршруту Москва — Ростов-на-Дону — Москва, и заметил, что каждый вечер директор круиза пытается найти оптимальную рассадку туристических групп по автобусам. Задача не такая сложная, но минимум 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, и, наконец, выполняем процедуру рассадки без всякой предварительной информации. Если на каком-то этапе, оценка улучшилась, полученное решение выводится.
    Действий, конечно, выполняется больше, но и ценность полученных результатов гораздо выше. На последок приведу небольшой пример работы программы:

    Понятно, что большинство из вас и так знает о эвристике случайного поиска, но вдруг этот пост прочитали люди, которые о ней не знают, или в силу каких-то причин боялись ей пользоваться. Надеюсь, теперь, чуть лучше узнав эту эвристику, вы сможете хотя бы немного упростить решение некоторых своих задач.
    Поделиться публикацией

    Комментарии 12

      0
      А в данном конкретном случае разве не лучше перебрать все возможные варианты распределения групп по автобусам (если у нас 3 автобуса и 15 групп, то понадобиться перебрать всего лишь 3^15 = 14 * 10^6 вариантов)? Если точно вести функцию, описывающую «оптимальность» расстановки, то мы меньше чем за секунду (при данных ограничениях) получим самое лучшее решение.

      P. S. я не в коем случае не пытаюсь сказать, что эвристические алгоритмы не нужны, только, что в данном случае можно обойтись без них (перебор всех вариантов пишется явно быстрее чем эти эвристики).
        0
        Я думал о переборе, но дело в том, что количество групп может очень сильно варьироваться, особенно на больших теплоходах. Но главная проблема даже не в этом. Довольно тяжело придумать оптимальную оценочную функцию, поэтому я остановился именно на том варианте, который описал.
        +4
        Для этой задачи рекомендую попробовать алгоритм имитации отжига (Simulated Annealing).
          +1
          Товарищи, а как же генетическая оптимизация?
            0
            А как же отдых? И генетические алгоритмы для такой задачи по-моему излишни.
              0
              почему так решили, кажется что трудоемкости больше? немало готовых программ, где сам генетический алгоритм уже реализован и только надо программировать постановку задачи в нотации ГА. Например вот программка Mendel 4
            –1
            Время дипломных проектов на хабре :)
              +4
              программист на отдыхе. я так как-то случайно сервер настроил в египте.
                0
                Потому что программист — это не профессия, это принцип жизни =)
                +2
                Для 3 автобусов по 50 человек + 20 групп получится 50^3*20=2500000=2.5e6 — динамическое программирование посчитает эту задачу без 3 пункта мгновенно. С третьим условием, если назначить, что неудачники — всегда последние группы, будет в несколько раз дольше. С 4 автобусами — нужно будет соптимизировать реализацию. От одного множителя 50 можно избавиться. Поскольку если мы рассмотрели k первых групп, то мы знаем сумму количества занятых мест.
                  –2
                  Да это понятно, но согласитесь, что написать случайное заполнение массива гораздо проще, чем манипулировать индексами в динамическом программировании.
                    +4
                    Динамическое программирование — простая штука. На написание графического интерфейса уйдет больше времени.

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое