​​​В задаче китайского почтальона нужно найти кратчайший обход всех ребер графа. 

задача.jpg 

 
Ее так назвали, потому что, по всей видимости, впервые ее изучал китайский математик Квон Мэй-Ко в 1960 году. Только в начале 1970-х годов ею также занялись математики на Западе и в Новосибирске. Авторы статьи заведующий лабораторией алгоритмики Механико-математического факультета НГУ Рене ван Беверн, младший научный сотрудник лаборатории алгоритмики ММФОксана Цидулко и студент ММФ НГУ Всеволод Афанасьев занимались задачей китайского почтальона с иерархиями, в которой ребра разбиты на классы и между классами есть ограничения предшествования: ребро можно пройти лишь тогда, когда пройдены все ребра в классах, предшествующих классу этого ребра. Статья опубликована в Operations Research Letters, который входит в Q2 по Scopus. 

 
— Вообще, все началось с разбора статьи по данной задаче. Потом Рене предложил рассмотреть определенную ее версию и процесс пошел. Мы читали статьи по теме и строили и проверяли какие-то гипотезы, а потом раз в 1–2 недели собирались и устраивали мозговой штурм по конкретным темам (например, придумывали приближенные алгоритмы, т. е. алгоритмы, которые в каком-то смысле «меняют точность на скорость работы» для определенных постановок задачи). После этого основные полученные результаты мы оформили в статью, — рассказал об исследовании студент ММФ Всеволод Афанасьев.​​

Условно говоря, требуется кратчайший маршрут для уборки снега, но сначала нужно убрать главные дороги. На самом деле, более подходящий пример — резка металла. Допустим, требуется вырезать букву О из листа металла. Нужно сначала вырезать внутренний круг (дырку), потом внешний. Если сначала вырезать внешний круг, то из листа выпадет вырезанный диск и вырезать дырку в нем мы уже не сможем. 

 
— Варианты задачи китайского почтальона интересны тем, что они на грани между легко и трудно решаемыми задачами. Это их отличает от задачи коммивояжера, в которой нужно найти кратчайший обход вершин (а не ребер) графа: она практически всегда сложна. Например, задача китайского почтальона, в которой нужно найти кратчайший обход всех ребер (а не вершин) графа, легко решается. А если требуется обойти лишь заданное подмножество ребер? Тогда она называется задачей деревенского почтальона, и она вдруг NP-трудна, значит, для нее нет эффективных алгоритмов, если не P=NP. Но если ребра в этом подмножестве распадаются на малое число несвязных компонент? Тогда задача опять эффективно решается, — уточнил Рене ван Беверн. — В 2014 году я участвовал в написании книги о задачах кратчайшего обхода ребер — обзора вычислительной сложности таких задач. Мы тогда выявили много открытых вопросов. С тех пор активно над закрытием этих пробелов независимо друг от друга работали мы и команда в Лондоне. Что касается задачи о китайском почтальоне с иерархиями, то по ней было известно лишь то, что она эффективно решается, если ребра в каждом классе образуют связный подграф и классы упорядочены линейно, то есть сначала нужно обойти все ребра уровня 1, потом уровня 2, потом уровня 3 и так далее. Также было известно, что задача NP-трудна, если классы не связаны.​


С одной стороны, ученые получили несколько удивительный результат, что малейшее отступление от линейного упорядочения классов приведет к NP-трудной задаче. Допустим, ребра в каждом классе связанные, но помимо линейно упорядоченных классов есть еще один класс ребер таких, что их можно проходить, когда угодно. В этом случае задача оказалась NP-трудна! С другой стороны, получили и положительные результаты: если классы линейно упорядочены, то в принципе не так уж страшно отказаться от связности ребер в каждом классе. Во-первых, авторы статьи доказали, что в этом случае можно эффективно найти хотя бы хорошие приближенные решения. Во-вторых, доказали, что если ребра в каждом классе образуют малое число несвязных компонент, то задача все же эффективно решается. 

 
— На самом деле для получения положительных результатов мы доказали намного более общий результат: на задачу китайского почтальона с линейно упорядоченными (но не обязательно связанными) классами переносятся все алгоритмы для точного решения задачи деревенского почтальона. А про деревенского почтальона мы уже знаем почти все. К сожалению, с одним открытым вопросом нам все же не удалось разобраться: задача китайского почтальона с тремя связанными классами эффективно решается или NP-трудна? Мы до сих пор не знаем, — подытожил Рене ван Беверн.

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

  • 11/08/2020

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

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

    Директор специализированного учебно-научного центра России Яворский покинул пост

    ​Директор Специализированного учебно-научного центра России (СУНЦ) - физико-математической школы им. М. А. Лаврентьева при Новосибирском государственном университете Николай Яворский, занимавший эту должность 15 лет, покинул свой пост.
    559
  • 12/02/2021

    В НГУ завершилась стратегическая сессия у будущих инженеров

    На первой неделе февраля состоялась стратегическая сессия для студентов, преподавателей и партнеров Инженерной школы НГУ. Проект «Инженерная школа НГУ (ИШ НГУ)» уникальный: первый набор состоялся в 2019 году.
    631
  • 25/03/2021

    В НГУ состоялся заключительный этап Всероссийского химического турнира школьников

    XVII Всероссийский химический турнир школьников, который последние 3 года проходит на площадке НГУ, завершился. Это командное соревнование по решению творческих научных задач, позволяющее участникам расширять научный кругозор, научиться презентовать свои научные проекты, вступать в полемику и отстаивать свое мнение, применять научные знания для решения прикладных и теоретических задач.
    398
  • 08/10/2019

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

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

    В НГУ состоится Huawei – NSU Open Day

    ​Компания Хуавей и НГУ в рамках сотрудничества в области образования приглашают всех заинтересованных студентов, аспирантов, преподавателей и научных сотрудников на Huawei – NSU Open Day 12 марта в 16:30 в аудиторию 3107 нового корпуса НГУ.
    444
  • 16/10/2020

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

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

    Прошел заключительный этап XXI Открытой Всесибирской олимпиады по программированию им. И.В. Поттосина

    ​​С 30 октября по 2 ноября прошел заключительный этап XXI Открытой Всесибирской олимпиады по программированию им. И.В. Поттосина. Омский государственный университет им. Ф.М. Достоевского в финальных соревнованиях представляли 3 команды, прошедшие отборочный тур.
    702
  • 15/10/2020

    Директор математического центра ТГУ победил в конкурсе фонда «Базис»

    ​Руководитель Регионального научно-образовательного математического центра (НОМЦ) ТГУ, доктор физико-математических наук, член-корреспондент РАН Андрей Веснин стал одним из семи победителей конкурса Leader («Ведущий ученый») по фундаментальной математике.
    853
  • 15/03/2021

    Профессия аналитик данных

    ​​Данные — очень важная информация для любой компании. По ним можно предсказать поведение клиентов, отследить спрос на определенный товар, улучшить сервис и повысить продажи. Обработка значений и показателей сформировала целую профессию — аналитик данных​.
    293