[Алгоритмы, Математика, Научно-популярное] Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
Натан Кляйн и его советники из Вашингтонского университета Анна Карлин и Шаян Гаран впервые за почти полвека смогли найти лучший способ решения задачи коммивояжера. Это одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута через указанные города с последующим возвратом в исходный город.
На протяжении десятилетий задача вдохновила на многие из фундаментальных достижений в области информатики, в частности, в сфере линейного программирования. В 1976 году Никос Кристофидес придумал алгоритм, который эффективно находит приблизительные решения задачи. Однако впоследствии ни у кого не получилось улучшить этот алгоритм.
В алгоритме Кристофидеса все начинается с остовного дерева, соединяющего города без замкнутых петель. Чтобы построить его, нужно начать с поиска кратчайшего пути между двумя городами. Для каждой следующей ветви нужно найти кратчайший путь между новым городом и одним из двух предыдущих.
Результирующее дерево позволяет пройти маршрут через каждый город и вернуться назад, но обычно длина такого пути далека от кратчайшей. Тем не менее, полученный путь в худшем случае не превышает кратчайший более чем на 50%.
В 2010 году Амин Сабери из Стэнфордского университета, аспиранты Араш Асадпур, Шайан Гаран и Александер Мадри, а также Майкл Гоманс из МТИ показали новый алгоритм, который начинает с подсчёеа точного дробного решения задачи коммивояжёра, а затем округляет это решение до остовного дерева. Наконец, алгоритм включает это дерево в сеть Кристофидеса.
Таким образом, исследователи смогли улучшить алгоритм Кристофидеса на небольшую долю для широкого подкласса «графических» задач коммивояжера.
Теперь Гаран и другие вернулись к задаче. Они решили использовать геометрию многочленов, составленных из чисел и переменных в степенях, например 3x2y + 8xz7. Чтобы изучить проблему коммивояжера, исследователи преобразовали карту городов в полином, в котором было по одной переменной для каждого края между городами и по одному члену для каждого дерева, которое могло соединить все города.
Они обнаружили, что этот многочлен обладает так называемой «реальной стабильностью». Поэтому, если исследователи хотят сосредоточиться на определенных городах, они могут использовать одну переменную для представления различных краев, ведущих в город, а для краев, которые им не важны, установить величину, равную 1.
Такой подход позволил исследователям выяснить, например, как часто алгоритм будет вынужден соединять два удаленных города. Им удалось показать, что этот алгоритм превосходит исходник Кристофидеса для решения общей задачи коммивояжера.
Пока улучшения алгоритма оцениваются в доли процента, но, как показывает практика, это может быть очередным прорывом в решении задачи коммивояжера. После разработки алгоритма Сабери и других результат решения уже улучшился с 50 до 40%.
===========
Источник:
habr.com
===========
Похожие новости:
- [Будущее здесь, Космонавтика, Научно-популярное, Транспорт] Лунная программа НАСА «Артемида». Почему всё не так?
- [Криптография, История IT, Научно-популярное, Старое железо] Gerät 32620: немецкое устройство для организации шпионских номерных станций (перевод)
- [Научно-популярное, Физика, Химия, Экология] Как ядерное топливо путешествует по городам России. Короткий комментарий
- [Обработка изображений, Научно-популярное] Восстановление утраченных текстов с помощью современных алгоритмов. Софт
- [Космонавтика, Научно-популярное] 2019. «Космический бюджет» Земли
- [C++, Алгоритмы, Программирование] Под капотом сортировок в STL
- [Алгоритмы, Обработка изображений, Машинное обучение, Искусственный интеллект] Разработка и тестирование на платформах Эльбрус программы для томографической реконструкции Smart Tomo Engine (+2 видео)
- [Алгоритмы, Искусственный интеллект, Машинное обучение, Социальные сети и сообщества] Бот GPT-3 в течение недели выдавал себя за человека на AskReddit
- [Научно-популярное, Химия] Нобелевскую премию по химии вручили за «переписывание кода жизни»
- [Алгоритмы, Машинное обучение, Искусственный интеллект] Ученые разработали метод обучения ИИ с меньшим числом параметров, который превзошел GPT-3
Теги для поиска: #_algoritmy (Алгоритмы), #_matematika (Математика), #_nauchnopopuljarnoe (Научно-популярное), #_matematika (математика), #_zadacha_kommivojazhera (задача коммивояжера), #_algoritmy (алгоритмы), #_algoritmy (
Алгоритмы
), #_matematika (
Математика
), #_nauchnopopuljarnoe (
Научно-популярное
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 18:00
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
 Натан Кляйн и его советники из Вашингтонского университета Анна Карлин и Шаян Гаран впервые за почти полвека смогли найти лучший способ решения задачи коммивояжера. Это одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута через указанные города с последующим возвратом в исходный город. На протяжении десятилетий задача вдохновила на многие из фундаментальных достижений в области информатики, в частности, в сфере линейного программирования. В 1976 году Никос Кристофидес придумал алгоритм, который эффективно находит приблизительные решения задачи. Однако впоследствии ни у кого не получилось улучшить этот алгоритм. В алгоритме Кристофидеса все начинается с остовного дерева, соединяющего города без замкнутых петель. Чтобы построить его, нужно начать с поиска кратчайшего пути между двумя городами. Для каждой следующей ветви нужно найти кратчайший путь между новым городом и одним из двух предыдущих. Результирующее дерево позволяет пройти маршрут через каждый город и вернуться назад, но обычно длина такого пути далека от кратчайшей. Тем не менее, полученный путь в худшем случае не превышает кратчайший более чем на 50%. В 2010 году Амин Сабери из Стэнфордского университета, аспиранты Араш Асадпур, Шайан Гаран и Александер Мадри, а также Майкл Гоманс из МТИ показали новый алгоритм, который начинает с подсчёеа точного дробного решения задачи коммивояжёра, а затем округляет это решение до остовного дерева. Наконец, алгоритм включает это дерево в сеть Кристофидеса. Таким образом, исследователи смогли улучшить алгоритм Кристофидеса на небольшую долю для широкого подкласса «графических» задач коммивояжера. Теперь Гаран и другие вернулись к задаче. Они решили использовать геометрию многочленов, составленных из чисел и переменных в степенях, например 3x2y + 8xz7. Чтобы изучить проблему коммивояжера, исследователи преобразовали карту городов в полином, в котором было по одной переменной для каждого края между городами и по одному члену для каждого дерева, которое могло соединить все города. Они обнаружили, что этот многочлен обладает так называемой «реальной стабильностью». Поэтому, если исследователи хотят сосредоточиться на определенных городах, они могут использовать одну переменную для представления различных краев, ведущих в город, а для краев, которые им не важны, установить величину, равную 1.   Такой подход позволил исследователям выяснить, например, как часто алгоритм будет вынужден соединять два удаленных города. Им удалось показать, что этот алгоритм превосходит исходник Кристофидеса для решения общей задачи коммивояжера. Пока улучшения алгоритма оцениваются в доли процента, но, как показывает практика, это может быть очередным прорывом в решении задачи коммивояжера. После разработки алгоритма Сабери и других результат решения уже улучшился с 50 до 40%. =========== Источник: habr.com =========== Похожие новости:
Алгоритмы ), #_matematika ( Математика ), #_nauchnopopuljarnoe ( Научно-популярное ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 22-Ноя 18:00
Часовой пояс: UTC + 5