ВВЕДЕНИЕ 3
1 ТЕОРИТИЧЕСКИЙ РАЗДЕЛ 5
1.1. Основные определения и понятия в теории графов 5
1.2. Эйлеровы графы 7
1.3. Задача почтальона 10
1.4. Основные структуры данных для машинного представления
графов 11
1.5. Влияние структур данных на трудоёмкость алгоритмов 15
1.6 Алгоритм Дейкстры 18
1.7 Алгоритм построения эйлерова цикла (Флери) 21
1.8 Венгерский алгоритм 22
2 ПРОЕКТНЫЙ РАЗДЕЛ 24
2.1. Неформальная постановка задачи 24
2.2. Задача, сформулированная в терминах теории графов 24
2.3. Проектирование алгоритмов решения задачи почтальона 25
3 РАЗРАБОТКА И ТЕСТИРОВАНИЕ ПРОГРАММЫ 31
3.1 .Реализация алгоритма решения задачи почтальона 31
3.2. Тестирование разработанного приложения 32
3.3 Эффективность работы алгоритма решения задачи почтальона
ЗАКЛЮЧЕНИЕ 35
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 36
ПРИЛОЖЕНИЯ

Купить

Задачи маршрутизации значимы для сфер логистики и управления транспортом. Проблемы маршрутизации в основном связаны с определением оптимального набора линий в мультиграфе. Цель почтальона считается особенным случаем проблемы маршрутизации, обладающим большое количество возможных дополнений. Почтальон обязан разнести почту согласно вверенному ему району, с целью чего он проходит по абсолютно всем без исключения улицам района и возвращается в начальную точку (в почтовое отделение). Необходимо отыскать короткий путь почтальона. Эта задача достаточно современна: оптимальные маршруты необходимо проводить для различных автомобилей, размечающих, посыпающих и поливающих дороги населенных пунктов. В представлении проблемы почтальона графом перекрестки соответствуют вершинам, а отрезки улиц между перекрестками — ребрам. В общем случае данной модели мало, так как отрезки улиц обладают различную длину, а в задаче надо уменьшить непосредственно длину маршрута. Точной моделью станет взвешенный граф, в котором ребрам приписаны положительные числа.
Целью, этой выпускной квалификационной работы является описание и реализация различных алгоритмов решения задачи почтальона, а кроме того дальнейшее сравнение эффективности и методы оптимизации данных алгоритмов в графах с различными характеристиками.
Данная работа состоит из введения, 3 глав, заключения, списка литературы и приложения. Содержит 10 рисунков, 14 использованных источников. В введении коротко сформулирована предметная область и цели исследования.
Первая глава содержит в себе описание главных понятий теории графов, описывается критерий существования эйлерова цикла. Эта глава включает теорему существования эйлерова цикла и доказательство достаточности и необходимости. Описывается неформальная задача почтальона и рассматривается алгоритмы решения задачи почтальона в терминах теории графов. Также описывается алгоритмы Дейкстры, алгоритм Флёри и алгоритм Маркеса-Куна.
Во второй главе описаны формальная и неформальная постановки задачи почтальона. Показаны блок-схемы алгоритмов решения задачи почтальона.
В третьей главе описывается практическая реализация алгоритма. Рассмотрена работа алгоритма в примере тестовых путей. Приведено сравнение эффективности работы в таблицах и в диаграмме для графов, содержащих различное число вершин и ребер.
В заключении приведены основные выводы, в приложениях содержится полный код разработанных программ.
Купить