Деревья Штейнера: различия между версиями

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

Пусть дано множество точек, называемых полюсами, в метрическом пространстве. Задача заключается в нахождении кратчайшего дерева, связывающего все точки. В случае деревьев Штейнера используются три основных метрических пространства: евклидова плоскость, плоскость с прямолинейными расстояниями и сеть с взвешенными ребрами. Задача построения дерева Штейнера в этих метрических пространствах носит название [[Евклидова задача Штейнера|евклидовой задачи Штейнера]] (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>\angle ASB = \angle BSC = \angle CSA = 120^{\circ} \;</math>.

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 году предположили, что отношение Штейнера на евклидовой плоскости равно <math>\sqrt{3/2} \;</math> и достигается для трех вершин равностороннего треугольника. Доказательству этой гипотезы было посвящено множество работ, в конечном итоге ее доказали Ду и Хван [7].

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

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

 

В дереве Штейнера полюс может иметь степень больше единицы. Можно провести декомпозицию дерева Штейнера, разбив все вершины со степенью больше 1 на меньшие деревья, в которых каждый полюс является листом. В такой декомпозиции каждое полученное маленькое дерево называется [[полный компонент|полным компонентом]]. Размер полного компонента равен количеству содержащихся в нем полюсов. Дерево Штейнера является k-ограниченным, если каждый его полный компонент имеет размер не более k. Кратчайшее k-ограниченное дерево Штейнера также называется k-ограниченным [[минимальное дерево Штейнера|минимальным деревом Штейнера]]. Обозначим его длину за <math>smt_k(P) \;</math>. Очевидно, что <math>smt_2(P) \;</math> – длина минимального остовного дерева на P, также обозначаемая как mst(P). Пусть smt(P) обозначает длину минимального дерева Штейнера на P. Если значение <math>smt_3(P) \;</math> можно вычислить за полиномиальное время, то этот способ лучше подходит для аппроксимации smt(P) по сравнению с mst(P). Однако до сих пор для <math>smt_3(P) \;</math> не было найдено аппроксимации с полиномиальным временем. Поэтому Зеликовский [14] использовал жадную аппроксимацию <math>smt_3(P) \;</math> для аппроксимации smt(P). Чанг [4, 5] использовал похожий жадный алгоритм для вычисления итеративного 1-дерева Штейнера. Пусть <math>\mathcal{F} \;</math> – семейство подграфов исходного графа G с взвешенными ребрами. Для любого связного подграфа H обозначим за mst(H) длину минимального остовного дерева H, а за mst(H) – сумму mst(H') для H' по всем связным компонентам H для любого подграфа H.

'''Жадный алгоритм <math>H \gets \empty \;</math>;'''

 

'''while''' в P остаются не связанные с H элементы '''do'''

 

выбрать <math>F \in \mathcal{F} \;</math> так, чтобы максимизировать gain(H <math>\cup \;</math> F);

 

выдать результат mst(H).

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

'''Лемма 1.''' Функция f является субмодулярной в том и только том случае, если для любых <math>A \subset E \;</math> и различных <math>x, y \in E - A \;</math> выполняется

Доказательство. Предположим, что f является субмодулярной. Положим <math>B = A \cup \{ x \} \;</math> и <math>C = A \cup \{ y \} \;</math>. Тогда <math>B \cup C = A \cup A \cup \{ x, y \} \;</math> и <math>В \cap C = A \;</math>. Следовательно, должно иметь место

<math>f(A \cup B) - f(A) - f(B) + f(A \cap B) = \sum^k_{i = 1} \sum^h_{j = 1} \Delta_{x_i} \Delta_{y_j} f(A \cup \{ x_1, ..., x_{i - 1} \} \cup \{ y_1, ..., y_{j - 1} \}) \le 0</math>,

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

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)

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

Доказательство. Заметим, что для любых 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.