Бегущий Город
Соревнования => Городское ориентирование => Общие вопросы => Тема начата: Bulawka от 27.09.2011, 09:22:50
-
Какому навигационному софту по силу сабж (http://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%BA%D0%BE%D0%BC%D0%BC%D0%B8%D0%B2%D0%BE%D1%8F%D0%B6%D1%91%D1%80%D0%B0)?
Ну точнее, в БГ-смысле -- расставить заданные точки в оптимальной последовательности прохождения с учётом выбранного способа передвижения?
iGO точно может, СитиГид, насколько я понял, нет.
Кто ещё может?
-
Ох мудриииииите вы :)
Ну и я молчу о том, что о синих заборах навигатор, скорее всего, будет в неведении. Как и о проходных дворах :)
-
Он на автомобиле.
-
Он на автомобиле.
Я этого не говорил. )))
На самом деле, она и в пешесмысле м.б. актуальна, ну в смысле если не охота думать головой.
В частности, с опцией "напрямик". Типа составил маршрут оптимальный напрямик, а потом уж думаешь, как этот напрямик пробежать максимально прямо.
Засада тока в реках (без мостов у нужном месте), КАД-ах, ж/д и т.п. линейных препятствиях.
-
кроме igo я почему то нигде не встречал. хотя я им не пользуюсь, но думаю что наверняка tomtom может, они с igo главные конкуренты.
osmand ещё маршруты строит, но то как он это делает - привело меня в тихий ужас.
-
Он на автомобиле.
Я этого не говорил. )))
На самом деле, она и в пешесмысле м.б. актуальна, ну в смысле если не охота думать головой.
Я в своё время, кстати, пытался запрограммировать (точнее, пытался сформулировать задачу, поскольку не программист ни в одной букве) навигационный софт под городской рогейн.
Типа ввёл туда все КП (с "ценами"), контрольное время и свою расчётную скорость -- он тебе и выдал оптимальный маршрут, с учётом ценности КП, "коммивояжёристости" и т.п.
Видишь что скорость отличается от расчётной -- софт пересчитывает маршрут.
Но дальше поставновки задачи дело не пошло, по крайней мере пока. ))
Наверняка такое уже написано сто лет назад, кстати.
-
Наверняка такое уже написано сто лет назад, кстати.
Напротив, подобными задачами по-прежнему занимаются многие исследователи по всему миру. Поскольку быстрого универсального алгоритма, по всей видимости, не существует, ищут решения для всяких частных случаев.
-
Не вижу ничего особо сложного в алгоритме.
Раз софт может проложить маршрут через К точек, сосчитать очки этих К точек тоже может, а также померить расстояние.
А дальше просто перебор, одну точку выкинули, другую воткнули и т.п.
Для немерянного числа точек (но при этом при сопоставимом -- тоже немерянном -- контрольном времени) -- да, задача станет громоздкой и, возможно, тяжёлой для подсчётов, но не потеряет алгоритмизируемости имхо.
-
Не вижу ничего особо сложного в алгоритме.
Ну, так Нобелевка почти в кармане тогда.
-
Нету Нобелевки по математике ((( Медаль Филдса, я так понимаю
-
Разумеется, проблема именно в том, чтобы написать быстрый алгоритм. Тупой перебор работает экспоненциальное время и перестаёт работать уже для десятков точек. Более хитрые эвристические алгоритмы работают до тысяч точек на суперкомпьютерах. Но для маршрутизации нужны десятки тысяч точек (сколько перекрёстков в СПб?) Поэтому решения обычно приблизительные и используют большие массивы предобработанных данных.
Если вдруг кто придумает полиномиальный алгоритм, то получит миллион долларов от института Клэя (как Перельман). Если хороший эвристический, то, может быть, премию Гёделя (http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%B5%D0%BC%D0%B8%D1%8F_%D0%93%D1%91%D0%B4%D0%B5%D0%BB%D1%8F) (собственно, Санжив Арора в 2010 году получил).
-
а зачем искать самый кратчайший маршрут? методом ветвей и границ достаточно быстро можно найти приемлемое приближение.
для Минска такая программа существует и работает. CityInfo 2.8, можете проверить :)
-
Для любого другого города она тоже существует. Про iGo уже сказано. А циклы светофоров и их количество ваша программа учитывает? А то, что прямо лучше чем зигзагом, даже если длиннее?
-
СитиГид
-
Что делает GPS в заголовке темы? По-моему, к обсуждаемой математике он никакого отношения не имеет.
Какие-то алгоритмы для небольшого числа точек существуют. Но будучи заложенными в устройство они будут работать исключительно на том графе, который в устройстве имеется, а этот граф отнюдь не обязательно разрабатывался с учётом потребностей и особенностей БГ. Например, таких, как неточная локализация КП, возможность движения "по площади" (диагональ через парк, двор) и т.п.
Для рогейна задача вообще вряд ли решаема. Мало, что точек несколько десятков, играют ещё цена, ограниченное время и непредсказуемый момент падения скорости. Наивно предполагать, что удастся поймать этот момент на местности и скорректировать маршрут. Ты можешь оказаться в такой точке, что скорректировать его будет уже невозможно, и придётся в лучшем случае всё бросить и бежать издалека прямо на финиш.
-
Разумеется, проблема именно в том, чтобы написать быстрый алгоритм. Тупой перебор работает экспоненциальное время и перестаёт работать уже для десятков точек.
Применительно к БГ -- десятков точек за глаза.
Тем более применительно к этапу, внутри которого точек менее 10.
-
Для любого другого города она тоже существует. Про iGo уже сказано. А циклы светофоров и их количество ваша программа учитывает? А то, что прямо лучше чем зигзагом, даже если длиннее?
Имхо, это (ситиинфо) чисто минская тема.
Циклы светофоров и их кол-во (а точнее, пропускную способность участка) учитывает имхо тот же "пробочный" ситигайд,
анализируя поступающие к нему данные по этому участку.
-
Например, таких, как неточная локализация КП, возможность движения "по площади" (диагональ через парк, двор) и т.п.
Неточная локализация -- ну нам сверхточность и не нужна.
Просто если решения (оптимальные пути) будут существенно разниться в зависимости от смещения КП на ± 100 метров -- значит решения, в целом, равноправные.
Для рогейна задача вообще вряд ли решаема. Мало, что точек несколько десятков, играют ещё цена, ограниченное время и непредсказуемый момент падения скорости. Наивно предполагать, что удастся поймать этот момент на местности и скорректировать маршрут. Ты можешь оказаться в такой точке, что скорректировать его будет уже невозможно, и придётся в лучшем случае всё бросить и бежать издалека прямо на финиш.
Как раз для рогейна (точнее, для "идеального" рогейна) задача вполне решаема.
Ситуация когда лишний дорогой КП вдалеке, а потом бегом на финиш, окажется выгоднее чем неспешное возвращение с поеданием недорогих КП -- вполне возможна.
Другое дело что в рогейне нет роутинга, ну или почти нет...
Ну то есть софт "рогейн на плоскости без дорог" -- скажем огромное поле -- вполне написуем, согласитесь.
И мощности компьютеров будет хватать на суточное число точек даже простым перебором, согласитесь.
Если от поля перейти к реальной ситуации -- то да, учесть рельеф и тем более дороги -- довольно сложно (потому что нет хороших подробных векторных карт со всеми дорожками и с реальным учётом их бегопроходимости).
Блин, хоть садись и языг изучай.... ))) На чём счас круто программировать, что изучить для написания сабжа?
-
Циклы светофоров и их кол-во (а точнее, пропускную способность участка) учитывает имхо тот же "пробочный" ситигайд,анализируя поступающие к нему данные по этому участку.
Возможно. Но я не об этом.
Я в первую очередь о том (см. схему), что маршрут по жирной линии будет на недлинных перегонах однозначно быстрее, чем маршрут по тонкой. Хоть и длиннее. iGo такие тонкости абсолютно точно не учитывает, регулярно пытается по известным мне финским городкам поводить задворками. Думаю, что по малоизвестным - успешно водит.
-
что изучить для написания сабжа?
Ручку шариковую. Т.к. на этапе разработки алгоритма всё и выяснится. А перевести на любой современный язык программирования - это будет уже дело техники.
-
Bulawka, действительно рогейн из 15 точек на плоскости можно написать перебором на любом языке программирования. Если точек будет хотя бы 30, то уже надо будет использоваться метод ветвей и границ или что-нибудь ещё. Но проблема-то как раз в том, что у нас не плоскость, а граф из дорог, поэтому нужно искать кратчайший путь по дорогам, а тут уже промежуточных точек могут быть десятки, а всего точек в рассмотрении тысячи.
MegaManiac, картинка хороша, но актуальна только для машин. Уже для велосипедов по тонкой линии скорее всего быстрее, а бегом так точно быстрее.
-
Musatych, велосипеду тоже надо скорость сбрасывать в повороте, особенно если тесном
-
MegaManiac, картинка хороша, но актуальна только для машин. Уже для велосипедов по тонкой линии скорее всего быстрее, а бегом так точно быстрее.
Не спорю. :) А возможно, еще быстрее - дворами. Но 100% адекватных средств навигации в городе для пешеходов/велосипедистов просто не существует, так что пишу о том, что есть...
-
а ещё и качество покрытия дороги играет свою немаловажную роль.это для всех категорий актуально
-
Я в первую очередь о том (см. схему), что маршрут по жирной линии будет на недлинных перегонах однозначно быстрее, чем маршрут по тонкой. Хоть и длиннее. iGo такие тонкости абсолютно точно не учитывает, регулярно пытается по известным мне финским городкам поводить задворками. Думаю, что по малоизвестным - успешно водит.
Адекватный софт, учитывающий скорости ТС на участках, не только пробки, но и сами скорости, вполне в состоянии оценить, что по жирной быстрее.
Тем более если он оценивает не моментальные скорости, а средние скорости (точнее, среднее время) проезда ломаной (ну скажем от самого начала до самого конца жирной линии по обоим маршрутам).
-
Блин, хоть садись и языг изучай.... ))) На чём счас круто программировать, что изучить для написания сабжа?
вливйся в http://www.osmand.net/ (http://www.osmand.net/) , там как раз с маршрутизацией не очень гладко. зато уже есть готовая векторная карта от OSM.
писано оно на жабе, я так понимаю.
-
А возможно, еще быстрее - дворами. Но 100% адекватных средств навигации в городе для пешеходов/велосипедистов просто не существует, так что пишу о том, что есть...
Кстати, ситигайд легчайше водит по дворам всяких промзон, если на шоссе рядом мегапробка.
И из ситигайда я на прошлом БГ узнал про весьма нетривиальный съезд с КАД к Ручьям (который с фуро-парковки начинается).
Не поверил и поехал мимо, в пробку, как потом выяснилось -- зря не поверил.
-
ИМХО, при некоторых допущениях, в первом приближении все сводится к уже решенной многими способами задаче:
http://ru.wikipedia.org/wiki/Задача_коммивояжёра (http://ru.wikipedia.org/wiki/Задача_коммивояжёра).
Имея нетбук с выносным ЖПС в рюкзаке можно не только решить задачу один раз для КП на этапе, но решать ее постоянно динамически с учетом текущей скорости движения и другой обстановки (например о пробках). Ведь автонавигаторы делают примерно тоже самое, но для двух точек. То есть алгоритмы (пусть нам в настоящее время неизвестные) существуют.
Далее можно построить граф всех КП на этапе, где каждый перегон между каждым КП (ну эвристически дурацкие пути можно и повыкидывать) будет считаться с помощью уже решенной задачи в автомобильном пофигаторе - потом к этому графу применяется алгоритм для решения этой задачи - И ВУАЛЯ!
ЗЫ: курите Кнута и Дейкстру, язык программирования - дело даже не десятое! (если решать задачу с нуля)
-
???
То есть алгоритмы (пусть нам в настоящее время неизвестные) существуют.
Нам - это кому? В смысле - узкому кругу БГ-шников или человечеству? Задача коммивояжёра "в первом приближении" весьма далека от БГ-реальности (тем более - от реальности любых видов спорта с ориентированием, в городе ещё хоть как-то можно использовать адресный план и сетку улиц). Если её худо-бедно умеют решать, то без гарантии и только в плане минимизации расстояния, но не времени. Ибо скорость не учитывается - нет таких алгоритмов (см. тему про 2GIS в разделе БГ-2011, ответы разработчиков). Да и как её учесть, если она непредсказуема вообще говоря?
Гипотетически: пусть мы снимаем скорость с приёмника, а компьютер её как-то прогнозирует дальше. И что? На сложной трассе новая порция данных с навигатора способна перевернуть весь план, а следующая вернуть всё обратно. Да этак только вред будет, а не оптимизация.
-
???
То есть алгоритмы (пусть нам в настоящее время неизвестные) существуют.
Нам - это кому?
Нам - это людям, общающимся в данной теме. Лично мне известно о принципиальном существовании этих и подобных алгоритмов, причем находящих решение за "разумное" время применительно к сетке КП в городе на современных вычислительных машинах. Но мне неизвестны эти алгоритмы в точности.
Задача коммивояжёра "в первом приближении" весьма далека от БГ-реальности (тем более - от реальности любых видов спорта с ориентированием, в городе ещё хоть как-то можно использовать адресный план и сетку улиц).
Как раз в первом приближении задача очень близка к БГ реальности.
Давайте например вести речь о:
1) броневиках, у которых
2) все КП известны (загадок нет) - впрочем это ограничение обходится очень легко, и если мы ведем речь о таки-динамическом обсчете, то при отгадке очередной загадки нужно будет просто добавить точку с известными географическими (широта-долгота) или городскими (улица-дом) координатами
3) все КП подъездные - впрочем это тоже не обязательно, просто при выходе из машины нужно будет брать с собой ЖПС (многие автопофигаторы имеют небольшую батарейку на час-два работы) чтобы он сразу вводил поправки на изменившуюся скорость
Если её худо-бедно умеют решать, то без гарантии и только в плане минимизации расстояния, но не времени.
Ибо скорость не учитывается - нет таких алгоритмов (...). Да и как её учесть, если она непредсказуема вообще говоря?
А кто мешает делать два графа - один по расстоянию с учетом текущего пути по улицам, другой по времени с учетом текущей скорости и некоего алгоритма ее прогноза (об этом ниже)? Далее из этих двух графов ваять один, в котором при слиянии учитывать параметры скорости и расстояния с различными весами (индивидуально для каждого участника).
Более того - в графе по расстоянию ведь можно задавать несколько путей из точки в точку - с учетом текущей дорожной обстановки и наиболее вероятных путях объезда в случае необходимости.
см. тему про 2GIS в разделе БГ-2011, ответы разработчиков
Систему 2GIS (не в обиду разработчикам) считаю картографической, но никак не навигационной. Ситигид и ему подобные, имхо, для примеров куда больше годятся.
Гипотетически: пусть мы снимаем скорость с приёмника, а компьютер её как-то прогнозирует дальше. И что? На сложной трассе новая порция данных с навигатора способна перевернуть весь план, а следующая вернуть всё обратно. Да этак только вред будет, а не оптимизация.
Для этого обсчет нужен динамический - то есть в реальном времени, чтобы "новая порция данных" приходила, согласно NMEA, ежесекундно (есть и более продвинутые варианты до 10 герц). Много Вы сможете за секунду убежать так, чтобы ситуация изменилась кардинально? Уехать - да, например проехать нужный поворот - ну так не страшно (см. ниже).
Возмем две точки и какой-нибудь автомобильный навигатор с функцией автороутинга автоматической прокладки маршрута. Вы с ним когда-нибудь работали?
Обратите внимание, как он пересчитывает маршрут в зависимости от вашего местоположения на участке пути (допустим пропущенного поворота), от вашей текущей скорости (а некоторые смотрят еще и историю скорости), от дорожных знаков (внесенных в его память - там могут быть и ошибки, но обычно все ок), от средней скорости потока автомобилей на данном участке пути и других (объездных) вариантах (эти данные получаются в автоматическом режиме с навигаторов других участников дорожного движения)!
Обратили внимание? Вывод - алгоритмы существуют. Работают с разной степенью эффективности, но уже неплохо.
То есть при имеющихся определенных данных (дорожные знаки, состояние покрытия, объезды, сами карты и проч) задача динамического расчета пути между двумя точками вполне под силу маленькой коробочке на торпеде. Если взять большой комп, которому навигатор будет передавать данные, то такому компу вполне под силу динамически обсчитывать графы БГ маршрута с несколькими десятками или даже сотнями точек. Тем более, что задача элементарно параллелится - следовательно количество точек можно относительно безболезненно (для скорости работы алгоритма) нарастить.
-
О том, что существуют автомобильные навигаторы, успешно решающие задачу для 5-6 точек, я в курсе. Только это не задача коммивояжёра, а целая пачка задач коммивояжёра. Там сложный граф с миллионами узлов. Сначала нужно найти по этому графу лучшие пути между всеми парами точек, и только потом перебирать варианты с порядком взятия. А теперь: 5!=120, 10!=3000000. 20! это уже одних цифр около двух десятков, такое количество вариантов если и впишется в "головку от торпеды", то с самыми современными технологиями и за большие деньги. 30! уже точно не впишется даже за большие деньги.
Наконец, задача "Броневика" наиболее проста среди всех БГ-задач. Ибо автомобиль не устаёт, и его скорость не зависит от времени суток. Так что задача минимизации времени с учётом весовых коэффициентов на ограничения скорости по участкам почти не отличается от задачи минимизации расстояния. Скорость же бегуна и велосипедиста предсказать крайне сложно - она в том числе зависит от морально-волевых качеств, взаимодействия партнёров внутри команды, а также эффекта "паровоза" при следовании по трассе многих команд. Об "Атланте" и вовсе стоило бы умолчать - к непредсказуемости скорости добавляется комбинация нескольких способов передвижения с разной скоростью у каждого способа ... уфф!
-
О том, что существуют автомобильные навигаторы, успешно решающие задачу для 5-6 точек, я в курсе. Только это не задача коммивояжёра, а целая пачка задач коммивояжёра. Там сложный граф с миллионами узлов. Сначала нужно найти по этому графу лучшие пути между всеми парами точек, и только потом перебирать варианты с порядком взятия.
Учитывая быстродействие современных встраиваемых (обычно ARM) процессоров и примерного знания этих алгоритмов, что-то мне говорит о том, что точек там не так уж и много - тысячи в лучшем случае, да и пути между всеми парами не считали даже на заре ЭВМ когда компьютеры были ОЧЕНЬ большими. Ведь к каждому алгоритму решения задачи в лоб, методом прямого перебора (в ширину или в глубину - не важно) существует несколько (а то и несколько десятков) методов его оптимизации, да еще и эвристический анализ никто не отменял.
Плюс ко всему, сдается мне, что в динамическом режиме нужно будет пересчитывать далеко не все (даже с учетом оптимизации и эвристики), а лишь изменения!
А теперь: 5!=120, 10!=3000000. 20! это уже одних цифр около двух десятков, такое количество вариантов если и впишется в "головку от торпеды", то с самыми современными технологиями и за большие деньги. 30! уже точно не впишется даже за большие деньги.
А не нужно ничего вписывать на торпеду, кроме терминального сервера с ЖПС приемником и мобильным интернетом - эту задачу даже не самый навороченный смартфон потянет. Остальное может решаться в ЛЮБОМ месте на чем угодно - одном большом компе, сети больших компов, вычислительной стойке или нейронной сети (да хоть SETI@HOME). Для этого вовсе не нужно таскать с собой непосредственно вычислитель! Достаточно кормить его свежими данными о своем местоположении и изменении маршрута (например появлении новых КП) - информацию о пробках и погоде (например туман, гололед) он вынет из интернета сам. Потом также в терминальном режиме зашлет вам обратно просчитанный маршрут.
Наконец, задача "Броневика" наиболее проста среди всех БГ-задач. Ибо автомобиль не устаёт, и его скорость не зависит от времени суток. Так что задача минимизации времени с учётом весовых коэффициентов на ограничения скорости по участкам почти не отличается от задачи минимизации расстояния.
ХМ..... Скорость автомобиля на дороге как раз очень зависит от: времени суток (светло-темно, солнце низко в глаза), состояния погоды (мокрый снег, проливной дождь, ясно, гололед), качества бензина, свежезалитого на очередной заправке и как он перемешивается с оставшимся в баке бензином....
Скорость же бегуна и велосипедиста предсказать крайне сложно - она в том числе зависит от морально-волевых качеств, взаимодействия партнёров внутри команды
ИМХО, для себя на велосипеде могу предсказать скорость куда точнее, чем на автомобиле - потому как меньше не зависящих непосредственно от меня обстоятельств. Бегом - еще точнее! Разве что ногу подвернул - так это ступенчатое изменение, означающее полный пересчет всего, включая вообще принципиальную возможность продолжать, идти на финиш или вообще домой.
а также эффекта "паровоза" при следовании по трассе многих команд
Имея такой девайс с уже зашитыми КП, лично мне паровозы будут побоку! На них начну смотреть только в том случае, если мой мозг и мозг моего девайса ошибутся явно в принятии решения о маршруте и, более того, не будут предлагать вообще никаких иных вариантов. Такая вероятность нулю конечно не равна, но очень к нему близка.
Об "Атланте" и вовсе стоило бы умолчать - к непредсказуемости скорости добавляется комбинация нескольких способов передвижения с разной скоростью у каждого способа.
Не вижу принципиальных сложностей вписывания нескольких способов передвижения с разной скоростью в алгоритм - достаточно лишь добавить дополнительные ветви с весами в граф. Где-то тут даже обсуждали онлайн сервис о местонахождении ОТ. Почему бы не получать инфу с него? Пусть пока и не в каждом городе....
... уфф!
Точно! Только дальше дискуссию считаю беспредметной.
Если есть люди, действительно готовые в том или ином виде решать задачу построения такого девайса (разработки алгоритма, тестирования и отладки, стыковки интерфейсами с ЖПС, со службами пробок, погоды и прочих, обеспечения вычислительной мощности) - готов помочь с учетом имеющихся знаний.
-
как говорится - флаг в руки! Я нахожу, что дело не стоит того, чтобы заниматься им бесплатно, и не вижу достаточного количества покупателей, готовых работу оплатить хотя бы когда она будет готова. В теории всё хорошо, а что будет на практике, выяснится только при попытке внедрения.
Учитывая быстродействие современных встраиваемых (обычно ARM) процессоров и примерного знания этих алгоритмов, что-то мне говорит о том, что точек там не так уж и много - тысячи в лучшем случае
Вероятно действительно так. Вспоминаю недавнюю поездку по Карельскому перешейку, когда навигатор, где бы мы ни находились, упорно посылал на трассу Скандинавия. Хотя по карте невооружённым глазом были видны пути более короткие. Что мы тогда вообще хотим оптимизировать? У нас нет графа, реально отображающего возможные пути на автомобиле, а что говорить о велосипедистах и пешеходах? Любопытно, подумал ли кто о роллерах - у них свои особенности.
ХМ..... Скорость автомобиля на дороге как раз очень зависит от: времени суток (светло-темно, солнце низко в глаза), состояния погоды (мокрый снег, проливной дождь, ясно, гололед), качества бензина, свежезалитого на очередной заправке и как он перемешивается с оставшимся в баке бензином....
Штука в том, что погодные факторы влияют на все ветви графа более-менее равномерно, и в статике значения не имеют. А вот в динамике - другое дело. То есть вообще говоря надо закладывать в алгоритм прогноз погоды и учитывать, что вечером скорость будет ниже.. А качество бензина вряд ли влияет в городе на низких скоростях, где превышать всё равно нельзя
ИМХО, для себя на велосипеде могу предсказать скорость куда точнее, чем на автомобиле - потому как меньше не зависящих непосредственно от меня обстоятельств. Бегом - еще точнее!
Смею заметить "я" и "компьютер" не одно и то же, ибо последний не обладает многолетним личным опытом и интуицией. Только и опыт с интуицией тоже не стопроцентны. Я свою скорость могу предсказать максимум на пару часов вперёд, это мало для точного планирования хорошей БГ-трассы.
Не вижу принципиальных сложностей вписывания нескольких способов передвижения с разной скоростью в алгоритм - достаточно лишь добавить дополнительные ветви с весами в граф. Где-то тут даже обсуждали онлайн сервис о местонахождении ОТ.
Угу. не забудьте добавить в граф каждый эскалатор и переход метро. И спрогнозировать количество пассажиров на станции в момент прибытия, можно ли будет бежать по эскалатору или придётся стоять (эта информация может повлиять на решение ехать в метро и очень важна!). И выясните на левых сайтах, где ездят левые маршрутки (а ни ГЛОНАСС, ни расписания у них нет). И главное, заложите во всё это тысячи и десятки тысяч ветвей графа, по которым можно бежать бегом. Уж точно никто и никогда не заложит веточку от Броневой до Маршала Говорова под ЗСД или народную тропинку от бульв. Дружбы до Авиационной ул. в Красном Селе. И попробуйте (см. выше) спрогнозировать скорость бегуна, да поточнее - ошибка в одну минуту приведёт к непопаданию в электричку и весь замечательно выстроенный маршрут рухнет.
Я это уже не в порядке дискуссии, а в порядке предложений по совершенствованию алгоритма. Желаю успеха.