autumn_orion
Junior Member | Редактировать | Профиль | Сообщение | ICQ | Цитировать | Сообщить модератору AlexGND сорри за корявое описание и тупой алгоритм... Наверное, существуют более оптимальные пути решения. Просто делюсь тем, что пришло в голову. Путь - это участок, который включает в себя часть одного или нескольких маршрутов 1. Определяем список точек пересадок. 2. Определяем список маршрутов, содержащих точку X. 3. Маршрут содержит точку Y? Если да, то добавляем в список маршрут в список путей. Если нет, то: 4. Маршрут содержит точки пересадок? Если нет, то исключаем из списка рассматриваемых маршрутов. Если да, то: 5. По всем точкам пересадок Z рассматриваемого маршрута составляем список маршрутов, содержащих точку Z (исключая маршруты, уже вошедшие в рассматриваемый путь -- иначе будут петли) 6. к пункту 3... ( с заменой слова "маршрут" на "отрезок маршрута") до тех пор, пока не достигнута точка Y или маршрут не содержит точек пересадок... А дальше, зная какие маршруты входят в каждый путь и стоимость проезда на маршруте ищем путь с минимальной стоимостью. Да, кстати алгоритм можно оптимизировать, если параллельно с построением пути считать стоимость. Если до точки Y не дошли, а стоимость превышает минимальную стоимость проезда по рассмотренным путям, то такой путь можно дальше не строить... |