Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

    image

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

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

    В алгоритме Кристофидеса все начинается с остовного дерева, соединяющего города без замкнутых петель. Чтобы построить его, нужно начать с поиска кратчайшего пути между двумя городами. Для каждой следующей ветви нужно найти кратчайший путь между новым городом и одним из двух предыдущих.

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

    В 2010 году Амин Сабери из Стэнфордского университета, аспиранты Араш Асадпур, Шайан Гаран и Александер Мадри, а также Майкл Гоманс из МТИ показали новый алгоритм, который начинает с подсчёта точного дробного решения задачи коммивояжёра, а затем округляет это решение до остовного дерева. Наконец, алгоритм включает это дерево в сеть Кристофидеса.

    Таким образом, исследователи смогли улучшить алгоритм Кристофидеса на небольшую долю для широкого подкласса «графических» задач коммивояжера.

    Теперь Гаран и другие вернулись к задаче. Они решили использовать геометрию многочленов, составленных из чисел и переменных в степенях, например 3x2y + 8xz7. Чтобы изучить проблему коммивояжера, исследователи преобразовали карту городов в полином, в котором было по одной переменной для каждого ребра между городами и по одному члену для каждого дерева, которое могло соединить все города.

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

    image image

    Такой подход позволил исследователям выяснить, например, как часто алгоритм будет вынужден соединять два удаленных города. Им удалось показать, что этот алгоритм превосходит исходник Кристофидеса для решения общей задачи коммивояжера.

    Пока улучшения алгоритма оцениваются в доли процента, но, как показывает практика, это может быть очередным прорывом в решении задачи коммивояжера. После разработки алгоритма Сабери и других результат решения уже улучшился с 50 до 40%.
    См. также:

    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 6

      0
      Важный теоретический прорыв, практика остаётся прежней:
      «only able to subtract 0.2 billionth of a trillionth of a trillionth of a percent.» от прошлого теоретического прорыва у академиков, ~1-2% длиньше оптимального пути у практиков на пачках эвристик.
        +1

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

          +7
          Да это же редактор. Он промптом переводит.
          real stable не от слова реальный, а от слова действительный. Числа там действительные в многочлене.
          «A stable polynomial with real coefficients is called real stable.»
          Лекция про реально стабильные многочлены:
          math.berkeley.edu/~nikhil/courses/270/lec2.pdf
          +5
          На протяжении десятилетий задача вдохновила на многие из фундаментальных достижений в области информатики, в частности, в сфере линейного программирования

          Линейное программирование — это раздел математики и, несмотря на название, не имеет никакого отношения к тому программированию, к которому мы привыкли, и, как следствие, прямого отношения к информатике
            0
            С учетом того, что похожая формулировка содержится в оригинальной статье в издании Quanta Magazine, и ее автор — Erica Klarreich, доктор математических наук, которая писала статьи в том числе для Nature, я бы не был столь однозначен в отношении того, что линейное программирование не имеет отношения к информатике.

            Точнее, в оригинальной статье сказано, что линейное программирование является одним из инструментов, которые позволили продвинуться в фундаментальных задачах компьютерных наук.

            Переводчик, безусловно, допустил грубую ошибку тем, что переформулировал предложение так, что линейное программирование получилось подобластью информатики.

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

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое