Задача коммивояжёра: NP-трудная проблема комбинаторной оптимизации

Введение

NP-трудная задача в комбинаторной оптимизации

Проблема коммивояжера, также известная как задача коммивояжера (TSP), ставит следующий вопрос: "Имея список городов и расстояния между каждой парой городов, каков кратчайший возможный маршрут, который посещает каждый город ровно один раз и возвращается в исходный город?" Это NP-трудная задача в комбинаторной оптимизации, важная в теоретической информатике и исследованиях операций. Проблема путешествующего покупателя и задача маршрутизации транспортных средств являются обобщениями TSP. В теории вычислительной сложности, версия TSP о разрешимости (где задана длина L, и требуется определить, существует ли в графе тур длиной не более L) принадлежит к классу NP-полных задач. Следовательно, возможно, что время работы в худшем случае для любого алгоритма для TSP растет суперполиномиально (но не более чем экспоненциально) с увеличением числа городов. Проблема была впервые сформулирована в 1930 году и является одной из наиболее интенсивно изучаемых задач в области оптимизации. Она используется в качестве эталона для многих методов оптимизации. Несмотря на вычислительную сложность задачи, известно множество эвристических и точных алгоритмов, позволяющих полностью решить некоторые экземпляры с десятками тысяч городов, и даже приближенно решить проблемы с миллионами городов с точностью до небольшой доли процента. TSP имеет несколько применений даже в своей чистейшей формулировке, например, в планировании, логистике и производстве микросхем. В слегка модифицированном виде она возникает как подзадача во многих областях, таких как секвенирование ДНК. В этих приложениях понятие "город" представляет, например, клиентов, точки пайки или фрагменты ДНК, а понятие "расстояние" – время или стоимость перемещения или меру сходства между фрагментами ДНК. TSP также встречается в астрономии, поскольку астрономы, наблюдающие множество источников, стремятся минимизировать время, затрачиваемое на перемещение телескопа между источниками; в таких задачах TSP может быть встроена в задачу оптимального управления. Во многих приложениях могут быть наложены дополнительные ограничения, такие как ограниченные ресурсы или временные окна.

История

Истоки проблемы коммивояжёра не ясны. В руководстве для путешествующих торговцев 1832 года упоминается проблема и приводятся примерные маршруты по Германии и Швейцарии, но отсутствует математическое рассмотрение. Математическая формулировка TSP была дана в XIX веке ирландским математиком Уильямом Роуэном Гамильтоном и британским математиком Томасом Киркманом. Икозианская игра Гамильтона представляла собой развлекательную головоломку, основанную на поиске гамильтонова цикла. Общая форма TSP, по-видимому, впервые была изучена математиками в 1930-х годах в Вене и Гарварде, в частности Карлом Менгером, который определяет проблему, рассматривает очевидный алгоритм полного перебора и отмечает неоптимальность эвристики ближайшего соседа: мы обозначаем «проблемой посыльного» (поскольку на практике этот вопрос должен решаться каждым почтальоном, а также многими путешественниками) задачу нахождения кратчайшего маршрута, соединяющего конечное множество точек, для которых известны попарные расстояния между ними. Конечно, эту проблему можно решить конечным числом попыток. Правила, позволяющие сократить число попыток по сравнению с числом перестановок заданных точек, неизвестны. Правило, согласно которому следует сначала двигаться от начальной точки к ближайшей к ней, затем к ближайшей к этой и так далее, как правило, не приводит к кратчайшему маршруту. Впервые математически проблема была рассмотрена в 1930-х годах Мерриллом М. Флаудом, который искал решение задачи маршрутизации школьных автобусов. Хасслер Уитни из Принстонского университета проявил интерес к проблеме, которую он назвал «проблемой 48 штатов». Самая ранняя публикация, использующая фразу «проблема коммивояжёра», — это отчёт RAND Corporation 1949 года Джулии Робинсон «Об игре Гамильтона (проблема коммивояжёра)». В 1950-х и 1960-х годах проблема приобрела всё большую популярность в научных кругах Европы и США после того, как корпорация RAND в Санта-Монике предложила призы за успехи в её решении. Алгоритм Кристофидеса-Сердюкова даёт решение, которое в худшем случае не более чем в 1,5 раза превышает оптимальное решение. Поскольку алгоритм был простым и быстрым, многие надеялись, что он уступит место почти оптимальному методу. Однако эта надежда на улучшение не реализовалась сразу, и алгоритм Кристофидеса-Сердюкова оставался методом с наилучшим худшим сценарием до 2011 года, когда был разработан (незначительно) улучшенный алгоритм аппроксимации для подмножества «графических» TSP. В 2020 году это незначительное улучшение было распространено на полный (метрический) TSP. Ричард М. Карп в 1972 году показал, что задача гамильтонова цикла является NP-полной, что подразумевает NP-трудность TSP. Это дало математическое объяснение кажущейся вычислительной сложности поиска оптимальных маршрутов. Значительный прогресс был достигнут в конце 1970-х и 1980-х годах, когда Гретшелю, Падбергу, Ринальди и другим удалось точно решить экземпляры с 2392 городами, используя методы отсечений и ветвей и границ. В 1990-х годах Апплегейт, Биксби, Чватал и Кук разработали программу Concorde, которая использовалась во многих недавних рекордных решениях. Герхард Райнельт опубликовал TSPLIB в 1991 году — сборник эталонных экземпляров различной сложности, который использовался многими исследовательскими группами для сравнения результатов. В 2006 году Кук и другие вычислили оптимальный маршрут для экземпляра в 85 900 городов, заданного задачей компоновки микросхем, что в настоящее время является самым крупным решённым экземпляром TSPLIB. Для многих других экземпляров с миллионами городов можно найти решения, гарантированно отличающиеся от оптимального маршрута не более чем на 2–3%.

