Одна из самых классических алгоритмических задач связана с вычислением кратчайшего пути между двумя точками. Более сложный вариант проблемы – когда маршрут пересекает изменяющуюся сеть, будь то дорожная сеть или интернет. В течение 40 лет исследователи искали алгоритм оптимального решения проблемы. Ученый-компьютерщик Кристиан Вульф-Нильсен из Копенгагенского университета с двумя коллегами нашли его.Большинство сейчас доверяют создание своих маршрутов компьютерным алгоритмам. Бывает, проложенный маршрут не совсем соответствует действительности. Транспортно-дорожные сети не статичны. Лучший маршрут может внезапно оказаться самым медленным из-за дорожных работ, аварии, резкого перераспределения трафика теми же навигационными приложениями.
Пользователи не задумываются о сложной математике в основе предложений маршрутизации в подобных ситуациях. Используемое программное обеспечение пытается решить вариант классической алгоритмической задачи «кратчайшего пути» в динамической сети. В течение 40 лет исследователи работали над поиском алгоритма, который мог бы оптимально решать такие математические головоломки. Кристиан Вульф-Нильсен с факультета компьютерных наук Копенгагенского университета с двумя коллегами создали алгоритм и математическое доказательство, что он лучше, чем любой другой существующий «и наиболее близок к оптимальному, который когда-либо будет, даже если мы заглянем на 1000 лет в будущее», утверждает доцент Вульф-Нильсен. Результаты были представлены на престижной конференции FOCS 2020.
«Оптимально» значит: алгоритм тратит минимум времени и памяти компьютера на вычисление наилучшего маршрута в данной сети. Это относится не только к дорожным и транспортным сетям, но к интернету и любым другим типам сетей.
Сети как графики
Исследователи представляют сеть в виде так называемого динамического графа – абстрактного представления сети, состоящей из ребер, например, дорог, и узлов, представляющих, например, перекрестки. Когда график динамический, это означает, что он может меняться со временем. Новый алгоритм обрабатывает изменения, состоящие из удаленных краев, например, если эквивалент участка дороги внезапно становится недоступным из-за дорожных работ.
Огромное преимущество рассмотрения сети как абстрактного графа состоит в том, что его можно использовать для представления любого типа сети. Это может быть интернет, куда вы хотите отправлять данные по как можно более короткому маршруту, человеческий мозг или лента друзей на Фейсбуке. Это делает алгоритмы графов применимыми в самых разных контекстах, объясняет Кристиан Вульф-Нильсен.
Традиционные алгоритмы предполагают, что график статичен, что редко бывает верным в реальном мире. Когда такие алгоритмы используются в динамической сети, их необходимо запускать повторно каждый раз, когда на графике происходит небольшое изменение, что тратит время.
Чем больше данных, тем лучше алгоритмы
Поиск лучших алгоритмов полезен не только во время путешествий. Как отмечает Кристиан Вульф-Нильсен, это необходимо практически в любой области, где производятся данные: мы живем в то время, когда объемы данных растут с огромной скоростью, а разработка оборудования просто не успевает за ними. Чтобы управлять всеми данными, которые мы производим, нам необходимо разработать более умное программное обеспечение, которое требует меньше памяти и времени на выполнение. Вот почему нам нужны более умные алгоритмы.
Кристиан Вульф-Нильсен надеется, что можно будет использовать этот алгоритм или некоторые из лежащих в его основе методов на практике, но подчеркивает, что пока это теория, которая требует экспериментов.
Исследовательская статья «Почти оптимальная декрементальная SSSP в плотных взвешенных орграфах» была представлена на престижной конференции FOCS 2020.