Задачи с метрикой

В этой главе представим приближенные алгоритмы для метрической задачи Штейнера и метрической задачи коммивояжера. Причины рассмотрения метрических вариантов этих задач разные. Для задачи Штейнера метрическая задача является ядром общей задачи, и общая задача может быть сведена к метрической. Для задачи коммивояжера без этого ограничения не существует «хороших» приближенных алгоритмов, в предположении, что \(P \neq N P\). Тем не менее, приближенные алгоритмы для этих задач используют общую идею, которая и будет рассмотрена в этой главе.

Задача о кратчайшей суперстроке (глава <<Кратчайшая суперстрока>> в части <<Прочие темы>>) также может быть сведена к задаче коммивояжера со специальной метрикой, и для нее существует 4-приближенный алгоритм.

1 Метрическая задача Штейнера

Задача о дереве Штейнера была поставлена Гауссом в письме Шумахеру. На плоскости задано \(n\) городов, необходимо соединить их ломаными линиями, чтобы каждый город был соединен с каждым и суммарная длина всех проведенных линий была минимальна. Заметим, что в оптимальное решение могут входить промежуточные точки, а все соединения должны быть отрезками, соединяющими точки (исходные или промежуточные). Далее рассмотрим задачу Штейнера на графах.

Задача Штейнера

Граф \(G=(V, E)\), стоимости ребер \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\), подмножество \(R \subseteq V\).

дерево \(T\) наименьшей стоимости, такое, что \(R \subseteq T\), т. е. содержит все вершины из \(R\).

Множество \(R\) называется множеством требований. Множество \(V \backslash R\) называется множеством Штейнера.

Частные случаи задачи Штейнера:

• \(R = V\). В этом случае задача Штейнера – это задача о минимальном остовном дереве (MST);

• \(R = \left\{ v_1, v_2\right\}\). В этом случае задача Штейнера – это задача поиска наименьшего по весу пути из \(v_1\) в \(v_2\).

Метрическая задача Штейнера

• Полный граф \(G=(V, E)\);

• стоимости ребер \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\), такие, что для любых трех вершин \(u, v\) и \(w\) выполнено неравенство: \(\operatorname {cost}(u, v) \leq \operatorname {cost}(u, w)+\operatorname {cost}(w, v)\);

• подмножество \(R \subseteq V\).

дерево \(T\) наименьшей стоимости, такое, что \(R \subseteq T\), т. е. содержит все вершины из \(R\).

MST на требованиях хуже дерева Штейнера

Фиолетовые вершины \(v_1,v_2,v_3\) — требования; оранжевая \(v_4\) — вершина Штейнера. MST на одних требованиях (без \(v_4\)) — допустимое, но не всегда оптимальное решение задачи Штейнера. Наведите курсор на ребро, чтобы увидеть его стоимость.

Теорема 1 Существование \(\rho\)-приближенного алгоритма для метрической задачи Штейнера влечет существование \(\rho\)-приближенного алгоритма для задачи Штейнера.

Mn-proofДоказательство

Пусть \(I\)- пример задачи Штейнера с графом \(G=\) \((V, E)\). По графу \(G\) построим полный граф \(G^{\prime }\) для примера \(I^{\prime }\) метрической задачи Штейнера. Определим стоимость ребра \((u, v)\) в \(G^{\prime }\), как стоимость кратчайшего \(u-v\)-пути в \(G\). Граф \(G^{\prime }\) называется метрическим замыканием графа \(G\). Множество требований и множество Штейнера в обоих примерах совпадают.

Стоимость любого ребра \((u, v) \in E\) в графе \(G^{\prime }\) не превосходит стоимости этого ребра в графе \(G\). Поэтому стоимость оптимального решения примера \(I\) не превосходит стоимости оптимального решения примера \(I^{\prime }\).

Пусть задано дерево Штейнера \(T^{\prime }\) в примере \(I^{\prime }\). Покажем, как за полиномиальное время построить в примере \(I\) дерево Штейнера не большей стоимости. Стоимость ребра \((u, v)\) в графе \(G^{\prime }\) соответствует стоимости пути в графе \(G\). Заменим каждое ребро дерева \(T^{\prime }\) на соответствующий путь для получения подграфа графа \(G\). Очевидно, что в этом подграфе все вершины множества требований соединены. Однако, этот подграф в общем случае может содержать цикл. Если это так, то удалим лишние ребра, чтобы получить дерево \(T\).

