Задача коммивояжёра простыми словами
Дайте коммивояжёру список городов и попросите найти самую короткую поездку, которая проходит через каждый из них один раз и возвращается домой. Предложенный маршрут может проверить кто угодно, и кто угодно может на глаз улучшить плохой маршрут, но никто не знает быстрого метода, который всегда находит лучший. Задача коммивояжёра стала стандартным примером трудной задачи, а методы, придуманные для её решения, сегодня планируют доставку, сверлят печатные платы и собирают геномы.
Задача
Маршрут посещает каждый город ровно один раз и заканчивается там, где начался; его длина — сумма расстояний по пути. Требуется найти кратчайший маршрут. В рассматриваемом здесь варианте расстояния — это прямые линии на карте, поэтому путь из A в C никогда не длиннее пути через B: это метрическая задача коммивояжёра. Головоломку обсуждал математик Карл Менгер около 1930 года, а название стало общепринятым в следующие десятилетия, когда за неё взялись математики корпорации RAND.
Взрыв числа маршрутов
Зафиксируйте начальный город. Для следующего города есть n − 1 вариантов, для следующего за ним — n − 2 и так далее, а каждый маршрут можно проехать в двух направлениях, поэтому всего маршрутов (n − 1)! / 2. Для 10 городов это 181 440 — для компьютера пустяк. Для 20 — около 6 × 10¹⁶, а для 70 это больше числа атомов в наблюдаемой Вселенной. Более быстрые компьютеры мало помогают: каждый дополнительный город увеличивает работу примерно в n раз.
NP-трудность
В 1972 году Ричард Карп показал, что вопрос о том, есть ли в графе замкнутый маршрут через все вершины — гамильтонов цикл, — относится к семейству NP-полных задач, которые все одинаково трудны. Задача коммивояжёра содержит его в себе, поэтому она NP-трудна. Быстрый метод для неё дал бы быстрые методы для тысяч других задач в планировании, логистике и криптографии. Существует ли такой метод — это вопрос о равенстве P и NP, одна из задач тысячелетия.
Точный метод: Хелд — Карп
В 1962 году Майкл Хелд и Ричард Карп, а независимо от них Ричард Беллман, применили динамическое программирование. Для каждого множества городов S и каждого города j из S вычисляется кратчайший путь, который начинается в домашнем городе, посещает ровно города из S и заканчивается в j. Каждое значение получается из значений для S без j, поэтому таблица заполняется от малых множеств к большим, а кратчайший маршрут получается в конце. Требуется около n² · 2ⁿ шагов вместо n!, что для 30 городов означает разницу между минутами и возрастом Вселенной, но рост всё равно экспоненциальный.
Быстрые правила построения
Ближайший сосед всегда едет в ближайший ещё не посещённый город. Это просто и быстро, но метод склонен оставлять в стороне несколько городов, за которыми в конце приходится ехать долгими крюками, поэтому его маршруты обычно примерно на 25 % длиннее лучших. Методы вставки, напротив, поддерживают замкнутую петлю и добавляют оставшиеся города по одному туда, где это обходится дешевле всего. В 1976 году Никос Кристофидес нашёл способ построения, который на любой метрической карте гарантированно даёт не более чем в 1,5 раза больше оптимума; эта оценка почти не улучшалась больше сорока лет.
Улучшение маршрута: 2-opt
Локальный поиск начинает с любого маршрута и раз за разом вносит небольшие изменения, которые его укорачивают. Классический ход 2-opt удаляет два ребра и соединяет два куска по-другому, разворачивая участок между ними. Когда два ребра пересекаются, этот ход распутывает их и экономит длину, поэтому маршрут, который 2-opt не может улучшить, никогда не пересекает сам себя. На случайных картах маршруты 2-opt обычно примерно на 5 % длиннее оптимума. Более сильные ходы, меняющие три ребра, или метод переменной глубины Лина и Кернигана 1973 года подбираются ещё ближе.
Имитация отжига
Локальный поиск может застрять на маршруте, где каждый отдельный ход только ухудшает дело, хотя существует гораздо лучший маршрут. Имитация отжига, которую применили к этой задаче Скотт Киркпатрик, Дэниел Гелатт и Марио Векки в 1983 году, заимствует идею из металлургии: она принимает ухудшающий ход с вероятностью, зависящей от температуры, которая сначала высока, а затем медленно снижается. Вначале маршрут свободно блуждает, в конце принимаются только улучшения. При достаточно медленном охлаждении метод надёжно находит очень хорошие маршруты.
Попробуйте сами
Откройте демонстрацию задачи коммивояжёра, чтобы расставить до 200 городов случайно, по окружности, скоплениями, по сетке или там, где вы щёлкнете. Посмотрите, как ближайший сосед оставляет в стороне последние города, как 2-opt распутывает каждое пересечение, следите за температурой имитации отжига по мере охлаждения и дайте алгоритму Хелда — Карпа доказать кратчайший маршрут для числа городов до 12. «Сравнить все» запускает все методы на одной карте и показывает, насколько каждый маршрут длиннее кратчайшего найденного.
Часто задаваемые вопросы
Где применяется задача коммивояжёра?
Везде, где нужно обойти много мест в эффективном порядке: в маршрутах доставки и сбора, в траектории сверла или лазера над печатной платой, в порядке, в котором телескоп наблюдает звёзды, в порядке комплектации заказов на складе и, с другими расстояниями, в порядке фрагментов при сборке последовательности ДНК.
Какая самая большая задача решена точно?
В 1954 году Джордж Данциг, Рэй Фалкерсон и Селмер Джонсон доказали кратчайший маршрут через 49 городов США. В 2006 году решатель Concorde Дэвида Эпплгейта, Роберта Биксби, Вашека Хватала и Уильяма Кука после многих лет машинного времени доказал оптимальный маршрут через 85 900 точек из проекта микросхемы.
Всегда ли кратчайший маршрут обходится без пересечений?
Да, на плоской карте с расстояниями по прямой. Если бы два ребра пересекались, замена их двумя сторонами образованного ими четырёхугольника укоротила бы маршрут, поэтому маршрут с пересечением не может быть кратчайшим.
Дают ли эвристики каждый раз один и тот же маршрут?
Ближайший сосед, дешёвая вставка и 2-opt в том виде, в каком они используются здесь, детерминированы: на одних и тех же городах они дают один и тот же маршрут. Имитация отжига начинает со случайного маршрута и делает случайные ходы, поэтому два запуска могут закончиться разными маршрутами, обычно почти одинаковой длины.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Открыть демонстрацию задачи коммивояжёра