Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 260
Текст из файла (страница 260)
(Максимальное иарасачеиеаиие (шах)ша1 шагслшй) — это паросочетание, юторое не является собственным подмножеством ни одного другого паросочетания.) Как было показано при доказательстве теоремы 35.1, размер максимального паросочетания равен нижней границе размера оптимального вершинного покрытия. Алгоритм возвращает вершинное покрытие, размер которого не более чем в два раза превышает размер максимального паросочетания множества А. Составив отношение размера возвращаемого решения к полученной нижней границе, находим коэффициент аппроксимации. Эта методика будет использоваться и в следующих разделах. Упражнения 35.1.1 Приведите пример графа, для которого процедура Арркох-Чектех-Сочкк всегда возвращает неоптимальное решение. 35.1.2 Докажите, что множество ребер, выбранных в строке 4 процедуры АггкохЧкктех-Сочик образует максимальное паросочетание в графе С.
35.1.3 * Профессор предложил такую эвристическую схему решения задачи о вершинном покрытии. Одна за другой выбираются вершины с максимальной степенью, и для каждой из них удаляются все инцидентиые ребра. Приведите пример, демонстрирующий, что коэффициент аппроксимации, предложенной профессором, превышает 2. (Указаииес попытайтесь построить двудольный граф, вершины в левой части которого имеют одинаковые степени, а вершины в правой части — разные степени.) Глава 55.
Приближенные алгоритмы Пбз Разработайте эффективный жадный алгоритм, позволяющий найти оптимальное вершинное покрытие дерева за линейное время. 55.1.5 Из доказательства теоремы 34А2 известно, что задача о вершинном покрытии и 1чР-полная задача о клике являются взаимодополняющими в том смысле, что оптимальное вершинное покрытие — это дополнение к клике максимапьного размера в дополняющем графе. Следует ли из этого, что для задачи о клике существует приближенный алгоритм с полиномиальным временем решения, обладающий постоянным коэффициентом аппроксимации? Обоснуйте свой ответ. 35.2.
Задача о коммивоижере Обратимся к задаче о коммивояжере, представленной в разделе 34.5.4. В ней задается полный неориентированный граф С = (1', Е), каждому из ребер (и, о) е Е которого сопоставляется неотрицательная целочисленная стоимость с(и,о), и в графе С требуется найти гамильтонов цикл минимальной стоимости.
Введем дополнительное обозначение с(А) — полную стоимость всех ребер подмножества АСЕ: с(А) = ~~> с(и,о) . (и,и)сА Во многих практических ситуациях наиболее дешевый переход из места и в место ш — по прямой, так что, если по пути зайти в какой-нибудь промежуточный путь о, это не может привести к уменьшению стоимости.
Выражаясь другими словами, если срезать путь, пропустив какой-нибудь промежуточный пункт, это никогда не станет причиной увеличения стоимости. Формализуем зто понятие, выдвинув утверждение, что функция стоимости с удовлетворяет иеравенслвву лвреугольника (цзапй!е шеццайгу), если для всех вершин и, о, во Е Ъ' с(и,ео) < с(и,о) + с(о,и!) . Неравенство треугольника имеет естественный характер и автоматически удовлетворяется во многих приложениях. Например, если вершины графа — точки на плоскости, а стоимость перехода от одной вершины к другой выражается обычным евклидовым расстоянием между ними, то неравенство треугольника выполняется. (Кроме евклидова расстояния, существует множество других функций стоимости, удовлетворяющих неравенству треугольника.) Как видно из упр. 35.2.2, задача о коммивояжере является ХР-полной даже в том случае, если потребовать, чтобы функция стоимости удовлетворяла неравенству треугольника.
Таким образом, мало надежд найти алгоритм с полиномиальным временем работы, позволяющий получить точное решение этой задачи. Поэтому есть смысл заняться поиском хороших приближенных алгоритмов. Нбя Часть 171. Избранные таиы В разделе 35.2.1 исследуется 2-приближенный алгоритм, позволяющий решить задачу о юммивояжере, в которой выполняется неравенство треугольника. В разделе 35.2.2 будет показано, что без соблюдения неравенства треугольника приближенный алгоритм с полиномиапьным временем работы„характеризующийся постоянным коэффициентом аппроксимации, не существует, если толью не окажется справедливым соотношение Р = ХР.
35.2.1. Задача о коммивояжере с неравенством треугольника Применив методику из предыдущего раздела, сначала вычислим структуру— минимальное остовное дерево, — вес которой яапяется нижней границей длины оптимального тура коммивояжера. Затем с помощью этого минимального остов- ного дерева создадим тур, стоимость которого не более чем в два раза превышает вес этого дерева при условии, что функция стоимости удовлетворяет неравенству треугольника. Этот подход реализован в приведенном ниже алгоритме, в котором используется алгоритм построения минимального остовного дерева МБТ-Рк!м, описанный в разделе 23.2.
Параметр С представляет собой полный неориентированный граф, а функция стоимости удовлетворяет неравенству треугольника. Аи кох-ТБР-Толк!С, с) 1 Выбираем вершину г е С. Р в качестве "юрневой" 2 Вычисляем минимальное остовное дерево Т для С из корня г с использованием алгоритма МБТ-Рк1м1С, с, г) 3 Пусть Н вЂ” список вершин, упорядоченный в соответствии с моментом первого посещения при обходе дерева Т в прямом порядке 4 гегнгп гамильтонов цикл Н Вспомним из раздела 12.1, что при прямом обходе дерева рекурсивно посещаются все его вершины, причем вершина заносится в список при первом посещении, до посещения ее дочерних вершин. Работа процедуры Аггкох-ТБР-Толк показана на рис.
35.2. В части (а) показан полный неориентироваиный граф, а в части (б) — минимальное остовное дерево Т с корнем а, вычисленное процедурой МБТ-Рк!м. В части (в) показано, как прямой обход дерева Т посещает вершины, а в части (г) показан соответствующий тур, возвращаемый процедурой Аггкох-ТБР-Тоок. В части (г) приведен оптимальный тур, который короче примерно на 23'Ъ. Согласно результатам упр. 23.2.2 даже при простой реализации алгоритма МБТ-Рк!м время работы алгоритма Акгкох-ТБР-Тоок равно !В!аз). Теперь покажем, что если функция стоимости в экземпляре задачи юммивояжера удовлетворяет неравенству треугольника, то алгоритм Аггкох-ТБР-Толк возвращает тур, стоимость которого не более чем в два раза превышает стоимость оптимального тура.
Глава 35. Приближенные алгоритмы Пб5 .'Ь) :;ау) .. + ~,к вв - ° „; 'К '1 Ь(б * ',Ф :"'4',"-'~ Ь (в) (б) [г) Рнс. 33.7. Работа процелуры Авккох-ТБР-Тоок, (в) Полный неориентированный граф. Вершины лежат на пересечении линий целочисленной решетки. Например, Г" находится на одну единицу правее и на две выше. чем Ь. Функция стоимости мекду двумя точками представляет собой обычное евклидово рвсспжние.
(6) Минимальное остовное дерево Т полного графя, вычисленное процедурой МБТ-Рщм. Корневой вершиной является вершина а. Показаны только те ребра. жпорые входят в минимальное остовное дерево. Метки присвоены вершинам таким образом, что они добавлшотся алгоритмом МБТ-Рк)м в основное дерево в алфавитном порядке.
(в) Порядок посещенил вершин при прямом обходе дерева Т, начиная с вершины а. При полном обходе дерева вершины посещакпсв в порядке а, Ь, с, Ь, Ь, Ь, а, 4, е, г', е, д, е, ((, а. При прямом обходе дерева Т составляется список вершин, посещенных впервые (на рисунке возле каждой такой вершины поставлена точка). Полученный в результате список имеет внд а, Ь, с, Ь, ((, е, 1, д.
(г) Тур Н, возвращенный алгоритмом Аквкох-ТБР-Тоок. Его полная сгоимос)ь составляет приблизительно 19.074. (д) Оптимальный тур Н' в исходном полном графе. Его общая стоимость приблизительно равна 14.713. Теорема 55.2 Алгоритм Арркох-ТЗР-То()к является 2-приближенным алгоритмом с полино- миальным временем работы, решающим задачу коммивояжера, в которой удовле- творяется неравенство треугольника. Даказагиелвс)наа Ранее было показано, что время работы алгоритма АрркохТБР-То()к выражается полиномиальной функцией.
Обозначим через Н' тур, который является оптимальным для данного множества вершин. Поскольку путем удаления из этого тура одного ребра получается остовное дерево, вес минимального остовного дерева Т, вычисляемого в строке 2 процедуры Арркох-ТИР-То()к, равен нижней границе стоимости оптимального тура, т.е. выполняется неравенспю !16б Часть еп. Избранные тамы При полном обходе (И! зьсайг) дерева Т составляется список вершин, которые посещаются впервые, а также когда к ним происходит возврат после посещения поддерева. Обозначим этот обход через И'. При полном обходе в рассматриваемом примере вершины посещаются в следующем порядке: а,Ь,с,Ь,Ь,Ь,а,д,е,7,е,д,е,Н,а Поскольку при полном обходе каждое ребро дерева Т проходится ровно по два раза, естественным образом обобщив определение стоимости с на множества, в которых ребра встречаются по несколько раз, получаем равенство с(Ис) = 2с(Т) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