Пусть \(C^{\prime }\)- решение, найденное \(\rho\)-приближенным алгоритмом для метрической задачи Штейнера. Способом, описанным выше, найдем решение стоимости \(C\) в задаче Штейнера, такое, что

\[ C \leq C^{\prime } \leq \rho \operatorname {OPT}^{\prime } \leq \rho \operatorname {OPT} \]

Минимальное остовное дерево не всегда является оптимальным решением задачи Штейнера. Однако стоимость минимального остовного дерева является хорошей оценкой на стоимость оптимального дерева Штейнера.

Теорема 2 Пусть \(R \subseteq V\) – множество требований в задаче Штейнера. Тогда стоимость минимального остовного дерева в \(R\) не превосходит двух стоимостей оптимального дерева Штейнера в графе \(G\).

Доказательство оценки 2 для задачи Штейнера

Фиолетовые вершины — требования, оранжевые — вершины Штейнера. Кнопка запускает обход: слева — эйлеров обход удвоенного дерева Штейнера (стоимость \(2\cdot\mathrm{OPT}\)), справа — тот же обход со «срезанными углами», пропускающий вершины Штейнера и повторы.

⟶

(а) Удваиваем рёбра дерева Штейнера — получаем эйлеров граф стоимости \(2\cdot\mathrm{OPT}\). (б) «Срезаем углы», пропуская вершины Штейнера и повторные посещения — получаем гамильтонов цикл на требованиях; по неравенству треугольника его стоимость \(\le 2\cdot\mathrm{OPT}\), а MST на \(R\) не дороже этого цикла: \(\mathrm{cost}(\mathrm{MST}(R))\le 2\cdot\mathrm{OPT}\).

Algorithm 1 Алгоритм Остовное дерево (\(G=(V, E), R, \operatorname {cost}: E \to \mathbb {Q}_+\))

• Найти минимальное остовное дерево \(T\) на множестве вершин \(R\).
• возврат \(T\).

Точный пример к оценке 2 для задачи Штейнера

\(n\) требований на окружности и одна вершина Штейнера в центре. Рёбра к центру стоят \(1\), рёбра между соседними требованиями — \(2\). MST на требованиях (цикл без одного ребра) стоит \(2(n-1)\), дерево Штейнера (звезда) — \(n\); отношение \(\to2\).

\(n=\)6

Можно ли лучше? Да! Самый лучший из известных алгоритмов: \(\rho = \ln (4) + \varepsilon \approx 1.39\).

Также известно, что нельзя придумать алгоритм с \(\rho < \frac{96}{95} \approx 1.0105\) (в предположении \(\operatorname {P} \neq \operatorname {NP}\)).

2 Метрическая задача коммивояжера

2.1 В общем виде задача коммивояжера неаппроксимируема

Задача коммивояжера - одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города ровно по одному разу с последующим возвратом в исходный город.

Задача коммивояжера

Полный граф \(G=(V, E)\), стоимости ребер \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\).

Гамильтонов цикл \(C\) минимальной стоимости.

Цикл, который содержит все вершины, называется гамильтоновым.

Теорема 3 Для любой полиномиально вычислимой функции \(\alpha (n)\), для задачи коммивояжера не существует \(\rho\)-приближенного алгоритма с \(\rho =\alpha (n)\), если \(P \neq N P\).

Mn-proofДоказательство

Докажем от противного. Предположим, что существует \(\rho\)-приближенный алгоритм \(\mathcal{A}\) с \(\rho =\alpha (n)\) для задачи коммивояжера. Покажем, что с помощью полиномиального алгоритма \(\mathcal{A}\) можно решать NP-трудную задачу Гамильтонов цикл. Это будет означать, что \(P=N P\).

Основная идея сведения - построить по графу \(G\) полный взвешенный граф \(G^{\prime }\), такой, что:

• если в \(G\) есть гамильтонов цикл, то стоимость оптимального решения задачи коммивояжера в графе \(G^{\prime }\) равна \(n\), и

• если в \(G\) нет гамильтонова цикла, то оптимальное решение задачи коммивояжера для графа \(G^{\prime }\) имеет стоимость больше, чем \(\alpha (n) \cdot n\).

Заметим, что алгоритм \(\mathcal{A}\) для графа \(G^{\prime }\) должен найти решение стоимости \(\operatorname {cost} \leq \alpha (n) \cdot n\) в первом случае и стоимости \(\operatorname {cost} > \alpha (n) \cdot n\) во втором случае.

По графу \(G\) построим полный взвешенный граф \(G^{\prime }\). Назначим стоимости, равные 1, тем ребрам, которые есть в графе \(G\), и стоимости, равные \(\alpha (n) \cdot n\), тем ребрам, которых нет в графе \(G\). Если в графе \(G\) есть гамильтонов цикл, то соответствующий ему обход в графе \(G^{\prime }\) имеет стоимость \(n\). С другой стороны, если в \(G\) нет гамильтонова цикла, то любой обход в графе \(G^{\prime }\) должен использовать ребро стоимости \(\alpha (n) \cdot n\), а значит, стоимость обхода будет cost \(>\alpha (n) \cdot n\).

Заметим, что в доказательстве такой сильной неаппроксимируемости используются стоимости ребер, которые нарушают неравенство треугольника. Если ограничиться только теми графами, на которых это неравенство выполняется, т. е. метрической задачей коммивояжера, то задача останется NP-трудной, но не будет столь трудна для аппроксимации.

Метрическая задача коммивояжера

Полный граф \(G=(V, E)\), стоимости ребер \(\operatorname {cost}: E \rightarrow \mathbf{Q}^{+}\), такие, что для любых трех вершин \(u, v\) и \(w\) выполняется \[ \operatorname {cost}(u, v) \leq \operatorname {cost}(u, w)+\operatorname {cost}(w, v) \]

Гамильтонов цикл \(C\) минимальной стоимости.

2.2 \(2\)-приближенный алгоритм

Представим простой 2-приближенный алгоритм для метрической задачи коммивояжера. В качестве нижней оценки используем оптимальное решение задачи о минимальном остовном дереве на графе \(G\). Это решение является нижней оценкой для оптимального решения задачи коммивояжера, поскольку при удалении любого ребра из гамильтонова цикла получается остовное дерево в графе \(G\).

Algorithm 2 Алгоритм Двойное остовное дерево (\(G=(V, E), \operatorname {cost} : E \rightarrow \mathbf{Q}^{+}\))

• Найти минимальное остовное дерево \(T\) в графе \(G\).
• Удвоить каждое ребро в дереве \(T\) и получить Эйлеров граф \(H\)
• Найти Эйлеров обход \(R\) в графе \(H\).
• Построить Гамильтонов цикл \(C\), посещая вершины графа \(G\) в том порядке, в котором они встречаются в \(R\).
• возврат \(C\).

Заметим, что выполнение шага 4 аналогично методу срезания углов из теоремы выше.

Алгоритм «Двойное остовное дерево» для метрической задачи коммивояжёра

1) строим MST; 2) удваиваем его рёбра — получаем эйлеров граф — и обходим его; 3) «срезаем углы», пропуская уже посещённые вершины, — получаем гамильтонов цикл стоимости \(\le 2\cdot\mathrm{MST}\le 2\cdot\mathrm{OPT}\). На шагах 3 и 4 обход прорисовывается анимацией.

Теорема 4 Алгоритм Двойное остовное дерево является \(2\)-приближенным алгоритмом для метрической задачи коммивояжера.

Mn-proofДоказательство

Как было замечено выше, \(\operatorname {cost}(T) \leq \operatorname {OPT}\). Поскольку граф \(H\) содержит каждое ребро из дерева \(T\) дважды, то \(\operatorname {cost}(R)=2 \cdot \operatorname {cost}(T)\). Тогда из неравенства треугольника после процедуры срезания углов получим \(\operatorname {cost}(C) \leq \operatorname {cost}(R)\) и \(\operatorname {cost}(C) \leq 2 \cdot \operatorname {OPT}\).

Точность оценки 2 для алгоритма «Двойное остовное дерево»

