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

Я не использовал TSP, насколько я знаю, но я работал в ряде автономных роботов для пересечения лабиринта. Так интересно, мог ли TSP быть применен к решению лабиринта.

Немного проблем в реальной жизни соответствуют материалу, который Вы изучаете в математическом классе. Проблемы упрощены и абстрагированы так, чтобы Вы видели математику, и не отвлечены деталями. Лучший реальный пример большого TSPs, как Вы упомянули, на самом деле не вовлекает коммивояжера: это включает машины планирования, которые имеют задания для выполнения с зависимое от последовательности время установки . Это включает машины, куда рука перемещает инструмент вокруг различных сайтов, и также некоторые приложения рисования (красный-> оранжевый-> желтый легче, чем красный-> желтый-> оранжевый). Существуют также некоторые приложения в кристаллография рентгеновского луча , где необходимо ориентировать некоторый образец кристалла под несколькими различными углами.

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

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

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

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

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

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

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

, Что, будучи упомянутым http://en.wikipedia.org/wiki/CONCORDE показывает что:

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

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

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

я действительно решал проблему в конце хотя:

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

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

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

И да я действительно сохранял код.

Много типов оптимизированного упорядочивания, таких как погрузка автобазы, доставка пакета UPS, и т.д. везде, где требования обхода узла могут быть выражены в одном размере усилия, такого как время или расстояние.

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

http://www.pointserve.com/

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

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

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

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

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

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

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

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

Обычно люди не хотят больше двух подключений, но нет верхнего предела количества подключений для данного рейса.

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

Обычно люди не хотят больше двух подключений, но нет верхнего предела количества подключений для данного рейса.

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

но не при решении самого длинного маршрута. Самый длинный и самый короткий маршруты имеют одинаковую сложность, но люди, кажется, обучены находить самые короткие маршруты, часто быстрее и лучше, чем компьютер.

но не при решении самого длинного маршрута. Самый длинный и самый короткий маршруты имеют одинаковую сложность, но люди, кажется, обучены находить самые короткие маршруты, часто быстрее и лучше, чем компьютер.

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