Аппроксимации с произвольной точностью: задача о рюкзаке
Когда к вам обращаются за помощью люди, столкнувшиеся с NP-сложной задачей оптимизации, они часто надеются получить алгоритм, способный выдать решение в пределах, скажем, 1 % от оптимума — или по крайней мере в относительно небольшом диапазоне от оптимума.
С этой точки зрения аппроксимирующие алгоритмы, рассматривавшиеся ранее, были довольно слабыми: решения с множителем 2 для минимума задач выбора центров и вершинного покрытия (то есть превышение оптимума может достигать 100 %).
С алгоритмом покрытия множества из раздела 10.3 дело обстоит еще хуже: его стоимость даже не лежит в пределах фиксированного постоянного множителя от возможного минимума!
Например, если P ≠ NP, то гарантия, предоставляемая алгоритмом выбора центров, является лучшей из возможных среди всех алгоритмов с полиномиальным временем. Аналогичным образом гарантия, предоставляемая алгоритмом покрытия множества, как бы плохо она ни выглядела, очень близка к лучшей из возможных (если только не окажется, что P = NP).
Для других задач — например, задачи о вершинном покрытии — приведенный нами аппроксимирующий алгоритм является лучшим из известных, но вопрос о том, не существуют ли алгоритмы с полиномиальным временем, обладающий лучшими гарантиями, остается открытым.
В этой книге тема нижних границ аппроксимируемости не рассматривается; хотя некоторые нижние границы такого типа доказываются не так уж сложно (например, как в задаче о выборе центров), доказательства во многих случаях перегружаются огромным количеством технических подробностей.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу