МОЩНОСТНАЯ ЗАДАЧА ШТЕЙНЕРА НА ОРИЕНТИРОВАННОМ ГРАФЕ

Ишин Данил Евгеньевич

Аннотация


Цель работы­ - рассмотрение, реализация и сравнение путем численного эксперимента наиболее популярных алгоритмов решения задачи Штейнера на ориентированном графе. Рассмотрены и реализованы пять аппроксимационных алгоритмов и один алгоритм нахождения точного решения задачи Штейнера на ориентированном графе: тривиальный алгоритм, алгоритм Чарикара, алгоритм Руса, GreedyFLAC, Greedy⊳FLAC, алгоритм динамического программирования. Произведено сравнение скорости работы и погрешности этих алгоритмов