В качестве задачи графа

TSP может быть смоделирована как неориентированный взвешенный граф, где города являются вершинами графа, маршруты – ребрами графа, а расстояние между городами – весом ребра. Это задача минимизации, начинающаяся и заканчивающаяся в заданной вершине после посещения каждой другой вершины ровно один раз. Часто модель представляет собой полный граф (то есть, каждая пара вершин соединена ребром). Если между двумя городами нет прямого пути, то добавление достаточно длинного ребра позволит построить полный граф, не изменив оптимальный маршрут.

Асимметричные и симметричные

В симметричной задаче коммивояжера (TSP) расстояние между двумя городами одинаково в обоих направлениях, что формирует неориентированный граф. Эта симметрия сокращает количество возможных решений вдвое. В асимметричной задаче коммивояжера (TSP) пути могут отсутствовать в одном или обоих направлениях, либо расстояния могут различаться, что формирует ориентированный граф. Факторы реального мира, такие как пробки, одностороннее движение и стоимость авиабилетов, зависящая от тарифов отправления и прибытия, могут привести к постановке задачи TSP в асимметричной форме.

Связанные проблемы

Эквивалентная формулировка с точки зрения теории графов: при заданном полном взвешенном графе (где вершины представляют города, ребра – дороги, а веса – стоимость или расстояние дороги), необходимо найти гамильтонов цикл с минимальным весом. Это более общая задача, чем задача о гамильтоновом пути, которая лишь спрашивает о существовании гамильтонова пути (или цикла) в неполном невзвешенном графе. Требование вернуться в исходный город не меняет вычислительную сложность задачи; см. задачу о гамильтоновом пути. Другая связанная задача – задача о путешествующем продавце с ограничением по пропускной способности: найти гамильтонов цикл во взвешенном графе с минимальным весом самого тяжелого ребра. Пример из реальной жизни – избежание узких улиц для больших автобусов. Задача имеет значительную практическую важность, помимо очевидных областей транспорта и логистики. Классический пример – производство печатных плат: планирование маршрута сверлильной машины для сверления отверстий в печатной плате. В робототехнических приложениях для обработки или сверления «городами» являются детали для обработки или отверстия (разных размеров) для сверления, а «стоимость перемещения» включает время на переналадку робота (задача последовательного выполнения работ на одном станке). Обобщенная задача о путешествующем продавце, также известная как «задача о путешествующем политике», рассматривает «штаты», которые имеют (один или несколько) «городов», и продавец должен посетить ровно один город из каждого штата. Одно из применений встречается при оптимизации раскроя материала для минимизации смены режущего инструмента. Другое связано с бурением в производстве полупроводников; например, Noon и Bean показали, что обобщенная задача о путешествующем продавце может быть преобразована в стандартную задачу TSP с тем же количеством городов, но с модифицированной матрицей расстояний. Задача последовательного упорядочения рассматривает проблему посещения набора городов, где существуют отношения предшествования между городами. Распространенный вопрос на собеседовании в Google – как маршрутизировать данные между узлами обработки данных; маршруты различаются по времени передачи данных, но узлы также отличаются вычислительной мощностью и объемом памяти, что усложняет проблему выбора места назначения данных. Задача о путешествующем покупателе рассматривает покупателя, которому поручено приобрести набор продуктов. Он может приобрести эти продукты в нескольких городах, но по разным ценам, и не во всех городах предлагаются одни и те же продукты. Цель состоит в том, чтобы найти маршрут между подмножеством городов, который минимизирует общую стоимость (стоимость проезда + стоимость покупки) и позволяет приобрести все необходимые продукты.

