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

Перейти к навигации Перейти к поиску

Деревья Штейнера (посмотреть исходный код)

Версия от 00:20, 2 июня 2016

360 байт добавлено ,  2 июня 2016
нет описания правки
Нет описания правки
Нет описания правки
Строка 45: Строка 45:


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


== Основные результаты ==
== Основные результаты ==
Строка 50: Строка 51:




В дереве Штейнера полюс может иметь степень больше единицы. Можно провести декомпозицию дерева Штейнера, разбив все вершины со степенью больше 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.  
В дереве Штейнера полюс может иметь степень больше единицы. Можно провести декомпозицию дерева Штейнера, разбив все вершины со степенью больше 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.
Определим
 
gain(H) = mst(P) - mst(P : H) - mst(H) ;
 
где mst(P : H) – длина минимального остовного дерева, связывающего все несвязанные полюса в P после того, как каждое ребро H будет стянуто в точку.
Определим gain(H) = mst(P) - mst(P : H) - mst(H), где mst(P : H) – длина минимального остовного дерева, связывающего все несвязанные полюса в P после того, как каждое ребро 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, но не является субмодулярной над всеми трехлучевыми звездами и всеми ребрами.




Жадный алгоритм H:
Рассмотрим базовое множество E и функцию f, областью определения которой являются все подмножества E, а областью значений – вещественные числа. f является [[субмодулярная функция|субмодулярной]], если для любых двух подмножеств A, B множества E выполняется соотношение
while в P остаются не связанные с H элементы do
выбрать F 2 F так, чтобы максимизировать gain(H [ F); выдать результат mst(H).




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




Рассмотрим базовое множество E и функцию f, областью определения которой являются все подмножества E, а областью значений – вещественные числа. f является субмодулярной, если для любых двух подмножеств A, B of E выполняется соотношение
Для <math>x \in E \;</math> и <math>A \subseteq E \;</math> обозначим <math>\Delta_x f(A) = f(A \cup \{ x \}) - f(A) \;</math>.
ДА)+ДВ)>ДАиВ)+ДАПВ).
Для x 2 E и A С E обозначим Axf(A) = f(AU{x})-f(A).




Irina
4551

правка

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/11557

Навигация