У математиці схема наближення до поліноміального часу (СНПЧ або PTAS від англ. polynomial-time approximation scheme) — клас наближених до поліноміальних за часом виконання алгоритмів для розв'язування, як правило, NP-складних оптимізаційних задач. Якщо P = NP, то впровадження цього поняття втрачає сенс. Тому далі припускатимемо, що Р не збігається з NP. І, без обмеження загальності, визначимо поняття для задачі мінімізації.
Визначення
СНПЧ це сімейство алгоритмів, які залежать від параметра ε , таких, що для довільного набору даних деякої оптимізаційної задачі та параметра ε > 0 алгоритм сімейства за поліноміальний час знаходить розв'язок із цільовою функцією S<(1 + ε)OPT, де OPT — мінімум цільової функції. Наприклад, для задачі комівояжера в евклідовому просторі існує СНПЧ, яка знаходить шлях обходу довжини не більше (1 + ε)L, де L — довжина найкоротшого шляху.
Час виконання СНПЧ має поліноміально залежати від n за будь-якого фіксованого ε, але може довільно змінюватися при зміні ε. Алгоритми з часом виконання O(n1/ε) або навіть O(nexp(1/ε)) є алгоритмами СНПЧ.
Детерміновані алгоритми
В алгоритмах СНПЧ показник степеня в оцінці складності може зростати катастрофічно при спаданні ε, наприклад, коли час виконання O(n(1/ε)!), що робить цей клас алгоритмів малоцікавим із практичної точки зору. Можна визначити ефективну схему наближення до поліноміального часу (ЕСНПЧ або EPTAS від англ. efficient polynomial-time approximation scheme), для якої час виконання має бути O(nc), де константа c не залежить від ε. Це гарантує, що збільшення вхідних даних збільшує час виконання незалежно від величини ε; однак множник під знаком O, при цьому продовжує довільно залежати від ε. Подальшим корисним обмеженням є схема повного наближення до поліноміального часу (СПНПЧ або FPTAS від англ. fully polynomial-time approximation scheme), яка вимагає, щоб час виконання алгоритму поліноміально залежав і від розміру задачі n, і від 1/ε. Прикладом задачі для якої існує СПНПЧ є задача про рюкзак. Але для спорідненої (задачі про пакування в ємності) немає навіть СНПЧ.
Будь-яка сильно NP-складна задача оптимізації з поліноміально обмеженою цільовою функцією не може мати СПНПЧ. Проте зворотне хибне. (Двовимірна задача про ранець) не є сильно NP-складною, але не має СПНПЧ навіть, коли цільова функція поліноміально обмежена.
Виконується СПНПЧ ⊊ СНПЧ ⊊ APX. Отже, APX-складні задачі не мають СНПЧ.
Іншою модифікацією СНПЧ є схема наближення до квазі-поліноміального часу (СНКПЧ або QPTAS від англ. quasi-polynomial-time approximation scheme). СНКПЧ має часову складність для будь-якого фіксованого
.
Увипадковлені алгоритми
Деякі задачі, які не мають СНПЧ, можуть мати увипадковлені алгоритми з подібними властивостями — увипадковлену схему наближення до поліноміального часу (УСНПЧ або PRAS від англ. polynomial-time randomized approximation scheme). Алгоритм УСНПЧ з параметром ε > 0 для довільного набору даних оптимізаційної задачі знаходить за поліноміальний час розв'язок, який з високою ймовірністю не перевищує (1 + ε)OPT. Зазвичай під «високою ймовірністю» розуміють ймовірність більше 3/4, хоча у визначенні цю величину не конкретизовано. Як і алгоритм СНПЧ алгоритм УСНПЧ повинен мати час виконання, що поліноміально залежить від n, але не від 1/ε. За аналогією з детермінованими алгоритмами уводяться ЕУСНПЧ (EPRAS), подібна до ЕСНПЧ, і УСПНПЧ (FPRAS), подібна до СПНПЧ.
Примітки
- [en], Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, Journal of the ACM 45(5) 753—782, 1998.
- Vazirani, Vijay V. Approximation Algorithms. — Berlin : Springer, 2003. — С. 294—295. — .
- H. Kellerer and U. Pferschy and D. Pisinger. Knapsack Problems. — Springer, 2004.
Посилання
- Зоопарк сложностей: , ,
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, , and Gerhard Woeginger, A compendium of NP optimization problems — список NP-складних задач оптимізації, які мають СНПЧ. Архівовано жовтень 2, 2013 на сайті Wayback Machine.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет