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

Задача

 коммивояжера.

Введение.

 

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

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

 

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

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

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

 

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

 

Общее описание

 

Постановка  задачи

 

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

 

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

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

Относительно математизированной формулировки ЗК уместно сделать два замечания. 

 

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

Сij0; Cjj=∞

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

Сij= Сji.

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

Сij+ СjkCik

 

 

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

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

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

 

Методы решения.

 

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

 

Посмотрим, как поведет  себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию  «иди в ближайший (в который еще  не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер  стартует из города 1. Алгоритм «иди вы ближайший город» выведет его  в город 2, затем 3, затем 4; на последнем  шаге придется платить за жадность, возвращаясь по длинной диагонали  ромба. В результате получится не кратчайший, а длиннейший тур.

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

 

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

Пусть fB - настоящий минимум, а fA - тот квазиминимум, который получен по алгоритму. Ясно, что fA/ fB≥1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно зажать отношение оценкой сверху:

fA/fB ≥1+ nε,

где, как обычно в высшей математике, ε≥0, но, против обычая, может быть очень большим. Величина ε и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (5), мы будем говорить, что он имеет погрешность ε.

 

Предположим теперь, что имеется  алгоритм А решения ЗК, погрешность  которого нужно оценить. Возьмем  произвольный граф G (V,E) и по нему составим входную матрицу ЗК:

 

 

Если в графе  G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и fB = n. Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, непереборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+nε. Но тогда fA(n-1)+(1+nε) так что fA/fB=1+nε т.е. превосходит погрешность ε на заданную неравенством (5). О величине ε в нашем рассуждении мы не договаривались, так что ε может быть произвольно велик.

• Таким образом доказана следующая теорема.

Либо алгоритм А определяет, существует ли в произвольном графе гамильтонов цикл, либо погрешность А при решении ЗК может быть произвольно велика.

 

 

Деревянный алгоритм

 

Теперь можно  обсудить алгоритм решения ЗК через  построение кратчайшего остовного дерева. Для краткости будет называть этот алгоритм деревянным.

Вначале обсудим  свойство спрямления. Рассмотрим какую-нибудь цепь, например, на рис.5. Если справедливо  неравенство треугольника, то

d[1,3]d[1,2]+d[2,3] и d[3,5]d[3,4]+d[4,5]                                           Сложив эти два неравенства, получим d[1,3]+d[3,5]d[1,2]+d[2,3]+d[3,4]+d[4,5]. По неравенству треугольника получим. d[1,5]d[1,3]+d[3,5]. Окончательно  d[1,5] d[1,2]+d[2,3]+d[3,4]+d[4,5]

 

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

Построим эйлеров цикл G, начиная с вершины 1, цикл задается перечнем вершин.

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

 

Решение.

 

Жадный алгоритм (иди в ближайший город из города 1) дает тур 1–(4)–3-(3)–5(5)–4–(11)–6–(10)–2–(6)–1, где без скобок показаны номера вершин, а в скобках – длины ребер. Длина тура равна 39, тур показан  на рис. 5.

 Деревянный алгоритм  вначале строит остовное дерево, показанное на рис. 6 штриховой линией, затем эйлеров цикл 1-2-1-3-4-3-5-6-5-3-1, затем тур 1-2-3-4-5-6-1 длиной 43, который показан сплошной линией на рис. 6.

 

Теорема. Погрешность  деревянного алгоритма равна 1.  

 

Доказательство. Возьмем  минимальный тур длины fB и удалим из него максимальное ребро. Длина получившейся гамильтоновой цепи LHC меньше fB. Но эту же цепь можно рассматривать как остовное дерево, т. к. эта цепь достигает все вершины и не имеет циклов. Длина кратчайшего остовного дерева  LMT меньше или равна LHC. Имеем цепочку неравенств     fB>LHCLMT

Но удвоенное  дерево – оно же эйлеров граф – мы свели к туру посредством спрямлений, следовательно, длина полученного по алгоритму тура удовлетворяет неравенству         2LMT>fA

Умножая (6) на два  и соединяя с (7), получаем цепочку  неравенств

2fB>2LHC2LMTfA      Т.е. 2fB>fA, т.е. fA/fB>1+; =1.

• Теорема доказана.

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

 

Пример:

 

Пусть имеется некоторый  алфавит и наборы символов алфавита (букв), называемые словами. Буквы в  алфавите упорядочены: например, в русском  алфавите порядок букв абя (символ  читается «предшествует)». Если задан порядок букв, можно упорядочить и слова. Скажем, дано слово u=(u1,u2,..,um) – состоящее из букв u1,u2,..,um - и слово v =(v1,v2,..,vb). Тогда если u1v1, то и uv, если же u1=v1, то сравнивают вторые буквы и т.д. Этот порядок слов и называется лексикографическим. Поэтому в русских словарях (лексиконах) слово «абажур» стоит раньше слова «абака». Слово «бур» стоит раньше слова «бура», потому что пробел считается предшествующим любой букве алфавита.

Рассмотрим, скажем, перестановки из пяти элементов, обозначенных цифрами 1..5. Лексикографически первой перестановкой является 1-2-3-4-5, второй – 1-2-3-5-4, …, последней – 5-4-3-2-1. Нужно  осознать общий алгоритм преобразования любой перестановки в непосредственно  следующую.

 

Правило такое: скажем, дана перестановка 1-3-5-4-2. Нужно двигаться  по перестановке справа налево, пока впервые  не увидим число, меньшее, чем предыдущее (в примере это 3 после 5). Это число, Pi-1 надо увеличить, поставив вместо него какое-то число из расположенных правее, от Pi до Pn. Число большее, чем Pi-1, несомненно, найдется, так как Pi-1< Pi . Если есть несколько больших чисел, то, очевидно, надо ставить меньшее из них. Пусть это будет Pj,j>i-1. Затем число Pi-1 и все числа от Pi до Pn, не считая Pj нужно упорядочить по возрастанию. В результате получится непосредственно следующая перестановка, в примере –   1-4-2-3-5. Потом получится 1-4-2-5-3 (тот же алгоритм, но упрощенный случай) и т.д.

Нужно понимать, что  в ЗК с n городами не нужны все перестановки из n элементов. Потому что перестановки, скажем, 1-3-5-4-2 и 3-5-4-2-1 (последний элемент соединен с первым) задают один и тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединять к нему все перестановки из остальных элементов. Этот перебор даст (n-1)! разных туров, т.е. полный перебор в несимметричной ЗК (мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3).

 

Метод ветвей и границ.

 

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

 Изложим алгоритм Литтла на примере предыдущего раздела. 
Запишем матрицу:  

 

-	1	2	3	4	5	6
1	-	6	4	8	7	14
2	6	-	7	11	7	10
3	4	7	-	4	3	10
4	8	11	4	-	5	11
5	7	7	3	5	-	7
6	14	10	10	11	7	-
табл. 2

 

-	1	2	3	4	5	6
1	-	2	0	4	3	10
2	0	-	1	5	1	4
3	1	4	-	1	0	7
4	4	7	0	-	1	7
5	4	4	0	2	-	4
6	7	3	3	4	0	-
табл. 3