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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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