Полный граф на \(n\) вершинах (здесь \(n=6\)) с рёбрами стоимости \(1\) и \(2\): толстые рёбра стоимости \(1\) образуют звезду \(K_{1,n-1}\) и цикл на остальных \(n-1\) вершинах. Наведите курсор на ребро, чтобы увидеть его стоимость; кнопка справа прокладывает неудачный обход.

(а) Оптимальный обход коммивояжёра стоимости \(n=6\): цикл по дешёвым рёбрам (центр \(\to\) внешняя вершина \(\to\) по циклу \(\to\) центр). (б) Если алгоритм найдёт MST в виде звезды с центром в \(1\), а эйлеров обход посетит вершины в порядке \(5,3,2,1,4,6\), то после срезания углов цикл содержит \(n-2\) рёбер стоимости \(2\) — стоимость \(2n-2\), при \(n\to\infty\) вдвое больше оптимума.

2.3 \(1.5\)-приближенный алгоритм

Алгоритм Двойное остовное дерево сначала находит недорогой Эйлеров обход из остовного дерева графа \(G\), а затем из него делает обход коммивояжера методом срезания углов. Существует ли Эйлеров обход, отличный от найденного с помощью двойного остовного дерева? Напомним, что граф имеет Эйлеров обход тогда и только тогда, когда степень каждой его вершины четна. Пусть множество \(V^{\prime }\) содержит все вершины, которые имеют нечетную степень в остовном дереве. Тогда количество таких вершин \(\left|V^{\prime }\right|\) должно быть четно, поскольку сумма степеней всех вершин в любом графе четна. Если мы добавим к минимальному остовному дереву минимальное совершенное паросочетание для множества \(V^{\prime }\), то степень каждой вершины будет четна, и мы получим Эйлеров граф. Напомним, что задача нахождения совершенного паросочетания минимальной стоимости разрешима за полиномиальное время.

Algorithm 3 Алгоритм Кристофидеса-Сердюкова (\(G=(V, E), \operatorname {cost} : E \rightarrow \mathbf{Q}^{+}\))

• Найти минимальное остовное дерево \(T\) в графе \(G\).
• Найти паросочетание минимальной стоимости \(M\) на множестве вершин в \(T\) с нечетными степенями.
• Добавить ребра \(M\) к \(T\) и получить Эйлеров граф \(H\).
• Найти Эйлеров обход \(R\) в графе \(H\).
• Построить Гамильтонов цикл \(C\), посещая вершины графа \(G\) в том порядке, в котором они встречаются в \(R\).
• возврат \(C\).

Алгоритм Кристофидеса–Сердюкова

Тот же граф \(v_1,\ldots,v_9\), что и в алгоритме «Двойное остовное дерево». Вместо удвоения всего дерева добавляем лишь минимальное совершенное паросочетание на вершинах нечётной степени — обход дешевле: \(\le\frac32\cdot\mathrm{OPT}\). Наведите курсор на вершину, чтобы увидеть её степень.

Для оценки точности этого алгоритма приведем новую нижнюю оценку на стоимость оптимального решения в задаче коммивояжера.

Лемма 1 Пусть \(V^{\prime } \subseteq V\), такое, что \(\left|V^{\prime }\right|\) четно, и пусть \(M-\) минимальное по стоимости совершенное паросочетание для \(V^{\prime }\). Тогда \(\operatorname {cost}(M) \leq \operatorname {OPT} / 2\).

Mn-proofДоказательство

Рассмотрим оптимальный цикл \(\tau\) в задаче коммивояжера на графе \(G\). Пусть цикл \(\tau^{\prime }\) получается из \(\tau\) на множестве вершин \(V^{\prime }\) методом срезания углов. Из неравенства треугольника имеем, что \(\operatorname {cost}\left(\tau^{\prime }\right) \leq \operatorname {cost}(\tau )\). Но \(\tau^{\prime }\) является объединением двух совершенных паросочетаний на \(V^{\prime }\), составленных из чередующихся ребер цикла \(\tau^{\prime }\). Таким образом, наименьшее из двух паросочетаний имеет стоимость не более \(\operatorname {cost}\left(\tau^{\prime }\right) / 2 \leq \operatorname {OPT} / 2\). Следовательно, оптимальное паросочетание также имеет стоимость не более \(\operatorname {OPT} / 2\).

