Приближённая схема полиномиального времени
Войти  |  Регистрация
Авторизация
» » Приближённая схема полиномиального времени

Приближённая схема полиномиального времени



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

Определение

PTAS это семейство алгоритмов, зависящих от параметра ε , таких, что для произвольного набора данных некоторой оптимизационной задачи и параметра ε > 0 алгоритм семейства за полиномиальное время находит решение с целевой функцией S < (1 + ε)OPT, где OPT минимум целевой функции. Например, для задачи коммивояжёра в Евклидовом пространстве существует PTAS, которое находит путь обхода длины не более (1 + ε)L, где L длина кратчайшего пути.

Время выполнения PTAS должно полиномиально зависеть от n при любом фиксированном ε, но может произвольно меняться при изменении ε. Алгоритмы со временем выполнения O(n1/ε) или даже O(nexp(1/ε)) являются алгоритмами PTAS.

Детерминированные алгоритмы

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

Всякая сильно NP-трудная задача оптимизации с полиномиально ограниченной целевой функцией не может иметь FPTAS. Однако обратное неверно. Двумерная задача о ранце не является сильно NP-трудной, но не имеет FPTAS даже, когда целевая функция полиномиально ограничена.

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

Другой модификацией PTAS является приближенная схема квази-полиномиального времени или quasi-polynomial-time approximation scheme (QPTAS). QPTAS имеет временную сложность n p o l y l o g ( n ) {displaystyle n^{polylog(n)}} для всякого фиксированного ϵ > 0 {displaystyle epsilon >0} .

Рандомизированные алгоритмы

Некоторые задачи, которые не имеют PTAS могут иметь рандомизированные алгоритмы с аналогичными свойствами - рандомизированную приближенную схему полиномиального времени или polynomial-time randomized approximation scheme (PRAS). Алгоритм PRAS c параметром ε > 0 для произвольного набора данных оптимизационной задачи находит за полиномиальное время решение, которое с высокой вероятностью не превосходит (1 + ε)OPT. Обычно под "высокой вероятностью" понимвют вероятность больше 3/4, хотя определение не конкретизирует эту величину. Как и алгоритм PTAS алгоритм PRAS должен иметь время выполнения полиномиально зависящее от n, но не от 1/ε. По аналогии с детерминированными алгоритмами вводятся EPRAS подобное EPTAS и FPRAS подобное FPTAS.


Добавлено Admin 13-03-2022, 21:00 Просмотров: 31
Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent