М.Ш. Левин, А.А. Замковой

Многокритериальное дерева Штейнера с стоимостью вершин Штейнера

Исследуется многокритериальная задача построения дерева Штейнера с учетом стоимости дополнительных вершин Штейнера. Описаны постановки задач построения покрывающих деревьев Штейнера, алгоритмические подходы. Инженерная постановка задачи направлена на построение телекоммуникационной сети с учетом пространственного распределения радиотехнических помех. Предложен подход к решению сформулированной многокритериальной задачи на основе комбинации двух схем решения: (1) базовая схема для построения покрывающего дерева Штейнера на основе кластеризации вершин исходного графа, (2) общая схема для построения покрывающих деревьев Штейнера с учетом числа дополнительных вершин и выделения Парето-эффективных решений. Дополнительно используется модуль на основе модифицированного алгоритма Прима для построения многокритериального покрывающего дерева. Кластеризация вершин исходного графа основана на применении иерархического (agglomerative) алгоритма. Приведены примеры вычислительного эксперимента по построению многокритериальных деревьев Штейнера.