Длина маршрута
Кратчайший найденный
Шаги
Возможные маршруты
  • Маршрут
  • Кратчайший найденный
  • Старт

Метод Длина Сверх кратчайшего Шаги
- - -
- - -
- - -
- - -
- - -

Подробнее о задаче коммивояжёра

Задача коммивояжёра

Коммивояжёр должен побывать в каждом городе по одному разу и вернуться домой. В каком порядке поездка окажется самой короткой? Вопрос задать легко, но с ростом числа городов ответить на него перебором всех порядков безнадёжно: уже 30 городов допускают около 4,4 × 10³⁰ замкнутых маршрутов. Разбросайте города по карте или расставьте свои щелчками, а затем посмотрите, как быстрые эмпирические правила, хитроумные улучшения и один точный метод шаг за шагом строят свои маршруты, и оцените, насколько близко подбираются быстрые методы. Выберите, как расположены города и сколько их, укажите метод и нажмите «Решить», чтобы посмотреть, как он шаг за шагом строит маршрут, или «Шаг», чтобы продвигаться по одному ходу. Щёлкните по карте, чтобы добавить город, или по городу, чтобы удалить его. «Сравнить все» запускает все методы на одних и тех же городах и показывает, насколько каждый из них отстаёт от кратчайшего найденного маршрута. Красный город — место, где начинается поездка.

Как это работает

  1. Выберите расположение и число городов или щёлкните по карте, чтобы поставить свои, а по городу — чтобы удалить его.
  2. Выберите метод и нажмите «Решить», чтобы следить за ним шаг за шагом, или «Шаг», чтобы продвигаться по одному ходу.
  3. Нажмите «Сравнить все», чтобы запустить все методы на одних и тех же городах, и посмотрите, насколько каждый маршрут длиннее кратчайшего найденного.

Почему это трудно

Для n городов существует (n − 1)! / 2 различных замкнутых маршрутов, потому что неважно, откуда начать и в какую сторону ехать. Это 12 для 5 городов, 181 440 для 10 и около 6 × 10¹⁶ для 20. Неизвестен метод, который для любой карты находил бы кратчайший маршрут за время, растущее лишь как степень n; задача NP-трудна. Лучшему точному методу в этом приложении, динамическому программированию Хелда — Карпа 1962 года, всё равно нужно около n² · 2ⁿ шагов, поэтому здесь он ограничен 12 городами.

Хорошие маршруты быстро

На практике почти кратчайшие маршруты находятся быстро. Ближайший сосед всегда едет в ближайший ещё не посещённый город и обычно получает маршрут примерно на 25 % длиннее лучшего. Дешёвая вставка наращивает петлю и добавляет тот город, который удлиняет её меньше всего. 2-opt берёт любой маршрут и раз за разом заменяет два ребра двумя более короткими; это убирает все пересечения и обычно даёт отставание всего около 5 %. Имитация отжига делает случайные ходы 2-opt и, пока она ещё «горячая», принимает и некоторые ходы, удлиняющие маршрут, поэтому может выбраться из тупиков, прежде чем остановиться.

Часто задаваемые вопросы

Есть ли формула для кратчайшего маршрута?

Нет. Кратчайший маршрут зависит от точного положения всех городов, и неизвестен метод, который находил бы его для любой карты, не требуя в худшем случае объёма работы, растущего экспоненциально. Для нескольких сотен или тысяч городов специализированные точные решатели, такие как Concorde, всё же доказывают оптимальность маршрутов, сочетая линейное программирование с хитроумным отсечением; самый большой экземпляр, решённый точно на сегодняшний день, содержит 85 900 точек.

Почему 2-opt убирает все пересечения?

Если два ребра маршрута пересекаются, четыре города, которые они соединяют, образуют четырёхугольник, диагоналями которого служат эти два ребра. Заменить их двумя противоположными сторонами четырёхугольника всегда короче — по неравенству треугольника, — а участок маршрута между ними при этом разворачивается. 2-opt делает такие замены, пока ни одна из них не помогает, поэтому его итоговый маршрут никогда не пересекает сам себя.

Что такое температура в имитации отжига?

Она определяет, насколько охотно метод принимает ход, удлиняющий маршрут. Ход, который добавляет к длине d, принимается с вероятностью e^(−d/T). При высокой температуре T допускается почти всё, что позволяет маршруту вырваться из неудачного расположения; по мере снижения T метод становится жадным и останавливается. Название происходит от медленного охлаждения металла, при котором его атомы находят расположение с низкой энергией.

Почему точный метод ограничен 12 городами?

Алгоритм Хелда — Карпа хранит кратчайший путь для каждого подмножества городов и каждого возможного последнего города, а это около n · 2ⁿ чисел, и заполняет каждое из них с помощью n сравнений. Для 12 городов это несколько сотен тысяч шагов, для 25 городов были бы миллиарды. И всё же это несравнимо быстрее, чем перебор всех (n − 1)! / 2 маршрутов: для 12 городов их было бы почти 20 миллионов.

Отправляется ли что-нибудь на сервер?

Нет. Города и все пять методов работают в вашем браузере. Города, которые вы поставили щелчками, остаются в локальном хранилище этого браузера.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Перейти в редактор