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

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

На основе вышеприведенных рассуждений создан псевдокод алгоритма, представленный на рис. 3. На начальном этапе работы алгоритма для генерации остовного графа G для заданного множества точек используется алгоритм построения прямолинейного остовного графа Чжоу и др [17]. Затем к графу применяется алгоритм Крускала для генерации минимального остовного дерева. Структура данных на основе непересекающихся множеств [ ] используется для слияния компонентов и проверки, принадлежат ли две точки к одному и тому же компоненту (первый цикл for). В процессе выполнения также генерируются бинарное дерево слияния и запросы по поводу наименьших общих предков для всех пар «точка-ребро». Здесь s, s1 и s2 представляют непересекающиеся множества, каждое из которых хранит корень компонента в бинарном дереве слияния. При каждом добавлении дуги (u, v) к T следует рассматривать любого соседа u или v, обозначим его за w, как кандидата на подключение к (u, v). Самое длиное ребро для этой пары будет наименьшим общим предком w и u либо w и v, в зависимости от того, какая точка оказывается в одном компоненте с точкой w. Добавление этого опроса производится при помощи процедуры lca_add_query. Соединение двух компонентов при помощи (u, v) также будет записано в бинарном дереве слияния при помощи процедуры lca_tree_edge. После генерации минимального остовного дерева у нас также имеются соответствующее бинарное дерево слияния и запросы по поводу наименьших общих предков. При помощи оффлайнового алгоритма Тарьяна для нахождения наименьших общих предков [5] (представленного процедурой lca_answer_queries) можно сгенерировать все самые длинные ребра для пар. При наличии информации о самом длинном ребре для каждой пары «точка-ребро» можно решить задачу подключения точки к ребру. После этого можно осуществить подключения точек к ребрам в порядке невозрастания прироста. Подключение может быть осуществлено только в случае, если ни ребро подключения, ни ребро удаления еще не были удалены.

Большую часть времени исполнения алгоритма занимают генерация остовного графа и сортировка ребер, требующие O(n log n) времени. Поскольку количество ребер в остовном графе составляет O(n), и алгоритм Крускала, и алгоритм Тарьяна для поиска наименьших общих предков занимают <math>O(n \alpha (n)) \;</math> времени, где <math>\alpha (n) \;</math> – обратная функция Аккермана, растущая исключительно медленно.

       '''if''' (s1!=s2){

   сгенерировать пары «точка-ребро» на основе lca_answer_queries;

Как отмечалось в работе [16], первая серия экспериментов была проведена на Linux-системе с процессором Intel Pentium III с тактовой частотой 938 МГц и 512 Мбайт оперативной памяти. Алгоритм RST сравнивался с другими публично доступными программами: точным алгоритмом GeoSteiner (версия 3.1) Уорма, Уинтера и Захарисена [14], пакетным итеративным алгоритмом 1-Steiner (BI1S) Робинса и алгоритмом Боры и коллег, реализованным Мэдденом (BOI).

В таблице 1 приведены результаты первой серии экспериментов. Для каждого экземпляра входных данных объемом от 100 до 5000 точек при помощи программы rand_points пакета GeoSteiner было случайно сгенерировано 30 различных тестовых сценариев. Коэффициент улучшения алгоритма вычисления дерева Штейнера St по сравнению с соответствующим алгоритмом вычисления минимального остовного дерева MST определяется как 100 x (MST - St)/MST. Для каждого варианта объема входных данных были вычислены средние значения коэффициента улучшения и времени исполнения (в секундах) каждой из программ. Легко увидеть, что RST всегда обеспечивает более высокую эффективность по сравнению с BOI при меньшей продолжительности работы.

Во второй серии экспериментов сравнивались алгоритмы RST, версия Боры его собственного алгоритма (Borah), алгоритм Роэ на базе подхода Прима (Rohe) [13] и жадный пакетный алгоритм Канга и др. (Batched Greedy Algorithm, BGA) [9]. Они исполнялись на различных Linux-системах с процессором Intel Xeon с 2,4 ГГц тактовой частоты и 2 ГБ оперативной памяти. Помимо случайно сгенерированных тестовых сценариев, также использовались промышленные тестовые сценарии из области разработки СБИС [9]. Результаты представлены в таблице 2.

  ! colspan="2" width="200" | RSt

  | 200||11,492|3,557||10,897||4,810||9,192||0,1287||10,869||0,020

  ! colspan="2" width="200" | RSt