Клуб API Карт

Построение оптимально маршрута при помощи Яндекс.Карт!

a.baybuz
6 августа 2012, 15:17

Добрый день! Возможно ли в Яндекс.Карт построение оптимального автомобильно маршрута в городе, проходящего через 20-30 точек? В качестве целевой функции должна быть выбраны минимум расстояния либо времени прохождения по маршруту. Спасибо!

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

В общем виде ваша задача является NP-полной,

и в математике известна под именем "задача коммивояжера"

Насколько я помню решение влоб - перебором, для 17 точек занимает несколько дней на самых мощных вычислительных системах

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

http://codepaste.ru/12855/ решение на питоне