+ Ответить в теме
Показано с 1 по 2 из 2

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

  1. #1
    Subway_ is on a distinguished road
    Регистрация
    05.09.2016
    Сообщений
    3
    Вес репутации
    0

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

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

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

  2. По умолчанию

     
    Хотите избавиться от рекламы? Зарегистрируйтесь
  3. #2
    Administrator Админ
    system architect
    AiK is on a distinguished road Аватар для AiK
    Регистрация
    13.02.2004
    Адрес
    СПб
    Сообщений
    2,298
    Вес репутации
    80

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

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

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

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

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

+ Ответить в теме

Похожие темы

  1. Программа для вычисления кол-во дней между двумя датами
    Добрый день!Ни как не получаеться написать в си программу, которая будет уметь считать дни между двумя заданными датами, без использования...
    от sazzka в разделе C и C++
  2. Выбор пути :D
    Здраствуйте. Я знаю что на этом форуме есть опытные программисты работющих в каких либо компаниях или учереждениях, мне нужен ваш совет в выборе...
    от Apokal в разделе Вопрошайка
  3. Как найти все пути между 2 узлами?
    Привет. Дан ориентированный граф. С помощью какого алгоритма можно найти все пути между двумя узлами?
    от Pawell2008 в разделе Алгоритмы
  4. Vba. формирование относительного пути
    Есть структура папок: ---------------------------------- C:\ROOT\FOLDER1\LINE1 C:\ROOT\FOLDER1\LINE2 ------- C:\ROOT\FOLDER2\LINE1...
    от Avsha в разделе MS Office и VB(A).
  5. Пути к дирректориям
    Вопрос может быть и глупый, но что-то я не понимаю Как задать путь и дирректории где находится программа, т.е. есть абсолютный путь...
    от Hup в разделе C и C++

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения