Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 241
Текст из файла (страница 241)
В разделе 35.2.2 будет показано, что без соблюдения неравенства треугольника приближенный алгоритм с полиномиальным временем работы, характеризующийся постоянным коэффициентом аппроксимации, не существует, если только не справедливо соотношение Р = МР. 35.2.1 Задача о коммивояжере с неравенством треугольника Воспользовавшись методикой предыдущего раздела, сначала вычислим минимальное остовное дерево, вес которого является нижней границей длины оптимального тура коммивояжера. Затем с помощью этого минимального остовного дерева создадим тур, стоимость которого не более чем в два раза превышает вес этого дерева при условии, что функция стоимости удовлетворяет неравенству Глава 35. Приближенные алгоритмы 1159 треугольника.
Этот подход реализован в приведенном ниже алгоритме, в котором используется алгоритм построения минимального остовного дерева МБТ Рк1м, описанный в разделе 23.2. Аггкох ТБР Тоок(С,с) 1 Выбирается вершина т Е ЦС~ которая будет "корневой" 2 Из корня т с помощью алгоритма МБТ-Ршм(С, с, т) строится минимальное остовное дерево Т для графа С 3 Пусть Т, — список вершин, которые посещаются при обходе вершин дерева Т в прямом порядке 4 геГпгп Гамильтонов цикл Н, который посещает вершины в порядке перечисления в списке Т, Напомним, что при прямом обходе дерева рекурсивно посещаются все его вершины (см. раздел 12.1), причем вершина заносится в список при первом посещении, до посещения ее дочерних вершин. Работа процедуры Аи'кох ТБР Толк проиллюстрирована на рис.
35.2. В части а рисунка показано заданное множество точек, расположенных в вершинах целочисленной решетки. Например, точка У находится на один шаг правее и на два шага выше от точки Ь. В качестве функции стоимости между двумя точками используется обычное евклидово расстояние.
В части б рисунка изображено полученное в результате выполнения алгоритма МБТ Ркгм минимальное остовное дерево Т, берущее свое начало в корневой вершине а. Вершинам присвоены метки таким образом, что они добавляются алгоритмом МБТ Рк1м в основное дерево в алфавитном порядке. В части в показан порядок посещения вершин при прямом обходе дерева Т, начиная с вершины а. При полном обходе дерева вершины посещаются в порядке а, Ь, с, Ь, Ь, Ь, а, и, е, г, е, д, е, И, а. При прямом обходе дерева Т составляется список вершин, посещенных впервые (на рисунке возле каждой такой вершины поставлена точка).
Полученный в результате список имеет вид а, Ь, с, й, И, е, г", д. В части г рисунка представлен тур Н, возвращенный алгоритмом Агркох ТБР Толк. Его полная стоимость составляет приблизительно 19.074. В части д рисунка изображен оптимальный тур Н', длина которого примерно на 23% меньше (она приблизительно равна 14.715).
Согласно результатам упражнения 23.2-2, даже при простой реализации алгоритма МБТ Рк1м время работы алгоритма Аи'кох ТБР Тоок равно 6 (1тз). Теперь покажем, что если функция стоимости в экземпляре задачи юммивояжера удовлетворяет неравенству треугольника, то алгоритм АгРкох ТБР Толк возвращает тур, стоимость юторого не более чем в два раза превышает стоимость оптимального тура. Часть ЧП. Избранные темы 1160 В! 1-(а)~ ,ь) ' 1т~ + (г) Рис. 35.2. Работа алгоритма Аи'аох Т5Р Тона Теорема 35.2. Алгоритм Аргкох ТЯР ТОм является 2-приближенным алгоритмом с полиномиальным временем работы, позволяющим решить задачу коммивояжера, в которой удовлетворяется неравенство треугольника.
Доказательсюияо. Ранее уже было показано, что время работы алгоритма АрРкОх ТБР Таин выражается полиномиальной функцией. Обозначим через Н' тур, который является оптимальным для данного множества вершин. Поскольку путем удаления из этого тура одного ребра получается остовное дерево, вес минимального остовного дерева Т равен нижней границе стоимости оптимального тура, т.е. выполняется неравенство с(Т) < с(Н'). (35.4) При полном оЫоде (й1! иа)к) дерева Т составляется список вершин„которые посещаются впервые, если к ним происходит возврат после посещения поддерева.
Обозначим этот обход через И~. При полном обходе в рассматриваемом примере вершины посещаются в следующем порядке: а, Ь, с, Ь, Ь, Ь, а, Н, е, 1, е, д, е, Н, а. Поскольку при полном обходе каждое ребро дерева Т проходится ровно по два раза, естественным образом обобщив определение стоимости с на множества, Глава 35. Приближенные алгоритмы 1161 в которых ребра встречаются по несколько раз, получаем равенство с(Иг) = 2с(Т).
(35.5) Из соотношений (35.4) и (35.5) следует неравенство с(Иг) < 2с(Н'). (35.6) Таким образом, стоимость обхода Иг превышает стоимость оптимального тура не более чем в два раза. К сожалению, обход Иг в общем случае не является туром, поскольку он посещает некоторые вершины более одного раза. Однако, согласно неравенству треугольника, посещение любой из вершин в обходе И' можно отменить, и при этом стоимость не возрастет. (Если из маршрута И' удалить вершину е, которая посещается в этом маршруте на пути от вершины и к вершине щ то в полученном в результате такой операции упорядоченном списке вершин будет определяться переход непосредственно от вершины и к вершине и.) Путем неоднократного выполнения этой операции из обхода И' можно исключить все посещения каждой вершины, кроме первого.
В рассматриваемом примере упорядоченный список вершин принимает вид а, 6, с, Ь, Ы, е, г', д. Этот порядок совпадает с тем, который получается при прямом обходе дерева Т. Пусть Н вЂ” цикл, соответствующий данному прямому обходу. Это гамильтонов цикл, так как каждая вершина посещается по одному разу. Именно этот цикл составляется алгоритмом Аргкох ТБР Толк. Поскольку цикл Н получается путем удаления вершин из полного обхода Иг, выполняется неравенство с(Н) < с(Иг). (35.7) Сопоставляя неравенства (35.6) и (35.7), получаем соотношение с (Н) < 2с (Н'), что и завершает доказательство теоремы. Ы Несмотря на то, что теорема 35.2 позволяет добиться неплохого коэффициента аппроксимации, обычно на практике алгоритм Аррнох ТБР Топи — не лучший выбор для решения этой задачи. Существует другой приближенный алгоритм, который обычно дает намного лучшие практические результаты (см.
ссылки в конце этой главы). 35.2.2 Общая задача о коммивояжере Если опустить предположение о том, что функция стоимости с удовлетворяет неравенству треугольника, то нельзя найти туры с хорошим приближением за полиномиальное время, если не выполняется условие Р = ХР. Часть ЧП. Избранные темы 1162 Теорема 35.3. Если Р ф 'г1Р, то для любой константы р > 1 не существует приближенного алгоритма с полиномиальным временем работы и коэффициентом аппроксимации р, позволяющего решить задачу о коммивояжере в общем виде. Доказательство. Докажем теорему методом "от противного". Предположим, что для некоторого числа р > 1 существует приближенный алгоритм А с полиномиальным временем работы и коэффициентом аппроксимации р.
Без потери общности предположим, что число р — целое, округлив его при необходимости. Затем покажем, как с помощью алгоритма А можно решать экземпляры задачи о гамильтоновом цикле (определенной в разделе 34.2) в течение полиномиального времени. Поскольку задача о гамильтоновом цикле Хр-полная, согласно теореме 34.13, из ее разрешимости в течение полиномиального времени и теоремы 34.4 следует равенство Р = ХР. Пусть С = (У,Е) — эюемпляр задачи о гамнльтоновом цикле. Необходим эффективный способ, позволяющий с помощью гипотетического приближенного алгоритма А определить, содержит ли граф С гамильтонов цикл. Преобразуем граф С в эюемпляр задачи о коммивояжере.
Пусть С' = (У, Е') — полный граф на множестве У, т.е. Е' = ((и,о): и, о Е У и и ф о). Назначим каждому ребру из множества Е' целочисленную стоимость 1 если (и, о) Е Е, с(и,п) = р!У!+1 в противном случае. Представление графа С' и функции с можно получить из представления графа С в течение времени, являющегося полиномиальной функцией от величин !У! и !Е!.
Теперь рассмотрим задачу о коммивояжере (С', с). Если исходный граф С содержит гамильтонов цикл Н, то функция стоимости с сопоставляет каждому ребру цикла Н единичную стоимость, а значит, экземпляр (С', с) содержит тур стоимостью !У!. С другой стороны, если граф С не содержит гамильтонового цикла, то в любом туре по графу С' должно использоваться некоторое ребро, отсутствующее в множестве Е. Однако стоимость любого тура, в котором используется ребро, не содержащееся в множестве Е, не меньше величины (р!У!+1)+(!У!+1) =Р!У!+!У! > р!У! Из-за большой стоимости ребер, отсутствующих в графе С, между стоимостью тура, который представляет собой гамильтонов цикл в графе С (она равна !У!), и стоимостью любого другого тура (его величина не меньше р !У! + !У!) существует интервал, величина которого не меньше р !У!.
Глава 35. Приближенные алгоритмы 1163 Что произойдет, если применить к задаче о коммивояжере (С', с) алгоритм А? Поскольку этот алгоритм гарантированно возвращает тур, стоимость которого не более чем в р раз превышает стоимость оптимального тура, если граф С содержит гамильтонов цикл, алгоритм А должен его возвратить. Если же граф С не содержит гамильтоновых циклов, то алгоритм А возвращает тур, стоимость которого превышает величину р Щ. Поэтому с помощью алгоритма А задачу о гамильтоновом цикле можно решить в течение полиномиального времени. О Доказательство теоремы 35.3 — это пример общей методики доказательства того, что задачу нельзя хорошо аппроксимировать.
Предположим, что заданной ХР-сложной задаче Х в течение полиномиального времени можно сопоставить такую задачу минимизации У, что "да"-экземпляры задачи Х будут соответствовать экземплярам залачи У, стоимость юторых не превышает /с (где й — неюторая фиксированная величина), а "нет"-экземпляры задачи Х будут соответствовать экземплярам задачи У, стоимость которых превышает рй. Затем нужно показать, что если не выполняется равенство Р = МР, то не существует р-приближеиного алгоритма с полиномиальным временем работы, позволяющего решить задачу У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
