Что такое проблема коммивояжера?
Задача коммивояжера - это классическая задача информатики, которая, как известно, не имеет эффективного решения.
Почему это должно меня беспокоить?
Есть много реальных проблем, которые очень похожи на задачу коммивояжера.
Изучение подобных проблем поможет вам распознать, когда вы сталкиваетесь с чем-то столь же трудным для решения.
Через 5 минут или меньше
Это «Задача коммивояжера» (или TSP): « Учитывая список городов, какой самый короткий маршрут проходит через каждый город один раз, а затем возвращается в исходный город?»
Это звучит просто, но когда мы добавляем достаточное количество городов, компьютер становится невозможным для решения в реалистичные временные рамки.
Посмотрим почему.
Подход «грубой силы».
Есть только один способ найти кратчайшее решение проблемы коммивояжера, мы должны попробовать все возможные варианты по очереди.
Мы возьмем простой пример, четыре города:
Мы начнем с A. Мы можем перейти к B, C или D. Давайте представим, что мы перейдем к B. Оттуда у нас есть возможность посетить C или D. Как только мы доберемся до любого из них, мы затем отправляйтесь в оставшийся город, прежде чем вернуться в A.
Подведя итог: из нашего первого города у нас есть на выбор 3 варианта, куда пойти дальше. Как только мы выберем один из них, у нас будут останется 2 города на выбор. И наконец остался только 1 город.
Это означает, что общее количество маршрутов, которые мы должны попробовать, равно 3 x 2 x 1 = 6.
Теперь добавим еще один город E:
Как только мы выберем место для начала, у нас теперь есть выбор из 4 других городов для посещения. Из каждого из них мы должны выбрать один из оставшихся 3, чтобы посетить следующий. Из каждого из них есть 2 города на выбор ... вы поняли идею.
Количество возможных перестановок для пяти городов равно 4 x 3 x 2 x 1 = 24. Мы добавили один город, но теперь их количество в четыре раза больше!
Некоторые из этих маршрутов дублируются (мы путешествуем по тому же маршруту, но в обратном направлении), поэтому их можно не учитывать. Но это нам не особо помогает, так как количество возможных маршрутов по-прежнему будет расти очень быстро.
Имея всего 10 городов, существует 181 440 возможных маршрутов. Добавьте еще один, и теперь их более 1,8 миллиона. К тому времени, когда мы доберемся всего до 15 городов, существует более 43 миллиардов возможных маршрутов!
При достаточном количестве городов количество маршрутов становится настолько большим, что мы просто не можем рассчитать его в разумные сроки.
Существует относительно более эффективный метод вычисления всех возможных перестановок с использованием динамического программирования, но это не имеет значения - он все равно становится слишком медленным при масштабировании.
«Решение» TSP
Поскольку мы не можем по-настоящему решить эту проблему, лучшее, что мы можем сделать, - это найти хорошее приближение.
Один из способов сделать это - использовать метод ближайшего соседа:
Начиная со случайного города, выберите ближайший город и отправляйтесь туда. Продолжайте выбирать ближайший город, пока не посетите их все один раз, прежде чем вернуться к исходной точке.
Это простейший алгоритм для поиска приближенного решения, но есть и другие алгоритмы (различной сложности), которые обычно позволяют находить более короткие маршруты.
До недавнего времени лучшим был алгоритм, разработанный в 1976 году Никосом Христофидесом.
Алгоритм Кристофидеса способен находить решения, которые не более чем на 50% длиннее «идеального» путешествия.
В 2019 году Карлин, Кляйн и Овейс Гаран доказали, что алгоритм, первоначально разработанный в 2010 году, на самом деле может превзойти алгоритм Христофидеса на крошечные доли процента.
Это может показаться незначительным, но это доказывает, что можно улучшить этот алгоритм, и открывает дверь для новых решений.
TSP в маскировке
Легко отклонить задачу коммивояжера как чисто академическую задачу, неприменимую к повседневному развитию. Однако это имеет последствия для реального мира.
«Доставка на последнюю милю» является наиболее часто используемым примером. Это процесс доставки чего-либо из транспортного узла в конечный пункт назначения. Например, грузовик Amazon доставляет сотни посылок по домам.
Однако если присмотреться, другие проблемы начинают напоминать TSP:
- Как быстрее всего собрать товар на складе для выполнения заказа?
- Как мы можем спланировать маршрут автобуса, чтобы посетить все остановки в кратчайшие сроки / расстояние?
- Какой самый короткий способ проложить проводку в электрическом компоненте?
Нужно рассчитать все возможные перестановки вещей в коллекции? Это очень похоже на задачу коммивояжера.
