Деревья Штейнера

Ключевые слова и синонимы

Разработка алгоритма аппроксимации

Определение

Пусть дано множество точек, называемых полюсами, в метрическом пространстве. Задача заключается в нахождении кратчайшего дерева, связывающего все точки. В случае деревьев Штейнера используются три основных метрических пространства: евклидова плоскость, плоскость с прямолинейными расстояниями и сеть с взвешенными ребрами. Задача построения дерева Штейнера в этих метрических пространствах носит название евклидовой задачи Штейнера (Euclidean Steiner Tree, EST), прямолинейного дерева Штейнера (Rectilinear Steiner Tree, RST) и сетевого дерева Штейнера (Network Steiner Tree, NST), соответственно. Было обнаружено, что для EST и RST имеются схемы аппроксимации с полиномиальным временем выполнения (PTAS) при помощи адаптивного разбиения. Однако для NST существует положительное число r, такое, что вычисление r-аппроксимации является NP-полной задачей. До настоящего момента лучший коэффициент эффективности для аппроксимации NST с полиномиальным временем выполнения был получен при помощи k-ограниченных деревьев Штейнера. Однако на практике очень часто используется итеративное 1-дерево Штейнера. Фактически итеративное 1-дерево Штейнера уже давно предлагалось в качестве кандидата на хорошую аппроксимацию минимальных деревьев Штейнера. Оно отлично проявило себя в компьютерных экспериментах, однако не было проведено корректного анализа, который показал бы, что коэффициент эффективности итеративного 1-дерева Штейнера превосходит коэффициент эффективности минимального остовного дерева. Недавно такую работу проделали Ду и коллеги [9]. Небольшое различие в построении 3-ограниченного дерева Штейнера и итеративного 1-дерева Штейнера приводит к значительному различию при анализе этих двух типов деревьев. В чем заключается сложность такого анализа? Это будет описано ниже.

История и предпосылки

Задача построения дерева Штейнера была предложена Карлом Фридрихом Гауссом в 1835 году в виде обобщения задачи Ферма. Пусть даны три точки A, B и C на евклидовой плоскости. Ферма изучал задачу нахождения точки S, для которой |SA| + |SB| + |SC| будет минимально. Он обнаружил, что в случае, когда все три внутренних угла треугольника ABC имеют величину менее 120°, оптимальная точка S должна находится в положении ZASB = ZBSC = ZCSA = 120°.

Обобщение задачи Ферма можно произвести по двум направлениям:

1. Пусть имеется n точек на евклидовой плоскости. Найти точку S с минимальным суммарным расстоянием от S до заданных n точек. Эта задача также называется задачей Ферма.

2. Пусть имеется n точек на евклидовой плоскости. Найти кратчайшую сеть, соединяющую все точки.

Гаусс решил вторую обобщенную задачу в переписке с Шумахером. 19 марта 1836 Генрих Христиан Шумахер в письме Гауссу упомянул парадокс, связанный с задачей Ферма. Рассмотрим выпуклый четырехугольник ABCD. Известно, что решение задачи Ферма для четырех точек A, B, C, D представляет собой пересечение E диагоналей AC и BD. Предположим, что продолжение отрезков DA и CB дает точку пересечения F. Переместим A и B в F. Тогда E также будет перемещена в F. Однако в случае, если величина угла при F меньше 120°, точка F не может быть решением задачи Ферма для исходных точек F, D и C. В чем же дело? (См. рис. 1).

Деревья Штейнера, рис. 1

21 марта 1836 в ответном письме Гаусс поясняет Шумахеру, что ошибка в парадоксе Ферма возникает в тот момент, когда задача Ферма для четырех точек A, B, C, D заменяется на задачу для трех точек F, C, D. Когда A и B оказываются идентичными F, суммарное расстояние от E до четырех точек A, B, C и D равняется 2|EF| + |EC| + |ED|, а не |EF| + |EC| + |ED|. Следовательно, точка E не может быть решением задачи Ферма для F, C и D. Что более важно, Гаусс предложил новую задачу. По его мнению, интереснее было бы найти кратчайшую сеть, а не точку. Гаусс также предложил несколько возможных вариантов соединений кратчайшей сети для четырех заданных точек.

К сожалению, исследователи деревьев Штейнера на ранней стадии изучения вопроса не были знакомы с письмом Гаусса. Рихард Курант и Герберт Роббинс в своей популярной книге «Что такое математика?» , опубликованной в 1941 году, назвали задачу Гаусса деревом Штейнера, так что именно это наименование получило широкое распространение.

Дерево Штейнера стало популярной темой исследований в математике и компьютерных науках в связи с его широким применением в области телекоммуникаций и компьютерных сетей. Начиная с опубликованной в 1968 году работы Гилберта и Поллака, было выпущено множество работ, посвященных различным задачам, связанным с деревьями Штейнера.

Хорошо известной задачей является гипотеза Гилберта-Поллака об отношении Штейнера, представляющем собой минимальное отношение длин между минимальным деревом Штейнера и минимальным остовным деревом для того же множества точек. Гилберт и Поллак в 1968 году предположили, что отношение Штейнера на евклидовой плоскости равно p3/2 и достигается для трех вершин равностороннего треугольника. Доказательству этой гипотезы было посвящено множество работ, в конечном итоге ее доказали Ду и Хван [ ].

Еще одной важной задачей является задача лучшей аппроксимации. Довольно долгое время не удавалось доказать наличие аппроксимации с коэффициентом эффективности меньше обратного значения отношения Штейнера. Первый прорыв совершил Зеликовский [ ], который нашел 11/6-аппроксимацию с полиномиальным временем выполнения для задачи NST, что лучше 1/2 – обратного значения отношения Штейнера для сети с взвешенными ребрами. Позднее Берман и Рамайе [ ] предложили 92/72-аппроксимацию с полиномиальным временем выполнения для RST, а Ду, Цзян и Фэн [8] закрыли тему, показав, что в любом метрическом пространстве существует аппроксимация с полиномиальным временем выполнения с коэффициентом эффективности меньше обратного значения отношения Штейнера, при условии, что для любого множества с фиксированным количеством точек его дерево Штейнера вычислимо за полиномиальное время.

Все вышеперечисленные аппроксимации были созданы на базе семейства k-ограниченных деревьев Штейнера. В результате улучшения некоторых деталей построения константный коэффициент эффективности удалось понизить, однако при этом улучшения также становятся меньше. В 1996 году Ароре [ ] удалось достичь значительного прогресса в решении задач EST и RST. Он доказал существование PTAS для этих двух задач. Таким образом, исследователи-теоретики теперь основное внимание уделяют задаче NST. Берн и Плассман [ ] показали, что эта задача является MaxSNP-полной. Это означает, что существует положительное число r, такое, что вычисление r-аппроксимации для NST является NP-полной задачей. Самый эффективный на данный момент алгоритм построения NST предложили Робин и Зеликовский [12]. Они также дали очень простой анализ хорошо известной эвристики – итеративного 1-дерева Штейнера для псевдодвудольных графов.

Анализ итеративного 1-дерева Штейнера также долго время оставался нерешенной задачей. С тех пор как Чанг [4, 5] в 1972 году предположил, что итеративное 1-дерево Штейнера аппроксимирует минимальное дерево Штейнера, его эффективность в тщательно проведенных компьютерных экспериментах оказалась весьма высокой [10, 13], однако подкреплений со стороны теоретического анализа этому утверждению до сих пор не найдено. Фактически и k-ограниченное дерево Штейнера, и итеративное 1-дерево Штейнера строятся при помощи жадных алгоритмов, но с различными типами гармонических функций. В случае итеративного 1-дерева Штейнера гармоническая функция не является субмодулярной, тогда как в случае k-ограниченного дерева Штейнера она является таковой; свойство, выполняющееся для второго типа деревьев, может оказаться неверным для первого. Оказывается, что субмодулярность гармонической функции исключительно важна для анализа жадных аппроксимаций [11]. Ду и др. [9] дали точный анализ для итеративного 1-дерева Штейнера при помощи обобщенной техники обработки несубмодулярной гармонической функции.

Основные результаты

Рассмотрим входной граф с взвешенными ребрами G = (V, E) для задачи построения NST (сетевого дерева Штейнера). Предположим, что G – полный граф и что веса ребер удовлетворяют неравенству треугольника. В противном случае рассмотрим полный граф на V, в котором каждое ребро (u, v) имеет вес, равный длине кратчайшего пути между u и v в графе G. Пусть дано множество полюсов P; деревом Штейнера является дерево, связывающее все указанные полюса таким образом, что каждый лист является полюсом.

В дереве Штейнера полюс может иметь степень больше единицы. Можно провести декомпозицию дерева Штейнера, разбив все вершины со степенью больше 1 на меньшие деревья, в которых каждый полюс является листом. В такой декомпозиции каждое полученное маленькое дерево называется полным компонентом. Размер полного компонента равен количеству содержащихся в нем полюсов. Дерево Штейнера является k-ограниченным, если каждый его полный компонент имеет размер не более k. Кратчайшее k-ограниченное дерево Штейнера также называется k-ограниченным минимальным деревом Штейнера. Обозначим его длину за smtk(P). Очевидно, что smt2(P) – длина минимального остовного дерева на P, также обозначаемая как mst(P). Пусть smt(P) обозначает длину минимального дерева Штейнера на P. Если значение smt3(P) можно вычислить за полиномиальное время, то этот способ лучше подходит для аппроксимации smt(P) по сравнению с mst(P). Однако до сих пор для smt3(P) не было найдено аппроксимации с полиномиальным временем. Поэтому Зеликовский [14] использовал жадную аппроксимацию smt3 (P) для аппроксимации smt(P). Чанг [4 , 5] использовал похожий жадный алгоритм для вычисления итеративного 1-дерева Штейнера. Пусть F – семейство подграфов исходного графа G с взвешенными ребрами. Для любого связного подграфа H обозначим за mst(H) длину минимального остовного дерева H, а за mst(H) – сумму mst(H0) для H0 по всем связным компонентам H для любого подграфа H. Определим gain(H) = mst(P) - mst(P : H) - mst(H) ; где mst(P : H) – длина минимального остовного дерева, связывающего все несвязанные полюса в P после того, как каждое ребро H будет стянуто в точку.

Жадный алгоритм H: while в P остаются не связанные с H элементы do выбрать F 2 F так, чтобы максимизировать gain(H [ F); выдать результат mst(H).

Если множество F состоит из всех полных компонентов размером не более 3, этот жадный алгоритм дает на выходе 3-ограниченное дерево Штейнера, введенное Зеликовским [ ]. Если F состоит из всех трехлучевых звезд и всех ребер, где трехлучевая звезда представляет собой дерево с 3 листьями и центральной вершиной, то жадный алгоритм дает на выходе итеративное 1-дерево Штейнера. Интересный факт, на которой обратили внимание Ду и коллеги [ ], заключается в том, что функция gain(-) является субмодулярной над всеми полными компонентами размера не более 3, но не является субмодулярной над всеми трехлучевыми звездами и всеми ребрами.

Рассмотрим базовое множество E и функцию f, областью определения которой являются все подмножества E, а областью значений – вещественные числа. f является субмодулярной, если для любых двух подмножеств A, B of E выполняется соотношение ДА)+ДВ)>ДАиВ)+ДАПВ). Для x 2 E и A С E обозначим Axf(A) = f(AU{x})-f(A).

Лемма 1. Функция f является субмодулярной в том и только том случае, если для любых A С E и различных x, y 2 E — A, (1) AxAyf(A)<0.

Доказательство. Предположим, f является субмодулярной. Положим B = A [ fxg и C = A U yg. Тогда B[ C = A[ A[ fx; yg и В \ C = A. Следовательно, должно иметь место f(A [ fx; yg) - f(A [ fxg) - f(A U yg) + f(A) < 0 ; это означает, что соотношение (1) верно.

Напротив, предположим, что свойство (1) выполняется для любых A С E и различных x, y 2 E — A. Рассмотрим два подмножества A, B of E. Если А С B или B С A, тогда тривиально получается f(A) + f(B) > f( U В) + f( П В) :

О Следовательно, должно иметь место A n B ф и В \ А ф 0. Запишем это как A \ В = {xx,... , xk} и В \ A = {yx, :::;yhg. Тогда О

Q f(AUB)-f(A)-f(B) к h

^yjf(   A [fx 1 • • - xi-i i=1 j=1

<o;

_ig = ;  □

где fx 1..: x,_ig = для i = 1 и forj=1.

Лемма 2. Определим f(H) = —mst(P : H). Тогда функция f является субмодулярной над множеством ребер E.

Доказательство. Заметим, что для любых двух различных ребер x и y, не принадлежащих подграфу H, gain(H) = mst(P) - mst(P : + mst(P :HUy)- mst(P : H) = (mst(P : H) - mst(P : H [ x [ y)) - (mst(P : H) - mst(P :H[x)) + (mst(P : H) - mst(P :H[y)):

Пусть T – минимальное остовное дерево для несвязанных полюсов после стягивания каждого ребра H в точку. T содержит путь Px, соединяющий две конечные точки x, и путь Py, соединяющий две конечные точки y. Пусть ex (ey) – самое длинное ребро пути Px (Py). Тогда mst(P : H) - mst(P :H[x)= length(ex) ; mst(P : H) - mst(P : H [ y) = length(ey) : mst(P : H) — mst(P : H [ x [ y) можно вычислить следующим образом: выберем самое длинное ребро e0 из Px [ Py. Заметим, что TUxUy-e' содержит уникальный цикл Q. Выберем самое длинное ребро e00 из (Px [ Py) \ Q. Тогда mst(P : H)-mst(P : H[x[y) = length(e0)+length(e00): Теперь, чтобы показать субмодулярность f, достаточно доказать неравенство length(ex)+length(ey) > length(e0) + length(e00): (2)

Случай 1. ex g Px \ Py и ey 26 Px \ Py. Без потери общности будем считать, что length(ex) > length(ey). Тогда можно выбрать e0 = ex таким образом, что (Px [ Py) \ Q = Py. Следовательно, можно выбрать e00 = ey. Таким образом, выполняется равенство для (2).

Деревья Штейнера, рис. 2

Случай 2. ex g Px \ Py и ey 2 Px \ Py. Очевидно, что length(ex) > length(ey). Тогда можно выбрать e0 = ex таким образом, что (Px [ Py) \ Q = Py. Следовательно, можно выбрать e00 = ey. Таким образом, выполняется равенство для (2).

Случай 3. ex 2 Px \ Py и ey 2 Px \ Py. Аналогично случаю 2.

Случай 4. ex 2 Px \ Py и е;бР,ПРг. В этом случае length(ex) = length(ey) = length(e0). Таким образом, (2) верно. □

Далее поясняется, что субмодулярность gain(-) имеет место для k-ограниченного дерева Штейнера.

Предположение. Пусть E – множество всех полных компонентов дерева Штейнера. Тогда gain(-) как функция от множества всех подмножеств E является субмодулярной.

Доказательство. Заметим, что для любых H С E и x, y 2 E – H верно AxAymst(H) = 0, где H = [z2Hz. Таким образом, верность предположения следует из леммы 2. □

Пусть F – множество трехлучевых звезд и ребер, выбранных жадным алгоритмом для вычисления итеративного 1-дерева Штейнера. Тогда gain(-) может и не быть субмодулярной на F . Чтобы убедиться в этом, рассмотрим две трехлучевых звезды x и y на рис. 2. Заметим, что gain(x [ y) > gain(x);gain(y) < 0 и gain(;) = 0. Наблюдается gain(x [ y) — gain(x) — gain(y) + gain(;) > 0 :

Применение

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

Открытые вопросы

До сих пор неясно, является ли задача построения 3-ограниченного минимального дерева Штейнера NP-полной. Известно, что она является таковой при построении k-ограниченного минимального дерева Штейнера при k > 4.

См. также

• Алгоритмы жадной аппроксимации
• Минимальные остовные деревья
• Прямолинейное дерево Штейнера

Литература

1. Arora, S.: Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Proc. 37th IEEE Symp. on Foundations of Computer Science, pp. 2-12 (1996)

2. Berman, P., Ramaiyer, V.: Improved approximations for the Steiner tree problem. J. Algorithms 17, 381^08(1994)

3. Bern, M., Plassmann, P.: The Steiner problem with edge lengths 1 and 2. Inf. Proc. Lett. 32,171 -176 (1989)

4. Chang, S.K.: The generation of minimal trees with a Steiner topology. J.ACM 19,699-711 (1972)

5. Chang, S.K.: The design of network configurations with linear or piecewise linear cost functions. In: Symp. on Computer-Communications, Networks, and Teletraffic, pp. 363-369 IEEE Computer Society Press, California (1972)

6. Crourant, R., Robbins, H.: What Is Mathematics? Oxford University Press, New York (1941)

7. Du, D.Z., Hwang, F.K.: The Steiner ratio conjecture of Gilbert-Pollak is true. Proc. Natl. Acad. Sci. USA 87,9464-9466 (1990)

8. Du, D.Z., Zhang, Y., Feng, Q.: On better heuristic for euclidean Steiner minimum trees. In: Proceedings 32nd FOCS, IEEE Computer Society Press, California (1991)

9. Du, D.Z., Graham, R.L., Pardalos, P.M., Wan, P.J., Wu, W., Zhao, W.: Analysis of greedy approximations with nonsubmodular potential functions. In: Proceedings of 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 167-175. ACM, New York (2008)

10. Kahng, A., Robins, G.: A new family of Steiner tree heuristics with good performance: the iterated 1-Steiner approach. In: Proceedings of IEEE Int. Conf. on Computer-Aided Design, Santa Clara, pp.428-431 (1990)

11. Wolsey, L.A.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2, 385-393 (1982)

12. Robin, G., Zelikovsky, A.: Improved Steiner trees approximation in graphs. In: SIAM-ACM Symposium on Discrete Algorithms (SODA), San Francisco, CA, pp. 770-779. January (2000)

13. Smith, J.M., Lee, D.T., Liebman, J.S.: An O(N log N) heuristic for Steiner minimal tree problems in the Euclidean metric. Networks 11, 23-39 (1981)

14. Zelikovsky, A.Z.: The 11/6-approximation algorithm for the Steiner problem on networks. Algorithmica 9,463^70 (1993)