Математики из России решили задачу, которая более 20 лет не позволяла сократить число схем маршрутов для создания оптимальной сети связи

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

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

В математике и информатике для построения таких экономных сетей используют «деревья». Дерево — это схема связей (граф), в которой нет замкнутых маршрутов. Если два дома находятся на соседних улицах, но подключены к разным веткам сети, то сигналу придется идти от первого дома к центральной станции, а оттуда — ко второму. То есть путь по сети окажется во много раз длиннее, чем реальное расстояние по прямой.

Чтобы избежать таких крюков, программисты идут на хитрость: они создают сразу несколько разных деревьев (схем связи) для одних и тех же точек и накладывают их друг на друга. Если в первой схеме путь между нужными домами слишком длинный, система мгновенно проверяет вторую или третью схему, и находит короткий маршрут.

С 1998 года в компьютерных науках считалось, что для гарантированно короткого пути на плоскости (например, на карте) нужно использовать как минимум три перекрывающихся дерева. Было точно известно, что одного не хватит, а вопрос о том, достаточно ли двух, оставался загадкой более 20 лет.

Исследователи из МФТИ и СПбГУ закрыли эту проблему в своей недавней работе. Они строго математически доказали, что двух деревьев всегда достаточно, независимо от того, сколько точек на карте — десять или миллион. Работа опубликована в сборнике трудов Симпозиума SIAM по дискретным алгоритмам.

Секрет кроется в правильном распределении «зон ответственности». Ученые разработали алгоритм, при котором первая сеть выстраивается так, чтобы идеально соединять точки по одним направлениям (например, условно с севера на юг), а вторая сеть берет на себя остальные направления (с запада на восток). Взаимно дополняя друг друга, две эти схемы перекрывают все возможные углы и гарантируют, что для любых двух объектов хотя бы в одной из сетей найдется короткий и прямой путь.

Доказательство того, что двух деревьев достаточно, имеет прямое практическое следствие: теперь многие алгоритмы, использующие три и более сетей для подстраховки, можно будет переписать, сделав их компактнее и быстрее.

Граф с четырьмя вершинами и все восемь его остовных деревьев: ребра каждого дерева выделены оранжевым. Каждое остовное дерево содержит все вершины исходного графа и не содержит циклов / © Andreschulz / Wikimedia Commons

Андрей Купавский, заведующий лабораторией комбинаторных и геометрических структур МФТИ, прокомментировал открытие так: «Интерес к этой и подобным задачам вызван тем, что такие структуры внутри сложных сетей позволяют эффективно решать задачи типа маршрутизации. Действительно, маршрутизацию по дереву организовать предельно просто, ввиду того что между любыми двумя вершинами в дереве ровно один путь.

Задача об оптимальном числе таких сетей на плоскости выглядит обманчиво просто, но долго не поддавалась решению. Ключом к решению является симметричная конструкция двух деревьев, в которых зоны точек с большими расстояниями по дереву взаимно дополнительны. Вообще, довольно удивительно, что такая конструкция существует. Мы надеемся, что наш результат придаст импульс к изучению аналогичных вопросов в многомерных пространствах».