Алгоритмы - построение и анализ (1021735), страница 244
Текст из файла (страница 244)
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, поскольку никакое надмножество У не может быть оптимальным решением. Реализуем эту стратегию. Глава 35. Приближенные алгоритмы 1177 В качестве входных данных процедуры ЕхАст Бивзвт Бим, с псевдокодом которой мы скоро ознакомимся, выступает множество Я = (хы хз,..., х„) и целевое значение г. В этой процедуре итеративно вычисляется список Ц, содержащий суммы всех подмножеств множества (хы хз,..., х;), которые не превышают Ф. Затем возвращается максимальное значение из списка Ь„. Если Х, — список положительных целых чисел, а х — еще одно положительное целое число, тогда через Ь + х будет обозначаться список целых чисел, полученный из списка Ь путем увеличения каждого его элемента на величину х.
Например, если Ь = (1,2, 3, 5,9), то Ь+ 2 = (3, 4, 5, 7, 11). Воспользуемся этим обозначением и для множеств: Я+х = (а+х: з Е Я). Кроме того, нам понадобится вспомогательная процедура Мвкав 1!зтз(Ы,'), которая возвращает отсортированный список, представляющий собой объединение входных списков Ь и Ь' с исключением повторяющихся значений. Время выполнения процедуры Мвипв 1штз, как и время выполнения процедуры Мвксв, используемой для сортировки слиянием и описанной в разделе 2.3.1, ведет себя как О (!Ц + (Ц). (Псевдокод процедуры Мвисв 1!зтз опускается.) Ехлст Бивзвт Бом(Я, 1) 1 и — Д 2 Ьо ~ — (0) 3 тог г' — 1 то и 4 йо Ь; — Мекбв 1лзтз(Ь; ы 2; 1 + х;) 5 Из списка Ь; удаляются все элементы, большие 8 6 гегнгн Максимальный элемент из списка Ь„ Рассмотрим, как работает процедура Ехлст Бивзвт Б0м. Обозначим через Р; множество всех значений, которые можно получить, выбрав (возможно, пустое) подмножество множества (хы хз,..., х;) и просуммировав его элементы.
Например, если Я = (1, 4, 5), то Р = (0,1), Рз = (0,1,4,5), Рз = (0,1,4,5,6,9,10). Воспользовавшись тождеством Р, = Р, О (Р; + х;), (35.21) методом математической индукции по 1 можно доказать (см. упражнение 35.5-!), что Ц вЂ” отсортированный список, содержащий все элементы множества Ро значение которых не превышает 1. Поскольку длина списка Ь; может достигать 1178 Часть ЧП. Избранные темы значения 2', в общем случае время выполнения алгоритма Ехлст БОвзпт Зим ведет себя как показательная функция, хотя в некоторых случаях, когда величина 1 представляет собой полипом от Д или все содержащиеся в множестве Я числа ограничены сверху полиномиальными величинами от Д, это время также полиномиально зависит от )Я).
Схема аппроксимации с полностью полиномиальным временем работы Схему аппроксимации с полностью полиномиальным временем работы, позволяющую получить приближенное решение задачи о сумме подмножеств, можно составить путем "сокращения" каждого списка Ь; после его создания. Идея заключается в том, что если два значения в списке Х, мало отличаются друг от друга, то для получения приближенного решения нет смысла явно обрабатывать оба эти значения. Точнее говоря, используется некоторый параметр сокращения б, удовлетворяющий неравенству 0 < Б < 1. Чтобы сокравиивь (п1ш) список Ь по параметру б, нужно удалить из этого списка максимальное количество элементов таким образом, чтобы в полученном в результате этого сокращения списке Т,' для каждого удаленного из списка Т, элемента у содержался элемент з, аппроксимирующий элемент у, так что — < з < у.
1+5 Можно считать, что элемент з "представляет" элемент у в списке К т.е. каждый элемент у представлен элементом а, удовлетворяющим уравнению (35.22). Например, если б = 0.1 и Ь = (10,11,12,15,20,21,22,23,24,29), то путем сокращения списка Ь можно получить список Ь' = (10,12,15,20,23,29), где удаленное значение 11 представлено значением 10, удаленные значения 21 и 22 представлены значением 20, а удаленное значение 24 представлено значением 23. Поскольку каждый элемент измененной версии списка является одновременно элементом исходного списка, сокращение может значительно уменьшить количество элементов, сохраняя в списке близкие (несколько меньшие) представляюшие значения каждого удаленного элемента.
Приведенная ниже процедура по заданным параметрам Ь и б сокращает список Ь = (ры рз,..., уы) в течение времени 6 (т); при этом предполагается, что элементы списка Ь отсортированы в монотонно возрастающем порядке. На выходе процедуры получается сокращенный отсортированный список. Глава 35. Приближенные алгоритмы 1179 ТК1м(Ь, б) 1 т -Щ 2 Ь' ~ — (у1) 3 1азг - у1 4 1ог1 — 21о т 5 Йо!1 у; ) 1аз1 (1+ б) 1> у; > 1аз1 в силу с отсортированности списка Ь 6 гнев элемент у; добавляется в конец списка Г 7 1аз1 — у; 8 гегнгп Ь' Элементы списка Ь сканируются в монотонно возрастающем порядке, и в список Ь', который возвращается, элемент помещается, только если это первый элемент списка Ь или если его нельзя представить последним помещенным в список Л' элементом. Располагая процедурой Тк1 м, схему аппроксимации можно построить следующим образом.
В качестве входных данных в эту процедуру передается множество Я = (х1, хз,..., х„), состоящее из и целых чисел (расположенных в произвольном порядке), целевое значение 8 и "параметр аппроксимации" з, где (35.23) 0 < з < 1. Процедура возвращает значение з, величина которого отличается от оптимального решения не более чем в 1 + з раз. АРРкОх БУВзет Ббм(Я, 1, з) 1 и ~- 1'8! 2 Ьо +- (О) 3 1ог г' +- 1 то п 4 йе Ь; +- Мекпе Ь|зтз(Ь; 1, Ь1 1+ кч) 5 Ь1 +- Тк1М(Ь,, з/2п) б Из списка Хз удаляются все элементы, большие 8 7 Пусть з" — максимальное значение в списке Ь„ 8 гегигп з' В строке 2 список Ьо инициализируется таким образом, чтобы в нем содержался только элемент О. Цикл Тег в строках 3-6 вычисляет отсортированный список Ь;, содержащий соответствующим образом сокращенную версию множества Р;, из которого удалены все элементы, превышающие величину $.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
