???
То есть алгоритмы (пусть нам в настоящее время неизвестные) существуют.
Нам - это кому?
Нам - это людям, общающимся в данной теме. Лично мне известно о принципиальном существовании этих и подобных алгоритмов, причем находящих решение за "разумное" время применительно к сетке КП в городе на современных вычислительных машинах. Но мне неизвестны эти алгоритмы в точности.
Задача коммивояжёра "в первом приближении" весьма далека от БГ-реальности (тем более - от реальности любых видов спорта с ориентированием, в городе ещё хоть как-то можно использовать адресный план и сетку улиц).
Как раз в первом приближении задача очень близка к БГ реальности.
Давайте например вести речь о:
1) броневиках, у которых
2) все КП известны (загадок нет) - впрочем это ограничение обходится очень легко, и если мы ведем речь о таки-динамическом обсчете, то при отгадке очередной загадки нужно будет просто добавить точку с известными географическими (широта-долгота) или городскими (улица-дом) координатами
3) все КП подъездные - впрочем это тоже не обязательно, просто при выходе из машины нужно будет брать с собой ЖПС (многие автопофигаторы имеют небольшую батарейку на час-два работы) чтобы он сразу вводил поправки на изменившуюся скорость
Если её худо-бедно умеют решать, то без гарантии и только в плане минимизации расстояния, но не времени.
Ибо скорость не учитывается - нет таких алгоритмов (...). Да и как её учесть, если она непредсказуема вообще говоря?
А кто мешает делать два графа - один по расстоянию с учетом текущего пути по улицам, другой по времени с учетом текущей скорости и
некоего алгоритма ее прогноза (об этом ниже)? Далее из этих двух графов ваять один, в котором при слиянии учитывать параметры скорости и расстояния с различными весами (индивидуально для каждого участника).
Более того - в графе по расстоянию ведь можно задавать несколько путей из точки в точку - с учетом текущей дорожной обстановки и
наиболее вероятных путях объезда в случае необходимости.
см. тему про 2GIS в разделе БГ-2011, ответы разработчиков
Систему 2GIS (не в обиду разработчикам) считаю картографической, но никак не навигационной. Ситигид и ему подобные, имхо, для примеров куда больше годятся.
Гипотетически: пусть мы снимаем скорость с приёмника, а компьютер её как-то прогнозирует дальше. И что? На сложной трассе новая порция данных с навигатора способна перевернуть весь план, а следующая вернуть всё обратно. Да этак только вред будет, а не оптимизация.
Для этого обсчет нужен динамический - то есть в реальном времени, чтобы "новая порция данных" приходила, согласно NMEA, ежесекундно (есть и более продвинутые варианты до 10 герц). Много Вы сможете за секунду убежать так, чтобы ситуация изменилась кардинально? Уехать - да, например проехать нужный поворот - ну так не страшно (см. ниже).
Возмем две точки и какой-нибудь автомобильный навигатор с функцией
автороутинга автоматической прокладки маршрута. Вы с ним когда-нибудь работали?
Обратите внимание, как он пересчитывает маршрут в зависимости от вашего местоположения на участке пути (допустим пропущенного поворота), от вашей текущей скорости (а некоторые смотрят еще и историю скорости), от дорожных знаков (внесенных в его память - там могут быть и ошибки, но обычно все ок), от средней скорости потока автомобилей на данном участке пути и других (объездных) вариантах (эти данные получаются в автоматическом режиме с навигаторов других участников дорожного движения)!
Обратили внимание?
Вывод - алгоритмы существуют. Работают с разной степенью эффективности, но уже неплохо.
То есть при имеющихся определенных данных (дорожные знаки, состояние покрытия, объезды, сами карты и проч) задача
динамического расчета пути между двумя точками вполне под силу маленькой коробочке на торпеде. Если взять большой комп, которому навигатор будет передавать данные, то такому компу вполне под силу динамически обсчитывать графы БГ маршрута с несколькими десятками или даже сотнями точек. Тем более, что задача элементарно параллелится - следовательно количество точек можно относительно безболезненно (для скорости работы алгоритма) нарастить.
