Основной целью данной курсовой работы является изучение программной реализация алгоритма определения кратчайшего пути между двумя любыми вершинами графа, а также поиске основных методов решения задачи поиска кратчайшего пути и их обоснование.
Эта цель актуальна и в наше время актуальна, благодаря массовому применению для решения прикладных задач[1-5].
На ней оснвоаны используемые в алгоритмах определения оптимального пути между произвольными объектами (GPS-навигация), в автопилотах, для определения кратчайшего пути прохождения пакетов по сети, и некоторых других. Определение кратчайшего пути это одна из важных классических методов в математической теории графов. Сегодня известна масса алгоритмов для её решения. Определение кратчайшего путь рассматривается с помощью математической модели.
Курсовая работа направлена на изучение методов нахождении пути в графе. Сейчас алгоритмы определения кратчайшего пути применяются в картографиии, программах навигации и управления , при маршрутизации пакетов в сети, и в многих других областях.
Граф - математическая модель, представленная совокупностью множества вершин и связей между ними.
Дипломная работа по налогам на заказ позволит вам не тратить свое время. Доверьте написание дипломной работы профессионалам.
Она может быть определена для неориентированного, ориентированного или смешанного графа.
Сегодня много проблем в области науки и техники может быть
редуцировано к проблемам определения пути в графе, таких как задача кратчайшего пути на заданном графе. Отметим, что определение кратчайшего и оптимального пути в графе имеет важное практическое применение, например, при решении задач маршрутизации, трассировки печатных плат, GPS-навигации, принятии решений в области искусственного интеллекта.
Такие задачи решаются с помощью алгоритмов определения пути в
графе. Объектом ,который изучается , в курсовой работе является теория графов. Предметом исследования , которому посвящена курсовая работа являются программные алгоритмы нахождения путей в графе.
Цель курсовой работы – исследование программной функций определения кратчайшего пути в графе в системе компьютерной математики Maple. Достижение этой цели обеспечивается следующими задачами:
анализом проблемы нахождения кратчайшего пути в определённом графе;
анализом современных алгоритмов определения кратчайшего пути в графе;
выполнием программной реализации и тестирования современных
алгоритмов определения поиска кратчайшего пути в графе на платформе Maple.
Применяемый метод исследования – аппарат математический теории графов, современные алгоритмы поиска путей в графе, процессно - ориентированный подход к проектированию программного обеспечения.
Данная работа состоит из введения, трёх глав, заключения и списка
используемой литературы. В приложение вынесен пример полного описания свойств графа.
Первая глава проведён анализ и определение проблемы определения
кратчайшего пути в графе, описаны задачи определения кратчайшего и
пути в графе.
Во второй главе проанализированы современные алгоритмы определения
кратчайшего пути в графе: алгоритм поиска в ширину; жадный алгоритм и
алгоритм Дейкстры. Третья глава посвящено конкретной реализации известных алгоритмов поиска кратчайшего пути в графе. Разработаны скрипты решения задачи. Выполнено тестирование алгоритмов. В заключении описываются результаты выполнения курсовой работы.
27 страниц
62% уникальность
2023 год
13 просмотров
