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