Алгоритмы - построение и анализ (1021735), страница 241
Текст из файла (страница 241)
В части г рисунка представлен тур Н, возвращенный алгоритмом Агркох ТБР Толк. Его полная стоимость составляет приблизительно 19.074. В части д рисунка изображен оптимальный тур Н', длина которого примерно на 23% меньше (она приблизительно равна 14.715). Согласно результатам упражнения 23.2-2, даже при простой реализации алгоритма МБТ Рк1м время работы алгоритма Аи'кох ТБР Тоок равно 6 (1тз).
Теперь покажем, что если функция стоимости в экземпляре задачи юммивояжера удовлетворяет неравенству треугольника, то алгоритм АгРкох ТБР Толк возвращает тур, стоимость юторого не более чем в два раза превышает стоимость оптимального тура. Часть ЧП. Избранные темы 1160 В! ,ь) ' 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 — это пример общей методики доказательства того, что задачу нельзя хорошо аппроксимировать. Предположим, что заданной ХР-сложной задаче Х в течение полиномиального времени можно сопоставить такую задачу минимизации У, что "да"-экземпляры задачи Х будут соответствовать экземплярам залачи У, стоимость юторых не превышает /с (где й — неюторая фиксированная величина), а "нет"-экземпляры задачи Х будут соответствовать экземплярам задачи У, стоимость которых превышает рй.
Затем нужно показать, что если не выполняется равенство Р = МР, то не существует р-приближеиного алгоритма с полиномиальным временем работы, позволяющего решить задачу У. Упражнения 35.2-1. Предположим, что полный неориентированный граф С = (КЕ), содержащий не менее трех вершин, характеризуется функцией стоимости с, удовлетворяющей неравенству треугольника. Докажите, что для всех и, с е У выполняется неравенство с (и, о) > О. 35.2-2.
Покажите, как в течение полиномиального времени один экземпляр задачи о юммивояжере можно преобразовать в другой экземпляр, функция стоимости которого удовлетворяет неравенству треугольника. Оба экземпляра должны содержать одно и то же множество оптимальных туров. Объясните, почему такое полиномиально-временное преобразование не противоречит теореме 35.3, предполагая, что Р ~ МР.
35.2-3. Рассмотрим описанный ниже эвристический метод ближайшей точки (с1озезт-ро)п1 леипзцс), позволяющий создавать приближенные туры в задаче о коммивояжере, функция стоимости которой удовлетворяет неравенству треугольника. Начнем построение с тривиального цикла, состоящего из одной произвольным образом выбранной вершины. На каждом этапе идентифицируется вершина и, не принадлежащая циклу, причем такая, расстояние от которой до цикла является минимальным. Предположим, что ближе всех к вершине и в цикле расположена вершина о.
Цикл расширяется за счет включения в него вершины и сразу после вершины о. Описанные действия повторяются до тех пор, пока в цикл Часть Ч!1. Избранные темы 1164 не будут включены все вершины. Докажите, что этот эвристический метод возвращает тур, полная стоимость которого не более чем в два раза превышает полную стоимость оптимального тура. 35.2-4. Задача о коммивояжере с устранением узких мест (Ьоп!епес1с ггаче1- 11пя-за1езшап ргоЫеш) — это задача поиска такого гамильтонового цикла, для которого минимизируется стоимость самого дорогостоящего входящего в этот цикл ребра.
Предполагая, что функция стоимости удовлетворяет неравенству треугольника, покажите, что для этой задачи существует приближенный алгоритм с полиномиальным временем работы, коэффициент аппроксимации которого равен 3. (Указание: воспользовавшись рекурсией, покажите, что все узлы остовного дерева с узкими местами можно обойти ровно по одному разу, взяв полный обход дерева с пропусками узлов, если ограничить пропуски таким образом, чтобы не пропускать более двух последовательных промежуточных узлов (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
