Комбинаторная оптимизация: введение
Комбинаторная оптимизация — одно из самых молодых и активно развивающихся направлений дискретной математики. Задачи оптимизации возникают в теории расписаний, размещении предприятий, проектировании сетей, работе с базами данных, передаче информации, а также в экономике и финансах — от инвестиций до стратегий аукционов и маркетинга.
К сожалению, большинство таких задач являются \(\operatorname {NP}\)-трудными, и считается, что эффективных алгоритмов их точного решения не существует. Поэтому основной целью нашего курса будет изучение методов построения приближённых алгоритмов и приближённых схем. Для этого необходимо формально определить рассматриваемые задачи и свойства алгоритмов.
1 Вершинное покрытие
Начнём с конкретного примера. Одной из типичных задач комбинаторной оптимизации является задача о вершинном покрытии. Напомним, вершинным покрытием графа \(G=(V, E)\) называется такое подмножество вершин \(S \subseteq V\), что каждое ребро графа \(G\) имеет хотя бы одну вершину в \(S\).
Задача о вершинном покрытии наименьшей мощности
Неориентированный граф \(G=(V, E)\).
Вершинное покрытие минимального размера (мощности).
В более общей постановке каждой вершине приписан неотрицательный вес, и требуется найти вершинное покрытие минимального суммарного веса.
Задача о вершинном покрытии наименьшего веса
Неориентированный граф \(G=(V, E)\), веса вершин \(c: V \to \mathbb {Q}_+\).
Вершинное покрытие наименьшего суммарного веса.
Задача о вершинном покрытии наименьшего веса
Граф \(G=(V,E)\) с весами вершин \(c\) (числа на рёбрах показаны только как пример разметки; в задаче вес приписан каждой вершине \(v_i\)). Наведите курсор на вершину — увидите её вес и подсветку инцидентных рёбер.
Говорят, что задача о минимальном вершинном покрытии является \(\operatorname {NP}\)-трудной. Что это означает?
2 Оцениваем трудность задачи: от задачи оптимизации к задаче разрешимости
В общем случае любую задачу оптимизации можно сопоставить задаче разрешимости (т.е. задаче с ответом ДА/НЕТ). Если требуется, например, минимизировать некоторую функцию \(f(x)\), то формулировка задачи разрешимости выглядит так:
Существует ли решение \(x\), для которого \(f(x) \le k\)?
где \(k\) — параметр, поданный вместе с входом.
Например:
Задача оптимизации: найти вершинное покрытие минимального размера.
Соответствующая задача разрешимости: при заданном \(k\) определить, существует ли вершинное покрытие размера не более \(k\).
Если задача разрешимости является \(\operatorname {NP}\)-трудной, то и про исходную задачу оптимизации также говорят, что она \(\operatorname {NP}\)-трудна. Интуитивно это означает, что не существует эффективного (полиномиального) алгоритма для нахождения точного решения во всех возможных случаях.
До сих пор неизвестно, совпадают ли классы \(\mathrm{P}\) и \(\mathrm{NP}\). В частности, это означает, что быстрых (полиномиальных) алгоритмов точного решения задачи о вершинном покрытии на данный момент не найдено. Если бы такой алгоритм существовал, то автоматически следовало бы равенство \(\mathrm{P} = \mathrm{NP}\).
Преобладающая точка зрения ученых состоит в том, что \(\mathrm{P} \neq \mathrm{NP}\), а значит, скорее всего, эффективного алгоритма точного решения задачи о вершинном покрытии в принципе не существует. Именно поэтому особое внимание уделяется приближённым алгоритмам, позволяющим получать решения за полиномиальное время с гарантией на их качество.
3 Первый приближённый алгоритм: жадный алгоритм для вершинного покрытия
Одним из первых методов, который естественно попробовать при решении задачи оптимизации, является жадный алгоритм. Под жадным алгоритмом понимается итеративная процедура, которая на каждом шаге выбирает локально наилучшее решение, стараясь максимально улучшить целевую функцию, не учитывая последствия таких шагов в будущем.
В задаче о вершинном покрытии это означает, что на каждом шаге выбирается вершина, инцидентная наибольшему числу рёбер.
Легко построить пример, когда жадный алгоритм выдаёт решение, далёкое от оптимального. На рисунке ниже показан граф, для которого жадный выбор приводит к заведомо неоптимальному покрытию.
Жадный алгоритм для вершинного покрытия
На каждом шаге алгоритм берёт вершину максимальной степени (среди ещё непокрытых рёбер), добавляет её в решение и удаляет все инцидентные ей рёбра. Оранжевая обводка — вершина, которую алгоритм выберет следующей; наведите курсор, чтобы увидеть текущие степени.
Из этого примера становится понятно, что жадный алгоритм может выдать решение, как минимум в \(5/4\) раз большее оптимума. Возникает вопрос: насколько плохим может быть результат жадного алгоритма в худшем случае? Есть ли точная оценка? Чтобы ответить на него, необходимо провести формальный анализ и вывести оценку качества.
4 Анализ алгоритма
Оценка качества приближённого алгоритма обычно сводится к сравнению его решения с оптимальным. Однако в случае \(\operatorname {NP}\)-трудных задач не только нахождение оптимального решения, но даже вычисление его стоимости является \(\operatorname {NP}\)-трудной задачей. Иными словами, напрямую использовать оптимум для контроля качества алгоритма практически невозможно (его просто не вычислить за разумное время).
Поэтому стандартный подход заключается в построении полиномиально вычислимых нижних оценок стоимости оптимального решения. Такие оценки позволяют оценивать точность приближения и часто подсказывают структуру алгоритма.
Вычислить точность данного выше жадного алгоритма не так просто, как может показаться. Мы займемся этим в следующей главе. Пока давайте рассмотрим другой приближенный алгоритм для задачи о вершинном покрытии.
4.1 Алгоритм для вершинного покрытия через паросочетания
Алгоритм через паросочетания для вершинного покрытия
Алгоритм строит максимальное по включению паросочетание — набор рёбер без общих вершин — и выдаёт все вершины, инцидентные его рёбрам. Красные рёбра — паросочетание; наведите курсор на ребро, чтобы узнать, можно ли его ещё добавить.
Данный алгоритм на первый взгляд может показаться менее эффективным, чем жадный. Однако, как будет показано, у него есть константная оценка точности: решение максимум в \(2\) раза хуже оптимума. Жадный же алгоритм, как мы увидим в следующей главе, в худшем случае может отработать сколь угодно хуже оптимума.
Кроме того, результат работы алгоритма через паросочетания часто легко улучшить постпроцессингом: можно попробовать удалить из полученного множества вершины, удаление которых не нарушает покрытия всех рёбер. Таким образом, решение становится ближе к оптимальному. С результатом жадного алгоритма такой простой приём, как правило, не работает.
4.2 Точность алгоритма
Ключевой факт: мощность максимального по включению паросочетания является нижней оценкой мощности любого вершинного покрытия. Действительно, для каждого ребра из паросочетания хотя бы одна из его вершин должна принадлежать покрытию. Поскольку рёбра паросочетания не пересекаются по вершинам, число вершин в любом покрытии не может быть меньше числа рёбер в паросочетании. Этот простой факт показывает, как нижние оценки естественным образом связаны с построением приближённых решений.
Мы получили первый приближённый алгоритм. Основные вопросы для улучшения результата:
Можно ли уточнить анализ качества алгоритма? Является ли приведённая оценка 2 точной?
Существует ли алгоритм с коэффициентом приближения \(\rho <2\), который всегда выдаёт решение не хуже \(\rho\)-кратной нижней оценки?
Можно ли использовать другие нижние оценки для построения \(\rho\)-приближенного алгоритма с \(\rho <2\)?
4.3 Оценка алгоритма точна?
Следующий пример показывает, что улучшить анализ качества алгоритма через паросочетания нельзя. Построим бесконечное семейство примеров, при решении которых он ошибается в два раза. Рассмотрим полный двудольный граф \(K_{n, n}\), изображенный на рисунке ниже. Алгоритм через паросочетания в этом графе выберет в решение все \(2 n\) вершин, в то время как оптимальное решение состоит из \(n\) вершин одной доли.
Точность оценки алгоритма через паросочетания: \(K_{n,n}\)
В полном двудольном графе \(K_{n,n}\) любое совершенное паросочетание уже максимально по включению, поэтому алгоритм выбирает все \(2n\) вершин, а оптимальное покрытие — одна доля из \(n\) вершин: отношение стремится к \(2\).
4.4 Есть ли другой алгоритм, который будет лучше относительно полученной нами нижней оценки через мощность максимального паросочетания?
Пусть для оценки качества решения использовалась нижняя оценка через мощность паросочетания. Приведем пример, на котором значение нижней оценки отличается от оптимума в два раза. Рассмотрим полный граф на \(n\) вершинах, где \(n\) нечетно. Мощность максимального паросочетания равна \((n-1) / 2\), а мощность оптимального вершинного покрытия \(n-1\). Следовательно, стоимость решения любого (даже не полиномиального) алгоритма может быть почти в 2 раза хуже нижней оценки.
Полный граф \(K_5\): паросочетание из 2 рёбер против покрытия из 4 вершин
В \(K_5\) (нечётное число вершин) максимальное паросочетание содержит только 2 ребра, например \(\{v_1,v_2\}\) и \(\{v_3,v_4\}\), — алгоритм через паросочетания вернёт 4 вершины. Но и оптимальное покрытие состоит из 4 вершин (любые 4 из 5): здесь алгоритм случайно точен.
4.5 Есть ли другой алгоритм, который будет лучше вообще, может быть с какой-то другой нижней оценкой?
Вопрос о существовании \(\rho\)-приближенного алгоритма с \(\rho <2\), использующего другую нижнюю оценку, гораздо сложнее. Недавно Субхаш Кхот выдвинул правдоподобную гипотезу [7], [8], согласно которой существование полиномиального алгоритма для задачи о вершинном покрытии с гарантированной оценкой \(2-\varepsilon\) при любом фиксированном \(\varepsilon >0\) влечёт совпадение классов \(\operatorname {P}\) и \(\operatorname {NP}\).
5 Задачи оптимизации и приближенные алгоритмы
Дадим общие определения.
Если \(\Pi\) – задача минимизации, то оптимальным решением индивидуальной задачи \(I \in \Omega_{\Pi }\) называется такое допустимое решение \(\sigma^{*} \in \operatorname {Sol}_{\Pi }(I)\), что для всех \(\sigma \in \operatorname {Sol}_{\Pi }(I)\) выполнено неравенство
\[ \operatorname {COST}_{\Pi }\left(I, \sigma ^{*}\right) \leq \operatorname {COST}_{\Pi }(I, \sigma ) \]
(если \(\Pi\) – это задача максимизации, то неравенство надо развернуть).
Алгоритм, который находит оптимальное решение для каждого примера задачи, называется точным.
Большинство задач комбинаторной оптимизации, возникающих в приложениях, являются \(\operatorname {NP}\)-трудными. Существуют различные подходы к решению таких задач.
Решать точно «переборными» алгоритмами. К сожалению, для большинства \(\operatorname {NP}\)-трудных задач переборные алгоритмы решают только примеры малой размерности.
Решать приближенно.
Алгоритмы с апостериорной оценкой точности. Оценка точности неизвестна заранее, хотя на практике они часто находят решения, близкие к оптимальному
Алгоритмы с априорной оценкой точности. Для таких алгоритмов удается доказать, что они всегда находят решение с гарантированной оценкой точности в худшем случае.
В нашем курсе мы будем в основном изучать приближенные алгоритмы с гарантированной оценкой точности в худшем случае.
Как построить приближенный алгоритм?
Изучение комбинаторной структуры задачи.
Изучение свойств оптимального решения.
Поиск алгоритмической техники, которая использует эти свойства.
Обобщение и расширение техники и опыта, накопленного при построении полиномиальных алгоритмов.
6 Полиномиально разрешимые задачи
Существует ряд классических задач комбинаторной оптимизации, для которых известны эффективные точные алгоритмы с полиномиальным временем работы. Ниже приведены наиболее известные примеры.
6.1 Минимальное остовное дерево
Задача об остовном дереве минимального веса (minimum spanning tree, MST). Остовное дерево для связного графа \(G = (V,E)\) — это дерево, содержащее все вершины графа. Веса присваиваются рёбрам, и требуется найти остовное дерево минимального суммарного веса.
Для этой задачи существуют классические полиномиальные алгоритмы: алгоритм Краскала, алгоритм Прима, а также более быстрые алгоритмы на основе современных структур данных.
6.2 Кратчайшие пути
Одна из фундаментальных задач — поиск кратчайших путей в графе.
Из одной вершины (одноисточниковая задача): алгоритм Дейкстры (для неотрицательных весов), алгоритм Беллмана–Форда (работает и при отрицательных рёбрах).
Между всеми парами вершин: алгоритм Флойда–Уоршелла и алгоритм Джонсона.
Все эти задачи решаются за полиномиальное время и широко применяются на практике.
6.3 Максимальный поток
Задача о максимальном потоке (maximum flow) в транспортной сети. Дана ориентированная сеть \(G = (V,E)\) с пропускными способностями \(c : E \to \mathbb {R}_+\). Требуется найти наибольший поток из источника \(s\) в сток \(t\), удовлетворяющий ограничениям на рёбра и законам сохранения.
Известные алгоритмы: алгоритм Форда–Фалкерсона, алгоритм Эдмондса–Карпа, алгоритм Диница, а также современные модификации. Близкой является задача о минимальном разрезе, эквивалентная задаче о максимальном потоке (теорема Форда–Фалкерсона).
6.4 Минимальная стоимость потока
Обобщение задач о максимальном потоке и назначениях. Дана сеть с пропускными способностями \(c : E \to \mathbb {R}_+\) и стоимостями \(w : E \to \mathbb {R}\). Требуется найти поток заданного объёма минимальной стоимости.
Для этой задачи известны точные полиномиальные алгоритмы, например на основе алгоритмов потенциалов и поиска кратчайших путей.
6.5 Максимальное паросочетание
Подмножество рёбер \(M \subseteq E\) называется паросочетанием, если никакие два ребра из \(M\) не имеют общей вершины.
Максимальное по размеру паросочетание — паросочетание с наибольшим числом рёбер.
Максимальное по включению паросочетание — паросочетание, к которому нельзя добавить ни одно ребро.
Любое максимальное по размеру паросочетание является максимальным по включению, но не наоборот.
Для двудольных графов задача решается венгерским алгоритмом (алгоритмом Куна). Для произвольных графов применяется алгоритм Эдмондса (алгоритм цветка).
6.6 \(k\)-фактор минимального веса
Остовный подграф — подграф, содержащий все вершины исходного графа.
Граф называется \(k\)-регулярным, если степени всех его вершин равны \(k\).
\(k\)-фактор графа \(G\) — это \(k\)-регулярный остовный подграф \(G\). В частности:
\(1\)-фактор — совершенное паросочетание, то есть паросочетание, покрывающее все вершины графа;
\(2\)-фактор — набор циклов, покрывающих все вершины графа.
Для задачи нахождения \(k\)-фактора минимального веса существуют точные полиномиальные алгоритмы, в том числе основанные на редукции к задаче о совершенных паросочетаниях.
Таким образом, хотя многие задачи комбинаторной оптимизации являются \(\operatorname {NP}\)-трудными, существует широкий класс фундаментальных задач, для которых разработаны эффективные полиномиальные алгоритмы. Эти задачи и методы служат строительными блоками для более сложных алгоритмов и приближённых схем.