Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 86
Текст из файла (страница 86)
(З Пример 17.3. Рассмотрим индивидуальную задачу (11, 18, 24, 42, 15, 7; 56). Применяя наш алгоритм, построим следующие множества: Гл. 17. Приближгинмг алгоритмы при условии и ~' гп,х, ( К, х, = О, 1. 1=1 Не теряя общности, будем считать, чтошуе .К, 1=1,..., и, Напомним, что в нашем определении задач оптимизации они определяются через два алгоритма: А, (проверяющий, является ли решение допустимым) и А, (вычисляющий стоимость допусгз)мых решений).
1. М =(О). 2. Для 1=1, 2, ..., и выполнять: Му — Я; для каждого целого ~псла г нз М, добавить к М целые числа о н с+г, если онн не превышают К й еш( не входят в М ", 3. Заключить, что данная индивидуальная задача имеет решение в том н только в том случае, если К~Мгс Рнс. 17.16 Алгоритм ЛП-11 Таким образом, индивидуальная задача оптимизации представляется множеством параметров 3 для Аг — в нашем примере задачи ОПТИМИЗАЦИОННЫИО-1-РЮКЗАК 5=(гпо ш„,..., гп„, К)— и множеством параметром Я для А„в нашем примере (с„..., с„).
В данный момент важно отметить, что в задаче ОПТИМИЗАЦИОННЫЙ О-1-РЮКЗАК множества 5 и Я не пересекаюгпся Другими словами, допустимость и стоимость определяются совершенно различными множествами параметров. . Можно ли решить задачу ОПТИМИЗАЦИОННЫИ 0-1-РЮКЗАК с помощью псевдополиномиальвого алгоритма, аналогичного ДП-П (рис. 17.16)? Идея, естественно, могла бы состоять в построении множества Мл всех целых чисел, представимых в виде суммы ~(,х;со где ~~";,х,гп;(К и хе:=В пли 1, и выборе затем наибольшего целого числа в Мч. Однако есть одна трудность.
В алгоритме ДП-П множество М, не содержало повторяющихся копий целых чисел; если два подмйожества множества (1, 2,..., 1) имели одну и ту же сумму элементов с;, то они не различались. Однако в рассматриваемой задаче двум подмножествам 5 и Я' множества (1, 2. .. 1) может соответствовать одна и та же сумма элементов с;, но различные суммы элементов гао Ключевым замечанием здесь является то, что если ~.,'сг= ~~р с, и ~ч; шг( чр шг гез ге5' ге5 ге5' (другими словами, 5 и 5' — частичные решения с одинаковой стон. мастью, но различными весами), то можно выбросить Я', частичное решение с большим общим весом Интуитивно это вытекает из того что если 5'() Т вЂ” допустимое решение, где Т~(1+1, ., н), те Я () Т также допустимое решение с той же стоимостью ') Это приво ') В дальнейшем мы встретимся с прнмерамп таких отношений доминирогоии среди частичных решений задач в гл.
18 прн рассмотреннн метода ветвей границ, 435 17.3. 77риближенные схемы )дит к алгоритму для задачи ОПТИМИЗАЦИОННЫЙ 0-1-Р)ОКЗАК, ,'приведенному на рис. 17.17. положить мр = ((йу о))' 'й. Для /=1, 2, ..., л выполнят~ шаги а) — в) а) Положить Му=Я. б) Для каждого элемента (5, с) на Му г добавить к Му элемент (5, с), а также элемент (511(1), с+с ), если ~, гсг+шге.
1(. р Е5 в) Найти в Му пары элементов (5, с) и 15, с') с одной и той же второй компонентой. Для каждой такой пары удалить (5', с), если ~ игг~ г Е 5' ы ~Р ~шь и удалить (5, с) в противном случае. гЕ5 3. Оптимальным решением является 5, где (5, с) — элемент иэ М„е наибольшей второй компонентой. Рис. 17.17 Алгоритм ДП-П).
Лемма 17.2. Пусть (5, г),-М, конце гьгполненич члгоритдга ДП -111. Тогда а) 5с=(1, 2, б) ~р сг=с; 'е5 в) Х ш,<К; г Е5 г) если (5', с) ЕМП то 5'=5; д) если 5': — 11, 2, ..., У) и ~л сг=с, то ~ игг <,'У цгг; ге5' ге5 ге5' е) кроме пгого, если 5: — (1, 2, ..., () и ~ игг е-.К, ге 5' ,л,' с,=с, то нийдетсл пара (5', г,) бМо г е5 Доказательство.
Доказательство проведем индукцией по /. Все утверждения тривиально выполняются для 1=0. Для проведения шага индукции рассмотрим некоторое))0 и (5, с)ЕМ . Возможны два случая. Случай Д 1 ( 5. Тогда пара (5, с) была перенесена на шаге 2(б) из М, т, поэтому свойства а), б), в) и г) вытекают из предположения индукции. Случай 2. 1'б5. Тогда (5 — Я, о — о ) бМ „м Свойства а), б), в) и г) снова выполняются. Для доказательства свойства д) предположим, что 5 Ф 5'.
Возможны грн случая. Случай А (гГ5, 5'. Тогда (5, с) и (5', с) входили также в М, и по предположению индукции 5=5'. 436 Гл. 17. Приближенные алгоритмы Случай 2. )Е5, 5'. Тогда (5 — (1), с — с,), (5' — (1), с — су) Е ЕМ „и, следовательно, по предположению индукции 5=5'. Случай 3. ! ~5, но ! ~5' или наоборот. Тогда пара (5', с) была удалена на шаге 2(в), и свойство д) выполняется. Для доказательства свойства е) воспользуемся индукцией по шах 5.
Оно выполняется для 5=- 8; для проведения шага индукции допустим, что й =. гпах 5, Тогда, по предположению индукции, в М„, имеется элемент (5', с — сь). Поэтому на шаге 2(б) при построенииМ, к Мь был добавлен элемент(5'сл(Ф), с). Тогда либо сама эта пара входит в М„либо в Мт имеется некоторый элемент (5", с). В обоих случаях свойство е) выполняется. () Теорема 17.7. Алгоритм ДП-П1 решает задачу ОНТИМИЗАЦИОННЫИ' О-1-РЮКЗАК за время 0(и'с), где с — значение оптимальной стоимости. Доказательство. Корректность алгоритма следует непосредственно из леммы: поскольку в алгоритме ДП-П! на шаге 3 в качестве оптимума выбирается первая компонента 5 элемента из М„ с наибольшей второй компонентой с, то это 5 допустимо (по свойству в)), его стоимость равна с (по свойству б)) и нет более хороших допустимых решений (по свойству е)).
Для получения временнбй оценки заметим, что мощность каждого множества М, не превосходит с, так как в М,, нет двух элементов с одинаковой второй компонентой (по свойству г)). Каждую операцию перестройки на шаге 2(б) можно выполнить за время 0(п), и нужно повторить ее для всех 0(с) элементов из М,, Шаг 2(в) также требует 0(пс) времени, так как его можно реализовать одновременно с шагом 2(б): для этого все элементы множества М, хранятся в массиве длины с, занумерованные по второй компоненте, и каждый раз, когда производится попытка вставить на то же место второй элемент, вычисляются и сравниваются суммы весов ии и удаляется элемент, имеющий ббльшую сумму. Теорема доказана. П Пример 17.4.
Рассмотрим следующую индивидуальную задачу ОПТИМИЗАЦИОННЫЙ 0-1-РЮКЗАК: При выполнении алгоритма ДП-1П порождаются следующие множества: 437 !7,3, Приближенные схимы Ме = [(~,0)) М1 = (( 8, О), ([!), 6)) Ме =- [(О, О), ((1), 6), ([2), ! !), ([1, 2), 1 7)] М) = И В , О), (( !), 6), ([2), 1 1), ([1, 2), 1 7), ([ 1, 3), 23), ([2, 3), 28), ([1, 2, 3), 34)) Ме =- [(И, О), ((4), 3), ([1), 6), ([1, 4), 9), ([2), ! 1), ((2, 4), 14), (((, 2), !7), ([1, 2, 4), 20),((1, 3), 23),([2, 3), 28), ([1, 2, 3), 34)) М, = [(3', О), ([4), 3), ((! ), 6), ([5), 9), ([2), 1 1 ), ([4, 5), 12), ([2, 4), 14), ([1, 5), 1 5), ([1, 2), 17), ((1, 4, 5), 1 8), ([2, 5), 20), ((1, 3)> 23), ([1, 2, 5), 26), ((2, 3), 28),([1, 2, 3), 34)) Поэтому оптимальным подмножеством является подмножество (1, 2, 3), для которого ~ч'.", зсу=-34.
Е) До сих пор мы имели дело с нахождением точного оптимума в задаче ОПТИМИЗАЦИОННЫЙ 0-1-Р!ОКЗАК, Однако оказывается, что можно отказаться от точности в обмен на эффективность. Для иллюстрации этого предположим, что мы хотим решить следующую индивидуальную задачу: Х=!О Если к этой задаче применить алгоритм ДП-П 1, то в результате получим, что оптимальным решением является подмножество 5=-(1, 2, 3, 6, 7), для которого,'>~„зс =-777; однако при этом алгоритм пройдет через утомительное построение 91 пары (5, с), Очень естественная идея упрощения задачи состоит в игнорировании последнего десятичного разряда ларахиетрое с;; в результате приходим к следующей индивидуальной задаче: Х 10 Хотя эта индивидуальная задача дает проигрыш в точности, она дает выигрыш в эффективности.
Алгоритм ДП-П! для нее приводит к оптимальному решению 5'=(1, 3, 4, 6) с суммой ~„зс =-740 (отличие от оптимального решения около 6",е) после построения только 36 пар. В задачах большего размера при более сильных округлениях выигрыш может быть более разительным. Кроме того, эта сумма 740 соответствует еще лучшей сумме в исходной задаче— 4ЗВ Гл. 17. Приближенные илесритмы а именно ~(ез с, =-768. На самом деле мы могли заранее догадаться, что округление не даст слишком большой ошибки. Для доказательства этого предположим, что 5 и 5' — оптимальные решения соответственно исходного и округленного вариантов. Тогда имеют место следующие неравенства: ~(с1>,», с(> ~, с > ~~с1),У((с( — 10) > ~~ су — и 10.
(ез (из' (ея' (ез (ез (из ПозтомУ ошибка й,'(езс( — ~(из с,, не пРевосходит и 10 (в нашем случае 70). В общем случае еслй при округлении отбросить послелние 1 ДесЯтичных РазРЯДов в числах бр то отклонение от оптимального решения не будет превышать и !О'. Вычислим теперь выигрыш в сложности выполнения алгоритма ДП-П!, получаемый при использовании округления Пусть с наибольший коэффициент среди еу Время, необходимое для работы алгоритма ДП-1П в исходной задаче, не превосходи( 0(п'с ); после отбрасывания ! разрядов оценка принимает вид 0(пес „10 '), так как с, фактически разделились на 10'.
Интересно-отметить, что при любом 1 алгоритм ДП-! П, применяемый к индивидуальным задачам, а которых последние 1 разрядов в числах с отброшены, является е-приближенным алгоритмом, где а=а!0(lс . Это вытекает из того, что Эс( — ~зс, (ез (ез' н(О' 1'е ' Следовательно, для каждого данного значения е можно построить е-приближенный алгоритм для задачи ОПТИМИЗАЦИОННЫЙ 0-1-РЮКЗАК с временем работы О (а'(е), Этот алгоритм включает в себя отбрасывание последних 1= (!03„( — ")~ разрядов и применение затем алгоритма ДП-!11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
