Алгоритмы - построение и анализ (1021735), страница 243
Текст из файла (страница 243)
Покажите, что приведенное ниже неравенство (которое является более слабым по сравнению с тем, что было использовано в теореме 35.4) выполняется тривиальным образом: 1С) < ~С*~шах((Я~: Я Е У). 35.3-5. В зависимости от принципа, по которому осуществляется выбор в строке 4, алгоритм Окенче' Янт Сочин может возвращать несколько разных решений.
Разработайте процедуру ВАО Бвт Сочен 1нзтАмсв(п), возвращающую п-элемеитный экземпляр задачи о покрытии множества, для которого процедура бкнюу Бег СОчек при разной организации выбора в строке 4 могла бы возвращать различные решения, количество которых выражалось бы показательной функцией от и. 35.4 Рандомизация и линейное программирование В этом разделе исследуются два метода, весьма полезных для разработки приближенных алгоритмов: рандомизация и линейное программирование. Далее приводится простой рандомизированный алгоритм, позволяющий создать оптимизирующую версию решения задачи о 3-СХР выполнимости, после чего с помощью методов линейного программирования разрабатывается приближенный алгоритм для взвешенной версии задачи о вершинном покрытии.
В данном разделе эти два мощных метода рассматриваются лишь поверхностно. В сносках даются ссылки для дальнейшего изучения этой проблемы. Рандомизированный приближенный алгоритм для задачи о МАХ-3-СЯ выполнимости Рандомизированные алгоритмы можно создавать не только для поиска точных решений, но и для поиска приближенных решений. Говорят, что рандомизированный алгоритм решения задачи имеет «оэффициеит аплро«симации (арргох1т шапоп гайо) р (и), если для любых входных данных размера п математическое Глава 35. Приближенные алгоритмы 1171 ожидание стоимости С решения, полученного с помощью этого рандомизиро- ванного алгоритма, не более чем в р (п) раз превышает стоимость оптимального решения С*: /С С*~ п1ах ~ —, — ) < р(п).
1,С" С)- (35. 11) Рандомизированный алгоритм, позволяющий получить коэффициент аппроксимации р(п), называют рандомизированным р(п)-приблииеенным алгоритмом (гаврош)хек р (и)-арргох1ша11оп а18ог10пп). Другими словами, рандомизированный приближенный алгоритм похож на детерминистический приближенный алгоритм с тем отличием, что его коэффициент аппроксимации выражается через математическое ожидание.
Как видно из раздела 34.4, отдельно взятый экземпляр задачи о 3-СХР выполнимости может не выполняться. Чтобы он был выполнимым, должен существовать такой вариант присвоения переменных, при котором каждое выражение в скобках принимает значение 1. Если экземпляр невыполнимый, может возникнуть потребность оценить, насюлько он "близок" к выполнимому. Другими словами, может возникнуть желание определить, какие значения следует присвоить переменным, чтобы выполнялось максимально возможное количество выражений в скобках. Назовем задачу, которая получилась в результате, задачей о МАЛ'-3-СЖг выполнимости (МАХ-3-СХР забзбаЬ11йу). Входные данные этой задачи совпадают с входными данными задачи о 3-СХР выполнимости, а цель состоит в том, чтобы найти присваиваемые переменным значения, при которых максимальное количество подвыражений в сюбках принимает значение 1.
Теперь покажем, что если значения присваиваются каждой переменной случайным образом, причем значения О и 1 присваивается с вероятностью 1/2, то получится рандомизированный 8/7-приближенный алгоритм. В соответствии с определением 3-СХР выполнимости, приведенном в разделе 34.4, требуется, чтобы в каждом выражении в скобках содержалось ровно три различных литерала.
Затем предполагается, что ни одно из выражений в скобках не содержит одновременно переменной и ее отрицания. (В упражнении 35.4-1 предлагается отказаться от этого предположения.) Теорема 35.6. Для заданного экземпляра задачи о МАХ-3-СХР выполнимости с и переменными хм ха,..., х„и т выражениями в сюбках рандомизированный алгоритм, в котором каждой переменной независимо с вероятностью 1/2 присваивается значение 1 и с вероятностью 1/2 — значение О, является рандомизированным 8/7-приближенным алгоритмом. У; = 1(1-е подвыражение в скобках выполняется) Доказательство.
Предположим, что каждой переменной независимо с вероятно- стью 1/2 присваивается значение 1 и с вероятностью 1/2 — значение О. Определим для 1 = 1, 2,..., т индикаторную случайную величину Часть ЧП. Избранные темы 1172 так, что равенство У; = 1 выполняется, если хоть одному из литералов, содержащихся в ь'-м выражении в скобках, присвоено значение 1. Поскольку ни один из литералов не входит более одного раза в одно и то же выражение в скобках, и поскольку предполагается, что одни и те же скобки не содержат одновременно переменную и ее отрицание, присвоение значений трем переменным в каждых скобках выполняется независимым образом.
Выражение в скобках не выполняется только тогда, когда всем трем его литералам присваивается значение О, поэтому Рг (1-е подвыражение не выполняется) = (1/2) = 1/8. Тогда Рг (1-е подвыражение выполняется) = 1 — 1/8 = 7/8. Поэтому, согласно лемме 5.1, Е [Ц = 7/8. Пусть всего выполняется У подвыражений в скобках, те. У = 2 ~ 'Уь Тогда мы получаем 1П т ти Е[У1 = Е ~~) У; = ~) Е[Ц = ~~~ 7/8 = 7т/8, 1=1 1=1 1=1 где второе равенство следует из линейности математического ожидания. Очевидно, что верхняя граница количества выполняющихся подвыражений в скобках равна т, поэтому коэффициент аппроксимации не превышает значения пз/(7та/8) = = 8/7. И Аппроксимация взвешенного вершинного покрытия с помощью линейного программирования В задаче о вершинном покрытии с минимальным весам (т1л1щшп-юе181п чепех-сечет ргоЫеш) задается неориентированный граф С = (У, Е), в котором каждой вершине о Е У назначается положительный вес зо (о).
Вес любого вершинного покрытия У'СУ определяется как и (У') = 2 „еч, и (п). В задаче нужно найти вершинное покрытие с минимальным весом. К этой задаче нельзя применить ни алгоритм, который использовался для поиска невзвешенного вершинного покрытия, ни рандомизированное решение, так как оба эти метода могут дать решение, далекое от оптимального. Однако с помощью задачи линейного программирования можно вычислить нижнюю границу веса, который может возникать в задаче о вершинном покрытии минимального веса.
Затем мы "округлим" это решение и с его помощью получим вершинное покрытие. Предположим, что каждой вершине о е Ъ' сопоставляется переменная х (о), и поставим условие, чтобы х (о) е (О, 1) для каждой вершины ч е У. Равенство х (о) = 1 интерпретируется как принадлежность вершины ч вершинному покрытию, а равенство х (о) = Π— как ее отсутствие в вершинном покрытии. Тогда Глава 35. Приближенные алгоритмы 1173 ограничение, согласно которому для любого ребра (и, о) хотя бы одна из вершин и и с должна входить в вершинное покрытие, можно наложить с помощью неравенства х (и) + х (о) > 1. Такой подход приводит нас к 0-1 целочисленной задаче линейного нрограимирования (0-1 шгейег ргойгагп) поиска вершинного покрытия с минимальным весом: Минимизировать ,'! ю (о) х (с) при условиях че х(и)+х(с) > 1 х(о) ~ (0,1) (35.
12) для всех (и, о) Е Е (35.13) для всех о ~ Ъ'. (35.14) Минимизировать ~~! то (с) х (о) при условиях чек х(и)+х(о) > 1 х(п) < 1 х(п) > 0 (35.15) для всех (и, с) Е Е (35.16) для всех о Е У (35.17) для всех е б Ъ'. (35.18) Любое допустимое решение 0-1 целочисленной задачи линейного программирования, определенной выражениями (35.12)-(35.!4), также является допустимым решением задачи линейного программирования, определенной выражениями (35.15)-(35.18). Поэтому оптимальное решение задачи линейного программирования является нижней границей оптимального решения 0-1 целочисленной задачи, а следовательно, нижней границей оптимального решения задачи о вершинном покрытии с минимальным весом. В приведенной ниже процедуре с помощью решения сформулированной выше задачи линейного программирования строится приближенное решение задачи о вершинном покрытии с минимальным весом: АРРКОХ М!Х %Е!СНТ ЧС(С, ш) 1 С+ — 1! 2 Вычисляется х, оптимальное решение задачи линейного программирования (35.15)-(35.18) 3 1ог (для) каждой вершины с Е Ъ' В частном случае, когда все веса ю (о) равны 1, мы получаем ХР-сложную оптимизирующую версию задачи о вершинном покрытии.
Из упражнения 34.5-2 известно, что обычный поиск величин х (с), удовлетворяющих условиям (35.13) и (35.14), — ХР-сложная задача, и что непосредственная польза извлекается не из такой формулировки. Предположим, однако, что вместо ограничения х (о) Е б (О, 1) накладывается условие 0 < х(о) < 1. Тогда мы получим ослабленную задачу линейного нрограммирования (1шеаг-ргойгапптппй ге!ахагюп): Часть ЧП. Избранные темы 1174 4 до 11'х(о) > 1/2 5 гйеп С вЂ” С0(о) 6 гегпгп С Опишем работу процедуры АГГК0Х МЛЧ %Шсйт ЧС.
В строке 1 инициализируется пустое вершинное покрытие. В строке 2 формулируется и решается задача линейного программирования, определенная соотношениями (35.15)-(35.18). В оптимальном решении каждой вершине о сопоставляется величина 0 < й (и) < < 1. С помощью этой величины в строках 3 — 5 определяется, какие вершины добавятся в вершинное покрытие С. Если х(и) > 1/2, вершина о добавляется в покрытие С; в противном случае она не добавляется. В результате "округляется" каждая дробная величина, входящая в решение задачи линейного программирования, и получается решение 0-1 целочисленной задачи, определенной соотношениями (35.12)-(35.14): Наконец, в строке 6 возвращается вершинное покрытие С.
Теорема 35.1. Алгоритм Аи'кох М1н %шснт ЧС вЂ” это 2-приближенный алгоритм с полиномиальным временем выполнения, позволяющий решить задачу о вершинном покрытии с минимальным весом. Доказаигельство. Поскольку существует алгоритм с полиномиальным временем решения, позволяющий решить задачу линейного программирования в строке 2, и поскольку цикл 1ог в строках 3 — 5 завершает свою работу в течение полиномиального времени, алгоритм АГРНОХ М1Н %ШОНт ЧС выполняется в течение полиномиального времени.
Теперь покажем, что он является 2-приближенным алгоритмом. Пусть С'— оптимальное решение задачи о вершинном покрытии с минимальным весом, а з' — значение оптимального решения задачи линейного программирования, определенной соотношениями (35.15)-(35.18). Поскольку оптимальное вершинное покрытие — допустимое решение этой задачи, величина з' должна быть нижней границей величины ш (С"), т.е. выполняется неравенство г' < ю (С') (35.19) Далее, утверждается, что при округлении дробных значений переменных й (о) получается множество С, которое является вершинным покрытием, удовлетворяющим неравенству ш (С) < 2г".
Чтобы убедиться, что С вЂ” вершинное покрытие, рассмотрим произвольное ребро (и, о) е Е. Согласно ограничению (35.16), должно выполняться неравенство х(и) + х(и) > 1, из которого следует, что хотя бы одна из величин й (и) и й (о) не меньше 1/2. Поэтому хотя бы одна из вершин и и о будет включена в вершинное покрытие, а следовательно, будут покрыты все ребра.
Глава 35. Приближенные алгоритмы 1175 Теперь рассмотрим, чему равен вес этого покрытия. Имеем следующую цепочку соотношений: з' = ,'> ю (с) й (с) > чек > ,'~ ю (с)х (с) > вел";я(и) >1/3 > ~> ю(с) 1 червя(в))~1/3 1 = ,'~, ю (с) . — = 2 чЕС 1 = — ~~> ю(с) = 2 ивС 1 = -ю (С) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
