Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 261
Текст из файла (страница 261)
(35.5) Из (35.4) и (35.5) вытекает, что с(И') < 2с(Н'), (35.6) так что стоимость обхода Ис превышает стоимость оптимального тура не более чем в два раза. К сожалению„полный обход И' в общем случае не является туром, поскольку он посещает некоторые вершины более одного раза. Однако согласно неравенству треугольника посещение любой из вершин в обходе Ис можно отменить, и при этом стоимость не возрастет. (Если из маршрута И' удалить вершину и, которая посещается в этом маршруте на пути от вершины и к вершине зл, то в полученном в результате такой операции упорядоченном списке вершин будет определяться переход непосредственно от вершины и к вершине зл.) Путем неоднократного выполнения этой операции из обхода И' моясно исключить все посещения каждой вершины, кроме первого.
В рассматриваемом примере упорядоченный список вершин принимает вид а, Ь, с, Ь, с(, е, ), д . Зтот порядок совпадает с тем, который получается при прямом обходе дерева Т. Пусть Н вЂ” цикл, соответствующий данному прямому обходу. Зто гамильтонов цикл, так как каждая вершина посещается по одному разу. Именно этот цикл и вычисляется алгоритмом Аггкох-ТВР-Топи. Поскольку цикл Н получается путем удаления вершин из полного обхода И', выполняется неравенство с(Н) ( с(Иг) . (35.7) Объединив неравенства (35.6) и (35.7), получаем с(Н) < 2с(Н'), что и завершает доказательство. Несмотря на то что теорема 35.2 позволяет добиться неплохого коэффициента аппроксимации, обычно на практике алгоритм Аггкох-ТБР-Толк — не лучший выбор для решения этой задачи.
Существует другой приближенный алгоритм, который обычно дает намного лучшие практические результаты (см, ссылки в конце этой главы). Глава 3 я Прнщнжвнные ав:арнннни Пбг 35.2.2. Общая задача о коммивояжере Если отказаться от предположения о том, что функция стоимости с удовлетворяет неравенству треугольника, то нельзя найти туры с хорошим приближением за полиномиальное время, если только не выполняется условие Р = г1Р. Теорема 35.3 Если Р ф ХР, то для любой константы р > 1 не существует приближенного алгоритма с полиномиальным временем работы и коэффициентом аппроксимации р, позволяющего решить задачу о коммивояжере в общем случае. Доказаввельсовво.
Докажем теорему "от противного". Предположим, что для некоторого числа р > 1 существует приближенный алгоритм А с полиномиальным временем работы н коэффициентом аппроксимации р. Без потери общности предположим, что число р — целое, при необходимости округлив его. Затем покажем, как с помощью алгоритма А можно решать экземпляры задачи о гамильтоновом цикле (определенной в разделе 34.2) за полиномиальное время.
Поскольку задача о гамильтоновом цикле согласно теореме 34.13 ХР-полная, из ее разрешимости за полиномиальное время и теоремы 34.4 следует равенство Р = ХР. Пусть С = (К Е) — экземпляр задачи о гамильтоновом цикле. Мы хотим эффективно определить с помощью гипотетического приближенного алгоритма А, содержит ли граф С гамильтонов цикл. Преобразуем граф С в экземпляр задачи о коммивояжере. Пусть С' = ($', Е') — полный граф на множестве 1Г, т.е.
Е' = ((и, и): и, и Е $' и и Ф и) Назначим каждому ребру из множества Е' целочисленную стоимость: 1 , если (и,и) е Е, с(и, и) = рЩ+ 1 в противном случае . Представление графа С' и функции с можно получить из представления графа С за время, полиномиально зависящее от величин ))л! и )Е(. Теперь рассмотрим задачу о коммивояжере (С', с). Если исходный граф С содержит гамильтонов цикл Н, то функция стоимости с сопоставляет каждому ребру цикла Н единичную стоимость, а значит, экземпляр (С', с) содержит тур стоимостью ~Ц. С другой стороны, если граф С не содержит гамильтонова цикла, то в любом туре по графу С' должно использоваться некоторое ребро, отсутствующее в множестве Е.
Однаю стоимость любого тура, в котором используется ребро, не содержащееся в множестве Е, не меньше величины (р!~ 1+1)+ ОИ вЂ” 1) = р%+ И >р% . Из-за большой стоимости ребер, отсутствующих в графе С, между стоимостью тура, который представляет собой гамильтонов цикл в графе С (она равна ~Ц), и стоимостью любого другого тура (его величина не меньше р ) 1л(+ ) Ъ'!) существу- Часть ГГ1 Избранные тены 1168 ет интервал, величина которого не меньше р ~$'~. Следовательно, стоимость тура, не являющегося гамильтоновым циклом в С, как минимум в р+ 1 раз больше стоимости тура, являющегося гамильтоновым циклом в С. Теперь предположим, что мы применяем к задаче о коммивояжере (С', с) алгоритм А.
Поскольку этот алгоритм гарантированно возвращает тур, стоимость которого не более чем в р раз превышает стоимость оптимального тура, если граф С содержит гамильтонов цикл, алгоритм А должен его возвратить. Если же граф С не содержит гамильтоновых циклов, то алгоритм А возвращает тур, стоимость которого превышает величину р Щ. Поэтому с помощью алгоритма А задачу о гамильтоновом цикле можно решить за полиномиааьное время. ° Доказательство теоремы 35.3 служит примером общей методики доказательства того, что задачу нельзя очень хорошо аппроксимировать. Предположим, что заданной о1Р-сложной задаче Х в течение полиномиального времени можно сопоставить такую задачу минимизации У', что "да"-экземпляры задачи Х будут соответствовать экземплярам задачи У, стоимость которых не превышает й (где 1с — некоторая фиксированная величина), а "нет*'-экземпляры задачи Х будут соответствовать экземплярам задачи У, стоимость которых превышает р)е.
Затем мы должны показать, что, если только не выполняется равенство Р = НР, не сушествует р-приближенного алгоритма с полиномиальным временем работы, позволяющего решить задачу )с. Упражнения 35.2.1 Предположим, что полный неориентированный граф С = (1з, Е), содержащий не менее трех вершин, характеризуется функцией стоимости с, удовлетворяющей неравенству треугольника.
Докажите, что для всех и, о Е 1~ выполняется неравенство с(и, о) > О. 35.2.2 Покажите, как за полиномиальное время один экземпляр задачи о коммивояжере можно преобразовать в другой экземпляр, функция стоимости которого удовлетворяет неравенству треугольника. Оба экземпляра должны содержать одно и то же множество оптимальных туров. Обьясните, почему такое полиномиально-временное преобразование не противоречит теореме 35.3, в предположении, что Р Ф ЫР. 35.2.3 Рассмотрим описанный ниже эвристический метод ближайшей точки (с1озезь рош1 Ьеипз6с), позволяющий создавать приближенные туры в задаче о коммивояжере, функция стоимости которой удовлетворяет неравенству треугольника.
Начнем построение с тривиального цикла, состоящего из одной произвольным образом выбранной вершины. На каждом этапе находится вершина а, не принадлежащая циклу, причем такая, расстояние от которой до цикла является минимальным. Предположим, что ближе всех к вершине и в цикле расположена Пб9 Глааа 55. Приближенные алгоритмы вершина и. Цикл расширяется за счет включения в него вершины и сразу после вершины и. Описанные действия повторяются до тех пор, пока в цикл ие будут включены все вершины. Докажите, что этот эвристический метод возвращает тур, полная стоимость которого не более чем в два раза превышает полную стоимость оптимального тура.
35.2.4 Задача о коммивояжере с устранением узких мест (Ьоц)енес)с Ггаче)йпп-за!езшап ргоЫеш) — это задача поиска такого гамильтонова цикла, для которого минимизируется стоимость самого дорогостоящего входящего в этот цикл ребра. Предполагая, что функция стоимости удовлетворяет неравенству треугольника, покажите, что для этой задачи существует приближенный алгоритм с полиномиальным временем работы, коэффициент аппроксимации которого равен 3.
(Указание: воспользовавшись рекурсией, покажите, что все узлы остовного дерева с узкими местами можно обойти ровно по одному разу, беря полный обход дерева и выполняя в нем пропуски таким образом, чтобы не пропускать более двух последовательных промежуточных узлов (см. задачу 23.3). Покажите, что стоимость самого дорогостоящего ребра в остовном дереве с узкими местами не превышает стоимости самого дорогостоящего ребра в гамильтоновом цикле с узкими местами.) 35.2.5 Предположим, что вершины экземпляра задачи о коммивояжере расположены на плоскости и что стоимость с(и, и) равна евклидову расстоянию между точками и и и. Покажите, что в оптимальном туре никогда не будет самопересечений. 35.3. Задача о покрытии мпожестаа Задача о покрытии множества — это задача оптимизации, моделирующая многие задачи распределения ресурсов.
Соответствующая ей задача принятия решения представляет собой обобщение ЫР-полной задачи о вершинном покрытии и, таким образом, является ХР-сложной. Однако приближенный алгоритм, разработанный для задачи о вершинном покрытии, в данном случае неприменим, поэтому следует попытаться поискать другие подходы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
