Бюро научно-технической информации

Наука и жизньНаука

БНТИ

Бюро научно-технической информации

В конце ноября 2018 года состоялся седьмой Национальный суперкомпьютерный форум в Переславле-Залесском. Институт программных систем РАН ежегодно собирает специалистов отрасли для обсуждения передовых достижений, вопросов создания и применения суперкомпьютерных технологий. Корреспонденты «Науки и жизни» Ольга Баклицкая-Каменева и Анна Смирнова побывали на форуме и познакомились с некоторыми разработками.

Задача коммивояжёра: в сто раз быстрее «Конкорда»

В 1857 году ирландский математик Уильям Гамильтон придумал забавную головоломку «Кругосветное путешествие» по додекаэдру. Игра сводилась к обходу по рёбрам всех вершин правильного додекаэдра при условии, что ни в одну из вершин нельзя заходить более одного раза. Вершины символизировали названия городов, а рёбра — соединяющие их дороги. Такой додекаэдр Гамильтон В конце ноября 2018 года состоялся седьмой Национальный суперкомпьютерный форум в Переславле-Залесском. Институт программных систем РАН ежегодно собирает специалистов отрасли для обсуждения передовых достижений, вопросов создания и применения суперкомпьютерных технологий. Корреспонденты «Науки и жизни» Ольга Баклицкая-Каменева и Анна Смирнова побывали на форуме и познакомились с некоторыми разработками. заменил плоским графом (см. рисунок).

В современном виде эта головоломка известна как задача странствующего торговца или коммивояжёра, которому необходимо проложить через города самый выгодный маршрут, например, по времени и стоимости, а затем вернуться домой. Для нематематика эта задача кажется простой, но прямой способ перебора вариантов непосилен даже для современных компьютеров: число маршрутов с ростом городов увеличивается стремительно, а машино-часы начнут измерять миллионы и миллиарды лет! Для математика и формулировка звучит по-другому: это задача о нахождении минимального гамильтонова цикла на полном ориентированном графе с неотрицательными весами дуг. Для профессионала она NP-трудная. Это означает, что на данный момент не существует эффективных полиномиальных* алгоритмов её решения. Но если бы таковой нашёлся (или было бы получено доказательство, что его нет), то Математический институт Клэя (Кембридж, США) выплатил бы миллион долларов за решение этой — главной из семи задач тысячелетия (проблема равенства классов P и NP).

И вот, на прошедшей в рамках седьмого Национального суперкомпьютерного форума (НСКФ-2018) Молодёжной конференции студент Института математики, механики и компьютерных наук Южного федерального университета (ЮФУ) Виктор Бурховецкий представил работу, в которой предложен алгоритм быстрого и точного решения задачи коммивояжёра («Оптимизация и распараллеливание упрощённого алгоритма Балаша — Кристофидеса для задачи коммивояжёра»).

«Мы разработали параллельный точный алгоритм решения задачи коммивояжёра со значительно уменьшенным объёмом используемой памяти. Наш метод работает в сто раз быстрее, чем известный программный комплекс для решения задачи коммивояжёра ”Конкорд”», — рассказывает Виктор Бурховецкий.

Но почему математиков и компьютерных учёных так привлекает задача коммивояжёра? К классической задаче коммивояжёра, бесспорно, одной из самых знаменитых задач теории комбинаторики, сводятся многочисленные практические применения в области логистики и организации производства: выбор оптимальной последовательности операций при доставке грузов на склады и в магазины, при отправке корреспонденции в отделения связи или получателям на дом, при мониторинге нефтяных вышек и станций сотовых операторов или, например, во время работы сверлильного станка ЧПУ и сварочного робота, а также управление расписанием задач на компьютере и решение задач биоинформатики. На практике приходится решать задачи большой размерности, значит, для их решения на компьютерах необходимо изобретать эффективные алгоритмы. Таким полигоном для обкатки новых подходов уже давно служит как раз задача коммивояжёра.

Головоломка «Кругосветное путешествие» по додекаэдру в виде графа.

Как определить, какой из двух алгоритмов эффективнее? Тот, который потребляет меньше памяти и работает максимально быстро. Именно такое решение удалось найти Виктору Бурховецкому под руководством Бориса Штейнберга, заведующего кафедрой алгебры и дискретной математики ЮФУ. «Мы взяли за основу алгоритм Балаша и Кристофидеса, потому что уже сорок лет назад на старом компьютере с его помощью решали задачи большой размерности за сравнительно короткое время (325 городов за 50 секунд). Адаптировали его под современные архитектуры компьютеров и распараллелили, ускорив за счёт модификаций работу компьютера, а также значительно сократили объём используемой памяти. Благодаря этому мы смогли посчитать задачу коммивояжёра для пяти и десяти тысяч городов», — поделился Бурховецкий, ставший лауреатом Молодёжной конференции.

Программа в среднем за секунду может найти точное решение задачи для случайного графа размерности 1000. Такой быстрый алгоритм, как надеются математики из ЮФУ, можно будет использовать в биоинформатике, в том числе для решения задачи сборки генома.

Разработанная Виктором Бурховецким программа может поколебать представления математиков о том, что принадлежность задачи к классу NP означает отказ от точных алгоритмов.

* Мы говорим о полиномиальном времени работы, если зависимость времени работы программы от объёма входных данных описывается линейной, квадратичной, кубической и другими функциями. Дело в том, что линейная, квадратичная, кубическая и так далее функции — полиномы, то есть многочлены от некоторого числа переменных. Время работы программы может иметь не только полиномиальную зависимость от объёма входных данных. При экспоненциальной зависимости увеличение входных данных на единицу измерения влечёт увеличение времени работы алгоритма в несколько раз. То есть, сильно упрощая, можно сказать, что полиномиальные алгоритмы — это быстрые алгоритмы (в противоположность экспоненциальным).

«Живое сердце» на суперкомпьютере

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

Модель деформируемых полостей сердца. Расчёт выполнен с использованием FlowVision.

Таким исследованиям посвящён начатый в 2014 году проект «Живое сердце» (The Living Heart Project), в котором участвуют различные клиники, исследовательские институты, разработчики медицинского оборудования и программного обеспечения со всего мира. «Вместе с бельгийской компанией Capvidia мы разработали модель работы сердца для создания индивидуальных искусственных сердечных клапанов на основе программного комплекса FlowVision и методов динамики жидкости», — рассказывает Александр Щеляев, менеджер компании ТЕСИС, партнёра проекта «Живое сердце» в области вычислительной гидродинамики. FlowVision — программный продукт компании, прототип которого был разработан 20 лет назад в Институте автоматизации проектирования РАН. Сегодня его используют не только для решения задач аэро- и гидродинамики в промышленности, но и для объёмной визуализации скорости движения крови.

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Топливо больших скоростей Топливо больших скоростей

Прогресс привнес новейшие технологии в систему обеспечения лайнеров топливом

Популярная механика
Не пей вина, Гертруда Не пей вина, Гертруда

Известные исторические личности с репутацией завзятых отравителей

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

Исследователи разработали материал, который может накапливать энергию месяцами

National Geographic
DART –  самоубийственная миссия к двойному астероиду DART –  самоубийственная миссия к двойному астероиду

Сможем ли мы изменить орбиту небесного тела, движущегося к Земле?

Naked Science
Подкастинговая лихорадка Подкастинговая лихорадка

Individuum выпустил первую в России книгу, посвященную подкастам

Эксперт
7 тезисов — как изучать историю в школе 7 тезисов — как изучать историю в школе

История как объект исследования и изучения

Дилетант
Образ жизни Дэйва Эспри: пуленепробиваемый кофе, криокамера и 100 добавок Образ жизни Дэйва Эспри: пуленепробиваемый кофе, криокамера и 100 добавок

Как биохакер превратил эксперименты над собой в многомиллионный бизнес

Reminder
Прячут в скафандрах и книгах, пьют под видом сока: как космонавты нелегально провозят и употребляют алкоголь на МКС Прячут в скафандрах и книгах, пьют под видом сока: как космонавты нелегально провозят и употребляют алкоголь на МКС

Официально алкоголь в космосе запрещён, неофициально — его пьют постоянно

TJ
Квантовое превосходство Китая Квантовое превосходство Китая

Очередной год – и очередное сообщение о достижении «квантового превосходства»

