Тема: СРАВНЕНИЕ РАЗЛИЧНЫХ МЕТОДОВ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ШТЕЙНЕРА НА ГРАФАХ

Задача Штейнера - это задача о соединении заданного набора точек некоторой сетью так, чтобы длина этой сети была минимальной. Своё название получила в честь Якоба Штейнера (1796 - 1863).
В общей форме задача Штейнера была впервые сформулирована в статье Милоша Кёсслера и Войцеха Ярника, опубликованной в 1934 году, однако сама эта проблема не приобрела широкой известности вплоть до 1941 года, когда Рихард Курант и Герберт Е. Роббинс включили её в свою книгу «Что такое математика?».
Задачу Штейнера невозможно решить, просто рисуя линии между заданными точками. Для решения необходимо добавить новые точки, называемые точками Штейнера и служащие в качестве узлов искомой кратчайшей сети. Чтобы определить количество и расположение точек Штейнера, математики и программисты разработали специальные алгоритмы. Эта задача имеет полное решение, но, поскольку она относится к классу NP-полных, для задачи Штейнера не существует алгоритма, позволяющего получить решение за полиномиальное время.
Если для нее будет найдено полиномиальное решение, это будет эквивалентно решению «проблемы равенства классов P и NP», которая является одной из «Задач тысячелетия».
Приближённые решения, а также различные варианты задачи используются в таких передовых областях промышленности, как проектирование и производство интегральных микросхем, в т. ч. и микропроцессоров, для минимизации длины телекоммуникационных сетей, проектировании дорожных систем, и в некоторых других областях в прикладной роли.
Мы будем рассматривать не геометрическую задачу, а задачу Штейнера на графах.
Отмечу, что геометрической задаче Штейнера посвящено много литературы и различных материалов. Задаче Штейнера на графе же уделяют в разы меньше внимания, хотя ее актуальность не менее важна в современном мире.

Купить

В результате выполнения данной дипломной работы был разработан программный комплекс для решения задачи Штейнера на графах различных размерностей. Были разработаны и протестированы три алгоритма:
- Алгоритм нахождения полного MST
- Точный алгоритм
- Эвристический алгоритм Дейкстры - Краскала
Таким образом, комплекс предоставляет возможность получения данных для статистического анализа и сравнения алгоритмов. Было проведено по 50 экспериментов для количества вершин п = 12, 16, 20 и количества терминальных вершин т = 2 ... 5. Так же сравнение алгоритмов было проведено на больших размерностях п = 60, 80, т = 5.20 и разных вероятностях плотности ребер.
Основываясь на полученных результатах, можно сделать вывод, что целесообразнее всего использовать эвристический алгоритм Дейкстры - Краскала, так как он показывает лучшее время работы на любых размерностях, а эффективность его работы всего лишь на 10% меньше, чем у точного алгоритма. И учитывая факт NP-полноты задачи, это позволяет решать задачу, используя эвристический алгоритм без существенной потери качества решения.

Купить