Использовали ли вы алгоритм коммивояжера для решения какой-либо проблемы?
https://stackoverflow.com/questions/264050
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я изучал TSP в колледже в контексте полноты NP.На самом деле у меня никогда не было ситуации, когда это было бы применимо к практической проблеме.Небольшое исследование показывает, что оно использовалось для выбора самого дешевого способа перемещения дрели, то есть для проделывания отверстий в печатных платах.Это практически все, что я смог найти.
Вы им пользуетесь?Какие еще практические применения имеет TSA?
Решение
Как и в случае с другими в этой теме, я построил решение полной проблемы NP в колледже (это был сторонний проект для друга) - программу планирования. В то время, когда я согласился поработать над его проблемой, я не знал, чем закончен NP. Позже я понял, что придумал довольно неплохую эвристику для решения проблемы, но, конечно, реальная хитрость заключалась в том, чтобы знать, когда сказать пользователю, что решения не существует, и он чрезмерно ограничил проблему.
Это был отличный способ объединить мои возможные теоретические занятия и реальный мир.
Опять же эвристика и "достаточно близко" обычно подходят для реальных применений, где предпочтение отдается почти оптимальным решениям из-за стоимости поиска и реализации идеального решения.
Другие советы
Однажды мне было поручено написать программу, которая бы достаточно равномерно заполняла прямоугольную область с помощью "squiggle". - изогнутая линия, которая не пересекается. Моей первой попыткой было сгенерировать случайные точки внутри прямоугольника и попытаться найти их обход (не обязательно самый короткий). К сожалению, этот подход просто не сработал, и я отказался от него.
Я решил проблему в конце концов:
Мой успешный метод не был связан с TSP, но для любопытных я суммирую его:
Начните с одного отрезка. Цикл «Теперь»: если строка «слишком длинная», разделите ее на две части. Перемещайте каждую точку немного случайно, но заставляйте точки отталкивать друг друга. Завершите цикл, когда будет достигнут небольшой прогресс. Есть детали, но, надеюсь, вы поняли идею.
Конечно, это дает угловой путь (что было бы приемлемо), но углы легко превратить в гладкие дуги.
И да, я сохранил код.
Я никогда не использовал его лично, но кроме буровых плат, есть еще одно приложение, если вы хотите пойти в разные места, скажем, продавать пылесосы. Вы можете использовать решение проблемы, чтобы выбрать самый дешевый способ посещения везде ровно один раз.
Знание, когда проблема является NP-трудной, полезно исключить решения, включающие решение этой проблемы. Всякий раз, когда вы видите, что TSP (или любая другая NP-трудная проблема) поднимает свою уродливую голову за проблемы нетривиального размера, вы знаете , что идете по неверному пути. Мало того, что вы знаете это, но вы знаете почему , и можете с уверенностью сказать своему боссу / товарищу по команде / любому.
При этом http://en.wikipedia.org/wiki/CONCORDE показывает, что
Конкорд был применен к проблемам генного картирования, [1] функция белка прогноз, [2] автомобильный маршрут, [3] преобразование растровых изображений в непрерывные линейные рисунки, [4] планирование движения судов для сейсмики обзоры, [5] и при изучении скейлинговые свойства комбинаторных задачи оптимизации. [6]
Да, я использую его в приложении Geocaching для планирования маршрута.
В настоящее время он использует прямое расстояние между точками, но должен правильно (когда я до него дохожу) использовать дороги для расчета расстояний между точками.
В большинстве случаев вы не хотите использовать алгоритм, который решает проблему NP-Complete / Hard. Вы просто хотите, чтобы алгоритм был "достаточно хорош". Они обычно основаны на эвристике и дают разумные приближения.
У меня была одна проблема, которая была экземпляром Independent-Set (NP-Complete), но я нашел жадный алгоритм, который давал довольно хорошие результаты в подавляющем большинстве случаев и имел эффективное время выполнения.
Множество типов оптимизированных заказов, таких как сбор из автопарка, доставка посылок ИБП и т. д., где требования обхода узла могут быть выражены в одном измерении усилий, таких как время или расстояние.
Чайная ложка - это привет, мир из 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 с некоторыми нелинейными временными ограничениями и с дополнительной нелинейной функцией стоимости.
Мы использовали неоптимальный решатель для решения проблемы.
Разве Google Maps (и все остальные программы маршрутизации на основе карт) не используют какого-либо коммивояжера для определения направления движения?
Насколько я знаю, я не использовал TSP, но работал над несколькими автономными роботами, чтобы пройти через лабиринт. Поэтому мне интересно, можно ли использовать TSP для решения лабиринтов.
