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

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