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

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

БНТИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смех – подарок культуры Смех – подарок культуры

Арсений Дежуров напоминает: человека от животного отличает способность смеяться

Правила жизни
Взять кредит и подумать Взять кредит и подумать

Банки будут выдавать кредиты от 50 000 рублей с «периодом охлаждения»

Ведомости
Растущий на обочине Растущий на обочине

Да, пожалуй, ни одну из дорог невозможно представить без этого растения

Наука и жизнь
«Ревность о Севере: Прожектерское предпринимательство и изобретение Северного морского пути в Российской империи» «Ревность о Севере: Прожектерское предпринимательство и изобретение Северного морского пути в Российской империи»

Почему предпринимателей интересовала печорская древесина

N+1
Жизнь без гаджетов Жизнь без гаджетов

Как прекратить сидеть в телефоне: 9 шагов к цифровой свободе

Лиза
Биология эльфов Биология эльфов

Чем эльфам пришлось бы «пожертвовать» в обмен на вечную жизнь?

Вокруг света
Ксения Хаирова Ксения Хаирова

О Валентине Талызиной, актрисе поистине уникальной

Караван историй
Крупным планом: что происходит с отечественным кинорынком Крупным планом: что происходит с отечественным кинорынком

Какое кино сейчас интересно зрителям в России?

Inc.
Цветовые ошибки: как один оттенок способен испортить весь интерьер Цветовые ошибки: как один оттенок способен испортить весь интерьер

Какие ошибки в выборе цвета стен способны испортить весь интерьер?

VOICE
Академик Петр Чумаков: вирусы позволяют увидеть раковые клетки и сформировать иммунный ответ Академик Петр Чумаков: вирусы позволяют увидеть раковые клетки и сформировать иммунный ответ

Вирусы дают надежду в лечении самых злокачественных видов рака

Наука
Пушки или масло Пушки или масло

Как технологии двойного назначения помогли послевоенной конверсии

Эксперт
От «коробочек» — к нелинейной архитектуре От «коробочек» — к нелинейной архитектуре

Как может выглядеть архитектура XXI века?

Монокль
Гений, садовник и киноман: 10 эпизодов из биографии Кодзимы Гений, садовник и киноман: 10 эпизодов из биографии Кодзимы

Что вы знаете о Хидео Кодзиме?

Правила жизни
Как запустить посудомоечную машину первый раз — инструкция и советы Как запустить посудомоечную машину первый раз — инструкция и советы

Как правильно запускать посудомоечную машину первый раз?

CHIP
Одежда и надежды Одежда и надежды

Красивые книги о моде

Weekend
В зоне степей и полупустынь В зоне степей и полупустынь

Сергей Богун о проблемах защиты редких степных видов

Знание – сила
Кто живет на чердаке Кто живет на чердаке

Как оформить квартиру в стиле лофт, не ломая стены

Лиза
Мост в небесах Мост в небесах

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

Знание – сила
Иван Бунин Иван Бунин

Почему Бунин поссорился с Чеховым и на что истратил всю Нобелевскую премию?

Караван историй
Правда ли, что горячие напитки ведут к раку? Правда ли, что горячие напитки ведут к раку?

Существует ли связь между горячими напитками и раком пищевода?

ТехИнсайдер
Леопардовые тюлени поют песни, похожие на детские стишки Леопардовые тюлени поют песни, похожие на детские стишки

Ученые обнаружили, что песни леопардовых тюленей похожи на детские стишки

ТехИнсайдер
Мемолог или вайб-менеджер: какие новые профессии придумал российский бизнес и зачем Мемолог или вайб-менеджер: какие новые профессии придумал российский бизнес и зачем

Какие необычные позиции появились в российских компаниях за последние пару лет

Forbes
Разница принципиальна: чем цукини отличаются от кабачков Разница принципиальна: чем цукини отличаются от кабачков

Какие различия цукини и кабачков играют ключевую роль в кулинарии

ТехИнсайдер
«Когда-нибудь, возможно»: как потеря близкого человека меняет отношения в семье «Когда-нибудь, возможно»: как потеря близкого человека меняет отношения в семье

Отрывок из книги «Когда-нибудь, возможно» — как говорить о потере близкого

Forbes
Гейдельбергский человек из Петралонской пещеры умер не меньше 277 тысяч лет назад Гейдельбергский человек из Петралонской пещеры умер не меньше 277 тысяч лет назад

Как ученые установили датировку древнего черепа из пещеры Петралона

N+1
Листоносы собрали падалицу Листоносы собрали падалицу

Зоологи обнаружили свидетельства, что рукокрылые подбирают пищу с земли

N+1
Скрытая углеводная нагрузка: так ли полезны «здоровые» сладости и что нам не договаривают маркетологи Скрытая углеводная нагрузка: так ли полезны «здоровые» сладости и что нам не договаривают маркетологи

На что обратить внимание в составе «здоровых перекусов»

ТехИнсайдер
Без паники Без паники

Как не дать гиперответственности превратить жизнь в постоянный стресс

Лиза
Какое пиво лучше с оливье, борщом, окрошкой: ответ специалиста Какое пиво лучше с оливье, борщом, окрошкой: ответ специалиста

Крайне необычный варианты гастрономической пары к пиву

Maxim
Как правильно зарядить телефон: простые правила, которые сберегут его аккумулятор Как правильно зарядить телефон: простые правила, которые сберегут его аккумулятор

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

CHIP
Открыть в приложении