Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 263
Текст из файла (страница 263)
В этом случае решение, найденное алгоритмом Океепч-бет-Сочен, не более чем в Н(3) = 11/6 раз больше оптимального решения, т.е. оно несколько лучше решения, предоставляемого алгоритмом АРРкох-Чектех-СОчек. Упражнении 35.3.1 Будем рассматривать каждое из приведенных далее слов как множество букв: (агйс1, с1азЬ, с1гайп, Ьеагс1, 3.озС,позе, з1зпп, з1аСе, зпаге,сйгеаб). Приведите покрытие множества, которое будет возвращено алгоритмом Океепч- Бет-Сочен, если неоднозначности разрешаются в пользу слов, которые находят- ся в словаре раньше других, 35З.2 Покажите, что задача о покрытии множества в форме задачи принятия решения является МР-полной.
Для этого приведите к ней задачу о вершинном покрытии. 35.3.3 Покажите, как реализовать процедуру Океепч-бет-Сочен, чтобы она выполия- лась за время О(~ з г ~Я~). 35.3.4 Покажите, что приведенное ниже неравенство (более слабое по сравнению с ис- пользованным в теореме 35.4) выполняется тривиальным образом: Доказательство. Достаточно воспользоваться неравенством (А.14) и теоремой 35.4. Глава 55 Лридлииееииые авгаэгитлгы 7! 75 35.3.5 В зависимости от принципа разрешения неоднозначностей в строке 4 алгоритм Окпни'-Япт-Сочпк может возвращать несколько разных решений. Разработайте процедуру Влп-Бпт-Сочпк-1мзтлхсп(п), возврашающую п-элементный экземпляр задачи о покрытии множества, для которого процедура Слкпни'-Бпт-Сочил при разной организации разрешения неоднозначностей в строке 4 могла бы возвращать различные решения, количество которых выражалось бы показательной функцией от и.
35.4. Рандомнзлция н линейное программированне В этом разделе мы изучим два весьма полезных для разработки приближенных алгоритмов метода; рандомизацию и линейное программирование. Здесь будет приведен простой рандомизированный алгоритм, позволяющий создать оптимизирующую версию решения задачи о З-СИР-выполнимости, после чего с помощью методов линейного программирования будет разработан приближенный алгоритм для взвешенной версии задачи о вершинном покрытии. В тексте раздела эти два мощных метода рассматриваются лишь поверхностно, но в заключительных замечаниях к главе даются ссылки для дальнейшего изучения этой темы.
Рандомизироваиный приблнженныи алгоритм дли задачи о МАХ-3-С%-выполнимости Рандомизированные алгоритмы могут применяться для поиска как точных, так и приближенных решений. Говорят, что рандомизированный алгоритм решения задачи имеет коэффициент аппроксимации (арргохппайоп га1ю) р(п), если для любых входных данных размера п ожидаемая стоимость С решения, полученного с помощью этого рандомизированного алгоритма, не более чем в р(п) раз превышает стоимость С* оптимального решения: гпах —, — < р(п) . (35.13) Рандомизированный алгоритм, позволяющий получить коэффициент аппроксимации р(п), называют рандамиэирааанным р(п)-приближенным алгоритмам (гапбош1геб р(п)-арргохппайоп а!яопбпп).
Другими словами, рандомизированный приближенный алгоритм похож на детерминистический приближенный алгоритм, с тем отличием, что его коэффициент аппроксимации относится к ожидаемой стоимости. Конкретный экземпляр задачи о З-СХЕ-выполнимости, определенной в разделе 34.4, может не выполняться. Чтобы он был выполнимым, должен существовать такой вариант присвоения переменных, при котором каждое подвыражение в скобках принимает значение 1. Если экземпляр невыполнимый, может возникнуть потребность оценить, насколько он "близок" к выполнимому.
Другими сло- Игб Часть еэ!. Иэбранные таты вами, может возникнуть желание определить, какие значения следует присвоить переменным, чтобы выполнялось максимально возможное юличество подвыражений в скобках. Назовем задачу, которая получилась в результате, задачей о МАХ-3-СЛТ-вылоллимослэи (МАХ-3-С% аа!!зба)п!!гу). Входные данные этой задачи совпадают с входными данными задачи о З-С)ь(р-выполнимости, а цель состоит в том, чтобы найти присваиваемые переменным значения„при которых значение 1 принимает максимальное количество подвыражений в сюбках. Теперь покажем, что если значения присваиваются каждой переменной случайным образом, причем значения О и 1 присваивается с вероятностью 1/2, то получается раидомизированный 8/7-приближенный алгоритм.
В соответствии с определением 3-С!ь)р-выполнимости, приведенном в разделе 34.4, требуется, чтобы в каждом подвыражении в скобках содержалось ровно три различных литерала. Кроме того, предполагается, что ни одно из выражений в скобках не содержит одновременно переменной и ее отрицания. (В упр. 35.4.1 предлагается отказаться от этого предположения.) Теорема 35.6 Для заданного экземпляра задачи о МАХ-3-С!ь)Р-выполнимости с п переменными хм ха,..., х„и т подвыражениями в скобках рандомизированный алгоритм, в котором каждой переменной независимо с вероятностью 1/2 присваивается значение 1 и с той же вероятностью 1/2 — значение О, является рандомизированным 8/7-приближенным алгоритмом. Доказалеепьслзво. Предположим, что каждой переменной независимо с вероятностью 1/2 присваивается значение 1 и с той же вероятностью 1/2 — значение О.
Определим для ! = 1, 2,..., т индикаторную случайную величину У, = 1(подвыражение г выполняется) так что равенство У, = 1 выполняется, если хотя бы одному из литералов, содержащихся в 1-м выражении в скобках, присвоено значение 1. Поскольку ни один из литералов не входит в одно и то же подвыражение в скобках более одного раза н посюльку предполагается, что одни и те же скобки не содержат одновременно переменную и ее отрицание, присвоение значений трем переменным в каждых скобках выполняется независимым образом. Выражение в скобках не выполняется только тогда, когда всем трем его литералам присваивается значение О, поэтому Рг (подвыражение ! не выполняется) = (1/2)з = 1/8.
Таким образом, мы имеем Рг (подвыражение ! выполняется) = 1 — 1/8 = 7/8, и согласно лемме 5.1 имеем Е [Ц = 7/8. Пусть У вЂ” общее количество выполняющихся подвыражений, так что У = У! + Уз + .. + У . Тогда Е[У[ = Е ~~~ У; т Е [У,[ (из линейности математического ожидания) Глава 35. Прий~иженные алгоритмы Ы77 ы 7/8 ~=1 = 7т/8. Очевидно, что верхняя граница количества выполняющихся подвыражений в скобках равна т, поэтому коэффициент аппроксимации не превышает значе- ния т/(7т/8) = 8/7.
минимизировать 2 ш(о) х(о) чек при условиях х(и) + х(о) > 1 для каждого (и, с) Е Е х(о) Е (0,1) для каждой о Е $' . (35.14) (35. 15) (35.1б) В частном случае, когда все веса зс(о) равны 1, мы получаем 74Р-сложную оптимизирующую версию задачи о вершинном покрытии. Предположим, однако, что ограничение х(о) Е (О, 1) убирается, а вместо него накладывается условие 0 < х(о) < 1. Тогда мы получим ослабленную задачу линейного нрогранмиро- Аппроксимация взвешенного вершинного покрытии с помощью линейного программирования В задаче о вершинном накрытии с минимальным ассам (ш1пппшп-зче(8М успех-сосет ргоЫеш) задается неориентнрованный граф С = (17, Е), в котором каждой вершине с е $' назначается положительный вес ш(с).
Вес любого вершинного покрытия УГ с 17 определяется как ю($") = ~ „су, ю(с). В задаче нужно найти вершинное покрытие с минимальным весом. К этой задаче нельзя применить нн алгоритм, который использовался для поиска невзвешенного вершинного покрытия, ни рандомизированное решение, так как оба эти метода могут дать решение, далекое от оптимального. Однако с помощью задачи линейного программирования можно вычислить нижнюю границу веса, который может возникать в задаче о вершинном покрьпии минимального веса. Затем мы "округлим" это решение и с его помощью получим вершинное покрытие.
Предположим, что каждой вершине о Е 1' сопоставляется переменная х(о), н поставим условие, чтобы х(о) было равно либо О, либо 1 для каждой вершины с Е Ъ'. Равенство х(о) = 1 интерпретируется как принадлежность вершины с вершинному покрытию, а равенство х(с) = 0 — как ее отсутствие в вершинном покрытии. Тогда ограничение, согласно которому для любого ребра (и, о) хотя бы одна из вершин и и о должна входить в вершинное покрытие, можно наложить с помощью неравенства х(и) + х(о) > 1. Такой подход приводит нас к б-1-целочисленной задаче линейного программирования (0-1 1пгейег ргойгаш) поиска вершинного покрытия с минимальным весом: И7б Часть Н1. Избранные тены вавил (1(пеаг-ргойгапппшй ге!алайоп): минимизировать ~~~ зс(и) х(и) ее и при условиях (35.17) х(и) + х(и) > 1 для каждого (и,и) Е Е х(и) < 1 для каждой и Е 1' х(и) > 0 для каждой и е е' .
(35.18) (35.19) (35.20) АРРНОх-М1н-%е!Онт-ЧС(С, и) 1 С=И 2 Вычисление х, оптимальною решения задачи линейного программирования (35.17)-(35.20) 3 (ог каждой и Е )з 4 Ы х(и) > 1/2 5 С = С !1(и) 6 гетнгп С Процедура АРРкох-М!н-%е!Онт-ЧС работает следуюшим образом. В строке 1 вершинное покрытие инициализируется пустым множеством. В строке 2 формулируется и решается задача линейного программирования, определенная в (35.17)-(35.20). В оптимальном решении с каждой вершиной и связано значение 0 < х(и) < 1.
С помошью этой величины в строках 3 — 5 определяется, какие вершины добавятся в вершинное покрытие С. Если х(и) > 1/2, вершина и добавляется в покрытие С; в противном случае она не добавляется. В результате каждая дробная величина, входящая в решение задачи линейного программирования, "округляется" и получается решение 0-1 целочисленной задачи, определенной в (35.14)-(35.16).
Наконец в строке 6 возвращается вершинное покрытие С. Теорема 35. 7 Алгоритм АРРкох-М!Н-%Е!Онт-ЧС является 2-приближенным алгоритмом с полиномиальным временем работы, позволяюшим решить задачу о вершинном покрытии с минимальным весом. Любое допустимое решение 0-1 целочисленной задачи линейного программирования, определенной в (35.14)-(35.16), является также допустимым решением задачи линейного программирования, определенной в (35.17)-(35.20). Поэтому оптимальное решение задачи линейного программирования является нижней границей оптимального решения 0-1 целочисленной задачи, а следовательно, нижней границей оптимального решения задачи о вершинном покрытии с минимальным весом.
В приведенной ниже процедуре с помощью решения сформулированной выше задачи линейного программирования строится приближенное решение задачи о вершинном покрытии с минимальным весом. Глава 35. Приближенные алгоритмы и 79 2" < ю(С') . (35.21) Далее, утверждается, что при округлении дробных значений переменных х(о) получается множество С, которое является вершинным покрытием, удовлетворяющим неравенству ю(С) < 22*. Чтобы убедиться, что С вЂ” вершинное покрытие, рассмотрим произвольное ребро (и, с) е Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
