Деревья Штейнера
Ключевые слова и синонимы
Разработка алгоритма аппроксимации
Определение
Пусть дано множество точек, называемых полюсами, в метрическом пространстве. Задача заключается в нахождении кратчайшего дерева, связывающего все точки. В случае деревьев Штейнера используются три основных метрических пространства: евклидова плоскость, плоскость с прямолинейными расстояниями и сеть с взвешенными ребрами. Задача построения дерева Штейнера в этих метрических пространствах носит название евклидовой задачи Штейнера (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 должна находится в положении [math]\displaystyle{ \angle ASB = \angle BSC = \angle CSA = 120^{\circ} \; }[/math].
Обобщение задачи Ферма можно произвести по двум направлениям:
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 году предположили, что отношение Штейнера на евклидовой плоскости равно [math]\displaystyle{ \sqrt{3/2} \; }[/math] и достигается для трех вершин равностороннего треугольника. Доказательству этой гипотезы было посвящено множество работ, в конечном итоге ее доказали Ду и Хван [7].
Еще одной важной задачей является задача лучшей аппроксимации. Довольно долгое время не удавалось доказать наличие аппроксимации с коэффициентом эффективности меньше обратного значения отношения Штейнера. Первый прорыв совершил Зеликовский [14], который нашел 11/6-аппроксимацию с полиномиальным временем выполнения для задачи NST, что лучше 1/2 – обратного значения отношения Штейнера для сети с взвешенными ребрами. Позднее Берман и Рамайе [2] предложили 92/72-аппроксимацию с полиномиальным временем выполнения для RST, а Ду, Цзян и Фэн [8] закрыли тему, показав, что в любом метрическом пространстве существует аппроксимация с полиномиальным временем выполнения с коэффициентом эффективности меньше обратного значения отношения Штейнера, при условии, что для любого множества с фиксированным количеством точек его дерево Штейнера вычислимо за полиномиальное время.
Все вышеперечисленные аппроксимации были созданы на базе семейства k-ограниченных деревьев Штейнера. В результате улучшения некоторых деталей построения константный коэффициент эффективности удалось понизить, однако при этом улучшения также становятся меньше. В 1996 году Ароре [1] удалось достичь значительного прогресса в решении задач EST и RST. Он доказал существование PTAS для этих двух задач. Таким образом, исследователи-теоретики теперь основное внимание уделяют задаче NST. Берн и Плассман [3] показали, что эта задача является 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-ограниченным минимальным деревом Штейнера. Обозначим его длину за [math]\displaystyle{ smt_k(P) \; }[/math]. Очевидно, что [math]\displaystyle{ smt_2(P) \; }[/math] – длина минимального остовного дерева на P, также обозначаемая как mst(P). Пусть smt(P) обозначает длину минимального дерева Штейнера на P. Если значение [math]\displaystyle{ smt_3(P) \; }[/math] можно вычислить за полиномиальное время, то этот способ лучше подходит для аппроксимации smt(P) по сравнению с mst(P). Однако до сих пор для [math]\displaystyle{ smt_3(P) \; }[/math] не было найдено аппроксимации с полиномиальным временем. Поэтому Зеликовский [14] использовал жадную аппроксимацию [math]\displaystyle{ smt_3(P) \; }[/math] для аппроксимации 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)