Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 243
Текст из файла (страница 243)
(35.10) Из неравенств (35.9) и (35.10) следует соотношение /С/ < ,') Н(!Я!) < /С ~ Н(шахЩ: ЯЕУ)), лес' которое и доказывает теорему. Осталось доказать неравенство (35.10). Рассмотрим произвольное множество Я Е У и индекс г = 1, 2,..., )С~, и введем величину яч = ~Я вЂ” (51 О Яз О . О Я;)), которая равна количеству элементов множества Я, оставшихся непокрытыми после того, как в алгоритме были выбраны множества Яы Яз,..., Я;. Определим величину ио = (5), равную количеству элементов множества Я (которые изначально непокрыты).
Пусть й — минимальный индекс, при котором выполняется равенство иь = О, т.е. каждый элемент множества Я покрывается хотя бы одним из множеств ЯыЯз,...,Яь. Тогда и; т > ио и при1 = 1,2,...,й и; 1 — и; элементов множества Я впервые покрываются множеством Я;. Таким образом, я 1 ск = ,') (сч 1 — сн) хеэ 1=! Заметим, что ф; — (51ОЯзО ОЯ; ~)~>ф — (Я10Яз0 ° ° ° 05; 1)!=и; ы поскольку при жадном выборе множества Яз гарантируется, что множество Я не может покрыть больше новых элементов, чем множество Я, (в противном случае вместо множества Я; было бы выбрано множество Я). Таким образом, мы получаем неравенство ь ,') с < ~) (и; 1 — и;).—.
лез г=з тч-1 Глава 35. Приближенные алгоритмы 11б9 Теперь ограничим эту величину следующим образом: 1 — и,) и; 1 ~~> с < ~> (и; вез 1 — < 1 и; 1 1 3 (так как з < и; 1) ~~) (Н(и, г) — Н(щ)) = 1=1 Н (ио) — Н (иь) = Н (ио) — Н (О) = Н(ио) = Н (!5~), (поскольку сумма сворачивается) (поскольку Н (0) = 0) что завершает доказательство неравенства (35.10). Следствие35.5.
Алгоритм Оклик Бит Сочли является (1п)Х)+1)-приближенным алгоритмом с полиномиальным временем работы. В некоторых приложениях величина гпах ЦЯ~: Я е У) — это небольшая константа, поэтому решение, которое возвращается алгоритмом Окнвоу Бит Сочен, больше оптимального на множитель, не превышающий малую константу.
Одно из таких приложений — получение с помощью описанного выше эвристического метода приближенного вершинного покрытия графа, степень вершин которого не превышает 3. В этом случае решение, найденное алгоритмом Оке~~' Янт Сочен, не более чем в Н (3) = 11/б раз больше оптимального решения, т.е. оно немного лучше решения, предоставляемого алгоритмом Аи'кок Чнктех Сочин. Упражнения 35.3-1. Каждое из перечисленных слов рассматривается как набор букв: (агас1, с1азЬ, с1гайп, Ьеагс1, 1озо, позе, зппп, з1асе, влаге, сйгеас1). Доказаюельсиио.
Достаточно воспользоваться неравенством (А.14) и теоремой 35.4. и Часть ЧП. Избранные темы 1170 Приведите покрытие множества, которое будет возвращено алгоритмом блеют Бнт Сочна„если преимущество имеет слово, которое находится в словаре выше других.
35.3-2. Покажите, что задача о покрытии множества в форме задачи принятия решения является ХР-полной. Для этого приведите к ней задачу о вершинном покрытии. 35.3-3. Покажите, как реализовать процедуру бкнвпу Бьт СОчнк, чтобы она выполнялась в течение времени О О л ~ ф~). 35.3-4. Покажите, что приведенное ниже неравенство (которое является более слабым по сравнению с тем, что было использовано в теореме 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п чепех-сечет ргоЫеш) задается неориентированный граф С = (У, Е), в котором каждой вершине о Е У назначается положительный вес зо (о).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
