Уникальные учебные работы для студентов


Курсовая работа поиск путей в графах

Анализ исходных данных и разработка ТЗ 1. Назначение разработки - это изучение языка программирования Prolog. Эта программа должна быть полезной для навигации по нашему городу.

Исходя из того, что маршрутов в городе порядка пятидесяти, а остановки, я думаю что, исчисляются сотнями, то размерность задачи можно считать средней. При решении полным перебором, может возникнуть проблема, а именно, время отыскания пути может занять неопределённое время. Поэтому полный перебор здесь не подойдёт.

Далее я выбрал геометрическую интерпретацию. Эти два списка будут определять диапазон ветвей, которые будут участвовать в решении, а остальные просто-напросто отбрасываться, опираясь на то, что они все равно не дадут оптимального решения. С помощью него происходит отыскание пути от остановки1 до остановки2 и суммы времени, которое необходимо затратить на преодоление данного пути.

  • Пути минимальной длины во взвешенном графе;
  • Разработка алгоритма реализации на ЭВМ процесса поиска кратчайшего пути в графе методом Дейкстры;
  • Тем самым мы отбрасываем не нужные нам решения;
  • Волновой алгоритм поиска длиннейшего пути.

Ему пользователь передаёт два значения две остановкиа он возвращает путь и время. В ответе путь как переменная будет содержать не только остановки, но и маршрутные такси их номера. В качестве математической модели я выбрал ненаправленный граф, у которого 19 вершин и 29 дуг. Где вершины графа - это курсовая работа поиск путей в графах, а ветви - участки маршрутки, которые она может проехать не останавливаясь.

Граф, конечно, может и не только неориентированным, но и смешанным, то есть маршрутка может проезжать по ветви только в одном направлении, а возвращаться по иной ветви.

Мой граф имеет циклы, смежные вершины, а не только перекрёстки. Вершины графа представляют собой остановки, а ветви их соединяют соответственно с определённой стоимостью. За стоимость я принял время прохождения маршрутного такси по ветви.

Нахождение кратчайшего пути с использованием графов и алгоритма Дейкстры

Сеть, конечно же, предполагается очень густая. Моя цель на данном этапе - это определить наиболее оптимальный алгоритм поиска пути в нашем графе. Критерий оптимальности пути я выбрал время прохождения маршрутки, которое должно быть соответственно минимальным. Перейдём к поиску алгоритма.

Суть алгоритма, который мне пришёл на ум первым заключается в следующем: Стоимость складывается из цен каждой ветви. В таком алгоритме есть большой минус. Если граф будет состоять из большого числа курсовая работа поиск путей в графах, а в моём случае предполагается что город большой, значит и граф должен быть гутой, то поиск необходимого пути может занять неопределённое количество времени и в некоторых случаях персональный компьютер курсовая работа поиск путей в графах просто зависнуть.

Я считаю, что этот алгоритм оптимален сточки зрения результата. Потому что по этому алгоритму проверяются всевозможные пути. Но в таком случае он не оптимален с точки зрения процедуры поиска самого пути.

Значит, поиск оптимального пути должен производится не по всевозможным путям, а по путям, которые входят в некоторое подмножество. Отсюда следует следующий алгоритм. По данному алгоритму вся карта делится на квадраты: Каждый квадрат имеет пару координат. А в каждый квадрат могут попадать остановки, которые будут иметь координаты.

Диапазоны будут определяться из введённых пользователем данных: Недостаток этого алгоритма заключается в курсовая работа поиск путей в графах Поэтому не стоит делать коридор узким. Наверное, стоит его сделать искусственно шире, то есть расширить диапазоны.

Конечно вероятность получить ответ увеличивается, но остается вероятность также не получить оптимального результата или не получить ответа. Он оптимален с точки зрения процедуры поиска пути. В отличие от первого алгоритма мы можем, получит здесь путь по стоимости дороже, так как перебор ветвей ограничен. Сохраним систему координат и понятие из предыдущего алгоритма. Будем двигаться от начальной остановки к конечной остановке, выбирая ветвь наименьшей цены. Этот алгоритм ещё называется градиентным.

В таком алгоритме есть недостаток: То есть берётся конечная остановка ищется ветвь, примыкающая к ней с наименьшей ценой. Сохраняем стратегию второго алгоритма и добавляем ограничение на прохождение по ветви в обратном направлении.

  • Ввод исходных данных Решение задачи - нахождение оптимального пути Вывод найденного решения 2;
  • Пример сортировки массива, отсортированного случайным образом;
  • Если граф будет состоять из большого числа ветвей, а в моём случае предполагается что город большой, значит и граф должен быть гутой, то поиск необходимого пути может занять неопределённое количество времени и в некоторых случаях персональный компьютер может просто зависнуть;
  • Сохраним систему координат и понятие из предыдущего алгоритма;
  • В таком алгоритме есть большой минус;
  • Особенности составления программного кода на языке программирования Pascal с использованием алгоритма Форда-Беллмана, а также порядок ее тестирования с ручным просчетом.

Тем самым мы отбрасываем не нужные нам решения. Для решения поставленной задачи я выбрал пятый алгоритм. Объём этого подмножества, конечно, зависит не от объёма базы данных, а от того, на сколько удалены начальная курсовая работа поиск путей в графах конечная остановки. Ввод исходных данных Решение задачи - нахождение оптимального пути Вывод найденного решения 2. Или поиск пути в графе, где вершины графа - это остановки, а ветви - участки пути маршрутного такси.

С помощью этой программы можно отыскать путь за минимальное время проезда от одной остановки до заданной. Результатом программы является список остановок и номеров маршрутных такси, которые расположены между курсовая работа поиск путей в графах, и сумма времени.

Из списка будет видно, что делать пользователю, а именно, пересаживаться на другое маршрутное такси или ехать.

  • Для решения поставленной задачи я выбрал пятый алгоритм;
  • Программная реализация алгоритма поиска кратчайшего пути между двумя любыми вершинами графа;
  • В ответе путь как переменная будет содержать не только остановки, но и маршрутные такси их номера.
VK
OK
MR
GP