У математиці схема наближення до поліноміального часу (СНПЧ або 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, Інтернет
U matematici shema nablizhennya do polinomialnogo chasu SNPCh abo PTAS vid angl polynomial time approximation scheme klas nablizhenih do polinomialnih za chasom vikonannya algoritmiv dlya rozv yazuvannya yak pravilo NP skladnih optimizacijnih zadach Yaksho P NP to vprovadzhennya cogo ponyattya vtrachaye sens Tomu dali pripuskatimemo sho R ne zbigayetsya z NP I bez obmezhennya zagalnosti viznachimo ponyattya dlya zadachi minimizaciyi ViznachennyaSNPCh ce simejstvo algoritmiv yaki zalezhat vid parametra e takih sho dlya dovilnogo naboru danih deyakoyi optimizacijnoyi zadachi ta parametra e gt 0 algoritm simejstva za polinomialnij chas znahodit rozv yazok iz cilovoyu funkciyeyu S lt 1 e OPT de OPT minimum cilovoyi funkciyi Napriklad dlya zadachi komivoyazhera v evklidovomu prostori isnuye SNPCh yaka znahodit shlyah obhodu dovzhini ne bilshe 1 e L de L dovzhina najkorotshogo shlyahu Chas vikonannya SNPCh maye polinomialno zalezhati vid n za bud yakogo fiksovanogo e ale mozhe dovilno zminyuvatisya pri zmini e Algoritmi z chasom vikonannya O n1 e abo navit O nexp 1 e ye algoritmami SNPCh Determinovani algoritmiV algoritmah SNPCh pokaznik stepenya v ocinci skladnosti mozhe zrostati katastrofichno pri spadanni e napriklad koli chas vikonannya O n 1 e sho robit cej klas algoritmiv malocikavim iz praktichnoyi tochki zoru Mozhna viznachiti efektivnu shemu nablizhennya do polinomialnogo chasu ESNPCh abo EPTAS vid angl efficient polynomial time approximation scheme dlya yakoyi chas vikonannya maye buti O nc de konstanta c ne zalezhit vid e Ce garantuye sho zbilshennya vhidnih danih zbilshuye chas vikonannya nezalezhno vid velichini e odnak mnozhnik pid znakom O pri comu prodovzhuye dovilno zalezhati vid e Podalshim korisnim obmezhennyam ye shema povnogo nablizhennya do polinomialnogo chasu SPNPCh abo FPTAS vid angl fully polynomial time approximation scheme yaka vimagaye shob chas vikonannya algoritmu polinomialno zalezhav i vid rozmiru zadachi n i vid 1 e Prikladom zadachi dlya yakoyi isnuye SPNPCh ye zadacha pro ryukzak Ale dlya sporidnenoyi zadachi pro pakuvannya v yemnosti nemaye navit SNPCh Bud yaka silno NP skladna zadacha optimizaciyi z polinomialno obmezhenoyu cilovoyu funkciyeyu ne mozhe mati SPNPCh Prote zvorotne hibne Dvovimirna zadacha pro ranec ne ye silno NP skladnoyu ale ne maye SPNPCh navit koli cilova funkciya polinomialno obmezhena Vikonuyetsya SPNPCh SNPCh APX Otzhe APX skladni zadachi ne mayut SNPCh Inshoyu modifikaciyeyu SNPCh ye shema nablizhennya do kvazi polinomialnogo chasu SNKPCh abo QPTAS vid angl quasi polynomial time approximation scheme SNKPCh maye chasovu skladnist n p o l y l o g n displaystyle n polylog n dlya bud yakogo fiksovanogo ϵ gt 0 displaystyle epsilon gt 0 Uvipadkovleni algoritmiDeyaki zadachi yaki ne mayut SNPCh mozhut mati uvipadkovleni algoritmi z podibnimi vlastivostyami uvipadkovlenu shemu nablizhennya do polinomialnogo chasu USNPCh abo PRAS vid angl polynomial time randomized approximation scheme Algoritm USNPCh z parametrom e gt 0 dlya dovilnogo naboru danih optimizacijnoyi zadachi znahodit za polinomialnij chas rozv yazok yakij z visokoyu jmovirnistyu ne perevishuye 1 e OPT Zazvichaj pid visokoyu jmovirnistyu rozumiyut jmovirnist bilshe 3 4 hocha u viznachenni cyu velichinu ne konkretizovano Yak i algoritm SNPCh algoritm USNPCh povinen mati chas vikonannya sho polinomialno zalezhit vid n ale ne vid 1 e Za analogiyeyu z determinovanimi algoritmami uvodyatsya EUSNPCh EPRAS podibna do ESNPCh i USPNPCh FPRAS podibna do SPNPCh Primitki 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 S 294 295 ISBN 3 540 65367 8 H Kellerer and U Pferschy and D Pisinger Knapsack Problems Springer 2004 PosilannyaZoopark slozhnostej Pierluigi Crescenzi Viggo Kann Magnus Halldorsson and Gerhard Woeginger A compendium of NP optimization problems spisok NP skladnih zadach optimizaciyi yaki mayut SNPCh Arhivovano zhovten 2 2013 na sajti Wayback Machine