Формулировка Данциг Фулкерсон Джонсон

Пронумеруйте города числами 1, ..., n и определите: Пусть d_ij обозначает расстояние от города i до города j. Тогда задачу коммивояжера можно записать в виде следующей задачи целочисленного линейного программирования:

Последнее ограничение формулировки DFJ, называемое ограничением устранения подтуров, гарантирует, что никакое собственное подмножество Q не может образовать подтур, таким образом, решение представляет собой единый тур, а не объединение меньших туров. Поскольку это приводит к экспоненциальному количеству возможных ограничений, на практике задача решается методом генерации строк.

Эвристические и приблизительные алгоритмы

Разработаны различные эвристические и приближенные алгоритмы, которые позволяют быстро получать хорошие решения. К ним относится многофрагментный алгоритм. Современные методы способны находить решения для чрезвычайно больших задач (миллионы городов) за разумное время, которые с высокой вероятностью отличаются от оптимального решения всего на 2–3%. Это справедливо как для асимметричных, так и для симметричных задач о коммивояжере (TSP). Розенкранц и др. показали, что алгоритм NN имеет фактор приближения для экземпляров, удовлетворяющих неравенству треугольника. Вариация алгоритма NN, называемая оператором ближайшего фрагмента (NF), который соединяет группу (фрагмент) ближайших непосещенных городов, может находить более короткие маршруты с каждой итерацией. Оператор NF также может быть применен к исходному решению, полученному алгоритмом NN, для дальнейшего улучшения в элитарной модели, где принимаются только лучшие решения. Битонический тур множества точек – это монотонный многоугольник минимального периметра, вершины которого совпадают с этими точками; его можно эффективно вычислить с помощью динамического программирования. Другая конструктивная эвристика, Match Twice and Stitch (MTS), выполняет два последовательных сопоставления, при этом второе сопоставление выполняется после удаления всех ребер первого сопоставления, что приводит к набору циклов. Затем циклы сшиваются для получения конечного тура.

Алгоритм Кристофида и Сердюкова

Алгоритм Кристофида и Сердюкова имеет схожую структуру, но сочетает в себе минимальное остовное дерево с решением другой задачи — нахождением совершенного соответствия минимального веса. Это позволяет получить TSP-тур, длина которого не более чем в 1,5 раза превышает оптимальную. Он был одним из первых алгоритмов аппроксимации и во многом способствовал привлечению внимания к алгоритмам аппроксимации как к практическому подходу к сложным задачам. Фактически, термин "алгоритм" не сразу стал общепринятым для обозначения алгоритмов аппроксимации; алгоритм Кристофида изначально назывался эвристикой Кристофида.

k-opt эвристика, или эвристика Линн-Кернигана

Эвристика Линна–Кернигана является частным случаем V-оптики или переменной оптики. Она включает следующие шаги:

Для заданного тура удалите k взаимно непересекающихся ребер. Соберите оставшиеся фрагменты в тур, не допуская образования разрозненных подтуров (то есть, не соединяйте конечные точки фрагмента друг с другом). Это фактически упрощает рассматриваемую задачу коммивояжера (TSP) до гораздо более простой задачи. Каждая конечная точка фрагмента может быть соединена с 2k − 2 другими возможными точками: из 2k общего числа доступных конечных точек фрагмента, две конечные точки рассматриваемого фрагмента исключаются. Такую ограниченную задачу TSP на 2k городов можно затем решить методами полного перебора, чтобы найти рекомбинацию исходных фрагментов с наименьшей стоимостью. Наиболее популярным из методов k-opt является 3-opt, предложенный Шеном Лином из Bell Labs в 1965 году. Частным случаем 3-opt является ситуация, когда ребра не являются непересекающимися (два ребра смежны друг с другом). На практике часто удается добиться существенного улучшения по сравнению с 2-opt без комбинаторных затрат общего 3-opt, ограничивая 3 изменения специальным подмножеством, в котором два удаленных ребра смежны. Этот так называемый «два с половиной opt» обычно находится примерно посередине между 2-opt и 3-opt как с точки зрения качества получаемых туров, так и с точки зрения времени, необходимого для их построения.

