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

Аппроксимационный алгоритм — в исследовании операций алгоритм, использующийся для поиска приближённого решения оптимизационной задачи. Концепция аппроксимационного алгоритма была формализована в 1972-м году в статье Гарея, Грэхэма и Ульмана, а позднее Джонсоном.Аппроксимационные алгоритмы часто связаны с NP-трудными задачами, поскольку для них вряд ли найдётся эффективный алгоритм точного решения за полиномиальное время, так что имеет смысл попробовать найти близкое оптимальному решение.В отличие от эвристических алгоритмов, дающих достаточно хорошие решения за приемлемое время, аппроксимационные алгоритмы обеспечивают доказуемое качество решения в заранее определённых границах времени. В идеале аппроксимация даёт решение, отличающееся от оптимального на некоторый небольшой множитель (например, в пределах 5 %).Аппроксимационные алгоритмы всё чаще используются для решения задач, для которых известны точные алгоритмы, работающие за полиномиальное время, но работающие долго.Типичным примером аппроксимационного алгоритма может служить алгоритм решения задачи о вершинном покрытии в теории графов: найти непокрытое ребро и добавить обе его вершины к покрытию вершин, и так продолжать, пока все не будут покрыты.Ясно, что полученное покрытие может оказаться вдвое больше оптимального. Такое решение является аппроксимационным алгоритмом с постоянным коэффициентом 2. NP-трудные проблемы сильно различаются по возможности аппроксимации.Некоторые, среди которых, например, задача об упаковке в контейнеры, могут быть аппроксимированы с любым коэффициентом, большим 1 (это семейство алгоритмов называют приближённой схемой полиномиального времени, или PTAS).Другие задачи невозможно аппроксимировать ни с каким постоянным коэффициентом, или даже с полиномиальным коэффициентом (если P ≠ NP), и среди таких задач находится задача о максимальной клике. NP-трудные задачи часто можно выразить в терминах целочисленного программирования и решить в точности за экспоненциальное время. Многие экспоненциальные алгоритмы берут своё начало из целочисленной задачи. Не все аппроксимационные алгоритмы подходят для решения практических задач. Часто они используют в качестве подзадач ЦП/ЛП/полуопределённые задачи, сложные структуры данных или изощрённую технику программирования, что ведёт к сложности реализации.Некоторые аппроксимационные алгоритмы имеют неприемлемое время работы, хотя время и полиномиально (например, O(n2000)).Всё же изучение даже таких нереальных алгоритмов не преследует чисто теоретические цели, поскольку оно даёт возможность понять суть проблемы.Классический пример — начальный PTAS алгоритм для метрической задачи о коммивояжёре, принадлежащий Санджив Арора и имевший практически нереальное время работы. Однако, в течение года, Арора отточил идею до алгоритма, работающего за линейное время.Такие алгоритмы пригодны также для задач, в которых время работы и цена могут быть оправданы. К таким задачам относятся Вычислительная биология, , и . Другое ограничение связано с тем, что подход годится только для задач оптимизации, но не для «чистых» задач распознавания наподобие задачи выполнимости булевых формул, хотя часто бывает, что метод вполне применим для решения оптимизационных версий тех же задач, например, для (Max SAT). Невозможность аппроксимации является плодотворным полем исследований в области вычислительной сложности с тех пор, как в 1990 году Фейг (Feige), Голдвассер (Goldwasser), Ловаш (Lovasz), Сафра (Safra) и Шегеди (Szegedy) установили невозможность аппроксимации задачи нахождения максимального независимого множества вершин.Через год после того, как Арора (Arora) доказал теорему PCP, было доказано, что аппроксимационные алгоритмы Джонсона (Johnson) 1974-го года для задачи о выполнимости булевых формул, задачи о покрытии множества, задачи о независимом множестве и задача о хроматическом числе графа имеют оптимальный аппроксимационный коэффициент (в предположении, что P ≠ NP)