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

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

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

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

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

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

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

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

Гарантированная эффективностьПравить

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

\text{[math]}

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

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

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

\text{[math]}

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

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

\text{[math]}

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

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

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

Важное понятие относительной ошибки, связанной с задачами оптимизации, определяется в литературе по-разному: например, В. Канн^[7] определяет её как $\text{[math]}$ $\text{[math]}$ $|\mathrm {OPT} -f(y)|/\mathrm {OPT}$ , а Аузиелло и др.^[6] как $\text{[math]}$ $\text{[math]}$ $|\mathrm {OPT} -f(y)|/\max\{\mathrm {OPT} ,f(y)\}$ .

Абсолютная гарантированная эффективность $\text{[math]}$ $\text{[math]}$ $\mathrm {P} _{A}$ некоторого аппроксимационного алгоритма A определяется как

\text{[math]}

\mathrm {P} _{A}=\inf\{r\geqslant 1\mid R_{A}(x)\leqslant r,\forall x\}.

Здесь х обозначает задачу, а $\text{[math]}$ $\text{[math]}$ $R_{A}(x)$ — это гарантированная эффективность A для x.

Таким образом, $\text{[math]}$ $\text{[math]}$ $\mathrm {P} _{A}$ — это верхняя граница гарантированной эффективности r для всех возможных задач.

Подобным образом определяется асимптотическая эффективность $\text{[math]}$ $\text{[math]}$ $R_{A}^{\infty }$ :

\text{[math]}

R_{A}^{\infty }=\inf\{r\geqslant 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leqslant r,\forall x,|x|\geqslant n\}.

Гарантированная эффективность: границы снизу (сверху) для задач минимизации (максимизации) при заданных различных величинах
	r-аппрокс.^[6]^[7]	ρ-аппрокс.	относит. ошибка c^[7]	относит. ошибка c^[6]	норм. относ. ошибка c^[6]^[7]	абс. ошибка c^[6]^[7]
max: $\text{[math]}$ $\text{[math]}$ $f(x)\geqslant$	$\text{[math]}$ $\text{[math]}$ $r^{-1}\mathrm {OPT}$	$\text{[math]}$ $\text{[math]}$ $\rho \mathrm {OPT}$	$\text{[math]}$ $\text{[math]}$ $(1-c)\mathrm {OPT}$	$\text{[math]}$ $\text{[math]}$ $(1-c)\mathrm {OPT}$	$\text{[math]}$ $\text{[math]}$ $(1-c)\mathrm {OPT} +c\mathrm {WORST}$	$\text{[math]}$ $\text{[math]}$ $\mathrm {OPT} -c$
min: $\text{[math]}$ $\text{[math]}$ $f(x)\leqslant$	$\text{[math]}$ $\text{[math]}$ $r\mathrm {OPT}$	$\text{[math]}$ $\text{[math]}$ $\rho \mathrm {OPT}$	$\text{[math]}$ $\text{[math]}$ $(1+c)\mathrm {OPT}$	$\text{[math]}$ $\text{[math]}$ $(1-c)^{-1}\mathrm {OPT}$	$\text{[math]}$ $\text{[math]}$ $(1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST}$	$\text{[math]}$ $\text{[math]}$ $\mathrm {OPT} +c$

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

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

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

Эпсилон-членПравить

В литературе коэффициент аппроксимации для задачи на максимум (или минимум) записывается как $\text{[math]}$ $\text{[math]}$ $c-\epsilon$ (или $\text{[math]}$ $\text{[math]}$ $c+\epsilon$ ) для некоторого числа $\text{[math]}$ $\text{[math]}$ $c$ в том случае, когда существуют варианты алгоритма с коэффициентом аппроксимации $\text{[math]}$ $\text{[math]}$ $c\mp \epsilon$ для любого $\text{[math]}$ $\text{[math]}$ $\epsilon >0$ , но не для $\text{[math]}$ $\text{[math]}$ $\epsilon =0$ . Пример такой аппроксимации — недостижимость коэффициента 7 / 8 для задачи MAX-3SAT^[8].

ПримечанияПравить

↑ 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.
↑ D.S.Johnson. Approximation algorithms for combinatorial problems. J. Comput. System Sci., 9, 256—278, 1974.
↑ 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.
↑ Dorit S. Hochbaum, editor, Approximation Algorithms for NP-Hard Problems, page XV. PWS Publishing Company
↑ Tjark Vredeveld, Combinatorial approximation algorithms: Guaranteed versus experimental performance, Technische Universiteit Eindhoven, 2002, SBN 90-386-0532-3
↑ ¹ ² ³ ⁴ ⁵ ⁶ 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.
↑ ¹ ² ³ ⁴ ⁵ ⁶ Viggo Kann. On the Approximability of NP-complete Optimization Problems (англ.). — 1992. Архивная копия от 12 августа 2021 на Wayback Machine
↑ Johan Håstad. Some Optimal Inapproximability Results (англ.) // Journal of the ACM : journal. — 1999. Архивировано 12 марта 2012 года.

ЛитератураПравить

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

СсылкиПравить

Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger, A compendium of NP optimization problems (англ.)

[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

[ausiello99complexity-6] ¹ ² ³ ⁴ ⁵ ⁶ 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.

[kann92onthe-7] ¹ ² ³ ⁴ ⁵ ⁶ Viggo Kann. On the Approximability of NP-complete Optimization Problems (англ.). — 1992. Архивная копия от 12 августа 2021 на Wayback Machine

[hastad99someoptimal-8] Johan Håstad. Some Optimal Inapproximability Results (англ.) // Journal of the ACM : journal. — 1999. Архивировано 12 марта 2012 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]