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=? |(2)|

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

И удовлетворять неравенству треугольника, т.е. для всех:
|Сij+ Сjk(Cik |(4)|

В математической постановке говорится о произвольной матрице. Сделано это потому, что имеется много прикладных задач, которые описываются основной моделью, но всем условиям (2)-(4) не удовлетворяют. Особенно часто
нарушается условие (3) (например, если Сij – не расстояние, а плата за проезд: часто туда билет стоит одну цену, а обратно – другую). Поэтому мы будем различать два варианта ЗК: симметричную задачу, когда условие (3)
выполнено, и несимметричную - в противном случае. Условия (2)-(4) по умолчанию мы будем считать выполненными.
Второе замечание касается числа всех возможных туров. В несимметричной ЗК все туры 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, то он пройдёт по циклу, который включает все вершины по одному разу. Такой цикл называется гамильтоновым циклом. Незамкнутый гамильтонов цикл называется гамильтоновой цепью (гамильтоновым путём).
В терминах теории графов симметричную ЗК можно сформулировать так:
Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины.
В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги» или «стрелки».
Некоторые прикладные задачи формулируются как ЗК, но в них нужно минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах, но мы здесь их рассматривать не будем.

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

1.2.1. Жадный алгоритм

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

Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди вы ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.
В пользу процедуры «иди в ближайший» можно сказать лишь то, что при старте из одного города она не уступит стратегии «иди в дальнейший».
Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного логарифма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть fB - настоящий минимум, а fA - тот квазиминимум, который получен по алгоритму. Ясно, что fA/ fB?1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно зажать отношение оценкой сверху: |fA/fB ?1+ n?, |(5)|

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

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

|С={ |1,если ребро (i,j) принадлежит Е | | |1+n? в противном случае |

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

Таким образом доказана следующая теорема. Либо алгоритм А определяет, существует ли в произвольном графе гамильтонов цикл, либо погрешность А при решении ЗК может быть произвольно велика.
Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника (4).

Если оно соблюдается, можно предложить несколько алгоритмов с погрешностью 12. Прежде, чем описать такой алгоритм, следует вспомнить старинную головоломку. Можно ли начертить одной линией открытый конверт?
Рис.2 показывает, что можно (цифры на отрезках показывают порядок их проведения). Закрытый конверт (рис.3.) одной линией нарисовать нельзя и вот почему. Будем называть линии ребрами, а их перекрестья – вершинами.
Когда через точку проводится линия, то используется два ребра – одно для входа в вершину, одно – для выхода. Если степень вершины нечетна – то в ней линия должна начаться или кончиться. На рис. 3 вершин нечетной степени
две: в одной линия начинается, в другой – кончается. Однако на рис. 4 имеется четыре вершины степени три, но у одной линии не может быть четыре конца. Если же нужно прочертить фигуру одной замкнутой линией, то все ее вершины должны иметь четную степень. Верно и обратное утверждение: если все вершины имеют четную степень, то фигуру можно нарисовать одной незамкнутой линией. Действительно, процесс проведения линии может кончиться, только если линия придет в вершину,
откуда уже выхода нет: все ребра, присоединенные к этой вершине (обычно говорят: инцидентные этой вершине), уже прочерчены. Если при этом нарисована вся фигура, то нужное утверждение доказано; если нет, удалим уже
нарисованную часть G’. После этого от графа останется одна или несколько связных компонент; пусть G’ – одна из таких компонент. В силу связности исходного графа G, G’ и G’’ имеют хоть одну общую вершину, скажем, v. Если
в G’’ удалены какие-то ребра, то по четному числу от каждой вершины.

Поэтому G’’ – связный и все его вершины имеют четную степень. Построим цикл в G’’ (может быть, не нарисовав всего G’’) и через v добавим прорисованную часть G’’ к G’. Увеличивая таким образом прорисованную часть G’, мы добьемся того, что G’ охватит весь G.

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

Эйлеров цикл в графе существует тогда и только тогда, когда (1) граф связный и (2) все его вершины имеют четные степени.

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

Теперь можно обсудить алгоритм решения ЗК через построение кратчайшего остовного дерева. Для краткости будет называть этот алгоритм деревянным. Вначале обсудим свойство спрямления. Рассмотрим какую-нибудь цепь, например, на рис.5. Если справедливо неравенство треугольника, то d(d+d и d(d+d
Сложив эти два неравенства, получим d+d(d+d+d+d. По неравенству треугольника получим. d(d+d. Окончательно d(d+d+d+d

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

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

Пример 1. Дана полная сеть, показанная на рис.5. Найти тур жадным и
деревянным алгоритмами.
|- |1 |2 |3 |4 |5 |6 |
|1 |- |6 |4 |8 |7 |14|
|2 |6 |- |7 |11|7 |10|
|3 |4 |7 |- |4 |3 |10|

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

2. Деревянный алгоритм вначале строит остовное дерево, показанное на рис. 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 |(6)|

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

Умножая (6) на два и соединяя с (7), получаем цепочку неравенств |2fB>2LHC(2LMT(fA |(8)|

Т.е. 2fB>fA, т.е. fA/fB>1+(; (=1.
Теорема доказана.
Таким образом, мы доказали, что деревянный алгоритм ошибается менее, чем в два раза. Такие алгоритмы уже называют приблизительными, а не просто эвристическими.
Известно еще несколько простых алгоритмов, гарантирующих в худшем случае (=1. Для того, чтобы найти среди них алгоритм поточнее, зайдем с другого конца и для начала опишем «brute-force enumeration» - «перебор животной силой», как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера.
Напомним, что ЗК с n городами требует при полном переборе рассмотрения (n- 1)!/2 туров в симметричной задаче и (n-1)! Туров в несимметричной, а факториал, как показано в следующей таблице, растет удручающе быстро:
|1 |- |0 |0 |3 |3 |6 |
|2 |0 |- |1 |4 |1 |0 |
|3 |1 |2 |- |0 |0 |3 |
|табл. 4 |

Изложим алгоритм Литтла на примере 1 предыдущего раздела.. Повторно запишем матрицу:
|-|1 |2 |3 |4 |5|6 |
|1|- |6 |4 |8 |7|14|

Нам будет удобнее трактовать Сij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.
Вычитая любую константу из всех элементов любой строки или столбца матрицы С, мы оставляем минимальный тур минимальным.
Для алгоритма нам будет удобно получить побольше нулей в матрице С, не получая там, однако, отрицательных чисел. Для этого мы вычтем из каждой строки ее минимальный элемент (это называется приведением по строкам, см. табл. 3), а затем вычтем из каждого столбца матрицы, приведенной по строкам, его минимальный элемент, получив матрицу, приведенную по столбцам, см. табл. 4). Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34. Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на табл. 2.
Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один
подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На
табл. 2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.
Теперь будем рассуждать от приведенной матрицы на табл. 2. Если в ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми
элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет
обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров. Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена
перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1+0=1: если не ехать «по
нулю» из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на табл. 5 правее и выше нуля (оценки нуля, равные нулю, не ставились). Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).
Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два класса – включающие ребро (1,2) и не включающие ребро (1,2). Про второй класс можно сказать, что придется приплатить еще 1, так что туры этого класса стоят 35 или больше.
Что касается первого класса, то в нем надо рассмотреть матрицу на табл. 6 с вычеркнутой первой строкой и вторым столбцом.
| |1|2|3|4|5|6|
|1|-|0|0|3|3|6|
| | |1| | | | |
|2|0|-|1|4|1|0|
| |1| | | | | |
|3|1|2|-|0|0|3|
| | | | |1| | |
| |1|3|4|5|6|
|2|0|1|4|1|0|
| |1| | | | |
|3|1|-|0|0|3|
| | | |1| | |
|4|4|0|-|1|3|
| | |1| | | |
|5|4|0|1|-|0|
|6|7|3|3|0|-|
| | | | |1| |
|табл. 6 |
| |1|3|4|5|6|
|2|0|1|4|1|0|
| |1| | | | |
|3|0|-|0|0|3|
| |3| |1| | |
|4|3|0|-|1|3|
| | |1| | | |
|5|3|0|1|-|0|
|6|6|3|3|0|-|
| | | | |1| |
|табл. 7 |
| |3|4|5|6|
|2|1|4|1|0|
|4|0|-|1|3|
| |1| | | |
|5|0|1|-|0|
|6|3|3|0|-|
| | | |1| |
|табл. 8 |

Дополнительно в уменьшенной матрице поставлен запрет в клетке (2,1), т. к. выбрано ребро (1,2) и замыкать преждевременно тур ребром (2,1) нельзя. Уменьшенную матрицу можно привести на 1 по первому столбцу, так что каждый тур, ей отвечающий, стоит не меньше 35. Результат наших ветвлений и получения оценок показан на рис.6. Кружки представляют классы: верхний кружок – класс всех туров; нижний левый – класс всех туров, включающих ребро (1,2); нижний правый – класс всех
туров, не включающих ребро (1,2). Числа над кружками – оценки снизу. Продолжим ветвление в положительную сторону: влево - вниз. Для этого оценим нули в уменьшенной матрице C на табл. 7. Максимальная оценка в клетке (3,1) равна 3. Таким образом, оценка для правой нижней вершины на рис. 7 есть 35+3=38. Для оценки левой нижней вершины на рис. 7 нужно вычеркнуть из матрицы C еще строку 3 и столбец 1, получив матрицу C[(1,2),(3,1)] на табл. 8. В эту матрицу нужно поставить запрет в клетку (2,3), так как уже построен фрагмент тура из ребер (1,2) и (3,1), т.е. , и нужно запретить преждевременное замыкание (2,3). Эта матрица приводится по столбцу на 1 (табл. 9), таким образом, каждый тур
соответствующего класса (т.е. тур, содержащий ребра (1,2) и (3,1)) стоит 36 и более.
| |3 |4 |5 |6 |
|2 |1 |3 |1 |0 |
|4 |01|- |1 |3 |
|5 |0 |02|- |0 |
|6 |3 |2 |03|- |
|табл. 9 |
| |3|4|6|
|2|1|3|0|
| | | |3|
|4|0|-|3|
| |3| | |
|5|0|0|0|
| | |3| |
|табл. 10 |
| |3 |4 |
|4 |0 |- |
|5 |0 |0 |
|табл. 11 |

Оцениваем теперь нули в приведенной матрице C[(1,2),(3,1)] нуль с максимальной оценкой 3 находится в клетке (6,5). Отрицательный вариант имеет оценку 38+3=41. Для получения оценки положительного варианта убираем строчку 6 и столбец 5, ставим запрет в клетку (5,6), см. табл. 10. Эта матрица неприводима. Следовательно, оценка положительного варианта не
увеличивается (рис.8). Оценивая нули в матрице на табл. 10, получаем ветвление по выбору ребра (2,6), отрицательный вариант получает оценку 36+3=39, а для получения оценки положительного варианта вычеркиваем вторую строку и шестой столбец,
получая матрицу на табл. 11. В матрицу надо добавить запрет в клетку (5,3), ибо уже построен фрагмент тура и надо запретить преждевременный возврат (5,3). Теперь, когда осталась матрица 2х2 с запретами по диагонали, достраиваем
тур ребрами (4,3) и (5,4). Мы не зря ветвились, по положительным вариантам. Сейчас получен тур: 1>2>6>5>4>3>1 стоимостью в 36. При достижении низа по дереву перебора класс туров сузился до одного тура, а оценка снизу
превратилась в точную стоимость. Итак, все классы, имеющие оценку 36 и выше, лучшего тура не содержат.
Поэтому соответствующие вершины вычеркиваются. Вычеркиваются также вершины, оба потомка которой вычеркнуты. Мы колоссально сократили полный перебор. Осталось проверить, не содержит ли лучшего тура класс, соответствующий
матрице С, т.е. приведенной матрице С с запретом в клетке 1,2, приведенной на 1 по столбцу (что дало оценку 34+1=35). Оценка нулей дает 3 для нуля в клетке (1,3), так что оценка отрицательного варианта 35+3
превосходит стоимость уже полученного тура 36 и отрицательный вариант отсекается.
Для получения оценки положительного варианта исключаем из матрицы первую строку и третий столбец, ставим запрет (3,1) и получаем матрицу. Эта матрица приводится по четвертой строке на 1, оценка класса достигает 36 и
кружок зачеркивается. Поскольку у вершины «все» убиты оба потомка, она убивается тоже. Вершин не осталось, перебор окончен. Мы получили тот же минимальный тур, который показан подчеркиванием на табл. 2.
Удовлетворительных теоретических оценок быстродействия алгоритма Литтла и родственных алгоритмов нет, но практика показывает, что на современных ЭВМ они часто позволяют решить ЗК с n = 100. Это огромный прогресс по сравнению с полным перебором. Кроме того, алгоритмы типа ветвей и границ являются, если нет возможности доводить их до конца, эффективными эвристическими процедурами.

1.2.4. Алгоритм Дейкстры

Одним из вариантов решения ЗК является вариант нахождения кратчайшей цепи, содержащей все города. Затем полученная цепь дополняется начальным городом – получается искомый тур. Можно предложить много процедур решения этой задачи, например, физическое моделирование. На плоской доске рисуется карта местности, в города, лежащие на развилке дорог, вбиваются гвозди, на каждый гвоздь надевается кольцо, дороги укладываются верёвками, которые привязываются к
соответствующим кольцам. Чтобы найти кратчайшее расстояние между i и k, нужно взять I в одну руку и k в другую и растянуть. Те верёвки, которые натянутся и не дадут разводить руки шире и образуют кратчайший путь между i
и k. Однако математическая процедура, которая промоделирует эту физическую, выглядит очень сложно. Известны алгоритмы попроще. Один из них – алгоритм Дейкстры, предложенный Дейкстрой ещё в 1959г. Этот алгоритм решает общую
задачу:
В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети найти кратчайший путь между двумя заданными вершинами. Алгоритм использует три массива из n (= числу вершин сети) чисел каждый. Первый массив a содержит метки с двумя значениями: 0 (вершина ещё не рассмотрена) и 1 (вершина уже рассмотрена); второй массив b содержит расстояния – текущие кратчайшие расстояния от vi до соответствующей
вершины; третий массив c содержит номера вершин – k-й элемент ck есть номер предпоследней вершины на текущем кратчайшем пути из vi в vk. Матрица расстояний Dik задаёт длины дуг dik; если такой дуги нет, то dik присваивается большое число Б, равное «машинной бесконечности».

Теперь можно описать: Алгоритм Дейкстры 1(инициализация).

В цикле от одного до n заполнить нулями массив а; заполнить числом i массив с: перенести i-тую строку матрицы D в массив b;
a[i]:=1; c[i]:=0; {i-номер стартовой вершины} 2(общий шаг). Найти минимум среди неотмеченных (т. е. тех k, для которых a[k]=0); пусть минимум достигается на индексе j, т. е. bj(bk; a[j]:=1; если bk>bj+djk то (bk:=bj+djk; ck:=j) {Условие означает, что путь vi..vk длиннее, чем путь vi..vj,vk . Если все a[k] отмечены, то длина пути vi..vk равна b[k]. Теперь надо перечислить вершины, входящие в кратчайший путь}

3(выдача ответа).
{Путь vi..vk выдаётся в обратном порядке следующей процедурой:}
3.1. z:=c[k];
3.2. Выдать z;
3.3. z:=c[z]; Если z = 0, то конец, иначе перейти к 3.2.
Для выполнения алгоритма нужно n раз просмотреть массив b из n элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность. Проиллюстрируем работу алгоритма Дейкстры численным примером (для большей сложности, считаем, что некоторые города (вершины) i,j не соединены между собой, т. е. D=?). Пусть, например, i=3. Требуется найти кратчайшие
пути из вершины 3. Содержимое массивов a,b,c после выполнения первого пункта показано на табл. 12:

Очевидно, содержимое таблицы меняется по мере выполнения общего шага. Это видно из следующей таблицы:
Одним из возможных недостатков такого алгоритма является необходимость знать не матрицу расстояний, а координаты каждого города на плоскости. Если нам известна матрица расстояний между городами, но неизвестны их координаты, то для их нахождения нужно будет решить n систем квадратных уравнений с n неизвестными для каждой координаты. Уже для 6 городов это сделать очень сложно. Если же, наоборот, имеются координаты всех городов, но нет матрицы расстояний между ними, то создать эту матрицу несложно. Это можно легко сделать в уме для 5-6 городов. Для большего количества городов
можно воспользоваться возможностями компьютера, в то время как промоделировать решение системы квадратных уравнений на компьютере довольно сложно.
На основе вышеизложенного можно сделать вывод, что мой алгоритм, наряду с деревянным алгоритмом и алгоритмом Дейкстры, можно отнести к приближённым (хотя за этим алгоритмом ни разу не было замечено выдачи неправильного варианта).

1.2.6. Анализ методов решения задачи коммивояжера

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

Данные занесём в таблицу.
|Алгоритм лексического перебора |
|Кол-во |Время обработки,|Вероятность неправильного |Тип |
|городов |c |ответа, % |алгоритма |
|10 |41 |0 |точный |
|12 |12000=3ч.20мин |0 | |
|32 |-* |0 | |
|100 |-* |0 | |
|Метод ветвей и границ |
|10 |~0 |0 |точный |
|32 |~0.0001 |0 | |
|100 |1.2 |0 | |
|Мой алгоритм решения ЗК |
|10 |0.001 |0 |приближенный|
|32 |2.5 |0 | |
|100 |6 |0 | |

*- ЗК с таким количеством городов методом лексического перебора
современный компьютер не смог бы решить даже за всё время существования
Вселенной.
Как видим по результатам этой таблицы, алгоритм лексического перебора
можно применять лишь в случае с количеством городов 5..12. Метод ветвей и
границ, наряду с моим методом, можно применять всегда. Хотя мой метод я
отнёс к приближённым алгоритмам, он фактически является точным, так как
доказать обратное ещё не удалось.

1.3 Практическое применение задачи коммивояжера

Кроме очевидного применения ЗК на практике, существует ещё ряд задач, сводимых к решению ЗК.
Задача о производстве красок. Имеется производственная линия для производства n красок разного цвета; обозначим эти краски номерами 1,2… n. Всю производственную линию будем считать одним процессором.. Будем считать
также, что единовременно процессор производит только одну краску, поэтому краски нужно производить в некотором порядке Поскольку производство циклическое, то краски надо производить в циклическом порядке (=(j1,j2,..,jn,j1). После окончания производства краски i и перед началом производства краски j надо отмыть оборудование от краски i. Для этого
требуется время C. Очевидно, что C зависит как от i, так и от j, и что, вообще говоря,C?C. При некотором выбранном порядке придется на цикл производства красок потратить время
Где tk - чистое время производства k-ой краски (не считая переналадок). Однако вторая сумма в правой части постоянна, поэтому полное время на цикл производства минимизируется вместе с общим временем на переналадку.
Таким образом, ЗК и задача о минимизации времени переналадки – это просто одна задача, только варианты ее описаны разными словами. Задача о дыропробивном прессе. Дыропробивной пресс производит большое число одинаковых панелей – металлических листов, в которых последовательно по одному пробиваются отверстия разной формы и величины. Схематически пресс можно представить в виде стола, двигающегося независимо по координатам x, y, и вращающегося над столом диска, по периметру которого расположены дыропробивные инструменты разной формы и величины. Каждый инструмент присутствует в одном экземпляре. Диск может вращаться одинаково в двух направлениях (координата вращения z). Имеется собственно пресс, который надавливает на подвешенный под него инструмент тогда, когда под инструмент
подведена нужная точка листа. Операция пробивки j-того отверстия характеризуется четверкой чисел (xj,yj,zj,tj), где xj,yj- координаты нужного положения стола, zj - координата нужного положения диска и tj - время пробивки j-того отверстия.
Производство панелей носит циклический характер: в начале и конце обработки каждого листа стол должен находиться в положениях (x0, y0) диск в положении z0 причем в этом положении отверстие не пробивается. Это начальное состояние системы можно считать пробивкой фиктивного нулевого отверстия. С параметрами (x0,y0,z0,0). Чтобы пробить j-тое отверстие непосредственно после i-того необходимо произвести следующие действия:
1. Переместить стол по оси x из положения xi в положение xj, затрачивая
при этом время t(x)(|xi-xj|)=ti,j(x)
2. Проделать то же самое по оси y, затратив время ti,j(y)
3. Повернуть головку по кратчайшей из двух дуг из положения zi в положение zj, затратив время ti,j(z) .
4. Пробить j-тое отверстие, затратив время tj. Конкретный вид функций t(x), t(y), t(z) зависит от механических
свойств пресса и достаточно громоздок. Явно выписывать эти функции нет необходимости. Действия 1-3 (переналадка с i-того отверстия j-тое) происходит одновременно, и пробивка происходит немедленно после завершения самого длительного из этих действий. Поэтому С = max(t(x), t(y), t(z)) Теперь, как и в предыдущем случае, задача составления оптимальной
программы для дыропробивного пресса сводится к ЗК (здесь - симметричной).

Выводы

1. Изучены эвристический, приближенный и точный алгоритмы решения ЗК.
Точные алгоритмы решения ЗК – это полный перебор или
усовершенствованный перебор. Оба они, особенно первый, не эффективны
при большом числе вершин графа.
2. Предложен собственный эффективный метод решения ЗК на основе
построения выпуклого многоугольника и включения в него центральных
вершин (городов).
3. Проведён анализ наиболее рациональных методов решения ЗК и определены
области их эффективного действия: для малого числа вершин можно
использовать точный метод лексического перебора; для большого числа
вершин рациональнее применять метод ветвей и границ или метод автора
работы (Анищенко Сергея Александровича).
4. Изучены практические применения ЗК и задачи с переналадками, сводимые
к ЗК.
5. Приведены тексты программ, позволяющие решить ЗК различными методами.

LMatrix: На нашем сайте Вы можете познакомиться с решением задачи коммивояжера (TSP) для различных стран мира.

Определения

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

Маршрутом в графе

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

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

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

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c ij }, где c ij ≥0 – длинна (или цена) дуги (i , j ),

. Под маршрутом коммивояжера z будем понимать цикл i 1 , i 2 ,…, i n , i 1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера , длина маршрута l (z ) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i 1 – фиксирована. Требуется найти маршрут z 0 ÎZ , такой, что l (z 0)= minl (z ), z ÎZ .

Решение задачи

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

состояло из маршрутов, содержащих некоторую дугу (i, j), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножеств и оказываются не меньше нижней границы множества всех маршрутов, т.е. φ(Z)≤ φ (), φ(Z) ≤ φ ().

Сравнивая нижние границы φ (

) и φ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

Затем одно из подмножеств

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

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

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

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

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

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

Разбиение множества маршрутов на подмножества

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ ij нулевых элементов этой матрицы. Степень нулевого элемента Θ ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

Множество маршрутов, не включающих дугу (i , j ) получаем путем замены элемента c ij на бесконечность.

Пример решения задачи коммивояжера методом ветвей и границ

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

A	B	C	D	E	F
A	∞	26	42	15	29	25
B	7	∞	16	1	30	25
C	20	13	∞	35	5	0
D	21	16	25	∞	18	18
E	12	46	27	48	∞	5
F	23	5	5	9	5	∞

Решение задачи

Для удобства изложения везде ниже в платежной матрице заменим имена городов (A, B, …, F) номерами соответствующих строк и столбцов (1, 2, …, 6).

Найдем нижнюю границу длин множества всех маршрутов. Вычтем из каждой строки число, равное минимальному элементу этой строки, далее вычтем из каждого столбца число, равное минимальному элементу этого столбца, и таким образом приведем матрицу по строкам и столбцам. Минимумы по строкам: r 1 =15, r 2 =1, r 3 =0, r 4 =16, r 5 =5, r 6 =5.

После их вычитания по строкам получим:

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	6	∞	15	0	29	24
3	20	13	∞	35	5	0
4	5	0	9	∞	2	2
5	7	41	22	43	∞	0
6	18	0	0	4	0	∞

Минимумы по столбцам: h 1 =5, h 2 =h 3 =h 4 =h 5 =h 6 .

После их вычитания по столбцам получим приведенную матрицу:

1	2	3	4	5	6
1	∞	11	27	0	14	10
2	1	∞	15	0	29	24
3	15	13	∞	35	5	0
4	0	0	9	∞	2	2
5	2	41	22	43	∞	0
6	13	0	0	4	0	∞

Найдем нижнюю границу φ (Z ) = 15+1+0+16+5+5+5 = 47.

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, найдем степени Θ ij нулевых элементов этой матрицы (суммы минимумов по строке и столбцу). Θ 14 = 10 + 0,
Θ 24 = 1 + 0, Θ 36 = 5+0, Θ 41 = 0 + 1, Θ 42 = 0 + 0, Θ 56 = 2 + 0, Θ 62 = 0 + 0,
Θ 63 = 0 + 9, Θ 65 = 0 + 2. Наибольшая степень Θ 14 = 10. Ветвление проводим по дуге (1, 4).

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

Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом .

Математическая модель задачи коммивояжера

Сформулированная задача - задача целочисленная. Пусть х ij =1 , если путешественник переезжает из i -ого города в j -ый и х ij =0 , если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u 1 =0 , u n +1 =n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x ij и переменные u i (u i целые неотрицательные числа).

U i -u j +nx ij ≤ n-1, j=2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤u i ≤n, x in+1 =x i1 , i=2..n

Методы решения задачи коммивояжера

1. метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ ;
2. венгерский метод. Пример решения венгерским методом .

Алгоритм Литтла или исключения подциклов

1. Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент d min и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑d min .
2. Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент d min , и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑d min .
3. Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
4. Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
5. Выбирают дугу (i,j) , для которой степень нулевого элемента достигает максимального значения.
6. Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*) . Для получения матрицы контуров, включающих дугу (i,j) , вычеркивают в матрице строку i и столбец j . Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
7. Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*) .
8. Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*) . Если H(i,j)
9. Если в результате ветвлений получается матрица (2x2) , то определяют полученный ветвлением гамильтонов контур и его длину.
10. Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.

Пример . Решить по алгоритму Литтла задачу коммивояжера с матрицей

	1	2	3	4
1	-	5	8	7
2	5	-	6	15
3	8	6	-	10
4	7	15	10	-

Решение . Возьмем в качестве произвольного маршрута: X 0 = (1,2);(2,3);(3,4);(4,5);(5,1). Тогда F(X 0) = 20 + 14 + 6 + 12 + 5 = 57
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент: d i = min(j) d ij

i j	1	2	3	4	5	d i
1	M	20	18	12	8	8
2	5	M	14	7	11	5
3	12	18	M	6	11	6
4	11	17	11	M	12	11
5	5	5	5	5	M	5

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

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M
d j	0	0	0	0	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Сумма констант приведения определяет нижнюю границу H: H = ∑d i + ∑d j = 8+5+6+11+5+0+0+0+0+0 = 35
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления

i j	1	2	3	4	5	d i
1	M	12	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	12	M	0(5)	5	5
4	0(0)	6	0(0)	M	1	0
5	0(0)	0(6)	0(0)	0(0)	M	0
d j	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 6 = 6; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	12	10	4	0	0
2	0	M	9	2	6	0
3	6	12	M	0	5	0
4	0	6	0	M	1	0
5	0	M	0	0	M	0
d j	0	6	0	0	0	6

Нижняя граница гамильтоновых циклов этого подмножества: H(5*,2*) = 35 + 6 = 41
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	0	M	1	0
d j	0	0	0	0	0

Нижняя граница подмножества (5,2) равна: H(5,2) = 35 + 0 = 35 ≤ 41
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 35
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	5	d i
1	M	10	4	0(5)	4
2	0(2)	9	2	M	2
3	6	M	0(7)	5	5
4	0(0)	0(9)	M	1	0
d j	0	9	2	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 2 = 7; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 9 = 9;
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d 43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	M	M	1	0
d j	0	9	0	0	9

Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 35 + 9 = 44
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d 34 заменяем на М, для исключения образования негамильтонова цикла.

После операции приведения сокращенная матрица будет иметь вид:

i j	1	4	5	d i
1	M	4	0	0
2	0	2	M	0
3	6	M	5	5
d j	0	2	0	7

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 7
Нижняя граница подмножества (4,3) равна: H(4,3) = 35 + 7 = 42 ≤ 44
Поскольку 42 > 41, исключаем подмножество (5,2) для дальнейшего ветвления.
Возвращаемся к прежнему плану X 1 .
План X 1 .

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	M	0	0	M

Операция редукции .

i j	1	2	3	4	5
1	M	6	10	4	0
2	0	M	9	2	6
3	6	6	M	0	5
4	0	0	0	M	1
5	0	M	0	0	M

Шаг №1 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	4	5	d i
1	M	6	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	6	M	0(5)	5	5
4	0(0)	0(6)	0(0)	M	1	0
5	0(0)	M	0(0)	0(0)	M	0
d j	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 6 = 6; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Исключение ребра (4,2) проводим путем замены элемента d 42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	6	10	4	0	0
2	0	M	9	2	6	0
3	6	6	M	0	5	0
4	0	M	0	M	1	0
5	0	M	0	0	M	0
d j	0	6	0	0	0	6

Нижняя граница гамильтоновых циклов этого подмножества: H(4*,2*) = 41 + 6 = 47
Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d 24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
d j	0	0	0	0	0

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (4,2) равна: H(4,2) = 41 + 0 = 41 ≤ 47
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут с новой границей H = 41
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	5	d i
1	M	10	4	0(9)	4
2	0(6)	9	M	6	6
3	6	M	0(5)	5	5
5	0(0)	0(9)	0(0)	M	0
d j	0	9	0	5	0

d(1,5) = 4 + 5 = 9; d(2,1) = 6 + 0 = 6; d(3,4) = 5 + 0 = 5; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Исключение ребра (1,5) проводим путем замены элемента d 15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.

i j	1	3	4	5	d i
1	M	10	4	M	4
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
d j	0	0	0	5	9

Нижняя граница гамильтоновых циклов этого подмножества: H(1*,5*) = 41 + 9 = 50
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d 51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	4	d i
2	0	9	M	0
3	6	M	0	0
5	M	0	0	0
d j	0	0	0	0

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (1,5) равна: H(1,5) = 41 + 0 = 41 ≤ 50
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 41
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	d i
2	0(15)	9	M	9
3	6	M	0(6)	6
5	M	0(9)	0(0)	0
d j	6	9	0	0

d(2,1) = 9 + 6 = 15; d(3,4) = 6 + 0 = 6; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (9 + 6) = 15 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d 21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.

i j	1	3	4	d i
2	M	9	M	9
3	6	M	0	0
5	M	0	0	0
d j	6	0	0	15

Нижняя граница гамильтоновых циклов этого подмножества: H(2*,1*) = 41 + 15 = 56
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d 12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	3	4	d i
3	M	0	0
5	0	0	0
d j	0	0	0

Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 0
Нижняя граница подмножества (2,1) равна: H(2,1) = 41 + 0 = 41 ≤ 56
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 41.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (5,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(4,2), (2,1), (1,5), (5,3), (3,4). Длина маршрута равна F(Mk) = 41

Дерево решений.

																														1
								(5*,2*), H=41																																												(5,2)
(4*,2*), H=47																	(4,2)																															(4*,3*), H=44								(4,3)
								(1*,5*), H=50																	(1,5)
																(2*,1*), H=56																		(2,1)
																												(3,4)												(3*,4*), H=41
																								(5,3)								(5*,3*), H=41

(5х5) (Засчитывается за 4 условные задачи) время на исполнение 2 пары) (Презентация КОММИВОЯЖЁР) Самая сложная задача исследования операций

Методом ветвей и границ требуется найти Кратчайший маршрут объезда 5 городов с возвратом в исходный, при КОТОРОМ КАЖДЫЙ ГОРОД ПОСЕЩАЕТСЯ в ТОЧНОСТИ 1 раз (в матрице даны цены проезда из «левого» города в «верхний»).

Решение Методом ветвей и границ

Шаг №0 Оцениваем цикл 1-2-3-4-5-1 – это первое приближение верхней оценки. Далее, если на любой ветви дерева ветвления нижняя оценка подмножества решений окажется выше верхней эта ветвь «отмирает» , т.к. все её решения хуже уже имеющегося.

Шаг №1а) Выписываем константы редуцирования по строкам. Это минимальные числа в строках. Их надо вычесть из элементов своих строк (при этом появится не менее одного нуля в каждой строке).

Шаг №1б) В только что полученной на шаге 1а) матрице (с нулями в строках) ровно ту же операцию проводи и по столбцам - ищем столбцы, где минимум е равен 0 и вычитаем его. В формате самопроверки убедитесь, что теперь в каждом столбце и каждой строке матрицы стоимостей проезда имеется хотя бы один ноль.

Шаг №1в) Вычисляем сумму констант редуцирования полученных на шагах а) и б). Очевидно, никакой маршрут не может стоить дешевле – поэтому это оценка снизу. Далее мы будем увеличивать эту оценку на величину и
(эти величины опишем ниже), где- пара индексов ребра, по которому выбрано производить ветвление.

Опишем, как будет происходить ветвление: выбираем ребро i,j(удовлетворяющее требованиям следующего пункта) множество гамильтоновых маршрутов можно мыслить как комбинаторно большое множество своеобразных «бус» составленных из звеньев типа Петербург-Москва, Москва-Одесса, Одесса-Белград и т.д. Примем способ разделить всё множество замкнутых путей на те, где есть дорога Одесса-Белград и те где её нет (первое множество меньше второго).

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

Для этого: Шаг №2. Вычисляем стоимости обхода для каждого нулевого элемента (если он превратился в бесконечность ∞) - величина на которую увеличиваются константы редуцирования соответствующей строки и столбца.

Разбиваем текущее множество решений на два:




1. Процесс отчасти заканчивается после выбора k-2 ребер, гдеkобщее число вершин. В задаче 2х2 решение однозначно, оно (обычно) приводит к коррекции верхней оценки. Если все (остальные) нижние оценки хуже, ответ получен. В таком примере как приведенный в этом задании как правило имеет место эта ситуация, но в более большом и сложном графе (при создании универсального алгоритма), требуется описать дальнейшие действия. Если всё ещё не все нижние оценки хуже чем скорректированная верхняя оценка, то выжившие нетривиальные множества придется ветвить до тех пор пока либо они не исчезнут из-за высокой, т.е. плохой нижней оценки, либо (что редко) до того как будет получена новая верхняя оценка - новое решение, превосходящее по качеству предыдущее. Процесс продолжается до тех пор, пока полученное решение не останется безальтернативным.

Рассмотрим матрицу стоимостей проезда из «левого» города в «верхний»

Начальная глобальная оценка Zверхняя=10+10+20+15+10 = 65 получим по циклу. (соответствующие рёбра, обведены квадратами на рисунке - одно в левом нижнем углу, остальные над диагональю).

Начинаем рисовать дерево ветвления

В полученной матрице

рассчитаем дополнительную цену «объезда» каждого отдельного нуля  (то есть, на сколько возрастёт сумма констант редуцирования, если дорога перестанет существовать (цена проезда будет заменена на бесконечность)) и выберем, тот «ноль», цена объездакоторого максимальна.

(1,2)=0

(1,5)=1

(2,1)=0

 (2,3)=5 (Максимальная  )

(3,1)=0

(3,4)=2

(4,2)=4

(5,2)=2

Итак, максимальная цена объезда  наблюдается при выключении ребра (2,3)=5.

Нашим алгоритмом, естественно разделить все циклы объезда на содержащие ребро (2,3) и не содержащие его. Нижняя оценка стоимости первой группы циклов (мы её посчитаем позже), скорее всего не изменится, нижняя оценка циклов не включающих (2,3) возрастает на величину (2,3)=5.

На отдельной странице начинаем вырисовывать дерево ветвления.

На начальном этапе оно содержит множество всех циклов, которое разбивается на множество содержащее (2,3) (их меньше)– слева и не содержащее (2,3) – справа.

Нижняя оценка (большего) правого множества получается суммой оценки предшествующей вершины Z min =58 и(2,3)=5:Z min =58+5=63.

В левом множестве ребро (2,3) (условно говоря путь Санкт-Петербург - Москва) является обязательным – соответственно мы более не имеем выбора куда поехать из города 2 (удалим строку 2) и как приехать в город №3 (удалим столбец).

Итоговое дерево ветвления:

Финал метода.

Получается матрица размера 2х2.

Маломерный пример.

В заключении рассмотрим матрицу 3х3.

Тогда верхняя граница длин всех маршрутов Z max = 4+9+8 = 21

Таким образом, нижняя оценка Z нижн =16 (6+3+4+3).

Оцениваем константы обхода:

объединим города 2 и 1 в левой ветке, в правой ветке нижняя оценка стоимости возрастёт с 16 на 5 до 21.

получаем матрицу

Запретим короткое замыкание - во избежание

и редуцируем матрицу

На левой ветке ΔZ_=4, новая оценка целевой функции Z_=16+ ΔZ_=16+4=20.

Выбрано ребро

Остались рёбра
.

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

Это конкретный путь длина 20 в этот момент мы получаем новую верхнюю оценку, что лучше старой верхней оценки 21.

На дереве ветвления множеств перебора исчезает ветвь с более высокой нижней оценкой 21 (правая ветвь).

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

Ответ:
.

Проверка

Презентация КОММИВОЯЖЁР.

Задача проверяется преподавателем по оформлению дерева ветвления. Чтобы на нём была представлена максимально полная необходимая для проверки информация в вершинах дерева отобразить нижние оценки целевых функций, на рёбрах дерева обязательно должны быть отображены все θ (рост суммы констант редуцирования на правом повороте), все ΔZ(рост суммы констант редуцирования при левом повороте). При левом повороте выбирается одно обязательное ребро (отмечается на дереве ветвления) и добавляется одно запрещённое ребро. Для объяснения его выбора рядом с деревом ветвления на соответствующем уровне должна быть изображена цепочка в которой запрещаемое ребро вкупе с ранее выбранными (включая сейчас выбранное) порождает цикл не проходящий через все рёбра (так называемое «короткое замыкание» цикла).

В ответе дается цепочка Рёбер вида (1,k)(k,l)(l,m)..(r,1)(по размеру задачи), стоимость маршрута состоит из начальной нижней оценки и её приращений ΔZ(если были только ВЫЧЁРКИВАНИЯ – левые ПОВОРОТЫ) и – что бывает очень редко - ΔZи θ, если КРОМЕ левых ПОВОРОТОВ присутствовали один или несколько правых поворотов. Провести проверку стоимости ПОЛУЧЕНОГО решения по исходной матрице, объяснить причины несовпадения – если имелись (не совпадений быть не должно).

ЭММиМвЛ, ИСО, МПУР

ЗАДАЧА КОММИВОЯЖЕРА

Определения

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

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

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

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

В терминах теории графов задачу можно сформулировать следующим образом. Задано n вершин и матрица {c ij }, где c ij ≥0 – длина (или цена) дуги (i , j ),
. Подмаршрутом коммивояжера z будем понимать цикл i 1 , i 2 ,…, i n , i 1 точек 1,2,…, n. Таким образом, маршрут является набором дуг. Если между городами i и j нет перехода, то в матрице ставится символ «бесконечность». Он обязательно ставится по диагонали, что означает запрет на возвращение в точку, через которую уже проходил маршрут коммивояжера , длина маршрута l (z ) равна сумме длин дуг, входящих в маршрут. Пусть Z – множество всех возможных маршрутов. Начальная вершина i 1 – фиксирована. Требуется найти маршрут z 0  Z , такой, что l (z 0)= min l (z ), z  Z .

Решение задачи

Основная идея метода ветвей и границ состоит в том, что вначале строят нижнюю границу φ длин множества маршрутов Z. Затем множество маршрутов разбивается на два подмножества таким образом, чтобы первое подмножество состояло из маршрутов, содержащих некоторую дугу (i, j ), а другое подмножество не содержало этой дуги. Для каждого из подмножеств определяются нижние границы по тому же правилу, что и для первоначального множества маршрутов. Полученные нижние границы подмножествиоказываются не меньше нижней границы множества всех маршрутов, т.е.
.

Сравнивая нижние границы φ () иφ (), можно выделить то, подмножество маршрутов, которое с большей вероятностью содержит маршрут минимальной длины.

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

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

Основная идея метода ветвей и границ состоит в том, что ветвятся не все вершины. Сначала вершины просматриваются, и каждая вершина оценивается. Ветвится та вершина, которая получает лучшую оценку.

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

Оценка вершины должна удовлетворять следующим свойствам.

Алгоритм метода ветвей и границ

Шаг 1 . Строятся вершины первого уровня. Для каждой вершины подсчитывается оценка нижней (верхней) границы. Ветвится вершина, которой соответствует лучшая (минимальная или максимальная) оценка.

Шаг 2 . Для всех вершин -го уровня (
) подсчитывается оценка. Ветвится та из висячих вершин уровня
, которой соответствует лучшая (минимальная или максимальная) оценка.

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

Метод ветвей и границ не гарантирует того, что в ходе решения задачи не будет произведен полный перебор.

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

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

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

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

Разбиение множества маршрутов на подмножества

Для выделения претендентов на включение во множество дуг, по которым производится ветвление, рассмотрим в приведенной матрице все элементы, равные нулю. Найдем степени Θ ij нулевых элементов этой матрицы. Степень нулевого элемента Θ ij равна сумме минимального элемента в строке i и минимального элемента в столбце j (при выборе этих минимумов c ij – не учитывается). С наибольшей вероятностью искомому маршруту принадлежат дуги с максимальной степенью нуля.

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

Множество маршрутов, не включающих дугу (i , j ) получаем путем замены элемента c ij на бесконечность.

Пример (Г.И. Просветов, 2009, стр. 44)

Решим задачу коммивояжера для пяти пунктов.

Расстояния между населенными пунктами заданы с помощью матрицы

,

где - длина пути от пунктаi до пункта j .

На каждом шаге ребро
либо включается в ответ (обозначение
), либо не включается в ответ (обозначение
).

Шаг 1. Нахождение константы приведения .

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

Найденные минимумы в строке и столбце называются константами приведения строки или столбца соответственно. Сумма всех найденных минимумов равна 18 – константа приведения матрицы. Она дает оценку снизу на данном шаге длины маршрута.

Шаг 2 . Определение дуги, исключение которой максимально увеличивает оценку, полученную на предыдущем шаге.

С этой целью заменяем поочередно каждый из нулей на .

Элемент
имеет наибольшую сумму. Поэтому все множество маршрутов распадается на два класса:
(не содержат дугу
) и
(содержат дугу
).

Шаг 3 . Определение множества дуг для дальнейшего ветвления.

Рассмотрим множество
. Исключение дуги

на:

.

В полученной матрице нужно определить сумму констант приведения:

Нижняя граница множества
, где 18 – оценка предыдущего шага, 3 – оценка текущего шага.

Рассмотрим множество
. Включение дуги
проводится с помощью исключения 1-й строки (в множестве
из пункта 1 мы идем только в пункт 3) и 3-го столбца (в множестве
в пункт 3 мы можем попасть только из пункта 1). Элемент (3,1) заменяем на(исключаем возможность возвращения, зацикливания, образования негамильтонова цикла):

.

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

Так как
, то дальше ветвим множество
.

Для матрицы

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

Для элемента
эта сумма наибольшая. Поэтому все множество маршрутов распадается на два класса:
(не содержит дугу
) и
(содержит дугу
).

Рассмотрим множество
. Исключение дуги
проводится с помощью замены элемента
на:

.

Определим в полученной матрице ее константу приведения:

.