Задача о коммивояжере

Описание условий и постановка задачи

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

По-видимому, впервые этой задачей стали заниматься благодаря одной головоломке, придуманной английским математиком Гамильтоном в 1859 г. Она состояла в том, чтобы вычислить на графе все возможные маршруты, которыми может воспользоваться путешественник ( задача о гамильтоновском цикле ).

Этот граф породила игра, представляющая земной шар в форме додекаэдра. Поэтому её называют также задачей "кругосветного путешествия с возвращением в исходную точку".

Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти "расстояния" можно заменить на количество затраченного времени, стоимость проезда или предполагать другие произвольные значения. В общем случае мы даже не предполагаем, что стоимость проезда из I в J обязательно совпадает со стоимостью обратного проезда из I в J. Данная задача соединяет в себе простоту условия и сложность решения, обусловленную большими размерами поискового пространства.

Класс недетерминированных полиномиальных задач.

Задачи данного типа, как например задача о рюкзаке, задачи оптимального раскроя, оптимизация воздушных маршрутов, задачи диагностики, невозможно отнести ни к классу полиномиальных (P), ни к классу экспоненциальных (E) задач, то есть для их решения не найдено полиномиальных алгоритмов, и в их условиях не содержится экспоненциальных вычислений. Кроме этого была доказана их взаимная эквивалентность, то есть если удастся построить хотя бы для одной из задач хороший алгоритм ( полиномиальный ), то все они автоматически будут разрешены. Все перечисленные задачи относят к недетерминированным полиномиальным задачам (NP).

Для решения задачи класса NP, мы не располагаем ни явной формулой, ни рекурсивными выражениями приемлемой сложности. Поэтому остается два способа решения : построение действенного алгоритма подсчета или метод перебора.

Полиномиальный алгоритм можно представить абстрактной моделью детерминированной машины Тьюринта (ДМТ), то есть черным ящиком, который умеет выполнять только заданное число элементарных операций ( + , - , * , /, ИЛИ , И , ЧИТАТЬ , ПИСАТЬ , ЕСЛИ... ТО... , ПОВТОРЯТЬ ).В заданный момент автомат находится в строго определенном состоянии, за один шаг совершает одно действие, обусловленное этим состоянием. Модель недетерминированной машины Тьюринга (НДМТ) отличается тем, что помимо обычного набора инструкций, в ней существует специальная инструкция "ВЫБОР [E]", которая создает столько копий текущего состояния, сколько существует элементов во множестве E. Остановка происходит в момент достижения одной из возникших копий инструкции КОНЕЦ. Абстрактная модель НДТМ позволяет создать механизм перебора, то есть продвижения на ощупь, с совершением предварительных попыток.

Метод полного перебора.

Методы перебора и распространения ограничений предполагает, что пространство поиска Х является конечным и дискретным, все точки Х отделены друг от друга. Это полностью выполнено для задачи о коммивояжере. Одним из таких методов, дающих решение для задачи, является метод полного перебора. Метод надежен и прост, он заключается в вычислении всех возможных путей, определении стоимостей каждого, нахождении среди всех стоимостей минимума. Недостаток в том, что метод хорошо работает , если мощность множества не превышает некоторго числа. Заранее, когда зафиксирован исходный пункт в задаче о коммивояжере, мы располагаем числом различных маршрутов, равным числу перестановок из (n-1) городов, то есть (n-1)!, то есть размеры поискового пространства огромны. Поэтому такой подход не рационален из-за большого числа вычислений и сохранения огромного числа данных.

Динамическое программирование.

Для решения задачи лучше использовать процесс последовательной оптимизации, который осуществляется методами динамического программирования. Основная идея этих методов заключается в том, что неизвестные соответствующей системы рассматриваются как переменные решения, значения для которых надо выбирать последовательно. Если два набора решений приводят к одной и той же ситуации, то сохраняется наилучший из них. Все подходящие значения каждой переменной изучаются параллельно.

Основная теорема теории динамического программирования может быть сформулирована следующим образом: подстратегия оптимальной стратегии может быть только оптимальной. Выигрыш достигается за счет того, что на каждом из промежуточных этапов сравниваются все пути, ведущие к некоторой фиксированной ситуации, а в дальнейшем сохраняется только наилучший из этих путей. Именно с помощью теории динамического программирования создана схема решения задачи о коммивояжере.

Алгоритмы поиска оптимального решения.

Поиск одного решения.

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

На первый взгляд, легче всего найти оптимальный путь способом, при котором мы отправляемся из исходного пункта и всегда выбираем путь с наименьшей стоимостью. Но он, безусловно, не является оптимальным и даже может приводить к очень неудачным решениям. Действительно, условия К(х), в данном случае заключающиеся в том, что мы должны получить в конечном счете только один цикл, по мере нашего продвижения вперед все больше и больше ограничивают возможности выбора, и если вначале мы выберем небольшие значения скоростей , то значения стоимостей в конце пути будут обязательными, и могут оказаться сколь угодно большими. Тем не менее необходимо найти одним из предложенных вариантов какой-либо один путь, с тем, что иметь хотя бы одно значение стоимости итогового пути для сравнения с полученным. Таким образом, мы получаем как бы верхнюю грань для решения. Оптимальное решение не может быть больше уже полученного. Нужно заметить, что от начального значения может зависеть успешное нахождение оптимального алгоритма. Лучше, чтобы оно было как можно меньше, а следовательно, на первом этапе нужна своя оптимизация.

Определение нижней грани решения.

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

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

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

Оценка элементов матрицы.

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

Вычисление пошлин.

Для матрицы с уменьшенными стоимостями и вычеркнутыми неоптимальными дугами необходимо определить оптимальный путь. Естественно, прежде всего рассмотреть выгоду от использования дуг с наименьшими ( нулевыми ) стоимостями. Идеальный маршрут должен был бы проходить только по дугам с нулевой стоимостью, но практически он никогда не существует. Могут существуют дуги с нулевой стоимостью, которые не могут быть включены в маршрут ( две нулевые дуги в одном столбце). Поэтому необходимо выяснить : какова минимальная стоимость запрета на поездку по дуге с нулевой стоимостью ? Поскольку коммивояжер должен уехать из города, расположенного в столбце, минимальная стоимость этого перемещения составит сумму минимального значения стоимости по горизонтали и минимального значения по вертикали, исключая саму нулевую величину. Величину этого запрета называют пошлиной. Вычисляя пошлину для каждой нулевой дуги, можно оценить наименьшую стоимость, которую нужно заплатить при отказе от выбора этой дуги.

Стратегия выбора дуг.

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

Учет паразитных ветвей и циклов.

После выбора определенной дуги необходимо предусмотреть невозможность возникновения паразитных ветвей и циклов. Паразитный цикл возникает в случае замыкания пути в одном городе раньше, чем пройдены все города. Поэтому выбор дуги I J влечет за собой запрет на рассмотрение дуг, которые приводят в город J ( столбец J ) и которые выходят из I ( строка I ). Кроме этого необходимо запретить возврата в I по дуге JI. Самым сложным в проверке паразитных циклов является определение ситуаций вида ABCA, ABCDA и подобных, то есть когда замыкание происходит через два, три и более города. Тем не менее все эти ситуации должны быть выявлены и запрещены, иначе получить решение не представляется возможным.

Следующая страница: Информационно-измерительные технологии VXI