Программа поиска кратчайшего пути между улицами

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
Subway_
Сообщения: 3
Зарегистрирован: 05 сен 2016, 17:59

Программа поиска кратчайшего пути между улицами

Сообщение Subway_ » 05 сен 2016, 18:00

Хочется написать программу, которая выдаст оптимальный маршрут между двумя адресами (с учетом расписания движения общественного транспорта - метро, автобус, трамвай).

Скажите, пожалуйста, что и где почитать по теме? По каким ключевым словам искать ресурсы?

Аватара пользователя
AiK
Сообщения: 2271
Зарегистрирован: 13 фев 2004, 18:14
Откуда: СПб
Контактная информация:

Re: Программа поиска кратчайшего пути между улицами

Сообщение AiK » 06 сен 2016, 19:02

Задача достаточно сложная в плане внесения начальных данных и тривиальная в плане алгоритма. Где брать начальные данные (координаты остановок и маршруты общественного транспорта) я не знаю. Первопроходцу пришлось заносить их всех вручную :)
А дальше работаем примерно так:
1) Для скорости вычислений нужно иметь две копии массива координат остановок, одна копия отсортированная по X, другая по Y.
2) Объект (запись) остановка, кроме координат, должен содержать информацию о всех №№ транспорта, останавливающегося на ней. Я бы для каждого маршрута хранил ссылку на следующую и предыдущую остановку.
3) Понадобится процедура нахождения всех остановок в радиусе N метров от точки.

Процедура, прокладки маршрута простая: для точек A и B находим все остановки в радиусе N метров от неё и сравниваем номера транспорта. Если номера совпали, маршрут проложен. Если не совпали, для каждой остановки и каждого транспорта получаем следующие остановки в обе стороны и смотрим не появилось ли на этих остановках пересечений номеров с остановками у точки Б.

Моё мнение, что 2 пересадки это зло, но в принципе можно повторить процедуру поиска, двигаясь и от точки Б во все стороны.

Гуглить работу с объектами/записями и работу с указателями. Всё.
Даже самый дурацкий замысел можно воплотить мастерски

Ответить