Оглавление
- 1 Алгоритм аппроксимации
- 1.1 Определение аппроксимационных алгоритмов
- 1.2 Типы гарантий
- 1.3 Примеры алгоритмов
- 1.4 Методы разработки алгоритмов
- 1.5 Апостериорные гарантии
- 1.6 Жесткость аппроксимации
- 1.7 Практичность
- 1.8 Структура алгоритмов аппроксимации
- 1.9 Определение аппроксимации
- 1.10 Гарантии производительности
- 1.11 Термины Эпсилон
- 1.12 Анализ доминирования и PTAS
- 1.13 Сокращение с сохранением аппроксимации и точный алгоритм
- 1.14 Полный текст статьи:
- 2 Алгоритм аппроксимации
Алгоритм аппроксимации
-
Определение аппроксимационных алгоритмов
- Аппроксимационные алгоритмы находят приближенные решения задач оптимизации с доказуемыми гарантиями.
- Возникают из гипотезы P ≠ NP, которая утверждает, что NP-сложные задачи не могут быть решены точно за полиномиальное время.
-
Типы гарантий
- Большинство алгоритмов обеспечивают мультипликативную гарантию, выраженную в виде коэффициента аппроксимации.
- Некоторые алгоритмы также обеспечивают дополнительную гарантию качества решения.
-
Примеры алгоритмов
- Алгоритм аппроксимации Ленстры, Шмойса и Тардоса для планирования на несвязанных параллельных машинах.
- Алгоритм Гоеманса-Уильямсона для максимального сокращения.
-
Методы разработки алгоритмов
- Жадный алгоритм, локальный поиск, перечисление и динамическое программирование.
- Релаксации линейного программирования, полуопределенные программные релаксации, первично-дуальные методы.
- Двойной фитинг, внедрение метрики, случайная выборка.
-
Апостериорные гарантии
- Алгоритмы аппроксимации могут обеспечивать апостериорные гарантии, часто намного лучше априорных.
- Пример: алгоритм аппроксимации для минимального покрытия вершин, решающий задачу линейного программирования релаксации.
-
Жесткость аппроксимации
- Алгоритмы аппроксимации связаны с теорией неприменимости, которая доказывает несуществование эффективных алгоритмов с определенными коэффициентами аппроксимации.
- Пример: результат неприменимости для задачи о метрическом коммивояжере.
-
Практичность
- Не все алгоритмы аппроксимации подходят для практического применения из-за сложности реализации и времени выполнения.
- Идеи и прозрения, лежащие в основе таких алгоритмов, могут быть включены в практические алгоритмы.
-
Структура алгоритмов аппроксимации
- Задача оптимизации: Π : I × S, где Π — проблема аппроксимации, I — набор входных данных, S — набор решений.
- Функция затрат: c: S → R+, набор возможных решений: S(i) = {s ∈ S: iΠs}.
- Поиск наилучшего решения s∗ для задачи максимизации или минимизации.
- Гарантированная производительность (коэффициент аппроксимации) ρ(n) для всех i ∈ I s.t. |i| = n.
-
Определение аппроксимации
- Алгоритм аппроксимации A достигает соотношения ρ(n) между решением A и оптимальным решением s∗.
- Для задачи максимизации: c(s∗(i))/c(A(i)) ≤ ρ(n).
- Для задачи минимизации: c(A(i))/c(s∗(i)) ≤ ρ(n).
-
Гарантии производительности
- Алгоритм ρ-аппроксимации имеет гарантию производительности, что значение решения A не больше ρ от оптимального решения.
- Абсолютная гарантия производительности P(A) — это наибольшая граница коэффициента аппроксимации r.
- Асимптотический коэффициент полезного действия R(A)∞ — это то же самое, что и P(A), но с нижней границей n для размера экземпляров.
-
Термины Эпсилон
- Коэффициент аппроксимации c – ∞ означает, что алгоритм имеет коэффициент аппроксимации c для произвольного θ > 0, но не для θ = 0.
- Пример: оптимальная неприменимость для MAX-3SAT.
- Θ-член может появиться при мультипликативной ошибке и постоянной ошибке.
-
Анализ доминирования и PTAS
- Анализ доминирования рассматривает гарантии с точки зрения ранга решения.
- PTAS — тип алгоритма аппроксимации с параметром коэффициента аппроксимации.
- Параметризованный алгоритм аппроксимации выполняется за короткое время.
- APX — класс задач с алгоритмом аппроксимации с постоянным коэффициентом.
-
Сокращение с сохранением аппроксимации и точный алгоритм
- Сокращение с сохранением аппроксимации — это метод улучшения аппроксимации.
- Точный алгоритм — это алгоритм, который всегда дает оптимальное решение.