Клуб API Карт

Минимальный путь на карте

Ryder78
27 октября 2015, 14:38

Здравствуйте!

Передо мной стоит такая задача: пользователь на страничку загружает файл со списком адресов, и на карте хочет увидеть самый минимальный маршрут, который обходит все точки.

Сначала я пробовал через ymaps.route([...]), но эта функция, к сожалению, не сортирует, а выводит пути к точкам в той последовательности, в какой получает.

Потом пробовал просто получить длины всех возможных путей (довольно плохое решение изначально казалось) и рассортировать сам, но из-за ассинхронности запросов тоже неудалось, да и не хотелось так делать.

Какое может быть ещё решение такой задачи?

Возможно, есть вариант получить ещё также в ответ отсортированный список адресов?

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

Это называется задача коммивояжера и относится к категории NP-полных. Скорость нахождения решения перебором зависит от количества точек, кажется при 17 уже занимает несколько дней на самых мощных ПК. Есть всякие эвристики, которые ускоряют процесс, но снижают качество, находя не самый лучший маршрут.

 

В АПИ нет средств для ее решения. В общем даже можно сказать, что ее нельзя решать через АПИ т.к. получение матрицы расстояний через маршрутизатор АПИ нарушает условия его использования

Здравствуйте!

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