Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 245
Текст из файла (страница 245)
Глава 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 вычисляет отсортированный список Ь;, содержащий соответствующим образом сокращенную версию множества Р;, из которого удалены все элементы, превышающие величину $. Поскольку список Ьз создается на основе списка Ь; ы мы должны гарантировать, что повторное сокращение не вносит слишком большой неточности. Скоро станет понятно, что процедура АРРкОх БОВзет Бим возвращает корректную аппроксимацию, если она существует. Часть Чй.
Избранные темы 1180 В качестве примера рассмотрим экземпляр задачи, где Я = (104, 102, 201, 101), Ф = 308 и е = 0.40. Параметр 6 равен е/8 = 0.05. В процедуре Аггиох Бывает Бим вычисляются приведенные ниже значения (слева от которых указаны номера соответствующих строк): ~о = (О) Строка 2: Ь1 — — (О, 104), Ь| = (О, 104), Ь1 = (0,104), Строка 4: Строка 5: Строка 6: Ьг = (0,102,104,206), Ьг = (О, 102,206), Ьг = (О, 102, 206), Строка 4: Строка 5: Строка 6: Ьз = (О 102,201,206,303,407), Ьз = (0,102 201 303 407) Ьз = (0,102,201,303), Строка 4: Строка 5: Строка 6: Ь4 = (0,101,102,201,203,302,303,404), Ь4 = (0,101,201,302,404) > Ь4 = (О, 101) 201, 302) .
Строка 4: Строка 5: Строка 6: Алгоритм возвращает значение з' = 302, которое приближает оптимальное ре- шение 307 = 104+ 102+ 101 в пределах погрешности е = 40%; фактически погрешность составляет 2М. Теорема 35.8. Процедура Арркох Бивзвт Бом является схемой аппроксимации с полностью полиномиальным временем выполнения, позволяющей решить зада- чу о сумме подмножеств.
Доказательство. В результате сокращения списка Ь; в строке 5 и удаления из этого списка всех элементов, превышающих значение 1, поддерживается свойство, что каждый элемент списка Ь; также является элементом списка Р,. Поэтому значение г', которое возвращается в строке 8, на самом деле является суммой некоторого подмножества множества Я. Обозначим оптимальное решение задачи о сумме подмножества у' е Р„.
Далее, из строки 6 известно, что г' < у'. Согласно неравенству (35Л ), нужно показать, что у'/з' < 1+с. Необходимо также показать, что время работы этого алгоритма выражается полиномиальной функцией и от 1/е, и от размера входных данных. Глава 35. Приближенные алгоритмы 1181 Воспользовавшись индукцией по 1, можно показать, что для каждого не превышающего 1 элемента у из списка Р, существует элемент я Е Ц, такой что у .
(з(у (1+ е/2п)' (35.24) (см. упражнение 35.5-2). Неравенство (35.24) должно выполняться для у' е Р„, поэтому существует элемент я Е Ь„, удовлетворяющий неравенству (1 + е/2п) и, следовательно, ( 2п) (35.25) Поскольку существует элемент х Е Ь„, удовлетворяющий неравенству (35.25), это неравенство должно быть справедливым для элемента з', который имеет самое большое значение в списке Ь„, т.е. (35.26) Осталось показать, что у'/г' < 1+ е. Для этого покажем, что (1+ е/2п)" < < 1+ е. Согласно (3.13), 1пп„(1+ е/2п)" = е'7з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
