Вы использовали алгоритм коммивояжера для решения проблемы?
Я изучал TSP в колледже в контексте NP Полнота. У меня никогда не было ситуации, когда это применимо к практической проблеме. Небольшое исследование показывает, что он использовался, чтобы выбрать самый дешевый путь для перемещения сверла, в котором есть отверстия в платах. Это почти все, что я мог найти.
Вы используете это? Какие еще практические применения есть у TSA?
14 ответов
Как и в случае с другими в этой теме, я построил решение полной проблемы NP в колледже (это был сторонний проект для друга) - программу планирования. В то время, когда я согласился поработать над его проблемой, я не знал, чем закончен NP. Позже я понял, что придумал довольно неплохую эвристику для решения проблемы, но, конечно, реальная хитрость заключалась в том, чтобы знать, когда сказать пользователю, что решения не существует, и он чрезмерно ограничил проблему.
Это был отличный способ объединить мои возможные теоретические занятия и реальный мир.
Опять же, эвристика и "достаточно близко", как правило, хороши для реальных применений, где предпочтение отдается почти оптимальным решениям из-за стоимости поиска и реализации идеального решения.
Однажды мне было дано задание написать программу для равномерного заполнения прямоугольной области "волнистой линией" - изогнутой линией, которая не пересекается. Моей первой попыткой было сгенерировать случайные точки внутри прямоугольника и попытаться найти их обход (не обязательно самый короткий). К сожалению, этот подход просто не сработал, и я отказался от него.
Я решил проблему в конце концов, хотя:
Мой успешный метод не был связан с TSP, но для любопытных я суммирую его:
Начните с одного отрезка. Теперь цикл: если строка "слишком длинная", разделите ее на две части. Перемещайте каждую точку немного случайно, но заставляйте точки отталкивать друг друга. Завершите цикл, когда будет достигнут небольшой прогресс. Есть детали, но, надеюсь, вы поняли идею.
Конечно, это дает угловой путь (что было бы приемлемо), но углы легко превратить в гладкие дуги.
И да, я сохранил код.
Я никогда не использовал его лично, но кроме буровых плат, есть еще одно приложение, если вы хотите пойти в разные места, скажем, продавать пылесосы. Вы можете использовать решение проблемы, чтобы решить, какой самый дешевый способ побывать везде везде ровно один раз.
Знание того, когда проблема NP-трудна, полезно для исключения решений, связанных с ее решением. Всякий раз, когда вы видите, что TSP (или любая другая NP-трудная проблема) поднимает уродливую голову за проблемы нетривиального размера, вы знаете, что идете по неверному пути. Мало того, что вы это знаете, но вы знаете, почему, и можете с уверенностью сказать своему боссу / товарищу по команде / кому-либо.
При этом http://en.wikipedia.org/wiki/CONCORDE показывает, что:
Concorde был применен к задачам картирования генов,[1] предсказания функции белка,[2] маршрутизации транспортных средств,[3] преобразования растровых изображений в непрерывные линейные чертежи,[4] планирования движения судов для сейсмических исследований,[5] и в изучение скейлинговых свойств комбинаторных задач оптимизации.[6]
Да, я использую его в приложении Geocaching для планирования маршрута.
В настоящее время он использует прямое расстояние между точками, но должен правильно (когда я дохожу до него) использовать дороги для расчета расстояний между точками.
Большую часть времени вы не хотите использовать алгоритм, который решает проблему NP-Complete/Hard. Вы просто хотите алгоритм, который "достаточно хорош". Они обычно основаны на эвристике и дают разумные приближения.
У меня была одна проблема, которая была экземпляром Independent-Set (NP-Complete), но я нашел жадный алгоритм, который давал довольно хорошие результаты в подавляющем большинстве случаев и имел эффективное время выполнения.
TSP - это привет мир NP-проблем. В его чисто канонической форме вы не будете часто встречать его в дикой природе ( демоверсии, подобные этой, не включены), но огромное подмножество неполных задач NP связано или даже основано на TSP, например:
- Маршруты транспортных средств (включая маршрутизацию грузовых автомобилей)
- Авиакомпания / Маршрут полета
- Маршрут поезда
- Трасса машины для горнолыжного спуска
Каждый из них имеет дополнительные, специфичные для домена ограничения, которые затрудняют их решение. Так что TSP - это хорошее введение в комплексные задачи NP, чтобы понять их природу.
Немногие проблемы в реальной жизни соответствуют тому, что вы изучаете на уроке математики. Задачи упрощены и абстрагированы, так что вы можете видеть математику, а не отвлекаться на детали. Как вы уже упоминали, лучший реальный пример больших провайдеров TSP на самом деле не связан с каким-либо коммивояжером: он включает машины планирования, у которых есть задания для выполнения с зависящим от последовательности временем установки. Это включает в себя машины, на которых рука перемещает инструмент по разным участкам, а также некоторые приложения для рисования (красный-> оранжевый-> желтый легче, чем красный-> желтый-> оранжевый). Есть также некоторые приложения в рентгеновской кристаллографии, где вы должны ориентировать образец кристалла под несколькими разными углами.
Множество типов оптимизированных заказов, таких как сбор из автопарка, доставка посылок ИБП и т. Д., Где требования обхода узла могут быть выражены в одном измерении усилий, таких как время или расстояние.
Эта компания была основана на улучшенном алгоритме TSP.
Среди прочих проблем они направляют монтажников и ремонтников кабельного телевидения в Нью-Йорк.
Поскольку люди обычно могут решать проблемы TSP на равных или лучше, чем большинство алгоритмов для карт с 20-60 узлами, не очень часто компьютер решает эту проблему. Когда стоимость достаточно высока, компьютер может получить улучшение на 1-2% по сравнению с человеком, что может стоить затрат на выполнение расчетов. Если маршрут не изменится, то можно будет потратить некоторое время на его оптимизацию. Это часто встречается в интегральных схемах.
Веб-сайты авиакомпаний используют специализированную версию проблемы TSP, когда показывают список авиакомпаний и цены для каждого маршрута. Разница заключается не в расстоянии, а в оптимизации затрат и, конечно, нет необходимости посещать каждый город один раз! Скажем, вы хотите лететь из LGA в LAX. Там около 1/2 десятка прямых маршрутов и бесконечное количество других маршрутов. Он может предложить LGA->ORD->LAX или LGA->DWF->LAX. Люди, которые могут вручную оценивать маршруты, иногда могут найти более низкие тарифы, чем те, которые искали туристические сайты. Как правило, людям не нужно более двух соединений, но нет верхнего предела количества соединений для данного рейса.
Я использовал его для определения маршрутов для моей iPhone-игры "Путешественник-продавец". Что интересно, люди очень хорошо решают кратчайший маршрут, но не решают самый длинный маршрут. Самые длинные и короткие маршруты имеют одинаковую сложность, но люди, кажется, обучены, чтобы иметь возможность находить самые короткие маршруты, часто быстрее и лучше, чем то, что может сделать компьютер.
На моей первой работе мы создали приложение для планирования домашнего ухода.
Мы решили задачу TSP с некоторыми нелинейными временными ограничениями и с дополнительной нелинейной функцией стоимости.
Мы использовали неоптимальный решатель для решения проблемы.
Насколько я знаю, я не использовал TSP, но работал над несколькими автономными роботами, чтобы пройти через лабиринт. Поэтому мне интересно, можно ли использовать TSP для решения лабиринтов.
Разве Google Maps (и любое другое программное обеспечение для маршрутизации на основе карт) не будет использовать какого-либо коммивояжера для определения направления движения?