Данная работа посвящена исследованию точных алгоритмов решения задачи Штейнера на графах. Целью работы является разработка и реализация парал­ лельного точного алгоритма решения задачи Штейнера на неориентированных и ориентированных графах. В ходе работы построены и реализованы два алго­ ритма решения задачи на неориентированных графах и два алгоритма решения задачи на ориентированных графах. Получено, что задачи с числом вершин до 20000 и числом терминалов до 9 могут быть решены быстрее, чем за 20 секунд. Произведена оценка зависимости производительности построенных алгоритмов от параметров задачи Штейнера – числа вершин, числа рёбер, числа термина­ лов. Также исследована зависимость производительности от количества потоков. Теоретическая оценка производительности построенных алгоритмов совпала с фактической. Параллельная версия алгоритма Дрейфуса, Вагнера дала прирост производительности в 3,5 раза, параллельная версия алгоритма Эриксона, Монмы, Вейнотта – в 3,2 раза. Аналогичные значения были получены для ориентированных версий соответствующих алгоритмов. Полученные результаты позволяют сделать вывод об эффективности построенной параллельной реализации алгоритмов. Ал­ горитм Дрейфуса, Вагнера был успешно применён в рамках совместного проекта СПбПУ и Huawei.

The present work is devoted to the research of exact algorithms for Steiner problem in graphs. The aim is to develop and to implement parallel exact algorithms for Steiner problem in undirected and directed graphs. Two algorithms for the problem in undirected graphs and two algorithms for the problem in directed graphs have been implemented. The research has shown that problems having up to 20000 vertives and up to 9 terminals can be solved in 20 seconds. Performance measurements have been done. It has been checked that theoretical performance fits actual performance. It has been shown that parallel version of Dreyfus, Wagner algorithm increased performance up to 3.5 times, parallel version of Erickson, Monma, Veinott algorithm – up to 3.2 times. The equal results have been received for directed versions of mentioned algorithms. Results allow us to make conclusion about efficiency of parallel implementations. Dreyfus, Wagner algorithm has been successully applied to the R&D project of SPbPU and Huawei.

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