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

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

  • 28/11/2016

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

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

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

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

    Математический центр в Новосибирске будет развивать новую систему интеграции образования

    ​Новосибирский государственный университет и Институт математики им. Соболева СО РАН, создающие математический центр по нацпроекту "Наука", определили 10 научных направлений развития, среди которых обработка данных, искусственный интеллект, знания компьютерных технологий, сообщили ТАСС в пресс-службе НГУ.
    538
  • 12/01/2018

    Лаборатория алгоритмики НГУ и TU Berlin разрабатывают новые способы эффективного сокращения объёмов данных

    Лаборатория алгоритмики ММФ НГУ и группа «Алгоритмика и теория сложности вычислений» Берлинского технического университета (TU Berlin) получили поддержку РФФИ и Германского научно-исследовательского общества (DFG) для проведения совместного научно-исследовательского проекта.
    2004
  • 13/07/2016

    Аспирант из Японии проходит стажировку в НГУ

    ​В начале июля аспирант японского Университета Айзу (University of Aizu, Aizu-Wakamatsu) Хаяси Кэнсаку приехал пройти стажировку на факультет информационных технологий. Он занимается разработкой сервисно-ориентированной среды для моделирования цунами.
    1609
  • 19/05/2016

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

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

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

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

    Международная конференция «Актуальные проблемы вычислительной и прикладной математики 2019» (АПВПМ-19)

    С 1 по 5 июля 2019 года в Новосибирском Академгородке в рамках "Марчуковских научных чтений" состоится Международная конференция "Актуальные проблемы вычислительной и прикладной математики - 2019.
    1895
  • 11/08/2020

    Академгородок 2.0 – приобретения и потери: мнения экспертов

    Что удалось сделать для развития Новосибирского научного центра за последние годы и какие задачи остаются нерешенными? Три известных российских ученых инвентаризируют достижения и проблемы в статье, написанной для «Континента Сибирь»*.
    566
  • 08/10/2019

    Десять студентов и аспирантов НГУ получат стипендии Президента и Правительства Российской Федерации

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