Задача Штейнера о минимальном дереве

Задача Штейнера о минимальном дереве
Названо в честь	Якоб Штейнер
Вычислительная сложность	NP-полная задача
Медиафайлы на Викискладе

Минимальное дерево Штейнера для точек A, B и C, где S — точка Ферма треугольника ABC.

Зада́ча Ште́йнера о минима́льном де́реве состоит в поиске кратчайшей сети, соединяющей заданный конечный набор точек плоскости. Задача получила своё название в честь Якоба Штейнера (1796—1863).

Альтернативное условие задачи заключается в поиске минимального подграфа, соединяющего конечное число заданных вершин (терминалов) и образующего таким образом сеть кратчайших путей между этими вершинами.

Задача является вариацией задачи поиска минимального остовного дерева.

История

История этой задачи восходит ко времени Пьера Ферма (1601—1665), который, после изложения своего метода исследования минимумов и максимумов, написал:

Qui hanc methodum non probaverit, ei proponitur: Datis tribus punctis, quartum reperire, a quo si ducantur tres rectae ad data puncta, summa trium harum rectarum sit minima quantitas.

Тот же, кто этот метод не оценил, пусть он решит [следующую задачу]: для заданных трех точек найти такую четвертую, что если из неё провести три отрезка в данные точки, то сумма этих трех отрезков даст наименьшую величину.

Эта задача была частично решена Э. Торричелли (1608—1647) и Б. Кавальери (1598—1647), учениками Б. Кастелли (1577—1644), затем найденная ими конструкция была модифицирована Т. Симпсоном (1710—1761) и окончательно уточнена Ф. Хейненом и Ж. Бертраном (1822—1900). В результате было получено геометрическое построение точки S, ныне называемой точкой Ферма (иногда точкой Торричелли), которая для трёх заданных точек A, B и C даёт минимально возможную сумму длин отрезков AS, BS, CS.

В 1934 году В. Ярник и O. Кесслер сформулировали обобщение задачи Ферма, заменив три точки на произвольное конечное число. А именно, их задача состоит в описании связных плоских графов наименьшей длины, проходящих через данное конечное множество точек плоскости.

В 1941 году вышла популярная книжка «Что такое математика?» Р. Куранта и Г. Роббинса, в которой авторы писали следующее:

Очень простая и вместе с тем поучительная проблема была изучена в начале прошлого столетия знаменитым берлинским геометром Якобом Штейнером. Требуется соединить три деревни $A$, $B$, $C$ системой дорог таким образом, чтобы их общая протяженность была минимальной.
Было бы естественно обобщить эту проблему на случай $n$ заданных точек $A_{1},A_{2},\ldots ,A_{n}$ следующим образом: требуется найти в плоскости такую точку $P$, чтобы сумма расстояний $a_{1}+a_{2}+\ldots +a_{n}$ (где $a_{i}$ обозначает расстояние $PA_{i}$) обращалась в минимум. … Эта обобщенная проблема, также изученная Штейнером, не ведет к интересным результатам. В данном случае мы имеем дело с поверхностным обобщением, подобных которому немало встречается в математической литературе. Чтобы получить действительно достойное внимания обобщение проблемы Штейнера, приходится отказаться от поисков одной-единственной точки $P$. Вместо того поставим задачей построить «уличную сеть» или «сеть дорог между данными деревнями», обладающую минимальной общей длиной.

Эта книга завоевала заслуженную популярность, в результате чего и задачу Ферма, и задачу Ярника—Кесслера сейчас принято называть проблемой Штейнера.

Алгоритм решения

Эффективного (сложность выражается функцией, ограниченной сверху некоторым полиномом от параметра задачи, в данном случае число вершин графа) алгоритма, дающего точное решение проблемы Штейнера, не существует при условии неравенства классов P и NP, так как проблема является NP-полной. Доказать это несложно через редукцию к задаче о вершинном покрытии.

Несмотря на ограничения, задачу можно решить приближенно, что и делает алгоритм Коу, Марковского и Бергмана. Идея такого подхода заключается в том, что нижняя граница стоимости соединения двух вершин (терминалов) - кратчайший путь между ними, а множество путей минимальной стоимости, соединяющих все терминалы дает 2-аппроксимированное решение, как будет доказано далее. Таким образом алгоритм будет выглядеть следующим образом:

1. Даны граф $G=(V,E)$, множество терминалов $T\subset V$ и функция стоимости $c\colon E\to \mathbb {Q}$.
2. Найди клику $G_{D}=(T,F)$ и $c\colon F\to \mathbb {Q}$ такую, что $c_{D}(\{a,b\})=\operatorname {dist} _{G}(a,b)$.
3. Найди минимальное остовное дерево $S_{D}=(T,F')$ графа $G_{D}$.
4. Для каждого ребра $e\in F'$ определи $W_{e}=(V_{e},F_{e})$ как путь длины $c_{D}(e)$ в графе $G$.
5. Вычисли подграф $H=(\bigcup _{e\in F'}V_{e},\bigcup _{e\in F'}F_{e})$.
6. Найди минимальное оставное дерево $S_{H}$ подграфа $H$.
7. Удали из $S_{H}$ листья, не содержащиеся в $T$.
8. Выведи результат.

Доказательство фактора аппроксимации сводится к оценке результата алгоритма и точного решения: $c(S_{D})\leqslant 2\cdot c(S^{*})$. Если удвоить все рёбра оптимального решения, мы получим цикл $Z$, содержащий все вершины $T$. $Z$ же определяет остовное дерево $T_{Z}$ на графе $G_{D}$, состоящее только из терминальных вершин. Таким образом $c(S_{D})\leqslant c(T_{Z})\leqslant c(Z)=2\cdot c(S^{*})$. В качестве алгоритма поиска минимальных остовных деревьев можно использовать эффективный алгоритм Краскала.

Однако такая оценка аппроксимации не является пределом и возможно улучшить алгоритм, достигнув оценки $11/6$.

Основные определения

Приведем несколько современных формулировок проблемы Штейнера. В качестве объемлющего пространства вместо евклидовой плоскости рассмотрим произвольное метрическое пространство.

Минимальные деревья Штейнера

Пусть $(X,\rho )$ — метрическое пространство и $G=(V,E)$ — граф на X, то есть, $V\subset X$. Для каждого такого графа определены длины его рёбер $e=\{u,v\}\in E$ как расстояния $\rho (u,v)$ между их вершинами, а также длина $\rho (G)$ самого графа $G$ как сумма длин всех его рёбер.

Если $M$ — конечное подмножество $X$, а $G=(V,E)$ — связный граф на $X$, для которого $M\subset V$, то $G$ называется графом, соединяющим $M$. При этом граф $G$, соединяющий $M$, минимально возможной длины $\rho (G)$ является деревом, которое называется минимальным деревом Штейнера на $M$. Именно изучению таких деревьев и посвящена одна из версий проблемы Штейнера.

Отметим, что минимальные деревья Штейнера существуют не всегда. Тем не менее, точная нижняя грань величин $\rho (G)$ по всем связным графам, соединяющим $M$, всегда существует, называется длиной минимального дерева Штейнера на $M$ и обозначается через $\operatorname {smt} (M)$.

Примеры

Если $(X,\rho )$ — стандартная евклидова плоскость, то есть расстояние $\rho$ порождается нормой $\|(x,y)\|={\sqrt {x^{2}+y^{2}}}$, то получаем классическую проблему Штейнера, сформулированную Ярником и Кесслером (см. выше).

Если $(X,\rho )$ — манхэттенская плоскость, то есть расстояние $\rho$ порождается нормой $\|(x,y)\|=|x|+|y|$, то получает прямоугольную проблему Штейнера, одним из приложений которой является проектирование разводок микросхем. Более современные разводки моделируются метрикой, порожденной λ-нормой (единичный круг — правильный 2λ-угольник; в этих терминах манхеттенская норма является 2-нормой).

Если в качестве $X$ берётся сфера (приблизительно моделирующая поверхность Земли), а за $\rho (a,b)$ — длина кратчайшей из двух дуг большой окружности, высекаемой из сферы $X$ плоскостью, проходящей через $a$, $b$ и центр сферы, то получается разновидность транспортной задачи: требуется соединить заданный набор пунктов (городов, предприятий, абонентов и т. д.) кратчайшей коммуникационной сетью (дорог, трубопроводов, телефонных линий и т. д.), минимизировав затраты на строительство (предполагается, что затраты пропорциональны длине сети).

Если в качестве $X$ берётся множество всех слов над некоторым алфавитом, а в качестве $\rho (a,b)$ — расстояние Левенштейна, то получается вариант проблемы Штейнера, который широко используется в биоинформатике, в частности, для построения эволюционного дерева.

Если в качестве $X$ берётся множество вершин $V$ связного графа $G=(V,E)$, а в качестве $\rho$ — функция расстояния, порожденная некоторой весовой функцией $\omega \colon E\to \mathbb {R}$, то получается проблема Штейнера в графах. Частным случаем этой проблемы (когда заданное множество совпадает с множеством всех вершин, $M=X$) является задача построения минимального остовного дерева.

Минимальные параметрические сети

Пусть $\partial G$ — некоторое подмножество множества $V$ вершин графа $G=(V,E)$, содержащее все вершины степени 1 и 2. Пара $(G,\partial G)$ называется графом с границей $\partial G$. Если $G$ — связный граф, и $\varphi \colon \partial G\to X$ — некоторое отображение в метрическое пространство $(X,\rho )$, то каждое отображение $\Gamma \colon G\to X$, ограничение которого на $\partial G$ совпадает с $\varphi$, называется сетью типа $(G,\partial G)$ с границей $\varphi$ в метрическом пространстве $(X,\rho )$. Ограничение сети $\Gamma$ на вершины и ребра графа $G$ называются соответственно вершинами и ребрами этой сети. Длиной ребра $\Gamma \colon \{u,v\}\to X$ сети $\Gamma$ называется величина $\rho {\bigl (}\Gamma (u),\Gamma (v){\bigr )}$, а длиной $\rho (\Gamma )$ сети $\Gamma$ — сумма длин всех её ребер.

Обозначим через $[G,\varphi ]$ множество всех сетей типа $(G,\partial G)$ с границей $\varphi$. Сеть из $[G,\varphi ]$, имеющая наименьшую возможную длину, называется минимальной параметрической сетью типа $(G,\partial G)$ с границей $\varphi$.

Отметим, что, как и в случае минимальных деревьев Штейнера, минимальная параметрическая сеть существует не всегда. Тем не менее, точная нижняя грань величин $\rho (G)$ по всем сетям из $[G,\varphi ]$, всегда существует, называется длиной минимальной параметрической сети и обозначается через $\operatorname {mpn} [G,\varphi ]$.

Если $M$ — конечное подмножество $X$, а $\varphi$ отображает $\partial G$ на все $M$, то есть $\operatorname {im} (\varphi )=M$, то говорят, что сеть $\Gamma \in [G,\varphi ]$ соединяет $M$. Легко видеть, что $\operatorname {smt} (M)=\inf \operatorname {mpn} [G,\varphi ]$ по всем $[G,\varphi ]$, для которых $\operatorname {im} (\varphi )=M$. Таким образом, общая задача Штейнера сводится к изучению минимальных параметрических сетей и выбора из них кратчайших.

Одномерные минимальные заполнения в смысле Громова

Это естественное обобщение проблемы Штейнера было предложено А. О. Ивановым и А. А. Тужилиным. Пусть $M$ — произвольное конечное множество и $G=(V,E)$ — некоторый связный граф. Будем говорить, что $G$ соединяет $M$, если $M\subset V$. Пусть теперь ${\mathcal {M}}=(M,\rho )$ — конечное псевдометрическое пространство (где, в отличие от метрического пространства, расстояния между разными точками могут быть равны нулю), $G=(V,E)$ — связный граф, соединяющий $M$, и $\omega \colon E\to {\mathbb {R} }_{+}$ — некоторое отображение в неотрицательные вещественные числа, называемое обычно весовой функцией и порождающее взвешенный граф ${\mathcal {G}}=(G,\omega )$. Функция $\omega$ задает на $V$ псевдометрику $d_{\omega }$, а именно, расстоянием между вершинами графа ${\mathcal {G}}$ назовем наименьший из весов путей, соединяющих эти вершины. Если для любых точек $p$ и $q$ из $M$ выполняется $\rho (p,q)\leq d_{\omega }(p,q)$, то взвешенный граф ${\mathcal {G}}$ называется заполнением пространства ${\mathcal {M}}$, а граф $G$ — типом этого заполнения. Число $\operatorname {mf} ({\mathcal {M}})$, равное $\inf \omega ({\mathcal {G}})$ по всем заполнениям ${\mathcal {G}}$ пространства ${\mathcal {M}}$, назовем весом минимального заполнения, а заполнение ${\mathcal {G}}$, для которого $\omega ({\mathcal {G}})=\operatorname {mf} ({\mathcal {M}})$, — минимальным заполнением. Основная задача — научиться вычислять $\operatorname {mf} ({\mathcal {M}})$ и описывать минимальные заполнения.

Литература

• А. О. Иванов, А. А. Тужилин. Теория экстремальных сетей. — Москва–Ижевск: Институт компьютерных исследований, 2003. — ISBN 5-93972-292-X.
• А. О. Иванов, А. А. Тужилин. Задача Штейнера на плоскости или плоские минимальные сети // Матем. сб.. — 1991. — Т. 182, № 12. — С. 1813—1844.
• Протасов В. Ю. Максимумы и минимумы в геометрии. — М.: МЦНМО. — 56 с. — (Библиотека «Математическое просвещение», выпуск 31).
• Weisstein, Eric W. Steiner Tree (англ.) на сайте Wolfram MathWorld.