ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ 3
ВВЕДЕНИЕ 4
1 Постановка задачи 6
2 Алгоритм нахождения полного MST 8
2.1 Минимальное остовное дерево 8
2.2 Построение минимального остовного дерева 9
2.3 Алгоритм Краскала 10
3 Точный алгоритм 12
3.1 Описание алгоритма 12
3.2 Пример работы точного алгоритма 13
4. Эвристический алгоритм Дейкстры - Краскала 14
4.1 Алгоритм Дейкстры 14
4.2 Пример работы алгоритма Дейкстры 15
4.3 Реализация эвристического алгоритма Дейкстры - Краскала 18
5 Анализ полученных результатов 21
5.1 Сравнение алгоритма нахождения полного MST и точного алгоритма . 22
5.2 Сравнение алгоритма Дейкстры - Краскала и точного алгоритма 25
5.3 Сравнение алгоритма Дейкстры - Краскала и алгоритма нахождения
полного MST 26
ЗАКЛЮЧЕНИЕ 31
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 32
ПРИЛОЖЕНИЕ
Купить

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

Купить