Тема: Программная реализация алгоритма решения задачи почтальона

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

В данной выпускной квалификационной работе были выполнены все поставленные задачи. Были реализованы алгоритмы решения задачи почтальона, и проведено их тестирование.
В рамках данной работы был реализован алгоритм решения задачи почтальона на языке C++ в среде MicrosoftVisualStudio 2015.
Следует заметить, что алгоритм решения задачи почтальона может применяться для различных задач маршрутизации, как например для разработки кратчайшего маршрута снегоуборочной машины.
Стоит заметить, что только в случае ориентированного и неориентированного графа задача почтальона имеет полиномиальное решение.
На диаграмме видно, что поиск кратчайшего пути на ориентированном графе занимает больше времени. Так же стоит отметить: при достижении 500 вершин и 1000 ребер заметносильное увеличение времени работы алгоритма.

Купить