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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В исследовании операций под аппроксимационным алгоритмом понимается алгоритм, использующийся для поиска приближённого решения оптимизационной задачи.

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

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

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

Не все аппроксимационные алгоритмы подходят для решения практических задач. Часто они используют в качестве подзадач ЦП/ЛП/полуопределённые задачи, сложные структуры данных или изощрённую технику программирования, что ведёт к сложности реализации. Некоторые аппроксимационные алгоритмы имеют неприемлемое время работы, хотя время и полиномиально (например, O(n2000)). Всё же изучение даже таких нереальных алгоритмов не преследует чисто теоретические цели, поскольку оно даёт возможность понять суть проблемы. Классический пример – начальный PTAS алгоритм для метрической задачи о коммивояжёре, принадлежащий Санджив Арора и имевший практически нереальное время работы. Однако, в течение года, Арора отточил идею до алгоритма, работающего за линейное время. Такие алгоритмы пригодны также для задач, в которых время работы и цена могут быть оправданы. К таким задачам относятся Вычислительная биология, Финансовая инженерия, Транспортное планирование и Управление запасами.

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


Невозможность аппроксимации является плодотворным полем исследований в области вычислительной сложности с тех пор, как в 1990 году Фейг (Feige), Голдвассер (Goldwasser), Ловаш (Lovasz), Сафра (Safra) и Шегеди (Szegedy) установили невозможность аппроксимации задачи нахождения максимального независимого множества вершин. Через год после того, как Арора (Arora) доказал теорему PCP, было доказано, что аппроксимационные алгоритмы Джонсона (Johnson) 1974-го года для задачи о выполнимости булевых формул, задачи о покрытии множества, задачи о независимом множестве и задача о хроматическом числе графа имеют оптимальный аппроксимационный коэффициент (в предположении, что P ≠ NP)

Гарантированная эффективность[править | править вики-текст]

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

\begin{cases}\mathrm{OPT} \leq f(x) \leq \rho \mathrm{OPT}, \rho > 1; \\ \rho \mathrm{OPT} \leq f(x) \leq \mathrm{OPT}, \rho < 1.\end{cases}

Коэффициент ρ называется относительной гарантированной эффективностью.

Аппроксимационный алгоритм имеет абсолютную гарантированную эффективность или ограниченную ошибку c, если для любой задачи x выполняется

 (\mathrm{OPT} - c) \leq f(x) \leq (\mathrm{OPT} + c).

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

R(x,y) =  \max \left ( \frac{OPT}{f(y)}, \frac{f(y)}{OPT} \right ),

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

Легко заметить, что в случае задачи минимизации оба определения гарантированной эффективности дают одно значение, в то время как для задачи максимизации r = \rho^{-1}.

Абсолютная гарантированная эффективность \Rho_A некоторого аппроксимационного алгоритма A определяется как

 \Rho_A = \inf \{ r \geq 1 \mid R_A(x) \leq r, \forall x \}.

Здесь х обозначает задачу, а R_A(x) - это гарантированная эффективность A для x.

Таким образом, \Rho_A - это верхняя граница гарантированной эффективности r для всех возможных задач.

Подобным образом определяется асимптотическая эффективность R_A^\infty:

 R_A^\infty = \inf \{ r \geq 1 \mid \exists n \in \mathbb{Z}^+, R_A(x) \leq r, \forall x, |x| \geq n\}.
Гарантированная эффективность
r-аппрокс.[6][7] ρ-аппрокс. rel. error[7] относит. ошибка[6] норм. относ. ошибка[6][7] абс. ошибка[6][7]
max: f(x) \geq r^{-1} \mathrm{OPT} \rho \mathrm{OPT} (1-c)\mathrm{OPT} (1-c)\mathrm{OPT} (1-c)\mathrm{OPT} + c\mathrm{WORST} \mathrm{OPT} - c
min: f(x) \leq r \mathrm{OPT} \rho \mathrm{OPT} (1+c)\mathrm{OPT} (1-c)^{-1}\mathrm{OPT} (1-c)^{-1} \mathrm{OPT} + c\mathrm{WORST} \mathrm{OPT} + c

Техника разработки алгоритмов[править | править вики-текст]

На настоящее время существует несколько стандартных подходов к разработке аппроксимациооного алгоритма. Среди них:

  1. Жадный алгоритм.
  2. Локальный поиск.
  3. Перебор и динамическое программирование.
  4. Решение ослабленной задачи выпуклого программирования с возможностью получения дробного решения. Затем решение преобразуется в подходящее решение путём округления. Популярными методами ослабления задачи являются:
    1. Сведение к задаче линейного программирования.
    2. Сведение к задаче полуопределённого программирования.
  5. Определение для задачи некоторой простой метрики и решение задачи с этой метрикой.


Смотрите также[править | править вики-текст]

Ссылки[править | править вики-текст]

  1. M.R.Garey, R.L. Graham and J.D. Ullman. Worst case analysis of memory allocation algorithms. In Proc. Of the 4th ACM Symp. On Theory of Computing. 143-152, 1972.
  2. D.S.Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9, 256-278, 1974.
  3. Gomory, Ralph E. (1958), "Outline of an algorithm for integer solutions to linear programs", Bulletin of the American Mathematical Society 64 (5): 275–279, doi:10.1090/S0002-9904-1958-10224-4.
  4. Dorit S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, page XV. PWS Publishing Company
  5. Tjark Vredeveld, Combinatorial approximation algorithms: Guaranteed versus experimental performance, Technische Universiteit Eindhoven, 2002, SBN 90-386-0532-3
  6. 1 2 3 4 5 G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. — 1999.
  7. 1 2 3 4 5 Viggo Kann On the Approximability of NP-complete Optimization Problems. — 1992.
  • Vazirani Vijay V. Approximation Algorithms. — Berlin: Springer, 2003. — ISBN 3-540-65367-8
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 35: Approximation Algorithms, pp. 1022–1056.
  • Dorit H. Hochbaum, ed. Approximation Algorithms for NP-Hard problems, PWS Publishing Company, 1997. ISBN 0-534-94968-1. Chapter 9: Various Notions of Approximations: Good, Better, Best, and More
  • Williamson, David & Shmoys, David (April 26, 2011), «The Design of Approximation Algorithms», Cambridge University Press, ISBN 978-0521195270 

Внешние ссылки[править | править вики-текст]