Популярная механика
Издательство Individuum перевело книгу на русский с помощью машинного перевода: фрагмент до и после редактуры человеком Издательство Individuum перевело книгу на русский с помощью машинного перевода: фрагмент до и после редактуры человеком

Как «Яндекс.Переводчик» справился с переводом целой книги

VC.RU
Безумства храбрых Безумства храбрых

«Так высоко, как Ольга Кузьмина, на этом проекте не летает никто»

OK!
Пастор Вера Пастор Вера

Каким священником может быть женщина

Огонёк
«Дело жизни – печь!» «Дело жизни – печь!»

Что влияет на калорийность десерта и в чем секрет маложирного крема

Худеем правильно
Бейсбол перед эшафотом: как заключенные из камеры смертников чуть не стали чемпионами Америки Бейсбол перед эшафотом: как заключенные из камеры смертников чуть не стали чемпионами Америки

Каждый выигранный матч означал для этой команды отсрочку смертной казни

Maxim
Как продать идею и заставить всех в нее поверить: ключевые правила Как продать идею и заставить всех в нее поверить: ключевые правила

Презентация любого нового проекта требует серьезной подготовки

Playboy
Попугайчики-неразлучники: Алина Фаркаш о личных границах в браке Попугайчики-неразлучники: Алина Фаркаш о личных границах в браке

Насколько важно соблюдать личные границы в семье

Cosmopolitan
Кому удалось воскресить старые автомобильные бренды, а кто – облажался Кому удалось воскресить старые автомобильные бренды, а кто – облажался

Зачем Renault возрождают Alpine и почему с рынка исчезли автомобили Bugatti

GQ
«Будущее без работы. Технологии, автоматизация и стоит ли их бояться» «Будущее без работы. Технологии, автоматизация и стоит ли их бояться»

Отрывок из книги «Будущее без работы», переведенной Яндекс.Переводчиком

N+1
Правила жизни Джеффа Бриджеса Правила жизни Джеффа Бриджеса

Правила жизни актера Джеффа Бриджеса

Esquire
Эффективные упражнения на пресс: описание, видео, советы Эффективные упражнения на пресс: описание, видео, советы

Рассказываем, как сделать пресс сильным и рельефным, не выходя из дома

РБК
Что почитать о путешествиях, если надоели travel-блоги? Что почитать о путешествиях, если надоели travel-блоги?

Эти произведения — отличный способ проникнуться другими странами

МегаФон Путешествия
Опростившееся государство и конец «теории малых дел» Опростившееся государство и конец «теории малых дел»

Нет больше «малых дел», есть живая жизнь и есть мир государственной фальши

СНОБ
Книгоходовочка Книгоходовочка

Тур по самым выдающимся книжным магазинам мира

Elle
Зачем нужен PRO-режим камеры смартфона? Объясняем на примерах Зачем нужен PRO-режим камеры смартфона? Объясняем на примерах

Режим, который позволяет вручную установить практически все параметры съемки

CHIP
Игра протоколов Игра протоколов

Татьяна Алешичева о трех главных женщинах Британии 1980-х

Weekend
Загадка Антона Лапенко: как комик из многодетной семьи стал звездой YouTube и зарабатывает миллионы на ностальгии по 90-м Загадка Антона Лапенко: как комик из многодетной семьи стал звездой YouTube и зарабатывает миллионы на ностальгии по 90-м

В чем заключается гениальность Антона Лапенко?

Forbes
Два часа Два часа

Как пробежать марафон с невероятным результатом

kiozk originals
Моя терапия: «Я перестала бояться лифтов» Моя терапия: «Я перестала бояться лифтов»

Как быть, если у жителя мегаполиса в лифтах начинаются панические атаки?

Psychologies
«Когда ты по-настоящему счастлив, то не боишься всё потерять». Правила бизнеса легендарного главы Zappos Тони Шея «Когда ты по-настоящему счастлив, то не боишься всё потерять». Правила бизнеса легендарного главы Zappos Тони Шея

Тони Шей о том, как относиться к сотрудникам и почему не в деньгах счастье

Inc.
Лишний билетик Лишний билетик

Объясняем, как вернуть купленный билет и не потерять при этом деньги

Лиза
Открыть в приложении