Теорема 5 Алгоритм Кристофидеса-Сердюкова является \(\frac{3}{2}\)-приближенным алгоритмом для метрической задачи коммивояжера.

Mn-proofДоказательство

Оценим стоимость Эйлерова обхода \(R\) \[ \operatorname {cost}(R) \leq \operatorname {cost}(T)+\operatorname {cost}(M) \leq \operatorname {OPT}+\frac{1}{2} \operatorname {OPT}=\frac{3}{2} \operatorname {OPT} \] Используя неравенство треугольника, получим \(\operatorname {cost}(C) \leq \operatorname {cost}(R)\). Теорема доказана.

Точность оценки \(3/2\) для алгоритма Кристофидеса–Сердюкова

Зигзагообразная цепочка из \(m=\lceil n/2\rceil\) треугольников, все показанные рёбра стоимости \(1\). Жирные рёбра — MST \(T\) (путь-зигзаг): у него ровно две вершины нечётной степени — концы, и паросочетание на них — одно ребро между концами, стоимость которого (по метрике кратчайших путей) равна \(\lceil n/2\rceil\). Кнопка прокладывает обход алгоритма.

\(m=\lceil n/2\rceil=\)4

Можно ли подобрать алгоритм с лучшей точностью? Да! В 2020 году был получен алгоритм с точностью \(\alpha < 1.5 - 10^{-36}\). Улучшение, как видно, не очень существенно. Поиски лучших приближенных алгоритмов с гарантированной оценкой точности для метрической задачи коммивояжера продолжаются. Многие ученые считают, что должен существовать \(\frac{4}{3}\)-приближенный алгоритм.

Метрическая задача коммивояжера не может быть аппроксимирована с коэффициентом меньше \(\frac{123}{122} \approx 1.008\) (в предположении \(\operatorname {P} \neq \operatorname {NP}\)).

Для евклидовой задачи коммивояжера (случай, когда вершины графа – это точки в \(\mathbb {R}^{n}\), а стоимость ребра равна евклидовой метрике) существует приближенный алгоритм с коэффициентом \((1+\varepsilon )\) для любого \(\varepsilon > 0\). Т.е. существует полиномиальная приближенная схема. Однако она не вполне полиномиальная, зависимость от \(\frac{1}{\varepsilon }\) не полиномиальная.

3 Задачи

ProblemЗадача 1

Трудность задачи Штейнера состоит в поиске оптимального подмножества вершин Штейнера, которые необходимо включить в дерево. Показать, что если это множество известно, то задача Штейнера решается за полиномиальное время.

ProblemЗадача 2

Найти в полном графе на рис. ниже приближенное решение задачи коммивояжера, используя Алгоритм Двойное остовное дерево и Алгоритм Кристофидеса-Сердюкова.

Задача коммивояжёра: индивидуальная задача

Полный граф на 7 вершинах \(A,\ldots,G\); стоимости рёбер \((A,E)\), \((B,F)\), \((C,G)\) равны \(19\). Наведите курсор на вершину, чтобы подсветить все её рёбра, или на середину ребра — чтобы увидеть его стоимость. Найти приближённые решения задачи коммивояжёра.

ProblemЗадача 3

Рассмотрим вариант метрической задачи коммивояжера, в котором необходимо найти простой путь, содержащий все вершины графа. В зависимости от числа заданных концов пути (0,1 или 2) возникает три задачи.

1. Построить \(3/2\)-приближенный алгоритм для случая, если задана только одна конечная точка или ни одной.

2. Построить \(5/3\)-приближенный алгоритм для случая, если заданы обе конечные точки.

ProblemЗадача 4

Рассмотрим следующий алгоритм решения метрической задачи коммивояжера. Сначала найдем два самых близких города, обозначим их \(i\) и \(j\). Построим цикл \(S\), проходящий через них: \(i \rightarrow j \rightarrow i\). На каждой следующей итерации найдем пару городов \(i \in S\) и \(j \notin S\) с минимальным расстоянием \(c_{i j}\). Добавим город \(j\) в цикл \(S\) сразу после города \(i\). Доказать, что этот алгоритм является \(2\)-приближенным.