На практике бывает нужно проложить оптоволоконный кабель между сотнями городов или настроить маршрутизатор, который передает пакеты данных между тысячами компьютеров. Соединить каждую точку с каждой напрямую невозможно: это очень дорого и потребует гигантских вычислительных мощностей. Поэтому инженеры и программисты ищут способы создать такую экономную сеть проводов, чтобы, с одной стороны, потратить минимум ресурсов на ее постройку, а с другой — гарантировать, что путь между двумя точками не превратится в огромный крюк.
Экономные сети жизненно важны для работы интернета, синхронизации баз данных, сетей умных датчиков и систем машинного обучения. Чем проще схема такой сети, тем меньше памяти она занимает в устройстве и тем быстрее работает система.
В математике и информатике для построения таких экономных сетей используют «деревья». Дерево — это схема связей (граф), в которой нет замкнутых маршрутов. Если два дома находятся на соседних улицах, но подключены к разным веткам сети, то сигналу придется идти от первого дома к центральной станции, а оттуда — ко второму. То есть путь по сети окажется во много раз длиннее, чем реальное расстояние по прямой.
Чтобы избежать таких крюков, программисты идут на хитрость: они создают сразу несколько разных деревьев (схем связи) для одних и тех же точек и накладывают их друг на друга. Если в первой схеме путь между нужными домами слишком длинный, система мгновенно проверяет вторую или третью схему, и находит короткий маршрут.
С 1998 года в компьютерных науках считалось, что для гарантированно короткого пути на плоскости (например, на карте) нужно использовать как минимум три перекрывающихся дерева. Было точно известно, что одного не хватит, а вопрос о том, достаточно ли двух, оставался загадкой более 20 лет.
Исследователи из МФТИ и СПбГУ закрыли эту проблему в своей недавней работе. Они строго математически доказали, что двух деревьев всегда достаточно, независимо от того, сколько точек на карте — десять или миллион. Работа опубликована в сборнике трудов Симпозиума SIAM по дискретным алгоритмам.
Секрет кроется в правильном распределении «зон ответственности». Ученые разработали алгоритм, при котором первая сеть выстраивается так, чтобы идеально соединять точки по одним направлениям (например, условно с севера на юг), а вторая сеть берет на себя остальные направления (с запада на восток). Взаимно дополняя друг друга, две эти схемы перекрывают все возможные углы и гарантируют, что для любых двух объектов хотя бы в одной из сетей найдется короткий и прямой путь.
Доказательство того, что двух деревьев достаточно, имеет прямое практическое следствие: теперь многие алгоритмы, использующие три и более сетей для подстраховки, можно будет переписать, сделав их компактнее и быстрее.
Андрей Купавский, заведующий лабораторией комбинаторных и геометрических структур МФТИ, прокомментировал открытие так: «Интерес к этой и подобным задачам вызван тем, что такие структуры внутри сложных сетей позволяют эффективно решать задачи типа маршрутизации. Действительно, маршрутизацию по дереву организовать предельно просто, ввиду того что между любыми двумя вершинами в дереве ровно один путь.
Задача об оптимальном числе таких сетей на плоскости выглядит обманчиво просто, но долго не поддавалась решению. Ключом к решению является симметричная конструкция двух деревьев, в которых зоны точек с большими расстояниями по дереву взаимно дополнительны. Вообще, довольно удивительно, что такая конструкция существует. Мы надеемся, что наш результат придаст импульс к изучению аналогичных вопросов в многомерных пространствах».