В данной работе описан и реализован алгоритм построения направленного дерева минимальной стоимости greedyFLAC. На его основе разработан метод построения дерева Штейнера с ограничением. В предложенном алгоритме применены подходы к введению ограничения на задержку, изученные в ходе анализа существующих алгоритмов построения дерева минимального веса в приложениях телекоммуникаций, учитывающих задержку по сети. Проведено тестирование реализованных алгоритмов, сравнение их по точности и производительности с аналогами. В ходе экспериментов представлена зависимость производительности предложенного алгоритма от количества терминальных вершин на графе большого размера, близкого к реальной сети телекоммуникаций города. В результате проведенного исследования сделаны выводы о том, что алгоритм greedyFLAC дает лучшее приближение дерева Штейнера, при этом требуя больших временных затрат, и что предложенный алгоритм на некотором подмножестве графов находит дерево меньшей стоимости, чем его аналог, при этом также является более требовательным по вычислительным ресурсам.

In this work we describe and implement an algorithm greedyFLAC for constructing a directional minimum cost tree. On its basis, a method for constructing a Steiner tree with constraint is developed. The proposed algorithm applies the approaches for introducing a delay constraint studied during the analysis of existing minimum cost tree algorithms in telecommunication applications that consider the network delay. We tested the implemented algorithms and compared them in terms of accuracy and performance with their counterparts. During the experiments we presented the dependence of the performance on the number of terminal nodes of the proposed algorithm in a large-sized graph close to the real city telecommunications network. As a result of the study, it is concluded that the greedyFLAC algorithm gives a better approximation of the Steiner tree, though requiring more time, and that the proposed algorithm on subset of graphs finds a tree of less cost than its counterpart, while also being more computationally demanding.

• Алгоритм поиска дерева минимального веса с ограничением задержки в задачах телекоммуникации
  • Введение
  • 1. Постановка задачи и обзор литературы
  • 2. Разработка алгоритма для решения задачи Штейнера с ограничением по задержке
  • 3. Программная реализация алгоритмов GF и DGF
  • 4. Апробация программной реализации алгоритмов
  • Заключение
  • Список использованных источников