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

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

Пусть дано множество точек, называемых полюсами, в метрическом пространстве. Задача заключается в нахождении кратчайшего дерева, связывающего все точки. В случае деревьев Штейнера используются три основных метрических пространства: евклидова плоскость, плоскость с прямолинейными расстояниями и сеть с взвешенными ребрами. Задача построения дерева Штейнера в этих метрических пространствах носит название [[Евклидова задача Штейнера|евклидовой задачи Штейнера]] (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-дерева Штейнера. Пусть 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 будет стянуто в точку.

ДА)+ДВ)>ДАиВ)+ДАПВ).

Для 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.

Напротив, предположим, что свойство (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. Тогда

f(AUB)-f(A)-f(B)

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

<o;

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

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

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

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

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

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

Пусть 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.