Клуб API Карт

Клуб API Карт

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

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

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

3 комментария
Авторизуйтесь, чтобы оставить комментарий
dimik
28 января 2016, 03:58

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

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

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

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

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