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

Задача о коммивояжере удивительно просто формулируется: коммивояжер, выходящий из какого-нибудь города, желает посетить (n-1) других городов и вернуться к исходному пункту. Известны расстояния между всеми этими городами. Требуется установить в каком порядке он должен посещать города, чтобы общее пройденное расстояние было минимальным.

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

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

1 Задача Де-Мере заключается в следующем: два игрока условились сыграть ряд партий, выигравшим считается тот, кто первым выиграл S партий. Игра была прервана тогда, когда один из игроков выиграл a(a 2 Паскаль, Блез (1623—1661 гг.)— выдающийся французский математик и физик, автор большого числа работ по геометрии, теории чисел, теории вероятностей и т. д. В 1641 г. одним из первых сконструировал суммирующий автомат.

3 Борель, Эмиль (1871—1956 гг.)— французский математик, известен своими работами в области анализа, теории множеств и теории вероятностей.

В самом деле, выходя из первого города, коммивояжер может направиться в один из (n— 1) городов, откуда в один из (n-2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число вариантов, подлежащих просмотру, составляет (n— 1) (n —2) .2- 1 = (n— 1)! вариантов. С увеличением числа городов это число чрезвычайно быстро возрастает и уже при 15—20 городах достигает астрономических цифр. Пропорционально возрастает и время на перебор этих вариантов. Поэтому от полного перебора всех вариантов приходится с самого начала отказаться из-за невозможности уложиться в любое разумно назначенное время, а вот поиск методов (алгоритмов), позволяющих быстро находить оптимальный маршрут оказался чрезвычайно трудным.

О трудности отыскания таких алгоритмов говорит хотя бы тот факт, что за решение одного из контрольных вариантов задачи (для 33 городов) некая мыловаренная компания США установила премию в 10000 долларов. Только несколько человек угадали оптимальный маршрут, но и их ответы не были признаны решением, поскольку, помимо четких математических предписаний, допускалось применение не более 25 слов текста для обоснования догадки.

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

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

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

Наивная постановки задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 3, . . . , n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы, как говорят соискатели, обнаучить задачу, введем некоторые термины. Итак, города перенумерованы числами j= {1, 2, ., n}. Тур коммивояжера может быть описан циклической перестановкой t=(j1, j2, j3,., jn, j1), причем вce j1, j2, j3,., jn разные номера; повторяющийся в начале и конце j1 показывает, что перестановка зациклена. Расстояния между парами вершин cij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

Задача о коммивояжере удивительно просто формулируется: коммивояжер, выходящий из какого-нибудь города, желает посетить (n-1) других городов и вернуться к исходному пункту. Известны расстояния между всеми этими городами. Требуется установить в каком порядке он должен посещать города, чтобы общее пройденное расстояние было минимальным.

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

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

1 Задача Де-Мере заключается в следующем: два игрока условились сыграть ряд партий, выигравшим считается тот, кто первым выиграл S партий. Игра была прервана тогда, когда один из игроков выиграл a(a 2 Паскаль, Блез (1623—1661 гг.)— выдающийся французский математик и физик, автор большого числа работ по геометрии, теории чисел, теории вероятностей и т. д. В 1641 г. одним из первых сконструировал суммирующий автомат.

3 Борель, Эмиль (1871—1956 гг.)— французский математик, известен своими работами в области анализа, теории множеств и теории вероятностей.

В самом деле, выходя из первого города, коммивояжер может направиться в один из (n— 1) городов, откуда в один из (n-2) оставшихся городов и т. д., пока не останется один-единственный город, откуда он вышел. Таким образом, общее число вариантов, подлежащих просмотру, составляет (n— 1) (n —2) .2- 1 = (n— 1)! вариантов. С увеличением числа городов это число чрезвычайно быстро возрастает и уже при 15—20 городах достигает астрономических цифр. Пропорционально возрастает и время на перебор этих вариантов. Поэтому от полного перебора всех вариантов приходится с самого начала отказаться из-за невозможности уложиться в любое разумно назначенное время, а вот поиск методов (алгоритмов), позволяющих быстро находить оптимальный маршрут оказался чрезвычайно трудным.

О трудности отыскания таких алгоритмов говорит хотя бы тот факт, что за решение одного из контрольных вариантов задачи (для 33 городов) некая мыловаренная компания США установила премию в 10000 долларов. Только несколько человек угадали оптимальный маршрут, но и их ответы не были признаны решением, поскольку, помимо четких математических предписаний, допускалось применение не более 25 слов текста для обоснования догадки.

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

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

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

Наивная постановки задачи следующая.

Коммивояжер (бродячий торговец) должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 3, . . . , n и вернуться в первый город. Расстояния между всеми городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

Чтобы, как говорят соискатели, обнаучить задачу, введем некоторые термины. Итак, города перенумерованы числами j= {1, 2, ., n}. Тур коммивояжера может быть описан циклической перестановкой t=(j1, j2, j3,., jn, j1), причем вce j1, j2, j3,., jn разные номера; повторяющийся в начале и конце j1 показывает, что перестановка зациклена. Расстояния между парами вершин cij образуют матрицу С. Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать функционал

L=L(t)=∑ cik*tk+1 (1)

где jn+1=jn, а суммирование ведется по k от 1 до n. Относительно математизированной формулировки задачи коммивояжера уместно сделать два замечания.

Во-первых, в наивной постановке сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех i, j

cij ≥ 0, cii=∞ (2)

(последнее равенство означает запрет на петли в туре); симметричными, т.е. для всех i,j

cij =cji (3)

и удовлетворять неравенству треугольника, т.е. для всех i, j, k

cij + cij ≥ cjk (4)

В математической постановке говорится о произвольной матрице С. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2) —(4) не удовлетворяют. Особенно часто нарушается условие (3) (например, если сij — не расстояние, а плата за проезд: мы уже привыкли, что железнодорожный билет Харьков — Москва отличается по цене от билета Москва — Харьков). Поэтому мы будем различать два варианта задачи о коммивояжере— симметричную задачу, когда условие (3) выполнено и несимметричную в противном случае. Условия (2) и (4) по умолчанию мы будем считать выполненными.

Второе замечание касается числа всех возможных туров. В несимметричной задаче о коммивояжере туры t=(j1, j2, j3,., jn, j1) и t'=(j1, jn, ., j2, j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!

Зафиксируем на первом и последнем месте в циклической перестановке номер j1, а оставшиеся n-1 номеров переставим всеми (n-1)! возможными способами. В результате получим все несимметричные туры. А симметричных туров имеется в два раза меньше, ибо каждый засчитан как два раза: как t и как t'.

Можно представить, что С состоит только из единиц и нулей. Тогда С можно интерпретировать, как граф, где ребро (i,j) проведено, если сij = 0 (нулю, а не единице как обычно) и не проведено, если cij = 1. Тогда если существует тур длины 0, то он пройдет по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом (в орграфе — гамильтоновым контуром). Незамкнутый гамильтонов цикл (соответственно, контур) называется гамильтоновой цепью (соответственно, гамильтоновым путем).

В терминах теории графов симметричную задачу о коммивояжере можно сформулировать так:

Дана полная сеть с n вершинами, длина ребра (i,j) равна cij. Найти гамильтонов цикл минимальной длины.

В несимметричной задаче о коммивояжере вместо «цикл» говорят «контур», а вместо «ребра» — «дуги» или «стрелки».

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

§2. HЕKOTOРЫЕ ПРИМЕРЫ

1. Задача Гамильтона

Выдающийся английский математик и механик Гамильтон изобрел игру получившую в свое время широкое распространение. Игрушка представляет собой додекаэдр (правильный многогранник с 12 пятиугольными гранями и 20 вершинами). Считается, что этот додекаэдр приблизительно изображает земной шар. Пусть каждая из вершин изображает «столицу» одного из государств. Требуется, двигаясь по ребрам додекаэдра, обойти все «столицы», заходя в каждую из них один и только, один раз, и вернуться в исходный пункт (рис. 1). Каждый такой путь, если он существует, называется гамильтоновым контуром, или гамильтоновым циклом.

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

Практически установлено, что для указанного додекаэдра существует несколько совершенно равноценных гамильтоновых циклов.

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

2. Задача об обходе шахматной доски

Почти аналогично выглядит задача об обходе конем шахматной доски, рассмотренная еще Эйлером.

Перенумеруем все клетки шахматной доски и будем считать, что «расстояние» между двумя клетками равно единице, если конь может за один ход перескочить с одной из них на другую, и что это «расстояние» равно бесконечности в противоположном случае. Составив таким образом «матрицу расстояний» по типу таблицы 1.1 и считая, что конь первоначально стоит на поле а1, попробуем решить незамкнутую задачу о коммивояжере, В этом случае решением задачи о коммивояжере может быть либо L=63, либо L=∞ . Если окажется. что L= 63, то такой, обход возможен, и полученное решение укажет один из искомых вариaантов. Если же L = ∞, то обход невозможен. Надо сказать, что любители головоломок нашли пути решения не прибегая к помощи математики, и один из возможных вариантов такого обхода показан на рис. 3.

3. Сбор по тревоге

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

Пионеры одного звена проживают в разных местах города. Время на движение любого из них до всех других обозначим ti,j, где i и j — их порядковые номера. Для быстрого сбора звена установлен такой порядок: вожатый, получив сигнал тревоги, идет к одному из пионеров, извещает его о полученном сигнале, а сам направляется на место сбора звена. Этот пионер подобным же образом извещает другого и также направляется на место сбора, и так далее. Последний из пионеров, получив сигнал, прямо отправляется на пункт сбора. Спрашивается, как нужно составить эту цепочку, чтобы время сбора по тревоге всего звена было минимальным.

Сформулированная таким образом задача является задачей о кратчайшем n-звенном маршруте. Отличие этой задачи от незамкнутой задачи о коммивояжере состоит в том, что в последней пункт окончания маршрута не имеет значения, а в задаче о кратчайшем n-звенном маршруте заранее указаны как пункт старта, так и пункт финиша. В дальнейшем будет показано, что, как и незамкнутая задача о коммивояжере, эта тоже сводится к задаче о коммивояжере в общей постановке,

4. Проводка и энергоснабжение

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

Рассмотрим, например, задачу подводки электроэнергии к рабочим местам. Отправляясь от одного полюса источника энергии, требуется подвести провод к n потребителям и затем замкнуть проводник на другом полюсе. При этом расстояние между точками можно определить по формуле

R(i,j)=[(xi –xj)2+(yi –yj)2+(zi –zj)2]1/2

(x,y,z— координаты места потребления энергии), если допустимо проведение соединяющей проводки напрямую от одной точки до другой, или же несколько более сложным образом, если проводку разрешается осуществлять с соблюдением некоторых ограничений (например, только по стенкам помещения и обязательно параллельно его ребрам). Так, кратчайшее расстояние между точками i и j, определяемое с учетом указанных правил, изображено на рис. 4. Оно складывается из отрезков ia, ab, bj.

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

5. Определение оптимальной последовательности обработки деталей.

Пусть у нас имеется два станка и совокупность различных деталей, каждая из которых должна быть последовательно обработана на этих станках (например, токарная обработка и фрезерование). Будем считать, что:

а) на каждом станке может обрабатываться не более одной детали;

б) начавшаяся обработка детали не прерывается вплоть до ее окончания;

