Построение маршрута "Кратчайший путь объехать несколько точек"

В идеальном случае конечно да, нужно много мощностей чтобы всё это перебирать и считать, особенно если прокладывать маршут и высчитывать всё до километра.

Но в большинстве случаев хватит и упрощенного варианта, просто математического расчета по координатам, чтобы не гонять одну машину например из верхней части москвы в нижнюю и потом обратно наверх, т.е. сгруппировать сначала близлежащие точки, и потом по ним уже построить маршрут "как получится", будет уже серьезная экономия километража.

Всякие службы доставки ведь эту проблему как-то решают, вот и мне хотелось бы что-то более-менее рабочее но без огромных мега-расчетов. Кстати, по той же ссылке "задача коммивояжера" предложено несколько упрощенных вариантов решения этой задачи.

Кстати, ведь при просчете кратчайшего машрута от 1 точки к другой Яндекс также перебирает кучу возможных вариантов проезда среди тысячи возможных чтобы найти кратчайший, это же он сделать успевает довольно быстро ;)

Посмотрел тут как дела у навигаторов, и выяснил что Garmin эту задачу как-то уже умеет решать:

http://www.gps-piter.ru/description/nuvi700.htm

- решение "задачи коммивояжера" (до 200 пунктов назначения в одном маршруте)

и это всё на довольно дохленьком процессоре 2007 года.

Спасибо. Есть над чем подумать.