%
Алгоритм Рюкзака

Меню сайта

Статистика
Рейтинг@Mail.ru Яндекс.Метрика

Задача о рюкзаке: PTAS

Алгоритмы динамического программирования для задачи о рюкзаке дают точное решение за время O(nf*) или O(nB). Если величины f* и B не ограничена сверху никаким полиномом (то есть имеются большие коэффициенты), то эти псевдополиномиальные алгоритмы не является полиномиальными.

Однако, существует общий метод (который условно можно назвать «масштабированием»), позволяющий перейти к задаче с небольшими коэффициентами в целевой функции, оптимум которой не сильно отличается от оптимума исходной задачи.

Если мы отмасштабируем коэффициенты c1,…,cn, поделив нацело их на некоторый параметр scale, решим «отмасштабированную» задачу, и затем снова умножим коэффициенты на параметр scale, то очевидно, что мы получим допустимое решение исходной задачи и абсолютная погрешность стоимости «округленного и восстановленного» набора не превосходит величины n⋅scale.

Если потребовать, чтобы эта величина не превосходила ε1+εf∗, то получим, что каждое допустимое решение исходной задачи отличается от решения «отмасштабированной» задачи не более, чем на эту же величину.

Обозначая оптимум «отмасштабированной» задачи через f˜, получаем, что f˜≥f∗−ε1+εf∗=f∗(1+ε), то есть оптимум «отмасштабированной» задачи отличается от оптимума исходной задачи не более, чем в 1+ε раз.

При этом величина значение оптимального решения для «отмасштабированной» задачи уменьшается не менее, чем в scale раз по сравнению с исходной. И таким образом, для отмасштабированной задачи, версия алгоритма, ориентированная на отбор «самых легких решений» будет работать существенно меньшее время.

Однако проблема состоит в том, что в момент масштабирования мы не знаем величины оптимума f*, и не можем выбрать коэффициент scale, который, чтобы решение было 1+ε-оптимальным, не должен превышать εf∗n(1+ε), с одной стороны, с другой — желательно максимально приблизить его к этой оценке, чтобы уменьшить коэффициенты в задаче.

Поэтому, важное наблюдение состоит в том, что вместо f* можно рассматривать нижнюю оценку f*, обозначим ее flb, и выбирать параметр масштабирования scale=εflbn(1+ε) тогда все вышеизложенные соображения о точности «отмасштабированного» решения сохранят силу.

Таким образом, стоит задача выбора нижней оценки flb, которую можно найти быстро с одной стороны, и желательно чтобы она была как можно ближе к f*, так как это даст возможность увеличить коэффициент scale, и тем самым, сильнее уменьшить коэффициенты c1,…,cn и время выполнения алгоритма. Таким образом, общая схема алгоритма, представлена как процедура «knapsack_ptas_generic», которой на вход, кроме обычных параметров рюкзака, передают функцию «f_lower_bound», используемую для получения нижней оценки стоимости решения.

Осталось найти такую функцию. Например, можно рассмотреть тривиальную аппроксимацию ncmax≥f∗≥flb≡cmax,, где cmax=maxici; и получим функцию «knapsack_ptas_trivial».

Какова сложность этого алгоритма? Она, есть величина O(nf˜). Учитывая, что f∗≤ncmax, а f˜≤ncmaxscale, получаем оценку сложности алгоритма «knapsack_ptas_trivial»: O(nf˜)=On2cmaxscale=On3(1+ε)ε=On3ε.

Можно ли улучшить эту оценку? Ответ на этот вопрос положителен.

Для этого рассмотрим менее наивную аппроксимацию величины f*, используя задача о рюкзаке: жадный алгоритм, дающий точность не хуже чем в два раза.

Используя эту оценку, получаем функцию «knapsack_ptas_nontrivial» Аналогично получаем оценку сложности для этого алгоритма: O(nf˜)=OnfGscale=On2(1+ε)ε=On2ε.


Назад Домой Вперед
Друзья сайта
  • Группа AR в ВК.
  • Группа AR в FB.
  • Группа AR в OK.
  • Алгебра Логики.
  • Альтернатива Групп.

  • Алгоритм Рюкзака © 2017 created AD.