Схема аппроксимации полиномиального времени

Хорошо известно, что не существует известного решения за полиномиальное время для задач NP Complete, и эти проблемы часто возникают в реальном мире (см. Это, это и это, например). Так что должен быть способ справиться с ними. Мы видели приблизительные алгоритмы решения этих задач (например, 2 приблизительных алгоритма для коммивояжера). Можем ли мы сделать лучше?

Р olynomial Т IME pproximation S cheme (СПТ) представляет собой тип приближенных алгоритмов , которые обеспечивают пользователю контроль над точность , которая является желательным признаком. Эти алгоритмы принимают дополнительный параметр ε> 0 и предоставляют решение, которое является (1 + ε) приближенным для минимизации и (1 - ε) для максимизации. Например, рассмотрим задачу минимизации: если ε равно 0,5, то решение, предоставляемое алгоритмом PTAS, приближенно составляет 1,5. Время работы PTAS должно быть полиномиальным по n, однако оно может быть экспоненциальным по ε.

В алгоритмах PTAS показатель полинома может резко увеличиваться при уменьшении ε, например, если время выполнения равно O (n ^{(1 / ε)!} ), Что является проблемой. Существует схема строже, F ully Р olynomial Т IME pproximation S cheme (FPTAS). В FPTAS алгоритм должен быть полиномом как от размера задачи n, так и от 1 / ε.

Пример (задача о рюкзаке 0-1):
Мы знаем, что рюкзак 0-1 - это NP Complete. Для этого существует псевдополиномиальное решение на основе DP. Но если входные значения высоки, решение становится недопустимым, и возникает необходимость в приближенном решении. Одним из приблизительных решений является использование жадного подхода (вычислить значение на кг для всех элементов и сначала указать максимальное значение на кг, если оно меньше W), но жадный подход не является PTAS, поэтому мы не можем контролировать точность.

Ниже приведено решение FPTAS для задачи о рюкзаке 0-1:
Вход:
Вт (Вместимость ранца)
val [0..n-1] (значения элементов)
wt [0..n-1] (Вес предметов)

1. Найдите элемент с максимальным значением, т. Е. Найдите максимальное значение в val []. Пусть это максимальное значение будет maxVal.
2. Вычислить поправочный коэффициент k для всех значений

         k = (maxVal * ε) / n

3. Отрегулируйте все значения, т.е. создайте новый массив val '[], в котором значения делятся на k. Выполните следующие действия для каждого значения val [i].

         val '[i] = этаж (val [i] / k)

4. Запустите решение на основе DP для уменьшенных значений, i, e, val '[0..n-1] и всех остальных параметров, таких же.

Вышеупомянутое решение работает за полиномиальное время как по n, так и по ε. Решение, предоставляемое этой FPTAS, является (1 - ε) приближенным. Идея состоит в том, чтобы округлить некоторые из наименее значащих цифр значений, тогда они будут ограничены полиномом и 1 / ε.

Пример:

val [] = {12, 16, 4, 8}
wt [] = {3, 4, 5, 2}
W = 10
ε = 0,5
 
maxVal = 16 [максимальное значение в val []]
Коэффициент корректировки, k = (16 * 0,5) / 4 = 2,0

Теперь мы применяем решение на основе DP на модифицированном ниже 
экземпляр проблемы.

val '[] = {6, 8, 2, 4} [val' [i] = floor (val [i] / k)]
wt [] = {3, 4, 5, 2}
W = 10

Каково решение (1 - ε) * OPT?
Здесь OPT - оптимальное значение. Пусть S будет набором, созданным вышеупомянутым алгоритмом FPTAS, а общее значение S будет val (S). Нам нужно показать, что

       val (S)> = (1 - ε) * OPT

Пусть O будет множеством, созданным оптимальным решением (решение с полным значением OPT), т. Е. Val (O) = OPT.

       val (O) - k * val '(O) <= n * k 
       [Потому что val '[i] = floor (val [i] / k)]

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

      val '(S)> = k. val '(O)
              > = val (O) - nk
              > = OPT - ε * maxVal
              > = OPT - ε * OPT [OPT> = maxVal]
              > = (1 - ε) * ОПТ

Источники:
http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf
https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme

Эта статья предоставлена Дираджем Гуптой. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.