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

Пусть даны точки на плоскости. Минимальное дерево Штейнера (SMT) соединяет эти точки при помощи дополнительных точек, называемых точками Штейнера, так, чтобы общая сумма расстояний между ними была минимальной. Если в качестве расстояния между двумя точками берется расстояние по прямой, такое дерево называется прямолинейным минимальным деревом Штейнера.

В силу высокой значимости этой задачи для ее решения было разработано немало алгоритмов, которые можно разбить на два класса: точные и эвристические. Поскольку задача SMT является NP-полной, любой точный алгоритм будет иметь ожидаемое экспоненциальное время исполнения в наихудшем случае. Однако в этой области были достигнуты два значительных улучшения. Одним из них стал алгоритм GeoSteiner в реализации Уорма, Уинтера и Захарисена [14, 15] – самый быстрый на данный момент точный алгоритм для решения этой задачи. Второй алгоритм, схема аппроксимации с полиномиальным временем исполнения (Polynomial Time Approximation Scheme, PTAS) Ароры [ ], имеет скорее теоретическую значимость. Поскольку время исполнения точных алгоритмов получается очень долгим, особенно для входных данных большого объема, намного больше внимания было уделено разработке эвристических алгоритмов. Многие из них генерируют дерево Штейнера посредством улучшения топологии минимального остовного дерева (MST) [ ], так как было доказано, что MST является 3/2-аппроксимацией SMT [ ]. Однако из-за того, что в этих подходах базовые структуры ограничены топологией минимального остовного дерева, степень улучшений по сравнению с ним ограничена. Итерационный алгоритм 1-Steiner Канга и Робинса [ ] был одной из первых попыток обойти это ограничение, а его улучшенная реализация [ ] стала самой популярной из подобных программ общедоступного класса. Время исполнения этого алгоритма в версии [10] составляет O(n4 log n), а реализации в [ ] – O(n3). Намного более эффективный алгоритм позднее предложили Бора и коллеги [2]. В их версии остовное дерево итеративно улучшается за счет подключения точки к ребру и последующего удаления самого длинного ребра в получившейся схеме. Время исполнения этого алгоритма в наихудшем случае составляет &(n2), также была предложена альтернативная реализация с временем O(n log n). Поскольку базовые структуры теперь уже не ограничены топологией МОД, эффективность данного подхода сравнялась с эффективностью итеративного алгоритма 1-Steiner [2]. Недавно был предложен новый эвристический алгоритм Мандуи и др. [11], основанный на 3/2-аппроксимации алгоритма вычисления метрического дерева Штейнера на квази-двудольных графах [ ]. Он работает несколько лучше итеративного алгоритма 1-Steiner, но слегка уступает этому же алгоритму в случае использования последним проверки на пустые прямоугольники [11]. Недавно Чу [3], а также Чу и Вонг [4] предложили эффективный подход на базе таблицы поиска для построения прямолинейного дерева Штейнера.