Max Home IndustryЗадача коммивояжера важна, потому что она является NP-полной. Если вы можете найти быстрый способ ее решения, вы доказали, что P = NP и изменили лицо вычислений.
Последний результат показывает, что специальный тип задачи коммивояжера (TSP) разрешим за полиномиальное время.
Проблему TSP легко сформулировать, но сложно решить эффективно. Все, что вам нужно сделать, это найти кратчайший маршрут, по которому продавцу придется пройти, чтобы посетить каждый из n городов. Оказывается, не было найдено ни одного полиномиального алгоритма (т. Е. Времени, пропорционального nc, где c — константа).
Эта форма TSP — NP Hard, а версия решения, которая просто должна решить, есть ли решение лучше, чем предоставленный образец тура, — NP Complete.
Это означает, что решение версии решения за полиномиальное время обеспечит быстрое решение всех проблем NP. Это не только теоретически интересно, но и имеет практическое значение, поскольку криптография с открытым ключом зависит от отсутствия такого решения, поскольку оно основано на проблеме — факторизации больших чисел — которая также присутствует в NP.
Вы можете думать о TSP как о большой вычислительной проблеме информатики, но, несмотря на большой объем работы, не было достигнуто большого прогресса — если не считать особых случаев.
Евклидова форма задачи просто помещает города в сетку xy и позволяет продавцу путешествовать по кратчайшему маршруту между каждым городом, то есть как птица летит, а не по дорогам. Возможно, вы не думаете, что евклидова форма проще, и вы будете правы, но вы можете добавить еще несколько ограничений. Евклидова TSP является NP-Complete, поэтому ее решение имеет тот же эффект, что и решение общей проблемы TSP.
Например, если все города лежат на оси x, вы можете быстро найти решение. Фактически, вы можете пойти дальше — если города лежат на любой разумной кривой, вы можете вычислить решение за полиномиальное время. Это интересно, но ограниченная проблема не является полной NP, и нам нужно попытаться ослабить условия.
Причина того, что TSP на кривой проще, заключается в том, что города расположены в одном измерении. Это предполагает рассмотрение ограниченной 2D-задачи, простейшей из которых является XY TSP, которая заставляет города располагаться на оси x или y или на любых двух прямых линиях под прямым углом.
Проблема XY TSP изучалась с 1980 года без особого прогресса — до тех пор, пока Владимир Дейнеко (Бизнес-школа Варвика), Эранда Села (Технологический университет Граца) и Герхард Вегингер (Университет Эйндховена) не изобрели полиномиальный алгоритм. Новый алгоритм работает настолько быстро, насколько можно разумно ожидать, он будет работать во времени, пропорциональном n2. Алгоритм представляет собой подход динамического программирования, который использует правила, которые заставляют вас выбирать пути между городами в определенных группах.
Есть ли алгоритм, который работает быстрее?
Есть ли способ расширить алгоритм до более общей евклидовой TSP?
Например, предположим, что вы немного искажаете расположение, так что некоторые города находятся не совсем на осях x или y? Может ли пертурбационный подход работать, или есть какая-то принципиальная разница, как только города имеют более общее расположение. Это говорит о геометрии реального мира столько же, сколько и о комбинаторной теории графов.
Единственная проблема заключается в том, что статья, описывающая, как все это работает, находится за платным доступом и стоит 31,50 доллара за чтение, что является постоянным позором.