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

Пост в архиве.

Алексей У.

1 июля 2015, 14:19

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

6 комментариев

Авторизуйтесь, чтобы оставить комментарий

dimik

27 января 2016, 22:35

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

Алексей У.

27 января 2016, 22:35

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

HCLUBMK

27 января 2016, 22:35

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

ivan-eremin

27 января 2016, 22:35

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

HCLUBMK

27 января 2016, 22:35

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

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

kostik.sannikov

27 января 2016, 22:35

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