Share This
Связаться со мной
Крути в низ
Categories
//Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

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

09.10.2020Category : My Habr

issledovateli smogli preodolet barer v uluchshenii reshenija zadachi kommivojazhera 4c48056 - Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

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

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

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

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

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

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

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

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

issledovateli smogli preodolet barer v uluchshenii reshenija zadachi kommivojazhera 91f879c - Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

issledovateli smogli preodolet barer v uluchshenii reshenija zadachi kommivojazhera a4231d6 - Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

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

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

  • 0 views
  • 0 Comment

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Свежие комментарии

    Рубрики

    About Author 01.

    Roman Spiridonov
    Roman Spiridonov

    Привет ! Мне 38 лет, я работаю в области информационных технологий более 4 лет. Тут собрано самое интересное.

    Our Instagram 04.

    Categories 05.

    © Speccy 2020 / All rights reserved

    Связаться со мной
    Close