Деревья Штейнера
Ключевые слова и синонимы
Разработка алгоритма аппроксимации
Определение
Пусть дано множество точек, называемых полюсами, в метрическом пространстве. Задача заключается в нахождении кратчайшего дерева, связывающего все точки. В случае деревьев Штейнера используются три основных метрических пространства: евклидова плоскость, плоскость с прямолинейными расстояниями и сеть с взвешенными ребрами. Задачи построения дерева Штейнера в этих метрических пространствах носят названия евклидовой задачи Штейнера (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 должна находиться в положении
Обобщение задачи Ферма можно произвести по двум направлениям:
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. Что более важно, Гаусс предложил новую задачу. По его мнению, интереснее было бы найти кратчайшую сеть, а не точку. Гаусс также предложил несколько возможных вариантов соединений кратчайшей сети для четырех заданных точек.
К сожалению, исследователи деревьев Штейнера на ранней стадии изучения вопроса не были знакомы с письмом Гаусса. Рихард Курант и Герберт Роббинс в своей популярной книге «Что такое математика?» [6], опубликованной в 1941 году, назвали задачу Гаусса деревом Штейнера, так что именно это наименование получило широкое распространение.
Дерево Штейнера стало популярной темой исследований в математике и компьютерных науках в связи с его широким применением в области телекоммуникаций и компьютерных сетей. Начиная с опубликованной в 1968 году работы Гилберта и Поллака, было выпущено множество работ, посвященных различным задачам, связанным с деревьями Штейнера.
Хорошо известной задачей является гипотеза Гилберта-Поллака об отношении Штейнера, представляющем собой минимальное отношение длин между минимальным деревом Штейнера и минимальным остовным деревом для того же множества точек. Гилберт и Поллак в 1968 году предположили, что отношение Штейнера на евклидовой плоскости равно
Еще одной важной задачей является задача лучшей аппроксимации. Довольно долгое время не удавалось доказать наличие аппроксимации с коэффициентом эффективности меньше обратного значения отношения Штейнера. Первый прорыв совершил Зеликовский [14], который нашел 11/6-аппроксимацию с полиномиальным временем выполнения для задачи NST, что лучше 1/2 – обратного значения отношения Штейнера для сети с взвешенными ребрами [прим. переводчика: вероятно, имелось в виду значение 2, а не 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-ограниченным минимальным деревом Штейнера. Обозначим его длину за
Определим gain(H) = mst(P) - mst(P : H) - mst(H), где mst(P : H) – длина минимального остовного дерева, связывающего все несвязанные полюса в P после того, как каждое ребро H будет стянуто в точку.
Жадный алгоритм; while в P остаются не связанные с H элементы do выбрать так, чтобы максимизировать gain(H F); выдать результат mst(H).
Если множество
Рассмотрим базовое множество E и функцию f, областью определения которой являются все подмножества E, а областью значений – вещественные числа. f является субмодулярной, если для любых двух подмножеств A, B множества E выполняется соотношение
Для
Лемма 1. Функция f является субмодулярной в том и только том случае, если для любых
(1)
Доказательство. Предположим, что f является субмодулярной. Положим
это означает, что соотношение (1) верно.
Напротив, предположим, что свойство (1) выполняется для любых
Следовательно, должно иметь место
где
Лемма 2. Определим f(H) = -mst(P : H). Тогда функция f является субмодулярной над множеством ребер E.
Доказательство. Заметим, что для любых двух различных ребер x и y, не принадлежащих подграфу H,
Пусть T – минимальное остовное дерево для несвязанных полюсов после стягивания каждого ребра H в точку. T содержит путь
Значение
Теперь, чтобы показать субмодулярность f, достаточно доказать неравенство
(2)
Случай 1.
Случай 2.
Случай 3.
Случай 4.
Далее поясняется, что субмодулярность gain(
Предположение. Пусть
Доказательство. Заметим, что для любых
Пусть
Рисунок 2.
Применение
Задача построения дерева Штейнера является классической NP-полной проблемой и имеет множество приложений при разработке компьютерных микросхем, междугородних телефонных линий, многоадресной маршрутизации в сетях телекоммуникаций и т.п. Разработано множество эвристик жадного типа для построения деревьев Штейнера. Большинство из них демонстрируют высокую эффективность в компьютерных экспериментах, однако без подкрепления со стороны теоретического анализа. Предложенный подход может стать его основой.
Открытые вопросы
До сих пор неясно, является ли задача построения 3-ограниченного минимального дерева Штейнера NP-полной. Известно, что она является таковой при построении k-ограниченного минимального дерева Штейнера при
См. также
Литература
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)