Я послушал ваши отзывы и комментарии по поводу моего небольшого проекта. Реализовал некоторые из высказанных идей и, конечно, добавил к ним часть своих.
Самое главное, самое сложное и самое незаметное: поменялся алгоритм поиска. Вместо точного и медленного метода ветвей и границ теперь почти точный и метаэвристичекий метод муравьиной колонии. В основе проекта лежит Travelling Salesman Problem (Задача коммивояжёра), которая является NP-полной. А это означает, что нет другого пути решения её, кроме как перебрать все варианты. Количество вариантов можно посчитать по формуле \(n! \over 2\), где \(n\) — количество промежуточных городов. Если подставить в эту формулу, например, 15 получим 653 837 184 000 вариантов, а это уже очень много. Поэтому пришлось воспользоваться приближенным алгоритмом, который работает быстро, но и решение выдаёт не всегда оптимальное. Кстати, так как внутри алгоритма задействован генератор случайных чисел, решение может меняться от запуска к запуску, достаточно нажать кнопку обновить.
Я убрал из проекта AngularDart, что позволило уменьшить размер JavaScript-файла в 3 раза.
Теперь можно скопировать ссылку с маршрутом и отправить кому-нибудь. Только осторожно, чем больше городов будет в маршруте, тем длиннее будет ссылка и некоторые браузеры могут не справиться с такой длиной. Вот вам, например, ссылка на маршрут по всем европейским столицам.
Упростилось добавление городов в маршрут. Из вариантов объектов теперь убираются лишние, если вариант только один, то он добавляется автоматически. И самое главное: можно добавлять города, даже не прикасаясь к мышке, используя для выбора варианта клавиши «Вверх», «Вниз» и «Enter».
А ещё теперь можно развернуть карту на весь экран, чтобы было удобнее её изучать.
Исправлены ошибки.
Прошу любить и жаловать. Замеченные недочёты можно описывать в комментариях к этому посту, ну или присылать любым другим способом.
Здравствуйте, дорогие читатели!
За окном вовсю сияет март, а мы уже начали готовиться к новому большому летнему путешествию (обязательно посмотрите предыдущее, если, конечно, ещё не видели его). К сожалению, идея проехать Соединённые Штаты поперёк накрылась медным тазом отложена до лучших времён. Но это не причина для уныния, ведь есть ещё сотни стран, требующих нашего внимания. И мы решили не заморачиваться и повторить прошлогодний опыт бэкпэкерства с InterRail, благо пол-Европы осталось неизъезженной.
Сказано — сделано. Набросали списочек городов для посещения и оказалось, что маршрут, в отличие от предыдущего года, не очевиден. В каком порядке их нужно объезжать, чтобы расстояние, преодолённое на поезде, получилось минимальным? Поиск нужных сервисов для составления маршрутов ничего не дал, а значит нужно написать свой! Что я и сделал.
Представляю вам планировщик маршрутов. Сервис довольно простой: вводишь начальный город, конечный, а также список городов посередине, — и получаешь оптимальный маршрут. Расстояния между городами считаются по прямой, поэтому результат оптимален только для самолётов. А для остального транспорта стоит учитывать, что дороги кривые и ездят по ним с разной скоростью. Но для того, чтобы прикинуть маршрут, информации достаточно. Конечно, между некоторыми пунктами дороги может вообще не существовать, но не беда: любой отрезок из пути можно исключить и система выдаст другой маршрут с учётом этого ограничения.
Для приготовления сервиса мне понадобились: Яндекс.Карты, AngularDart, Bootstrap. Туда пришлось добавить немного логики и свободного времени. Всё это было смешано, взболтано, вылито в высокий бокал и украшено методом ветвей и границ, прямо как учили в универе. Приятного аппетита.
Прошу опробовать и написать свои замечания и пожелания в комментариях. Исходники всего это дела можно увидеть всё там же — на GitHub.
Всегда к вашим услугам,
Редакция блога.