Вы использовали алгоритм коммивояжера для решения проблемы?

Question

Я изучал TSP в колледже в контексте NP Completenness. У меня никогда не было ситуации, когда это применимо к практической проблеме. Небольшое исследование показывает, что он использовался, чтобы выбрать самый дешевый путь для перемещения сверла, в котором есть отверстия в платах. Это почти все, что я мог найти.

Вы используете это? Какие еще практические применения есть у TSA?

Answer 1

Однажды мне было дано задание написать программу для равномерного заполнения прямоугольной области "волнистой линией" - изогнутой линией, которая не пересекается. Моей первой попыткой было сгенерировать случайные точки внутри прямоугольника и попытаться найти их обход (не обязательно самый короткий). К сожалению, этот подход просто не сработал, и я отказался от него.

В конце концов я решил проблему:

Мой успешный метод не был связан с TSP, но для любопытных я суммирую его:

Начните с одного отрезка. Теперь цикл: если строка «слишком длинная», разделите ее на две части. Перемещайте каждую точку немного случайно, но заставляйте точки отталкивать друг друга. Завершите цикл, когда будет достигнут небольшой прогресс. Есть детали, но, надеюсь, вы поняли.

Конечно, это дает угловой путь (что было бы приемлемо), но углы легко превратить в гладкие дуги.

И да, я сохранил код.

Answer 2

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

То, что сказано http://en.wikipedia.org/wiki/CONCORDE показывает, что:

Конкорд был применен к проблемам генного картирования, [1] функция белка прогноз, [2] автомобильный маршрут, [3] преобразование растровых изображений в непрерывные линейные рисунки, [4] планирование движения судов для сейсмики обзоры, [5] и при изучении скейлинговые свойства комбинаторных задачи оптимизации. [6]

Answer 3

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

Answer 4

Да, я использую его в приложении Geocaching для планирования маршрута.

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

http://code.google.com/p/gpsturbo/

Answer 5

В большинстве случаев вы не хотите использовать алгоритм, который решает проблему NP-Complete / Hard. Вы просто хотите алгоритм, который "достаточно хорош". Они обычно основаны на эвристике и дают разумные приближения.

У меня была одна проблема, которая была экземпляром Independent-Set (NP-Complete), но я нашел жадный алгоритм, который давал довольно хорошие результаты в подавляющем большинстве случаев и имел эффективное время выполнения.

Answer 6

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

• Маршрут транспортного средства (включая маршрут грузового автомобиля)
• Авиакомпания / Маршрут полета
• Маршрут поезда
• Маршрутная машина для горнолыжного спуска

У каждого из них есть дополнительные, специфичные для домена ограничения, которые затрудняют их решение. Так что TSP - это хорошее введение в комплексные проблемы NP, чтобы понять их природу.

Answer 7

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

Это был отличный способ соединить мои возможные теоретические занятия и реальный мир.

Опять же, эвристика и "достаточно близко", как правило, хороши для реальных применений, где предпочтение отдается почти оптимальным решениям из-за стоимости поиска и реализации идеального решения.

Answer 8

Множество типов оптимизированных заказов, таких как сбор из автопарка, доставка посылок ИБП и т. Д., Где требования к обходу узла могут быть выражены в одном измерении усилий, таких как время или расстояние.

Answer 9

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

http://www.pointserve.com/

Они направляют монтажников и ремонтников кабельного телевидения вокруг Нью-Йорка среди других проблем.

Answer 10

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