Задача коммивояжера — страница 6

Просмотрим перечень вершин, начиная с 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 4 8 11 4 - 5 11 5 7 7 3 5 - 7 6 14 10 10 11 7 - табл. 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 (6) Но удвоенное дерево – оно же эйлеров граф – мы свели к туру посредством спрямлений, следовательно, длина полученного по алгоритму тура

удовлетворяет неравенству 2LMT>fA (7) Умножая (6) на два и соединяя с (7), получаем цепочку неравенств 2fB>2LHC³2LMT³fA (8) Т.е. 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 ~10125 ~1032 ~1040 ~1047 ~1056 ~1064 Чтобы проводить полный перебор в ЗК, нужно научиться (разумеется, без повторений) генерировать все перестановки заданного числа m элементов. Это можно сделать несколькими способами, но самый распространенный (т.е. приложимый для переборных алгоритмов решения других задач) – это перебор в лексикографическом порядке. Пусть имеется некоторый алфавит и наборы символов