Покажем, что существует Ui, которое для замкнутого цикла, начинающегося в некотором начальном пункте, удовлетворяют условию (4). При всех Xij (j-й город не посещается после i-го) в (4) имеем Ui-Uj £ N-1, что допустимо в силу произвольных Ui и Uj.
Пусть на некотором R-ом шаге i-й город посещается перед j-м, то есть Xij = 1. В силу произвольности значений Ui и Uj положим Ui = R, а Uj = R+1, тогда из (4) имеем:
Ui-Uj+N·Xij £ R-(R-1)+N = N-1
Итак, существуют такие конечные значения для Ui и Uj, что для маршрута, содержащего N городов, условие (4) удовлетворяется как неравенство или строгое равенство. А следовательно, модель (1)-(4) описывает задачу о коммивояжере.
В терминах теории графов симметричную ЗК можно сформулировать так:
Дана полная сеть с n вершинами, длина ребра (i,j)= Сij. Найти гамильтонов цикл минимальной длины.
В несимметричной ЗК вместо «цикл» надо говорить «контур», а вместо «ребра» - «дуги», «стрелки».
Некоторые прикладные задачи формулируются как ЗК, но в них нужно минимизировать длину не гамильтонова цикла, а гамильтоновой цепи. Такие задачи называются незамкнутыми. Некоторые модели сводятся к задаче о нескольких коммивояжерах, но мы здесь их рассматривать не будем.
Жадный алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. “Жадным” этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность.
Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь алгоритм превратится в стратегию “иди в ближайший, в который еще не входил, город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.
В пользу процедуры “иди в ближайший” можно сказать лишь то, что при старте из одного города она не уступит стратегии “иди в дальнейший”.
Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного алгоритма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть fB - настоящий минимум, а fA - тот квазиминимум, который получен по алгоритму. Ясно, что fA/ fB≥1, но это – тривиальное утверждение, что может быть погрешность. Чтобы оценить её, нужно «зажать» отношение оценкой сверху:
fA/fB ≥ 1+nε (8)
где, как обычно в высшей математике, ε≥0, но, против обычая, может быть очень большим. Величина ε и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (8), мы будем говорить, что он имеет погрешность ε.
Предположим теперь, что имеется алгоритм А решения ЗК, погрешность которого нужно оценить. Возьмем произвольный граф G(V,E) и по нему составим входную матрицу ЗК:
| С[i,j]={ | 1, если ребро (i,j) принадлежит Е |
| 1+nε, в противном случае |
Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и fB = n. Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, не переборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1+nε. Но тогда fA ³ (n-1)+(1+nε) так что fA/fB = 1+nε, т.е. превосходит погрешность ε на заданную неравенством (8). О величине ε в нашем рассуждении мы не договаривались, так что ε может быть произвольно большим.
Таким образом доказана следующая теорема.
Либо алгоритм А определяет, существует ли в произвольном графе гамильтонов цикл, либо погрешность А при решении ЗК может быть произвольно велика.
Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника (7).
Теперь можно обсудить алгоритм решения ЗК через построение кратчайшего остовного дерева. Для краткости будет называть этот алгоритм “деревянным”.
Вначале обсудим свойство спрямления. Рассмотрим какую-нибудь цепь, например, на рис. 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]
Итак, если справедливо неравенство треугольника, то для каждой цепи верно, что расстояние от начала до конца цепи меньше (или равно) суммарной длины всех ребер цепи. Это обобщение расхожего убеждения, что прямая короче кривой.
Вернемся к ЗК и опишем решающий ее “деревянный” алгоритм.
1. Построим на входной сети ЗК кратчайшее остовное дерево и удвоим все его ребра. Получим граф G – связный и с вершинами, имеющими только четные степени.
2. Построим эйлеров цикл в G, начиная с вершины 1, цикл задается перечнем вершин.
3. Просмотрим перечень вершин, начиная с 1, и будем зачеркивать каждую вершину, которая повторяет уже встреченную в последовательности. Останется тур, который и является результатом алгоритма.
Пример 1. Дана полная сеть, показанная на рис.5. Найти тур “жадным” и “деревянным” алгоритмами.
Решение.
1. “Жадный” алгоритм (иди в ближайший город из города 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 (9)
| — | 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 | — |
Но удвоенное дерево – оно же эйлеров граф – мы свели к туру посредством спрямлений, следовательно, длина полученного по алгоритму тура удовлетворяет неравенству 2LMT > fA (10)
Умножая (9) на два и соединяя с (10), получаем цепочку неравенств
2fB > 2LHC ³2LMT ³ fA (11)
Т.е. 2fB>fA, fA/fB>1+e; e=1. Теорема доказана.
Таким образом, мы доказали, что “деревянный” алгоритм ошибается менее, чем в два раза. Такие алгоритмы уже называют приблизительными, а не просто эвристическими.
Известно еще несколько простых алгоритмов, гарантирующих в худшем случае e=1. Для того, чтобы найти среди них алгоритм поточнее, зайдем с другого конца и для начала опишем “brute-force enumeration” - “перебор грубой силой”, как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что ЗК с n городами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! Туров в несимметричной, а факториал, как показано в следующей таблице, растет удручающе быстро:
| 5! | 10! | 15! | 20! | 25! | 30! | 35! | 40! | 45! | 50! |
| ~102 | ~106 | ~1012 | ~1018 | ~1025 | ~1032 | ~1040 | ~1047 | ~1056 | ~1064 |
Чтобы проводить полный перебор в ЗК, нужно научиться (разумеется, без повторений) генерировать все перестановки заданного числа m элементов. Это можно сделать несколькими способами, но самый распространенный (т.е. приложимый для переборных алгоритмов решения других задач) – это перебор в лексикографическом порядке.
Говорят, что перестановка (a1,…,an) лексикографически предшествует перестановке (b1,…,bn), если существует k ≤ n ak < bk и для любого i > k ai = bi.
Пусть имеется некоторый алфавит и наборы символов алфавита (букв), называемые словами. Буквы в алфавите упорядочены: например, в русском алфавите порядок букв аµбµя (символ µ читается “предшествует”). Если задан порядок букв, можно упорядочить и слова. Скажем, дано слово 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. Нужно осознать общий алгоритм преобразования любой перестановки в непосредственно следующую за ней.