Рис. 37.2 Работа алгоритма APPROX-MST-TOUR. (а) Исходные точки лежат в вершинах целочисленной решётки. (Например, вершина / на 1 правее и на 2 выше вершины h.) Стоимость ребра определяется как (евклидово) расстояние между точками. (Ь) Минимальное покрывающее дерево Т, построенное алгоритмом MST-PRIM. Вершина а является его корнем. (Алфавитный порядок названий вершин соответствует порядку их добавления в ходе работы алгоритма MST-PRIM.) (с) Обход дерева Т начинается с его корня а. Отмечая вершины на пути туда и обратно, мы получим последовательность a,b,c,b,h,b,a,d,e, f,e,g,e,d,a. Алгоритм обхода дерева в порядке «вершина-потомки» пропускает вершины на обратном пути, и остаётся а,Ь, с, h, d, е, /, g. (d) Соответствующий цикл Н является результатом работы алгоритма APPROX-MST-TOUR. Его стоимость примерно равна 19,074. (е) Оптимальный цикл стоимости и 14,715.

Approx-TSP-TOUR

1считаем произвольную вершину г £ V[G] «корнем»

2построим минимальное покрывающее дерево Г для графа G (с корнем в г) с помощью алгоритма MST-Prim(G, с, г)

3пусть L - перечень вершин этого дерева в порядке обхода «вершина-потомки»

4return гамильтонов цикл, обходящий вершины в порядке L Обход вершин дерева описан в разделе 13.1: рекурсивный алгоритм обхода поддерева с корнем в v посещает вершину v, а затем обходит поддеревья, корнями которых являются дети вершины v.

На рисунке 37.2 показана работа алгоритма. Для данной системы точек на плоскости (а) строится минимальное остовное дерево Г; вершина а - его корень (Ь). Определяемый им порядок обхода вершин (с) даёт гамильтонов цикл (d), который является результатом работы алгоритма Approx-MST-Tour. Он примерно на 23% длиннее оптимального цикла (е).

Время работы алгоритма Approx-MST-Tour равно Q(E) = ©(V2) поскольку алгоритм MST-Prim применяется к полному графу. (См. упражнение 24.2-2.) Осталось проверить, что найденный цикл не более чем вдвое длиннее оптимального. (При этом мы используем неравенство треугольника.)

Теорема 37.2

Алгоритм Approx-MST-Tour решает задачу о коммивояжёре с ошибкой не более чем в 2 раза, если выполнено неравенство треугольника.

Доказательство. Пусть Н* - гамильтонов цикл наименьшей стоимости. Нам надо доказать, что с(Н) 2с(Н*) для цикла Н, найденного с помощью нашего алгоритма. Удаляя любое ребро из цикла Н*, мы получаем покрывающее дерево. Его стоимость не превосходит с(Н*). Тем более это верно для оптимального покрывающего дерева Г:

Пусть мы обходим вершины дерева Г, посещая каждую верши-

(37.4)

ну дважды - до посещения её потомков и после. Для дерева на рис. 37.2 этот полный обход W включает в себя вершины

а, Ь, с, b, h, b, a, d, е, /, е, g, е, d, а

При этом каждое ребро дерева проходится дважды, поэтому суммарная стоимость всех рёбер c(W) будет вдвое больше с(Т)

c(W) = 2c(T).(37.5)

Из неравенств (37.4) и (37.5) следует, что

c(W) = 2c(H*).(37.5)

тем самым стоимость обхода вершин в порядке W не более чем вдвое превосходит оптимальную.

Однако это ещё не все: W не является циклом, так как мы бываем дважды в одной и той же вершине. Ничего страшного - мы можем удалить лишние вершины, при этом стоимость может только уменьшиться. Если в пути ... -> и -> w -> ... мы удаляем вершину v, остаётся ребро (и, w), длина которого по неравенству треугольника не больше суммы длин удалённых рёбер (и, v) и (v, w). Когда мы удалим из пути W повторно проходимые вершины (оставив только первое вхождение каждой), получится цикл

a,b,c,h,d,e,f,g.

который как раз и соответствует обходу дерева в порядке «вершина-потомки». Этот цикл Ни будет результатом работы алгоритма Approx-TSP-Tour. При этом

c(H)c(W),(37.7)

так как Н получен из W удалением вершин. Это неравенство вместе с (37.6) завершает доказательство теоремы.

Хотя алгоритм Approx-TSP-Tour и гарантирует ошибку не более чем в 2 раза, для практических целей он, как правило, недостаточно хорош, и применяются другие алгоритмы. (Соответствующие ссылки даны в конце главы.)

37.2.2. Общая задача коммивояжёра

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

Теорема 37.3. Пусть Р ф NP и р 1. Тогда не существует полиномиального приближённого алгоритма, решающего общую задачу о коммивояжёре с ошибкой не более чем в р раз.

Доказательство. Пусть такой алгоритм (назовём его А) существует для некоторого р 1 (не ограничивая общности, можно считать р целым). Мы покажем, как использовать А для решения задачи о гамильтоновом цикле, определённой в разделе 36.5.5. Так как эта задача NP-полна (теорема 36.14), существование решающего её полиномиального алгоритма влечёт Р = NP (теорема 36.4).

Итак, пусть дан граф G = (V, Е), и мы хотим узнать, есть ли в нём гамильтонов цикл, используя алгоритм А. Для этого рассмотрим полный граф G = (V, Е) с множеством вершин V:

Е = {(и, v) : и, vinV и и ф v}

На его рёбрах определим функцию стоимости слеудющим образом:

Г1, если (и, v) е Е,

с(и, V) = <

I Рг I + 1 в противном случае.

Легко понять, что время построение С и с не превосходит полинома от \V\ и \Е\.

Теперь посмотрим на задачу коммивояжёра для графа G с функцией стоимости с. Если исходный граф G имел гамильтонов цикл, то этот цикл является решением задачи о коммивояжёре со стоимостью \V\, поскольку содержит \V\ рёбер единичной стоимости. Если же гамильтонова цикла не было, то любое решение задачи о коммивояжёре проходит по одному из новых (не входящих в Е) рёбер. Новые рёбра дороги. Даже если новое ребро только одно, то общая стоимость (одно новое и \V\ - 1 старых) будет

(/,У + 1) + (У-1)>/,У;

если новых рёбер несколько, она будет ещё больше. Тем самым имеется большой - больше чем в р раз - разрыв между стоимостью оптимального цикла в G для случаев наличия или отсутствия гамильтонова цикла в С В первом случае есть цикл стоимостью \V\, во втором все циклы имеют стоимость больше p\V\.

Что даст приближённый алгоритм А, применённый к графу Gl Мы предполагаем, что даваемый им ответ не более чем в р раз хуже оптимального. Следовательно, если G имеет гамильтонов цикл, то А должен его выдать. Если же цикла нет, то А выдаёт цикл стоимости более p\V\. Тем самым можно различить один случай от другого за полиномиальное время.

Упражнения

37.2-1

Покажите, что в задаче о коммивояжёре можно (за полиномиальное время) модифицировать функцию стоимости так, чтобы она стала удовлетворять неравенству треугольника, и оптимальные циклы при этом не изменились. Почему это не противоречит теореме 37.3, даже если Р = NP?