​Заведующий лабораторией алгоритмики Механико-математического факультета Рене ван Беверн, младший научный сотрудник лаборатории алгоритмики ММФ Оксана Цидулко и аспирант Берлинского технического университета Тиль Флюшник предложили новый подход к решению одной классической труднорешаемой задачи маршрутизации транспорта — обобщения задачи коммивояжера и задачи о семи кенигсбергских мостах. Если транспортная сеть слишком большая для нахождения коротких маршрутов за приемлемое время, математики показали, как ее можно уменьшить, чтобы короткие маршруты для уменьшенной сети переносились на короткие маршруты для исходной сети. Поэтому достаточно решать задачу в уменьшенной сети. В вычислительных экспериментах транспортные сети сжимаются до 60% исходного размера при удлинении маршрутов всего на 1%.
 
 
В рамках задачи, известной как «задача деревенского почтальона», необходимо найти кратчайший замкнутый обход в графе, включающий заданное подмножество его ребер.
 
 
11.png 
 
Интуитивно требуется кратчайший замкнутый маршрут в транспортной сети для уборки снега с заданных дорог. Задача в этом простом виде также возникает при дистанционном снятии показаний со счётчиков, при резке металла и при решении куда более общих задач маршрутизации транспорта: например, ещё в 2015 году ученые НГУ и TU Berlin доказали, что улучшение качества решений для задачи деревенского почтальона непосредственно приводит к улучшению качества решений задач с несколькими транспортными средствами с ограниченной вместимости, за что они получили премию за лучший результат на международной конференции по алгоритмам маршрутизации транспорта.
 
— Задача о деревенском почтальоне относится к так называемым APX-трудным задачам. Поэтому трудоёмкость алгоритмов не только для оптимального решения, но даже для хорошего приближённого решения растёт экспоненциально с объемом входных данных. То есть если вдруг придётся почистить на одну дорогу больше, время работы алгоритма условно удвоится. И если вы сегодня купите суперкомпьютер, который оптимально решает задачу на сети из 1000 дорог за секунду, то над 1010 дорогами он будет работать уже 17 часов, а над 1020 дорогами — два года. Но это также указывает на возможный подход к решению задачи: ведь если удастся из транспортной сети удалить хотя бы одну дорогу, то алгоритм будет работать в два раза быстрее. Разумеется, нельзя просто так удалять какие угодно дороги из сети, ведь найденный в такой «испорченной» сети оптимальный маршрут может вовсе не оказаться оптимальным для исходной транспортной сети, — объяснил Рене ван Беверн.
 
Ученые выяснили, как нужно удалять дороги из транспортной сети, чтобы хорошие (или оптимальные) маршруты для уменьшенной сети переносились на хорошие (или почти оптимальные) маршруты для исходной сети. 
 
— Допустим, компания предлагает ПО для маршрутизации транспорта, но у ее заказчиков транспортные сети достигли размеров, при которых ПО уже не работает за приемлемое время. Тогда компания может легко применить наш алгоритм в своем ПО. Достаточно задать алгоритму «требуется уменьшить эту транспортную сеть так, чтобы маршруты удлинились не более, чем на х%», и алгоритм сожмет транспортную сеть до размера, зависящего от этих заданных х%. Потом существующее ПО может быть применено к уменьшенной сети, оно в ней найдёт хороший маршрут, и наш алгоритм превратит его в маршрут для исходной сети. При этом алгоритм гарантирует, что полученный таким подходом маршрут будет не более чем на x% длиннее, чем маршрут, который мы бы построили в исходной сети.  Тут x — любое число больше нуля, — отметил новосибирский ученый.
 
88.png 
 
Исследования проводятся в рамках совместного проекта НГУ и TU Berlin под совместной поддержкой Российского фонда фундаментальных исследований и Немецкого научно-исследовательского общества. 