V-opt эвристический

Метод переменного опта связан с методом k-опт и является его обобщением. В то время как методы k-опт удаляют фиксированное количество (k) ребер из исходного тура, методы переменного опта не фиксируют размер набора ребер, которые необходимо удалить. Вместо этого они расширяют этот набор по мере продолжения процесса поиска. Наиболее известным методом в этом семействе является метод Линна — Кернигана (упомянутый выше как ошибочное название для 2-опт). Шэнь Линь и Брайан Керниган впервые опубликовали свой метод в 1972 году, и он был самой надежной эвристикой для решения задач коммивояжера почти два десятилетия. Более продвинутые методы переменного опта были разработаны в Bell Labs в конце 1980-х годов Дэвидом Джонсоном и его исследовательской группой. Эти методы (иногда называемые Линн — Керниган — Джонсон) основаны на методе Линна — Кернигана, дополняя его идеями из табу-поиска и эволюционных вычислений. Базовая техника Линна — Кернигана гарантирует результаты не хуже 3-опт. Методы Линна — Кернигана — Джонсона вычисляют тур Линна — Кернигана, а затем изменяют тур посредством того, что было описано как мутация, удаляющая по крайней мере четыре ребра и пересоединяющая тур другим способом, после чего применяется V-опт к новому туру. Мутации часто достаточно, чтобы вывести тур из локального минимума, найденного методом Линна — Кернигана. Методы V-опт широко считаются наиболее мощными эвристиками для этой задачи и способны решать специальные случаи, такие как задача о гамильтоновом цикле и другие неметрические задачи о коммивояжере, в которых другие эвристики терпят неудачу. На протяжении многих лет метод Линна — Кернигана — Джонсона находил оптимальные решения для всех задач о коммивояжере, для которых было известно оптимальное решение, и находил лучшие известные решения для всех остальных задач о коммивояжере, на которых он был опробован.

Рандомизированное улучшение

Оптимизированные алгоритмы цепей Маркова, использующие локальный поиск в качестве эвристических подзадач, способны находить маршрут, крайне близкий к оптимальному, для 700–800 городов. Задача коммивояжера (TSP) служит лакмусовой бумажкой для многих универсальных эвристик, разработанных для комбинаторной оптимизации, таких как генетические алгоритмы, имитация отжига, поиск с запретами, оптимизация муравьиной колонией, динамика формирования рек (см. роевой интеллект) и метод перекрестной энтропии.

Сжатие вставки эвристика

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

Оптимизация муравьиной колонии

Исследователь в области искусственного интеллекта Марко Дориго в 1993 году описал метод эвристического поиска "хороших решений" для задачи коммивояжера (TSP) с использованием симуляции колонии муравьев, известной как ACS (система колонии муравьев). Она моделирует поведение, наблюдаемое у реальных муравьев при поиске кратчайших путей между источниками пищи и муравейником – эмерджентное поведение, возникающее из-за предпочтения каждого муравья следовать по феромонным следам, оставленным другими муравьями. ACS отправляет большое количество виртуальных агентов-муравьев для исследования множества возможных маршрутов на карте. Каждый муравей с определенной вероятностью выбирает следующий город для посещения, основываясь на эвристике, сочетающей расстояние до города и количество виртуального феромона, отложенного на ребре, ведущем в этот город. Муравьи исследуют местность, оставляя феромон на каждом ребре, которое они проходят, пока не завершат полный маршрут. После этого муравей, прошедший самый короткий маршрут, оставляет виртуальный феромон вдоль всего своего пути (глобальное обновление следа). Количество оставленного феромона обратно пропорционально длине маршрута: чем короче маршрут, тем больше феромона он оставляет.

Асимметричный

В большинстве случаев расстояние между двумя узлами в сети TSP одинаково в обоих направлениях. Случай, когда расстояние от A до B не равно расстоянию от B до A, называется асимметричной задачей коммивояжера (TSP). Практическим применением асимметричной задачи коммивояжера является оптимизация маршрутов с использованием дорожной сети (которая становится асимметричной из-за одностороннего движения, съездов, автомагистралей и т.п.).

Проблема аналитиков

В теории геометрических мер существует аналогичная проблема, которая формулируется следующим образом: при каких условиях подмножество E евклидова пространства может быть заключено в ректифицируемую кривую (то есть, когда существует кривая конечной длины, проходящая через каждую точку в E)? Эта проблема известна как задача о странствующем продавце для аналитиков.

