Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 264
Текст из файла (страница 264)
Согласно ограничению (35.18) должно выполняться неравенство х(и) + х(о) > 1, из которого следует, что хотя бы одна из величин х(п) и х(о) не меньше 1/2. Поэтому хотя бы одна нз вершин и н о будет включена в вершинное покрытие, а следовательно, будут покрыты все ребра. Теперь рассмотрим, чему равен вес этого покрытия.
Имеем следукнцую цепочку соотношений: ()х() оЕК ю(о)х(о) оЕ К: В(о) >1/2 1 ()— 2 иЕ К:а(о) > 1/2 1 ю(о) 2 оЕС 1 -',7. (с) 2 оЕС 1 -ю(С) . 2 (35.22) Объединение неравенств (35.21) и (35.22) дает ю(С) < 22* < 2ю(С*), а следовательно, Арркох-Мцч-%е1аит-ЧС является 2-приближенным алгорит- мом. Докаэагиельеюиво. Поскольку существует алгоритм с полиномиальным временем решения, позволяющий решить задачу линейного программирования в строке 2, и поскольку цикл Гог в строках 3 — 5 выполняется за полиномиачьное время, алгоритм Арркох-М))ч-%е)снт-ЧС имеет полиномиальное время работы.
Теперь покажем, что он является 2-приближенным алгоритмом. Пусть С'— оптимальное решение задачи о вершинном покрытии с минимальным весом, а 2' — значение оптимального решения задачи линейного программирования, определенной в (35.17К35.20). Поскольку оптимальное вершинное покрытие является допустимым решением этой задачи, величина лв должна быть нижней границей величины ю(С*), т.е. выполняется неравенство Ибб Часть Рпа Избранные темы Упражнении 35.4.1 Покажите, что даже если бы подвыражение в скобках могло содержать одновременно переменную и ее отрицание, то в результате независимого присвоения каждой переменной значения 1 с вероятностью 1/2 и значения О с той же вероятностью все равно получился бы рандомизированный 8/7-приближенный алгоритм.
35.4.2 Задача о МАХ-С1ЧР-выиолиимосизи (МАХ-С14Р заг(з(1аЫ11зу ргоЫеш) похожа на задачу о МАХ-3-С)ь(Р-выполнимости с тем исключением, что в каждом подвыражении в скобках необязательно содержится по три литерала. Разработайте рандомизированный 2-приближенный алгоритм, позволяющий решить задачу о МАХС1ь(р-выполнимости. 35.4.3 В задаче МАХ-СПТ задан невзвешенный неориентированный граф С = (К Е). Определим разрез (Я, Ъ' — Я), как это было сделано в главе 23, а вес (нее)йпс) этого разреза, как количество пересекающих его ребер. Требуется найти разрез с максимальным весом.
Предположим, что каждая вершина о случайно и независимо с вероятностью 1/2 помещается в множество Я или )з — Я. Покажите, что этот алгоритм является рандомизированным 2-приближенным алгоритмом. 35.4.4 Покажите, что ограничение (35.19) избыточно в том смысле, что если опустить его из задачи линейного программирования, определенной в (35.17)-(35.20), то любое оптимальное решение полученной в результате задачи линейного программирования для каждой вершины о Е (з должно удовлетворять неравенству х(зз) < 1. 35.5. Задача о сумме подмножества Вспомним из раздела 34.5.5, что экземпляр задачи о сумме подмножества имеет вид пары (о',1), где Я вЂ” множество (хъ сз,...,х„) положительных целых чисел, а 1 — положительное целое число. В этой задаче принятия решений спрашивается, существует ли подмножество множества Я, сумма элементов которого равна целевому значению 1.
Эта задача является )ь(Р-полной (см. раздел 34.5.5). Задача оптимизации, связанная с этой задачей принятия решений, возникает в различных практических приложениях. В такой задаче оптимизации требуется найти подмножество множества (хы хз,..., х„), сумма элементов которого принимает максимально возможное значение, не большее 1. Например, пусть имеется грузовик, грузоподъемность которого не превышает 1 кг, и и различных ящиков, которые нужно перевезти. Вес з-го ящика равен хз кг.
Требуется загрузить грузо- пВ! Глава 35. Прйилиженные алгоритмы вик максимально возможным весом, но так, чтобы не превысить его грузоподьем ность. В этом разделе приведен алгоритм, позволяющий решить задачу оптимизации за экспоненциальное время. Затем показано, как модифицировать приведенный алгоритм, чтобы он превратился в схему аппроксимации с полностью полиномиальным временем решения. (Напомним, что время работы схемы аппроксимации с полностью полииомиальиым временем выполнения выражается полиномиальной функцией от величины 1/е и от размера входных данных.) 'Точный алгоритм с экспоненциальным временем работы Предположим, что для каждого подмножества У множества Я вычисляется сумма его элементов, после чего из всех подмножеств, сумма элементов которых не превышает г, выбирается подмножество, для которого эта сумма меньше других отличается от Ь Очевидно, что таюй алгоритм возвратит оптимальное решение, но время его работы выражается показательной функцией. Для реализации этого алгоритма можно было бы воспользоваться итеративной процедурой, в которой в 1-й итерации вычислялись бы суммы элементов всех подмножеств множества (хм хз,..., х,) на основе вычисленных ранее сумм всех подмножеств множества (хм хз,..., к, 1).
Если пойти этим путем, то легко понять, что нег смысла продолжать обработку некоторого подмножества У после того, как сумма его элементов превысит Ь посюльку никакое надмножество Я' не может быть оптимальным решением. Реализуем эту стратегию. В качестве входных данных процедуры ЕхАст-Бивзет-815м, с псевдокодом которой мы скоро ознакомимся, выступают множество Я = (хы хз,..., х„) и целевое значение Ь В этой процедуре итеративно вычисляется список Ьы содержащий суммы всех подмножеств множества (ям..., хз), которые не превышают Ь Затем возвращается максимальное значение из списка Ь„. Если Ь вЂ” список положительных целых чисел, а х — еще одно положительное целое число, тогда через Ь + х будет обозначаться список целых чисел, полученный из списка Ь путем увеличения каждого его элемента на величину х. Например, если Ь = (1,2,3,5,9), то Ь+ 2 = (3,4,5,7,11). Воспользуемся этим обозначением и для множеств, так что Я+х = (В+ к: В Е Я) Кроме того, нам понадобится вспомогательная процедура МекпеЬ|зтз(Ы,'), которая возвращает отсортированный список, представляющий собой объединение входных отсортированных списков Ь и Ь' с исключением повторяющихся значений.
Время выполнения процедуры Мексе-Ь1зтз, как и время выполнения процедуры Мексе, используемой для сортировки слиянием и описанной в разделе 2.3.1, равно 0(Щ + ~Ц). (Псевдокод процедуры Меньше-1лзтз опущен.) ИВ2 Чаете ГИ. Избраииые темы Ехлст-ББВБет-бпм(Я, т) 1 п=(Я) 2 Ьо еа (0) 3 Гога' = 1 топ 4 Ь; = Мвкпв-Ещтз(Ь; 1,Ь; 1+х,) 5 Удалить из Ь, все элементы, превышающие г 6 гетпгп наибольший элемент в Ь„ Рассмотрим, как работает процедура Ехлст-Яввзвт-50м.
Обозначим через Р; множество всех значений, которые можно получить, выбрав (возможно, пустое) подмножество множества (хп хз,..., хе) и просуммировав его элементы. Например, если Я = (1, 4, 5), то Р =(О,Ц, Рз = (0,1,4,5), Рз = (О 1 4 5 6 9 10) Воспользовавшись тождеством (35.23) методом математической индукции по 1 можно доказать (см. упр. 35.5.1), что Тч— отсортированный список, содержащий все элементы множества Рь значения которых не превышают г. Поскольку длина списка Тч может достигать значения 2', в общем случае время выполнения алгоритма Ехлст-Бпвзвт-Бим ведет себя как показательная функция, хотя в некоторых частных случаях, когда величина г представляет собой полипом от ф~ или все содержащиеся в множестве Я числа ограничены сверху полиномиальными величинами от ~Я~, это время также полиномиально зависит от ~Я).
Схема аппроксимации с полностью полнномнальным временем работы Схему аппроксимации с полностью полиномиальным временем работы, позволяющую получить приближенное решение задачи о сумме подмножеств, можно составить путем "сокращения" каждого списка Ь, после его создания. Идея заключается в том, что если два значения в списке Ь мало отличаются одно от другого, то для получения приближенного решения нет смысла явно поддерживать оба эти значения. Точнее говоря, используется некоторый параметр сокращения б, удовлетворяющий неравенству 0 < б < 1. Чтобы сокрагиивеь (пзш) список Ь по параметру б, нужно удалить из этого списка максимальное количество элементов таким образом, чтобы в полученном в результате этого сокращения списке Ь' для каждого удаленного из списка Ь элемента у содержался элемент з, аппроксимирующий элемент у, т.е.
(35.24) <а<у 1+б Глава 55. Приавилненные авгааынлвы Можно считать, что элемент з "представляет*' элемент у в новом списке К т.е. каждыи удаленный элемент у представлен элементом з, удовлетворяющим неравенству (35.24). Например, если б = 0.1 и Е = (10,11,12,16,20,21,22,23,24,29) то путем сокращения списка Ь можно получить список Ь' = (10,12,16,20,23,29), где удаленное значение 11 представлено значением 10, удаленные значения 21 и 22 представлены значением 20, а удаленное значение 24 представлено значением 23. Поскольку каждый элемент измененной версии списка является одновременно элементом исходного списка, сокращение может значительно уменьшить количество элементов, сохраняя в списке близкие (несколько меньшие) представительные значения каждого удаленного элемента.
Приведенная ниже процедура по заданным параметрам Ь и б сокращает список Ь = (ум уз,..., у ) за время тЭ(т); при этом предполагается, что элементы списка Е отсортированы в неубывающем порядке. На выходе процедуры получается сокращенный отсортированный список. ТК!М(в., б) 1 Пусть т — длина списка Е 2 ~ =(у1) 3 1аав = у1 4 вогв =2тот 5 Ы у; ) 1аз1 . (1+ б) // у; > 1ааг (список Ь отсортирован) 6 Добавить у; в конец списка Ь' 7 1688 = ув 8 гевпгп Ь' Элементы списка Ь сканируются в неубывающем порядке, и в возвращаемый список Ь' элемент помещается, только если это первый элемент списка Ь или если его нельзя представить последним помещенным в список Ь' элементом. Располагая процедурой Тк1м, схему аппроксимации можно построить следующим образом. В качестве входных данных в эту процедуру передается множество Я = (хм хз,..., х„), состоящее из и целых чисел (расположенных в произвольном порядке), целевое значение 1 и "параметр аппроксимации" е, где (35.25) 0 < е < 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
