апроксимаційний алгоритм

У дослідженні операцій під Апроксимаційні алгоритмом розуміється алгоритм. використовується для пошуку наближеного рішення оптимізаційної задачі.

Концепція апроксимаційного алгоритму була формалізована в 1972-му році в статті Гарі, Грехема і Ульмана [1]. а пізніше Джонсоном [2]. Апроксимаційні алгоритми часто пов'язані з NP-важкими завданнями, оскільки для них навряд чи знайдеться ефективний алгоритм точного рішення за поліноміальний час, так що має сенс спробувати знайти близьке оптимальному рішення. На відміну від евристичних алгоритмів. дають досить хороші рішення за прийнятний час, апроксимаційні алгоритми забезпечують доказове якість рішення в заздалегідь визначених межах часу. В ідеалі апроксимація дає рішення, яке відрізняється від оптимального на деякий невеликий множник (наприклад, в межах 5%). Апроксимаційні алгоритми все частіше використовуються для вирішення завдань, для яких відомі точні алгоритми, що працює за поліноміальний час, але працюють довго. Типовим прикладом апроксимаційного алгоритму може служити алгоритм вирішення задачі про вершинному покритті в теорії графів. знайти непокрите ребро і додати обидві його вершини до покриття вершин, і так продовжувати, поки все не будуть покриті. Ясно, що отримане покриття може виявитися вдвічі більше оптимального. Таке рішення є Апроксимаційні алгоритмом з постійним коефіцієнтом 2.

NP-важкі проблеми сильно розрізняються по можливості апроксимації. Деякі, серед яких, наприклад, завдання про упаковку в контейнери. можуть бути апроксимувати з будь-яким коефіцієнтом, більшим 1 (це сімейство алгоритмів називають наближеною схемою полиномиального часу. або PTAS). Інші завдання неможливо апроксимувати ні з яким постійним коефіцієнтом, або навіть з поліноміальних коефіцієнтом (якщо P ≠ NP), і серед таких завдань знаходиться завдання про максимальну кліці.

NP-важкі завдання часто можна виразити в термінах цілочисельного програмування і вирішити в точності за експоненціальне час. Багато експоненціальні алгоритми беруть свій початок з приведення до задачі лінійного програмування целочисленной завдання. [3]

Інше обмеження пов'язане з тим, що підхід годиться тільки для задач оптимізації, але не для "чистих" завдань розпізнавання на зразок завдання здійсненності булевих формул. хоча часто буває, що метод цілком можна застосувати для вирішення оптимізаційних версій тих же завдань, наприклад, для завдання максимальної здійсненності булевих формул (Max SAT).

Для деяких апроксимаційних алгоритмів вдається довести деякі властивості результату апроксимації. Наприклад, ρ -аппроксімаціонний алгорітмA - це за визначенням алгоритм, для якого відношення f (x) = цінність / витрати для вирішення апроксимаційної завдання A (x) для завдання x не перевищує (або не менше, в залежності від ситуації) твори коефіцієнта ρ на оптимальну величину цінності [4] [5]:

Коефіцієнт ρ називається відносної гарантованої ефективністю.

Апроксимаційний алгоритм має абсолютну гарантовану ефективність або обмежену ошібкуc. якщо для будь-якого завдання x виконується

Подібним чином визначається гарантована ефективність. R (x, y), рішення y для завдання x

де f (y) - відношення цінність / витрати для вирішення y завдання x. Ясно, що гарантована ефективність не менше одиниці і дорівнює одиниці тільки в разі, коли y є оптимальним рішенням. Якщо алгоритм A гарантує рішення з максимальною ефективністю r (n), то говорять, що A є r (n) -аппроксімаціонним алгоритмом і має апроксимаційний коефіцієнт r (n) [6] [7].

Легко помітити, що в разі завдання мінімізації обидва визначення гарантованої ефективності дають одне значення, в той час як для завдання максимізації r = ρ - 1>.

Важливе поняття відносної помилки. пов'язаної із завданнями оптимізації, визначається в літературі по-різному: наприклад, В. Канн [7] визначає її як | O P T - f (y) | / O P T -f (y) | / \ mathrm>. а Аузіелло і ін. [6] як | O P T - f (y) | / max -f (y) | / \ max \, f (y) \ >>.

Абсолютна гарантована ефективність P A _> деякого апроксимаційного алгоритму A визначається як

Тут х позначає завдання, а R A (x) - це гарантована ефективність A для x.

Таким чином, P A _> - це верхня межа гарантованої ефективності r для всіх можливих завдань.

Подібним чином визначається асимптотична ефективність R A ∞>:

Гарантована ефективність: кордону знизу (зверху) для задач мінімізації (максимізації) при заданих різних величинах

Техніка розробки алгоритмів

На даний час існує декілька стандартних підходів до розробки аппроксімаціооного алгоритму. Серед них:

  1. Жадібний алгоритм.
  2. Локальний пошук.
  3. Перебір і динамічне програмування.
  4. Рішення ослабленою завдання опуклого програмування з можливістю отримання дрібного рішення. Потім рішення перетворюється в відповідне рішення шляхом округлення. Популярними методами ослаблення завдання є:
    1. Зведення до задачі лінійного програмування.
    2. Зведення до задачі полуопределённого програмування.
  5. Визначення для завдання деякої простої метрики і рішення задачі з цієї метрикою.

У літературі коефіцієнт апроксимації для завдання на максимум (або мінімум) записується як c - ε (або c + ε) для деякого числа c в тому випадку, коли існують варіанти алгоритму з коефіцієнтом апроксимації c ∓ ε для будь-якого ε> 0. але не для ε = 0. Приклад такої апроксимації - недосяжність коефіцієнта 7/8 для завдання MAX-3SAT [8].

  • Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems.

Схожі статті