Просмотр кода страницы Приближённая схема полиномиального времени

В [[Математика|математике]], '''приближенная схема полиномиального времени'''  или '''polynomial-time approximation scheme''' ('''PTAS''') обозначает класс приближенных полиномиальных по времени выполнения [[алгоритм]]ов для решения, как правило, [[NP-трудность|NP-трудных]] оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности  определим понятие для задачи минимизации.

== Определение ==
PTAS это семейство алгоритмов, зависящих от параметра ε&nbsp;, таких, что для произвольного набора данных некоторой оптимизационной задачи и параметра ε&nbsp;>&nbsp;0 алгоритм семейства  за полиномиальное время находит решение с целевой функцией S  < (1 + ε)OPT, где OPT минимум целевой функции. Например, для [[Задача коммивояжёра|задачи коммивояжёра]] в евклидовом пространстве существует  PTAS, которое находит путь обхода длины не более (1&nbsp;+&nbsp;ε)''L'', где ''L'' длина кратчайшего  пути.<ref>[[Sanjeev Arora]], Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753–782, 1998.</ref>

Время выполнения PTAS должно полиномиально зависеть от ''n''  при любом фиксированном ε, но может произвольно меняться при изменении ε. Алгоритмы со временем выполнения ''[[«O» большое и «o» малое|O]]''(''n''<sup>1/ε</sup>) или даже ''O''(''n''<sup>exp(1/ε)</sup>) являются алгоритмами PTAS.

==Детерминированные алгоритмы==
В алгоритмах PTAS показатель степени в оценке сложности может расти катастрофически  при убывании ε, например, когда время выполнения  O(''n''<sup>(1/ε)!</sup>), что делает этот класс алгоритмов малоинтересным с практической точки зрения. Можно определить  '''эффективную приближенную схему полиномиального времени''' или '''efficient polynomial-time approximation scheme'''  ('''EPTAS'''), для которой время выполнения должно быть ''O''(''n''<sup>''c''</sup>), где константа ''c'' не зависит от ε. Это гарантирует, что увеличение размера входных данных увеличивает время выполнения независимо от величины ε; однако множитель под знаком [[«O» большое и «o» малое|O]]  при этом продолжает произвольно зависеть от ε. Дальнейшим ограничением более полезным на практике является '''приближенная схема полностью полиномиального времени''' или  '''fully polynomial-time approximation scheme''' ('''FPTAS'''), которая требует, чтобы время выполнения алгоритма полиномиально зависело и от размера задачи ''n'', и от 1/ε.  Примером задачи для которой существует FPTAS является [[задача о ранце]]. Но для родственной [[Задача об упаковке в контейнеры|задачи об упаковке в контейнеры]] нет даже PTAS.

Всякая [[Сильная NP-трудность|сильно NP-трудная]] задача оптимизации с полиномиально ограниченной целевой функцией не может иметь FPTAS.<ref name="vvv"/> Однако обратное неверно.  [[Список задач о ранце|Двумерная задача о ранце]] не является сильно NP-трудной, но не имеет FPTAS даже, когда целевая функция полиномиально ограничена.<ref>{{книга |заглавие=Knapsack Problems |издательство=Springer |год=2004 |язык=und |автор=H. Kellerer and U. Pferschy and D. Pisinger}}</ref>

Выполняется  FPTAS&nbsp;⊊&nbsp;PTAS&nbsp;⊊&nbsp;[[Класс APX|APX]]. Следовательно, APX-трудные задачи не имеют  PTAS.

Другой модификацией  PTAS является  '''приближенная схема квази-полиномиального времени''' или '''quasi-polynomial-time approximation scheme'''  ('''QPTAS'''). QPTAS имеет временную сложность <math>n^{polylog(n)}</math> для всякого фиксированного <math>\epsilon >0</math>.

==Рандомизированные алгоритмы==
Некоторые задачи, которые не имеют PTAS могут иметь [[рандомизированный алгоритм|рандомизированные алгоритмы]] с аналогичными свойствами -  '''рандомизированную приближенную схему полиномиального времени''' или '''polynomial-time randomized approximation scheme''' ('''PRAS''').  Алгоритм PRAS c параметром ε&nbsp;>&nbsp;0 для произвольного набора данных оптимизационной  задачи находит за полиномиальное время решение, которое с высокой вероятностью не превосходит (1 + ε)OPT.  Обычно под "высокой вероятностью" понимают вероятность больше 3/4, хотя определение не конкретизирует эту величину. Как и алгоритм PTAS алгоритм PRAS должен иметь время выполнения полиномиально зависящее от ''n'', но не от 1/ε. По аналогии с детерминированными алгоритмами вводятся '''EPRAS''' подобное EPTAS и '''FPRAS''' подобное FPTAS.<ref name="vvv">{{книга
|заглавие=Approximation Algorithms
|ссылка=https://archive.org/details/approximationalg00vazi_820
|издательство=Springer
|год=2003
|страницы=[https://archive.org/details/approximationalg00vazi_820/page/n304 294]—295
|место=Berlin
|isbn=3-540-65367-8
|язык=und
|автор=Vazirani, Vijay V.
}}</ref>

==Примечания==
<references/>

==Ссылки==
*Зоопарк сложностей: [https://web.archive.org/web/20120307124950/http://qwiki.stanford.edu/index.php/Complexity_Zoo:P#ptas PTAS], [https://web.archive.org/web/20120307125347/http://qwiki.stanford.edu/index.php/Complexity_Zoo:E#eptas EPTAS], [https://web.archive.org/web/20120307125343/http://qwiki.stanford.edu/index.php/Complexity_Zoo:F#fptas FPTAS]
*Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, [[Marek Karpinski]], and Gerhard Woeginger, [http://www.nada.kth.se/~viggo/wwwcompendium/ ''A compendium of NP optimization problems''] {{Wayback|url=http://www.nada.kth.se/~viggo/wwwcompendium/ |date=20131002065551 }} – list which NP optimization problems have PTAS.

[[Категория:Алгоритмы]]
[[Категория:Решение задач]]
[[Категория:Классы сложности]]