Похожие новости

  • 28/11/2016

    Лаборатория алгоритмики открылась в НГУ

    Лаборатория алгоритмики, организованная при поддержке Проекта 5–100, начала свою работу в Новосибирском государственном университете.  Специалисты будут решать фундаментальные и прикладные задачи, участвовать в разработке образовательных курсов, привлекать студентов и аспирантов к работе над проектами.
    1693
  • 02/03/2021

    Молодой преподаватель НГУ выиграла стипендию Стэнфордского форума для работы над проектом об Арктике

    Стэнфордский российско-американский форум — это годовая программа для студентов и молодых ученых из ведущих вузов России и США, цель которой — продвижение сотрудничества между двумя странами с помощью проведения совместных исследований.
    716
  • 05/07/2021

    Выпускник НГУ занял призовое место на соревнованиях Waymo Motion Prediction Challenge

    Суть задания на соревнованиях Waymo Motion Prediction Challenge заключалась в наблюдении за поведением участников дорожного движения на протяжении одной секунды, чтобы предсказать их действия в течение следующих восьми секунд.
    301
  • 28/12/2020

    Сеть математических центров: успехи и результаты работы

    ​Сеть математических центров объединяет международные математические центры мирового уровня, созданные в рамках нацпроекта «Наука», и региональные научно-образовательные математические центры (НОМЦ), созданные в рамках реализации Концепции развития математического образования в Российской Федерации, утвержденной распоряжением Правительства РФ от 24 декабря 2013 г.
    874
  • 16/10/2020

    Сильнее в математике: ректор НГУ Михаил Федорук выступил в рамках Совета молодых ученых и специалистов при Правительстве Новосибирской области

    Депутат Законодательного Cобрания Новосибирской области Михаил Федорук 15 октября выступил в рамках Совета молодых ученых и специалистов при Правительстве Новосибирской области.  «Наша цель – создать в Академгородке научный центр мирового уровня, добившись привлечения ведущих отечественных и зарубежных специалистов, – отметил депутат в докладе о работе над проектом Международного математического центра Академгородка, – причем специалистов не только именитых, но и молодых, готовых работать над передовыми научными задачами, такими как математические проблемы в естествознании, обработка данных, машинное обучение, криптография, эффективные алгоритмы и вычисления».
    1265
  • 24/03/2021

    Студенты НГУ заняли третье место в международном соревновании команд по искусственному интеллекту

    ​В хакатоне Samruk Hackathon — 2021 участвовали студенты двух университетов, имеющих уникальное положение относительно фонда «Самрук-Казына». Только с двумя университетами в мире у фонда имеются соглашения о сотрудничестве.
    528
  • 25/12/2020

    Математики НГУ совместно с иностранными коллегами исследовали устойчивость Google Scholar к манипуляциям индексом Хирша

    ​В наукометрии самым известным показателем оценки производительности ученого является индекс Хирша (h) — наибольшее число h такое, что у ученого есть h публикаций, цитируемых хотя бы h раз. База данных публикаций и цитирований Google Scholar позволяет авторам заводить профиль и в нем объединять записи о публикациях.
    871
  • 23/07/2021

    Большая математическая мастерская приурочена к Году науки и технологий

    ​С 12 по 16 июля 2021 года прошла первая неделя Большой математической мастерской (БММ), приуроченной к году науки и технологий. Четыре площадки — Международный математический институт им. Леонарда Эйлера (г.
    679
  • 19/05/2016

    Аспирантка НГУ - первая российская участница семинаров по цифровой гуманитаристике в Кембридже

    Аспирантка НГУ, сотрудница кафедры древних литератур и литературного источниковедения Ксения Грищенко приняла участие в курсе MMSDA-2016 (Manuscript Studies in the Digital Age 2016/Исследования рукописей в цифровую эпоху-2016).
    3404
  • 28/06/2016

    В НГУ откроется англоязычная магистерская программа по Big Dat

    ​Механико-математический факультет НГУ открывает англоязычную магистерскую программу Big Data Analytics по направлению Data Science. Студенты и выпускники магистратуры смогут применять свои навыки в самых разных направлениях — от физики элементарных частиц и когнитивных наук до IT и ритейла.
    2486