Данная работа посвящена реализации приближенного алгоритма 11/6 для решения задачи поиска минимального дерева Штейнера. Целью данной работы было изучение статьи про алгоритм 11/6 и реализация предложенного алгоритма на языке С++. В рамках данной работы также было проведено сравнение полученного алгоритма с алгоритмом KMB. В результате данного исследования были сделаны выводы, что решение поставленной задачи с помощью алгоритма 11/6 получается точнее, чем с помощью алгоритма KMB, но время работы алгоритма 11/6 больше, чем у KMB. Также было произведено распараллеливание блока алгоритма 11/6, что дало прирост производительности почти в 2 раза. Были также сделаны выводы о зависимости времени работы от количества потоков на четырехъядерном процессоре.

The present work is devoted to the implementation of the approximate algorithm 11/6 for solving Steiner tree problem. The purpose of this work was to research the article about the 11/6 algorithm and the implementation of the proposed algorithm in C++. As part of this work, the obtained algorithm was also compared with the KMB algorithm. As a result of this research, it was concluded that the solution of the problem using the 11/6 algorithm is obtained more accurately than using the KMB algorithm, but the running time of the 11/6 algorithm is longer that that of KMB. Also, the block of the 11/6 algorithm was parallelized, which gave a performance increase of almost 2 times. Conclusions were also drawn about the dependence of the algorithm’s runtime on the number of threads on a quad-core processor.

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