Алгоритмы - построение и анализ (1021735), страница 240
Текст из файла (страница 240)
В части в рисунка выбрано ребро (е, г"), а вершины е и г" добавляются в множество С. В части г выбрано ребро (И,д), а вершины д и д добавляются в множество С. В части д показано множество С, которое представляет собой вершинное покрытие, полученное в результате выполнения алгоритма Аггкох Чнктнх Сочнк. Как видно из рисунка, оно состоит из шести вершин: Ь, с, с1, е, г", д. В части е рисунка показано оптимальное вершинное покрытие для рассмотренного экземпляра задачи.
Оно состоит всего из трех вершин: Ь, д и е. Часть Ч11. Избранные темы 1156 Теорема 35.1. Алгоритм АРекох Чектех Сочек является 2-приближенным ал- горитмом с полиномиальным временем работы. Доказаюиельсигво. Мы уже показали, что время работы алгоритма Аеекох Чектех Сочек выражается полиномиальной функцией. Множество вершин С, которое возвращается алгоритмом Ае кох Чектех Сочек, является вершинным покрытием, поскольку алгоритм не выходит из цикла, пока каждое ребро Е [С] не будет покрыто некоторой вершиной из множества С. Чтобы показать, что рассматриваемый алгоритм возвращает вершинное покрытие, размер которого превышает размер оптимального вершинного покрытия не более чем в два раза, обозначим через А множество ребер, выбранных в строке 4 алгоритма Аеекох Чектех Сочек.
Чтобы покрыть ребра множества А, каждое вершинное покрытие, в том числе и оптимальное покрытие С', должно содержать хотя бы одну конечную точку каждого ребра из множества А. Никакие два ребра из этого множества не имеют общих конечных точек, поскольку после того, как ребро выбирается в строке 4, все другие ребра с такими же конечными точками удаляются из множества Е' в строке 6. Таким образом, никакие два ребра из множества А не покрываются одной и той же вершиной из множества С', из чего следует, что нижняя граница размера оптимального вершинного покрытия равна 1С'~ > 1А). (35.2) При кажцом выполнении строки 4 выбирается ребро, ни одна из конечных точек которого пока еще не вошла в множество С.
Это позволяет оценить сверху (фактически указать точную верхнюю границу) размера возвращаемого вершинного покрытия: 1С) = 21А). (35. 3) Сопоставляя уравнения (35.2) и (35.3), получаем 1С( = 21А! < 21С'), что и доказывает теорему. Еще раз вернемся к приведенному выше доказательству. На первый взгляд может показаться удивительным, как можно доказать, что размер вершинного покрытия, возвращенного процедурой Аеккох Чектех Сочек, не более чем в два раза превышает размер оптимального вершинного покрытия, если не известно, чему равен размер оптимального вершинного покрытия.
Это становится возможным благодаря использованию нижней границы оптимального вершинного покрытия. Как предлагается показать в упражнении 35.1-2, множество А, состоящее из ребер, выбранных в строке 4 процедуры Аеекох Чектех Сочек, фактически является Глава 35. Приближенные алгоритмы 1157 максимальным паросочетанием вершин в графе С. (Максимальное иаросочетание (шахппа1 ша1сЫпд) — это паросочетание, которое не является собственным подмножеством какого-нибудь другого паросочетания.) Как было показано при доказательстве теоремы 35.1, размер максимального паросочетания равен нижней границе размера оптимального вершинного покрытия. Алгоритм возвращает вершинное покрытие, размер которого не более чем в два раза превышает размер максимального паросочетания множества А.
Составив отношение размера возвращаемого решения к полученной нижней границе, находим коэффициент аппроксимации. Эта методика будет использоваться и в следующих разделах. Упражнения 35.1-1. Приведите пример графа, для которого процедура АРгкох Чнктех Сочли всегда возвращает неоптимальное решение. 35.1-2. Обозначим через А множество ребер, выбранных в строке 4 процедуры Авркох Чектпх Сочли. Докажите, что множество А — максимальное паросочетание в графе С. * 35.1-3. Профессор предложил такую эвристическую схему решения задачи о вершинном покрытии. Одна за другой выбираются вершины с максимальной степенью, и для каждой из них удаляются все инцидентные ребра.
Приведите пример, демонстрирующий, что коэффициент аппроксимации, предложенной профессором, превышает 2. (Указание: попытайтесь построить двудольный граф, вершины в левой части которого имеют одинаковые степени, а вершины в правой части — разные степени.) 35.1-4. Сформулируйте эффективный жадный алгоритм, позволяющий найти оптимальное вершинное покрытие дерева в течение линейного времени. 35.1-5. Из доказательства теоремы 34.12 известно, что задача о вершинном покрытии и ХР-полная задача о клике являются взаимодополняющими в том смысле, что оптимальное вершинное покрытие — это дополнение к клику максимального размера в дополняющем графе.
Следует лн из этого, что для задачи о клике существует приближенный алгоритм с полиномиальным временем решения, обладающий постоянным коэффициентом аппроксимации? Обоснуйте ваш ответ. 35.2 Задача о коммивояжере Обратимся к задаче о коммивояжере, представленной в разделе 34.5.4. В этой задаче задается полный неориентированный граф С = (У, Е), каждому из ребер (и,п) е Е которого сопоставляется неотрицательная целочисленная стоимость с(и,с), и необходимо найти гамильтонов цикл (тур) минимальной стоимости Часть ЧП. Избранные темы 1158 графа С. Введем дополнительное обозначение с(А) — полную стоимость всех ребер подмножества А С Е; с(А) = ~~~ с(и, и). (и,ь) сА Во многих практических ситуациях наиболее дешевый переход из места и в место ш — всегда по прямой, так что если по пути зайти в какой-нибудь промежуточный путь и, это не может привести к уменьшению стоимости.
Выражаясь другими словами, если срезать путь, пропустив каюй-нибудь промежуточный пункт, — это никогда не станет причиной увеличения стоимости. Формализуем это понятие, выдвинув утверждение, что функция стоимости с удовлетворяет неравенству треугольнике (птап81е (пейна!йу), если для всех вершин и, и, ю Е Ъ' с(и,ю) < с(и,и)+с(и,ю).
Неравенство треугольника имеет естественный характер и автоматически удовлетворяется во многих приложениях. Например, если вершины графа — точки на плосюсти, и стоимость перехода от одной вершины к другой выражается обычным евклидовым расстоянием между ними, то неравенство треугольника выполняется. (Кроме евклидового расстояния существует множество других функций стоимости, удовлетворяющих неравенству треугольника.) Как видно из упражнения 35.2-2, задача о коммивояжере является МР-полной даже в том случае, если потребовать, чтобы функция стоимости удовлетворяла неравенству треугольника. Таким образом, мапо надежд найти алгоритм с полиномиальным временем работы, позволяющий получить точное решение этой задачи.
Поэтому есть смысл заняться поиском хороших приближенных алгоритмов. В разделе 35.2.1 исследуется 2-приближенный алгоритм, позволяющий решить задачу о юммивояжере, в которой выполняется неравенство треугольника. В разделе 35.2.2 будет показано, что без соблюдения неравенства треугольника приближенный алгоритм с полиномиальным временем работы, характеризующийся постоянным коэффициентом аппроксимации, не существует, если только не справедливо соотношение Р = МР. 35.2.1 Задача о коммивояжере с неравенством треугольника Воспользовавшись методиюй предыдущего раздела, сначала вычислим минимальное остовное дерево, вес которого является нижней границей длины оптимального тура коммивояжера.
Затем с помощью этого минимального остовного дерева создадим тур, стоимость которого не более чем в два раза превышает вес этого дерева при условии, что функция стоимости удовлетворяет неравенству Глава 35. Приближенные алгоритмы 1159 треугольника. Этот подход реализован в приведенном ниже алгоритме, в котором используется алгоритм построения минимального остовного дерева МБТ Рк1м, описанный в разделе 23.2. Аггкох ТБР Тоок(С,с) 1 Выбирается вершина т Е ЦС~ которая будет "корневой" 2 Из корня т с помощью алгоритма МБТ-Ршм(С, с, т) строится минимальное остовное дерево Т для графа С 3 Пусть Т, — список вершин, которые посещаются при обходе вершин дерева Т в прямом порядке 4 геГпгп Гамильтонов цикл Н, который посещает вершины в порядке перечисления в списке Т, Напомним, что при прямом обходе дерева рекурсивно посещаются все его вершины (см.
раздел 12.1), причем вершина заносится в список при первом посещении, до посещения ее дочерних вершин. Работа процедуры Аи'кох ТБР Толк проиллюстрирована на рис. 35.2. В части а рисунка показано заданное множество точек, расположенных в вершинах целочисленной решетки. Например, точка У находится на один шаг правее и на два шага выше от точки Ь. В качестве функции стоимости между двумя точками используется обычное евклидово расстояние.
В части б рисунка изображено полученное в результате выполнения алгоритма МБТ Ркгм минимальное остовное дерево Т, берущее свое начало в корневой вершине а. Вершинам присвоены метки таким образом, что они добавляются алгоритмом МБТ Рк1м в основное дерево в алфавитном порядке. В части в показан порядок посещения вершин при прямом обходе дерева Т, начиная с вершины а. При полном обходе дерева вершины посещаются в порядке а, Ь, с, Ь, Ь, Ь, а, и, е, г, е, д, е, И, а. При прямом обходе дерева Т составляется список вершин, посещенных впервые (на рисунке возле каждой такой вершины поставлена точка). Полученный в результате список имеет вид а, Ь, с, й, И, е, г", д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