в) время на переналадку станков при переходе на обработку следующей детали пренебрежимо мало.

Время обработки k-й детали на каждом из станков обозначим ak и bk. Спрашивается в каком порядке надо обрабатывать детали, чтобы вся их совокупность была обработана возможно быстрее?

Легко заметить, что какую бы последовательность мы ни выбрали, токарный станок простаивать не будет, обрабатывая одну деталь за другой. Простаивает фрезерный станок, и вот время-то его простоя с момента начала выполнения заказа, по существу, и требуется минимизировать.

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

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

min(a1, b2)< min(a2, b1),

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

min(a2, b1)< min(a1, b2),

в обработку следует сначала пускать вторую деталь.

Наконец, в случае, если

min(a2, b1)= min(a1, b2),

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

Оказывается, что и в более общем случае нескольких деталей i-я деталь должна обрабатываться ранее j-ой, детали если

min(ai, bj)≤ min(aj, bi). (1.1)

Если теперь поставить в соответствие каждой i-ой детали совершенно произвольную точку на плоскости и считать что расстояние между i-й и j-й точками равно 1, если соблюдается соотношение (1.1) и ri,j=∞ в противоположном случае, то получим некоторую «матрацу расстояний».

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

Составим небольшой численный пример.

Пусть дан набор деталей, каждая из которых требует следующих затрат времени на токарную обработку и фрезерование: