Планировщик маршрутов v2.0
Понедельник, 7 апреля 2014

Я послушал ваши отзывы и комментарии по поводу моего небольшого проекта. Реализовал некоторые из высказанных идей и, конечно, добавил к ним часть своих.

  1. Самое главное, самое сложное и самое незаметное: поменялся алгоритм поиска. Вместо точного и медленного метода ветвей и границ теперь почти точный и метаэвристичекий метод муравьиной колонии. В основе проекта лежит Travelling Salesman Problem (Задача коммивояжёра), которая является NP-полной. А это означает, что нет другого пути решения её, кроме как перебрать все варианты. Количество вариантов можно посчитать по формуле \(n! \over 2\), где \(n\) — количество промежуточных городов. Если подставить в эту формулу, например, 15 получим 653 837 184 000 вариантов, а это уже очень много. Поэтому пришлось воспользоваться приближенным алгоритмом, который работает быстро, но и решение выдаёт не всегда оптимальное. Кстати, так как внутри алгоритма задействован генератор случайных чисел, решение может меняться от запуска к запуску, достаточно нажать кнопку обновить.

  2. Я убрал из проекта AngularDart, что позволило уменьшить размер JavaScript-файла в 3 раза.

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

  4. Упростилось добавление городов в маршрут. Из вариантов объектов теперь убираются лишние, если вариант только один, то он добавляется автоматически. И самое главное: можно добавлять города, даже не прикасаясь к мышке, используя для выбора варианта клавиши «Вверх», «Вниз» и «Enter».

  5. А ещё теперь можно развернуть карту на весь экран, чтобы было удобнее её изучать.

  6. Исправлены ошибки.

Маршрут по Европе

Прошу любить и жаловать. Замеченные недочёты можно описывать в комментариях к этому посту, ну или присылать любым другим способом.

← Проблемы с запуском планировщикаВильнюс →

Хочется что-то добавить или сказать? Я всегда рад обсудить. Пишите на me@dikmax.name.