Как построить идеальный маршрут? Задача коммивояжёра вокруг школы

В чём математическая суть задачи коммивояжёра

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

Маршрут, проходящий через каждую вершину ровно один раз с возвращением в исходную точку, математики называют гамильтоновым циклом. Если между всеми местами можно пройти напрямую, граф считается полносвязным. Поиск идеального пути сводится к поиску гамильтонова цикла с наименьшей суммарной длиной. Сложность в том, что задача коммивояжёра относится к классу NP-трудных задач. Универсальной быстрой формулы для мгновенного вычисления самого короткого пути человечество пока не нашло.

Почему число вариантов растёт с катастрофической скоростью

Количество возможных круговых маршрутов зависит от числа точек и подчиняется правилу факториала. Если школа зафиксирована как старт и финиш, а вокруг неё нужно посетить четыре места, выбор первого пункта даёт четыре варианта, второго — три, третьего — два, последнего — один. Всего получается 24 маршрута. Если направление обхода по часовой стрелке и против часовой стрелки даёт одинаковое расстояние, число уникальных траекторий делится пополам, оставляя 12 вариантов. Это легко посчитать на листе бумаги за несколько минут.

Ситуация резко меняется, когда список дел расширяется. Для 10 локаций число замкнутых путей рассчитывается по формуле (n - 1)! / 2 и составляет 181 440 вариантов. Для 15 точек вокруг школы число маршрутов превышает 43 миллиарда. При 20 остановках количество комбинаций переваливает за 60 триллионов. Даже мощный компьютер потратит годы на перебор всех вариантов для скромного района из 30 перекрёстков. Это явление называют комбинаторным взрывом.

Методы поиска оптимального пути на карте микрорайона

Существуют два принципиальных подхода к решению этой задачи. Первый подход гарантирует нахождение абсолютно лучшего маршрута, но требует огромных вычислительных ресурсов. Второй подход находит маршрут, близкий к идеальному, за доли секунды с помощью математических эвристик.

Точные методы для небольшого числа объектов

Если вокруг школы нужно обойти до 10-12 точек, применяют метод ветвей и границ. Алгоритм делит все возможные пути на группы и вычисляет для каждой нижнюю границу длины. Если становится ясно, что в определённой ветке маршруты заведомо длиннее уже найденного ориентира, всю эту группу отбрасывают целиком без пошагового пересчёта. Это экономит время вычислений, хотя при сотнях вершин метод всё равно теряет практическую скорость.

Жадный алгоритм ближайшего соседа

Самый простой эвристический способ — алгоритм ближайшего соседа. Находясь на крыльце школы, вы выбираете самый близкий к ней магазин. Оказавшись у дверей магазина, ищете ближайшую из ещё не посещённых точек и идёте туда. Процесс повторяется, пока список не закончится, после чего вы возвращаетесь в школу.

Алгоритм двукратной оптимизации 2-opt

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

Пошаговый план построения маршрута вокруг школы

Чтобы построить качественный круговой маршрут для школьного проекта или реальной прогулки, последовательно выполняют несколько действий.

1. Составьте точный список объектов и зафиксируйте школу в качестве начальной и конечной точки обхода.
2. Постройте матрицу расстояний, измерив длину пешеходных дорожек между каждой парой объектов на онлайн-картах.
3. Составьте черновой маршрут с помощью жадного алгоритма, последовательно соединяя ближайшие вершины.
4. Проверьте получившийся чертёж на наличие самопересечений и устраните перехлёсты дорожек методом 2-opt.
5. Сравните длину полученного круга с альтернативным порядком обхода по часовой стрелке по периметру микрорайона.

Как решают эту задачу реальные городские службы

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

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