Клуб API Карт

Маршрут минимальной длины через заданные точки

ale3000931
1 июля 2015, 14:19

Здравствуйте!
Есть набор точек (порядка 30 штук), нужно построить автомобильный маршрут минимальной длины, который бы проходил через все точки. Возможно ли сделать это на карте в автоматическом или полуавтоматическом режиме, или через клиентское апи?

6 комментариев
Подписаться на комментарии к посту

Это называется задача коммивояжера. В АПИ нет встроенных средств для ее решения

Да, спасибо. Про название знаю, но решил так описать, чтобы сразу передать суть задачи.
---
Может кто уже делал подобное (напр. алгоритм ближайшего соседа или другие алгоритмы решения этой задачи)? Именно используя маршруты с яндекс.карт.

 

Делал когда-то (кривовато получилось, но может чем и поможет): http://routepath.narod.ru/

А есть сам код? Хотелось бы поработать с кодом. Уж очень надо задачку регить эту для своей работы.

Код доступен через "просмотр кода страницы"/"просмотр HTML кода" в контекстном меню браузера.

Сразу оговорюсь, что в данной реализации метод ветвей и границ не работает, но и без него результаты довольно сносные. Если всё-же нужно точное решение - математику можно поискать на dxdy.ru или погуглить Костюка (Томский университет)

Попробуйте сервис http://zig-zag.org/ строит самый оптимальный маршрут на основании заданных точек.