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

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

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