Аппроксимирующие алгоритмы
После обсуждения NP-полноты и концепции вычислительной неразрешимости в целом мы начали искать ответ на фундаментальный вопрос: как разрабатывать алгоритмы для задач, у которых полиномиальное время, скорее всего, является недостижимым?
В этом определении следует обратить внимание на ключевые слова: гарантированно и близкие. Мы не пытаемся искать оптимальное решение, и в результате появляется возможность достичь полиномиального времени выполнения.
В то же время нужно будет доказывать, что алгоритмы находят решения, гарантированно близкие к оптимуму. Эта задача весьма непростая по своей природе: чтобы доказать гарантию аппроксимации, необходимо сравнить решение с оптимальным решением, которое очень трудно найти (и, возможно, привести обоснование). Данная проблема неоднократно встречается при анализе алгоритмов в этой главе.
В этой главе рассматриваются четыре общие методологии разработки аппроксимирующих алгоритмов.
Эти алгоритмы быстры и просты, как и в главе 4, поэтому основная проблема связана с поиском жадного правила, приводящего к решению, доказуемо близкого к оптимальному.
Второй общий метод — метод назначения цены — имеет экономическую подоплеку; мы рассматриваем цену, которую необходимо уплатить за соблюдение каждого ограничения в задаче.
Метод назначения цены часто называется прямо-двойственным методом (primal-dual) — термин происходит из области линейного программирования, которое тоже может использоваться в этой области.
Описание метода назначения цены не требует знакомства с линейным программированием, которое будет представлено в третьей категории — линейном программировании с округлением, использующем отношения между вычислительной разрешимостью линейного программирования и выразительной мощью его «более сложного» родственника, целочисленного программирования.
В завершение будет описан метод, приводящий к исключительно качественным аппроксимациям: применение динамического программирования к округленной версии входных данных.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу