Страница 1 из 1

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

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

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

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

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

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

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

Гуглить работу с объектами/записями и работу с указателями. Всё.