Быстрый алгоритм труднорешаемой задачи

Исследователи НГУ доработали труднорешаемую задачу на построение энергоэффективных беспроводных коммуникационных сетей. При использовании нового алгоритма на решение уходит всего 10 секунд вместо прежних 16 минут.

Фундаментальная задача заключалась в том, чтобы построить связную коммуникационную сеть с минимальной суммарной мощностью передачи узлов. В 2017 году теоретическое решение было найдено заведующим лабораторией алгоритмики ММФ НГУ Рене ван Беверном и его берлинскими коллегами, за что ученые удостоились премии большого Европейского конгресса по алгоритмам.

Однако вопрос о практической ценности изобретенного алгоритма остался незатронутым. В 2018 году Павел Смирнов (сейчас аспирант 1-го курса ММФ НГУ) занялся изучением этого вопроса и пришел к выводу, что в предложенной форме на практике алгоритм практически неконкурентоспособен. Студент ускорил алгоритм как в теоретическом, так и в практическом аспектах.

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

Беспроводные датчиковые сети применяют для мониторинга экологической обстановки. Чаще всего они работают на батареях, поэтому вопрос энергоэффективности беспроводной коммуникационной сети напрямую связан с длительностью их эксплуатации.