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

Question

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

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

Answer 1

На моей первой работе мы создали приложение для планирования домашнего ухода.
Мы решили задачу TSP с некоторыми нелинейными временными ограничениями и с дополнительной нелинейной функцией стоимости.
Мы использовали неоптимальный решатель для решения проблемы.

Answer 2

Поскольку люди обычно могут решать проблемы TSP на равных или лучше, чем большинство алгоритмов для карт с 20-60 узлами, не очень часто компьютер решает проблему. Когда стоимость достаточно высока, компьютер может получить улучшение на 1-2% по сравнению с человеком, что может стоить затрат на выполнение расчетов. Если маршрут не меняется, то можно оправдать трату времени на его оптимизацию. Это часто встречается в интегральных схемах.

Веб-сайты авиакомпаний используют специализированную версию проблемы TSP, когда показывают список авиакомпаний и цены для каждого маршрута. Разница заключается не в расстоянии, а в оптимизации затрат и, конечно, нет необходимости посещать каждый город один раз! Скажем, вы хотите лететь из LGA в LAX. Там около 1/2 десятка прямых маршрутов и бесконечное количество других маршрутов. Он может предложить LGA-> ORD-> LAX или LGA-> DWF-> LAX. Люди, которые могут вручную оценивать маршруты, иногда могут найти более низкие тарифы, чем те, которые искали туристические сайты. Как правило, людям не нужно больше двух соединений, но нет верхнего предела количества соединений для данного рейса.

Я использовал его для определения маршрутов для моей Путешественника-продавца iPhone Game . Что интересно, люди очень хорошо решают кратчайший маршрут, но не решают самый длинный маршрут. Самые длинные и короткие маршруты имеют одинаковую сложность, но люди, кажется, обучены тому, чтобы находить самые короткие маршруты, часто быстрее и лучше, чем то, что может сделать компьютер.

Answer 3

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

Answer 4

Разве Google Maps (и все остальные программы маршрутизации на основе карт) не будут использовать какого-либо коммивояжера для определения направления движения?