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

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

Рис. 5.26. «Кругосветное путешествие» Гамильтона.

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

Этот граф породила игра, представляющая земной шар в форме додекаэдра. Данная задача «кругосветного путешествия с возвращением в исходную точку», известная также как задача о гамильтоновом цикле, связана с теорией групп, а также (неожиданным образом) с задачей о четырех красках, рассмотренной в предыдущем разделе.

Особенностью задачи о коммивояжере является необходимость дополнительно учитывать расстояния от города до города, которые предполагаются известными. Эти «расстояния»

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

Итак, пусть, например, наш коммивояжер должен посетить поочередно шесть городов (соответствующие стоимости указаны в табл. 5.3). Заранее, когда зафиксирован исходный пункт,

Таблица 5.3. Матрица расстояний для задачи о коммивояжере

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

(см. скан)

5.11.1. Первый этап: поиск решения

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

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

Тем не менее попробуем использовать этот способ. Из города С мы отправимся в город по дуге с нулевой стоимостью; дуга которая сразу же завершила бы данный цикл, запрещена. Поэтому мы «уедем» из города воспользовавшись первой же разрешенной дугой — стоимость которой равна 5; дуга запрещена. Теперь пойдем по дуге (стоимость 1), запрещающей использование дуги Дуга позволяет уйти из и запрещает приводит нас в Л, а дуга наконец, вынужденным образом завершает цикл. Ее стоимость равна 43, но она могла бы оказаться еще больше. Мы все-таки запомним полученное решение (стоимость 79), которое лучше предыдущего.

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

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

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

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

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

Таблица 5.4. (см. скан) Матрица, в которой устранены слишком дорогостоящие пути

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

Что же теперь из этого следует? Были ли мы настроены слишком оптимистично? Из табл. 5.4 видно, что в первой строке мы располагаем единственной возможностью: из А мы можем попасть только в Следовательно, дуга по которой можно вернуться обратно, запрещена. Кроме того, поскольку в мы уже были, мы должны вычеркнуть дуги и которые опять привели бы нас в ту же точку (табл. 5.5).

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

Таблица 5.5 (см. скан)

На этом этапе все степени свободы но горизонтали и вертикали равны 2. Поэтому следующую дугу мы должны действительно выбирать. Например, из самой «дорогой» строки мы можем взять дугу, имеющую наименьшую стоимость.

Рис. 5.27. Частичное решение задачи о коммивояжере.

Мы выбираем и тогда дуги и оказываются запрещенными, а дуги и — обязательными.

Итак, мы в конце концов получили гамильтонов цикл — и его стоимость (64) меньше, чем лучшая из найденных ранее. Таким образом, мы реализовали способ быстрого нахождения хорошего, допустимого правилами маршрута для коммивояжера.

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

Получив хорошее решение, следует перейти к фазе оптимизации.

5.11.2. Второй этап: поиск оптимального решения

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

и нижнюю грань. Иначе говоря, не существует ли какого-нибудь понятия (вроде клики), которое позволило бы нам утверждать, что стоимость любого решения заведомо не меньше некоторой известной величины?

Выделим в исходной задаче какую-нибудь подзадачу и займемся рассуждениями. Нужно, чтобы решение этой более простой или «маленькой» задачи оказалось обязательно меньшим по стоимости, чем решение исходной задачи. Так, рассмотрим все города отдельности: ведь в тот или иной момент коммивояжер уезжает из каждого города. Но тогда стоимость решения данной подзадачи — «уехать из города — не может быть меньше минимального значения соответствующей строки исходной матрицы. Так, для города А, где

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

Рассуждая аналогично для пяти оставшихся строк, мы вычитаем из строки А число 16, из В число 1, из С число 0, из число 16, из Е и число 5 и получаем табл. 5.6.

Таблица 5.6

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

Таблица 5.7 (см. скан)

минимальная стоимость приезда в который составляет 5. Мы можем вычесть из всего столбца эту величину, поскольку подзадача приезда в А обязательно должна быть решена. Новые стоимости приведены в табл. 5.7. Мы вычли величину

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

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

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

