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

История этой задачи восходит ко времени Пьера Ферма (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}})}$ и описывать минимальные заполнения.