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

Представленный алгоритм основан на эвристике подстановки ребер, предложенной Борой и коллегами [2 ]. и работающей следующим образом. Эвристика начинает работу с имеющегося минимального остовного дерева и итеративно рассматривает возможность подключения точки (см. рис. 1) к ближайшему ребру (например, (a, b)) и удаления самого длинного ребра (b, c)) из получившейся схемы. Алгоритм использует [[остовный граф]] [17] как базовую структуру вычисления: вначале он используется для генерации минимального остовного дерева, а затем – пар «точка-ребро» для улучшения этого дерева. Подобная унификация наблюдается также при вычислении остовного дерева и самого длиного ребра для каждой пары «точка-ребро»: эти два вычисления объединяет использование алгоритма Крускала для операций на непересекающихся множествах [5] вместо алгоритма Прима.

На основе вышеприведенных рассуждений создан псевдокод алгоритма, представленный на рис. 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. После генерации минимального остовного дерева у нас также имеются соответствующее бинарное дерево слияния и запросы по поводу наименьших общих предков. При помощи оффлайнового алгоритма Тарьяна для нахождения наименьших общих предков [ ] (представленного процедурой lca_answer_queries) можно сгенерировать все самые длинные ребра для пар. При наличии информации о самом длинном ребре для каждой пары «точка-ребро» можно решить задачу подключения точки к ребру. После этого можно осуществить подключения точек к ребрам в порядке невозрастания прироста. Подключение может быть осуществлено только в случае, если ни ребро подключения, ни ребро удаления еще не были удалены.

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