Длина пути для случайных наборов точек в квадрате

Предположим, что – независимые случайные величины с равномерным распределением в квадрате , и пусть – длина кратчайшего пути (т.е. решение задачи коммивояжера) для этого набора точек, вычисленная по стандартному евклидову расстоянию. Известно, что почти наверное,

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

Верхняя граница

Один из них, и, следовательно, используя наивный путь, монотонно посещающий точки внутри каждого из слоев шириной в квадрате. Несколько результатов были доказаны, а затем улучшены Карлоффом (1987): Фитчер показал верхнюю оценку .

Комплексность вычислений

Было показано, что задача является NP-трудной (точнее, она полна для класса сложности FPNP; см. задачу о функциях), а версия задачи принятия решения ("при заданных стоимостях и числе x, определить, существует ли маршрут в обе стороны стоимостью меньше x") является NP-полной. Задача о путешествующем продавце с ограничениями также является NP-трудной. Задача остаётся NP-трудной даже в случае, когда города расположены на плоскости с евклидовыми расстояниями, а также в ряде других ограничивающих случаев. Отказ от условия посещения каждого города "только один раз" не снимает NP-трудность, поскольку в случае плоскости существует оптимальный маршрут, посещающий каждый город ровно один раз (иначе, согласно неравенству треугольника, более коротный путь, исключающий повторное посещение, не увеличит длину маршрута).

Сложность приближения

В общем случае, поиск кратчайшего маршрута коммивояжера является NP-полной задачей. Если мера расстояния является метрикой (и, следовательно, симметричной), задача становится APX-полной, и алгоритм Кристофидеса и Сердюкова приближает решение с точностью до 1,5. Лучший на сегодняшний день алгоритм, разработанный Верой Трауб и де, достигает коэффициента аппроксимации 75/74. Наилучшая известная нижняя граница неаппроксимируемости составляет 75/74. Соответствующая задача максимизации – поиск самого длинного маршрута коммивояжера – аппроксимируема с точностью до 63/38. Если функция расстояния симметрична, то самый длинный маршрут может быть приближен с точностью до 4/3 детерминированным алгоритмом и с точностью до рандомизированным алгоритмом.

Уровень эффективности человека и животных

TSP, в частности, евклидова версия задачи, привлекла внимание исследователей в области когнитивной психологии. Было замечено, что люди способны быстро находить почти оптимальные решения, демонстрируя производительность, близкую к линейной, которая варьируется от 1% менее эффективной для графов с 10–20 вершинами до 11% менее эффективной для графов с 120 вершинами. Очевидная легкость, с которой люди точно генерируют решения, близкие к оптимальным, побудила исследователей предположить, что люди используют одну или несколько эвристик, среди которых наиболее популярными являются гипотеза выпуклой оболочки и эвристика избежания пересечений. Однако, дополнительные данные свидетельствуют о том, что человеческая производительность весьма разнообразна, и на результаты влияют как индивидуальные различия, так и геометрия графа. Тем не менее, результаты показывают, что понимание и эмуляция методов, используемых людьми для решения этой задачи, могут улучшить производительность компьютеров в TSP, а также привели к новым представлениям о механизмах человеческого мышления. Первый выпуск журнала "Journal of Problem Solving" был посвящен теме человеческой производительности в TSP, а обзор 2011 года содержал список десятков статей по этой теме. Эти результаты согласуются с другими экспериментами, проведенными на не-приматах, которые показали, что некоторые из них способны планировать сложные маршруты. Это позволяет предположить, что не-приматы могут обладать относительно развитыми пространственными когнитивными способностями.

Натуральные вычисления

Когда амебоидному Physarum polycephalum представлена пространственная конфигурация источников пищи, он адаптирует свою морфологию для создания эффективного пути между ними, что также можно рассматривать как приближенное решение задачи коммивояжера (TSP).

Сравнительные показатели

Для проведения сравнительного анализа алгоритмов решения задачи коммивояжера (TSP) поддерживается библиотека TSPLIB, содержащая примеры экземпляров задачи TSP и смежных задач; см. внешнюю ссылку TSPLIB. Многие из этих экземпляров представляют собой списки реальных городов и компоновки реальных печатных плат.

Популярная культура

"Путешествующий торговец" режиссера Тимоти Ланзона – это история о четырех математиках, нанятых правительством США для решения самой сложной проблемы в истории компьютерной науки: P против NP. Решения этой проблемы используются математиком Бобом Бошем в таком поджанре, как TSP-арт.