Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 244
Текст из файла (страница 244)
Вес любого вершинного покрытия У'СУ определяется как и (У') = 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 = -ю (С) . 2 Объединение неравенств (35.19) и (35.20) дает нам соотношение (35.20) ю (С) < 2з' < 2ю (С'), Упражнения 35.4-!. Покажите, что даже если бы выражение в скобках могло содержать одновременно переменную и ее отрицание, то в результате независимого присвоения каждой переменной значения 1 с вероятностью 1/2 и значения 0 с вероятностью 1/2 все равно получился бы ранцомизированный 8/7-приближенный алгоритм.
35.4-2. Задача о МАХ-СЖР выполнимости (МАХ-СИР забзйаЫ1(гу ргоЫеш) похожа на задачу о МАХ-3-С)ЧР выполнимости с тем исключением, что в каждом выражении в скобках не обязательно содержится по 3 литерала. Разработайте рандомизированный 2-приближенный алгоритм, позволяющий решить задачу о МАХ-Сг(Р выполнимости. 35.4-3. В задаче МАХ С()Т задается невзвешенный неориентированный граф С = (У, Е). Определим разрез (Я, У вЂ” Я), как это было сделано в главе 23, и вес (юе18)з() этого разреза, как количество пересекающих его ребер. Требуется найти разрез с максимальным весом.
Предположим, что каждая вершина с случайно и независимо с вероятностью 1/2 помещается в множество Я или У вЂ” Я. Покажите, что этот алгоритм является рандомизированным 2-приближенным алгоритмом. так что алгоритм Арркох М)н 'тЧнснт ЧС является 2-приближенным алгоритмом. З Часть Ч)!. Избранные темы 1176 35.4-4. Покажите, что ограничение (35.!7) избыточно в том смысле, что если опустить его из задачи линейного программирования, определенной соотношениями (35.!5)-(35.!8), то любое оптимальное решение получившейся в результате задачи для каждой вершины о Е У должно удовлетворять неравенству х (и) < 1. 35.5 Задача о сумме подмножества Экземпляр задачи о сумме подмножества имеет вид пары (Я, т), где Я вЂ” множество (хы хз,..., х„) положительных целых чисел, а 1 — положительное целое число. В этой задаче принятия решений спрашивается, существует ли подмножество множества Я, сумма элементов которого равна целевому значению 1. Эта задача является ХР-полной (см.
раздел 34.5.5). Задача оптимизации, связанная с этой задачей принятия решений, возникает в различных практических приложениях. В такой задаче требуется найти подмножество множества (зы хз,..., х„), сумма элементов которого принимает максимально возможное значение, не большее 1.
Например, пусть имеется грузовик, грузоподъемность которого не превышает 1 кг, и п различных ящиков, которые нужно перевезти. Вес 1-го ящика равен х! кг. Требуется загрузить грузовик максимально возможным весом, но так, чтобы не превысить его грузоподъемности. В этом разделе приведен алгоритм, позволяющий решить задачу оптимизации в течение экспоненциального времени. Затем показано, как модифицировать приведенный алгоритм, чтобы он превратился в схему аппроксимации с полностью полиномиальным временем решения.
(Напомним, что время работы схемы аппроксимации с полностью полиномиальным временем выполнения выражается полиномиальной функцией от величины 1/е и от размера входных данных.) Точный алгоритм с экспоненциальным временем работы Предположим, что для каждого подмножества У множества Я вычисляется сумма его элементов, после чего из всех подмножеств, сумма элементов которых не превышает г, выбирается подмножество, для которого эта сумма меньше других отличается от 1. Очевидно, что такой алгоритм возвратит оптимальное решение, но время его работы выражается показательной функцией. Для реализации этого алгоритма можно было бы воспользоваться итеративной процедурой, в которой в 1-й итерации вычислялись бы суммы элементов всех подмножеств множества (хы хз,..., яч) на основе вычисленных ранее сумм всех подмножеств множества (хы хз,..., яй 1).
Если пойти этим путем, то легко понять, что нет смысла продолжать обработку некоторого подмножества У после того, как сумма его элементов превысит 1, поскольку никакое надмножество У не может быть оптимальным решением. Реализуем эту стратегию.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
