Компьютерные ученые побили рекорд “путешествующих продавцов”

Когда Натан Кляйн Он поступил в аспирантуру два года назад, его советники предложили скромный план: работать вместе над одной из самых известных и давних проблем теоретической информатики.

Оригинальная история перепечатано с разрешения Журнал Quanta, редакционно независимое издание Фонд Саймонса чья миссия состоит в том, чтобы улучшить понимание науки общественностью, освещая исследования и тенденции в математике, физических науках и науках о жизни.

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

Теперь в бумага размещена в Интернете В июле Кляйн и его советники из Вашингтонского университета Анна Карлин и Шаян Овейс Гаран наконец достигли цели, которую компьютерные ученые преследовали почти полвека: лучший способ найти приблизительное решение проблемы коммивояжера.

Эта задача оптимизации, которая направлена ​​на поиск кратчайшего (или наименее затратного) пути туда и обратно через набор городов, имеет самые разные приложения – от секвенирования ДНК до логистики совместного использования. На протяжении десятилетий он вдохновил многих из самых фундаментальных достижений в области информатики, помогая осветить мощь таких методов, как линейное программирование. Но исследователям еще предстоит полностью изучить его возможности – и не из-за отсутствия попыток.

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

Большинство специалистов по информатике считают, что не существует алгоритма, который мог бы эффективно находить лучшие решения для всех возможных комбинаций городов. Но в 1976 году Никос Христофидес придумал алгоритм которая эффективно находит приблизительные решения – поездки туда и обратно, которые не более чем на 50 процентов длиннее, чем лучший путь туда и обратно. В то время компьютерные ученые ожидали, что кто-то скоро улучшит простой алгоритм Кристофидеса и приблизится к истинному решению. Но ожидаемого прогресса не произошло.

«Многие люди потратили бесчисленные часы, пытаясь улучшить этот результат, – сказал Амин Сабери из Стэнфордского университета.

Карлин, Кляйн и Овейс Гаран доказали, что алгоритм, разработанный десять лет назад, превосходит 50-процентный коэффициент Христофидеса, хотя они смогли вычесть лишь 0,2 миллиардной триллионной из триллионной доли процента. Тем не менее, это незначительное улучшение позволяет преодолеть теоретический и психологический тупик. Исследователи надеются, что это откроет двери для дальнейших улучшений.

«Это результат, к которому я стремился всю свою карьеру», – сказал Дэвид Уильямсон из Корнельского университета, изучавший проблему коммивояжера с 1980-х годов.

Проблема коммивояжера – одна из немногих фундаментальных проблем, к которым теоретики-информатики обращаются снова и снова, чтобы проверить пределы эффективных вычислений. Новый результат «является первым шагом к тому, чтобы показать, что границы эффективных вычислений на самом деле лучше, чем мы думали», – сказал Уильямсон.

Частичный прогресс

Хотя, вероятно, не существует эффективного метода, который всегда находил бы кратчайшее путешествие, можно найти что-то почти такое же хорошее: кратчайшее дерево, соединяющее все города, то есть сеть соединений (или «ребер») без замкнутых петель. Алгоритм Кристофидеса использует это дерево в качестве основы для кругового обхода, добавляя дополнительные ребра, чтобы преобразовать его в круговой обход.

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

У самого короткого дерева, соединяющего все города, отсутствует это свойство равномерности, поскольку любой город в конце ветви имеет только одно соединение с другим городом. Итак, чтобы превратить самое короткое дерево в путешествие туда и обратно, Христофидес (который умер в прошлом году) нашел лучший способ соединить пары городов с нечетным числом ребер. Затем он доказал, что результирующее путешествие туда и обратно никогда не будет более чем на 50 процентов длиннее, чем наилучшее из возможных.

Поступая так, он разработал, пожалуй, самый известный алгоритм аппроксимации в теоретической информатике, который обычно является первым примером в учебниках и курсах.

«Всем известен простой алгоритм», – сказала Аланта Ньюман из Университета Гренобль-Альпы и Национального центра научных исследований Франции. И когда вы это узнали, она сказала: «Вы знаете состояние дел» – по крайней мере, так было до июля этого года.

.

Leave a Comment