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

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

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

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

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

где mst(P : H) – длина минимального остовного дерева, связывающего все несвязанные полюса в P после того, как каждое ребро H будет стянуто в точку.

выбрать 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).

Доказательство. Предположим, 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) выполняется для любых 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.

Случай 1. ex g Px \ Py и ey 26 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. □

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

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