Таблица 5.8 (см. скан)

Теперь осталось построить на этой матрице новый маршрут, обладающий, если это возможно, стоимостью, меньшей а потом начать все сначала — и так до тех пор, пока мы не докажем оптимальность.

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

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

Некоторые из дуг с нулевыми стоимостями не могут быть включены в маршрут." Тогда встает вопрос: какова минимальная стоимость запрета на «поездку» по дуге с нулевой стоимостью? Поскольку в любом случае мы должны уехать из города, расположенного в данном столбце, минимальная стоимость этого перемещения составит сумму минимального значения стоимости по горизонтали (наш нуль не считается) и минимального значения стоимости по вертикали. Эта величина, используемая во многих задачах на оптимизацию, обычно называется пошлиной. Она вычисляется для идеального варианта, который состоит в выборе дуги с нулевой стоимостью, и оценивает наименьшую стоимость — минимальную пошлину, которую нужно заплатить при отказе от этого выбора.

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

записывается в виде

Таким образом, в нашем примере

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

Таблица 5.9. (см. скан)

Ниже приводится рабочая таблица (табл. 5.9, а).

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

Вычислим пошлины: Приняв первое предположение, мы обязательно должны пропустить коммивояжера по дуге поскольку в противном случае минимальная стоимость полученного маршрута (она была бы равна превысит 64 — порог, который мы знаем из уже найденного решения и который мы хотели улучшить.

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

результате мы получаем новую таблицу (табл. 5.10, а). После вычитания двух единиц по горизонтали вследствие чего остановится равным 51, мы получаем еще один вариант таблицы (табл. 5.10, б). Теперь только дуга (ее стоимость равна 13) является слишком «дорогостоящей» для того, чтобы составить часть маршрута, обладающего стоимостью меньше заданной предельной; действительно, стоимость Следовательно эту дугу мы вычеркнем.

Таблица 5.10. (см. скан)

На этот раз мы больше не располагаем возможностью выбора: дуга осталась в своей строке одна; нужно добавить ее к нашему незавершенному циклу и удалить дугу Кроме того, единственным кандидатом оказалась дуга (поэтому нет смысла производить в соответствующей строке вычитание), что дает нам и влечет за собой одновременное вхождение в данный цикл дуг и . В конце концов мы получаем маршрут с суммарной стоимостью 63. Дерево поиска изображено на рис. 5.28.

У нас нет гарантии, что полученный цикл является оптимальным, поскольку на дереве остается еще одна ветвь, которая может привести к результату, обладающему приемлемой стоимостью. Эта ветвь соответствует отрицанию нашего первого предположения, т. е. случаю, когда искомый цикл не проходит по дуге Мы восстанавливаем исходную матрицу для этого варианта с учетом необходимых преобразований строки А. Так как мы вычитаем довольно большое число, мы должны вычеркнуть новые дуги — все, стоимость которых не меньше величины (не В результате остается табл. 5.11, из которой видио, что (строка С) и (столбец С) являются обязательными. Если граф содержит более двух вершин, такая ситуация невозможна. Это доказывает, что

Рис. 5.28. (см. скан) Решеиие задачи о коммивояжере.

на данной ветви нет ни одного решения со стоимостью меньше 63 и полученный раньше цикл является оптимальным.

Таблица 5.11 (см. скан)

Мы можем также доказать, что это оптимальное решение является единственным. Для этого достаточно опять ввести в предыдущую матрицу всего лишь одну дугу стоимостью 5 (дугу

Дуги и окажутся обязательными, и мы должны будем включить в наш цикл дугу Но тогда, чтобы не превысить стоимость 63, нам придется рассматривать только нулевые стоимости. Включение же в цикл дуги приведет к тому, что в столбце В будут вычеркнуты все приемлемые дуги.

Итак, единственный оптимальный маршрут для нашего коммивояжера — это (стоимость 63).