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

Одна из самых классических алгоритмических задач связана с вычислением кратчайшего пути между двумя точками. Более сложный вариант проблемы — когда маршрут пересекает изменяющуюся сеть — будь то дорожная сеть или Интернет. В течение 40 лет разрабатывался алгоритм, обеспечивающий оптимальное решение этой проблемы. Теперь компьютерный ученый Кристиан Вульф-Нильсен из Копенгагенского университета и двое его коллег-исследователей придумали рецепт.

Направляясь в новое место, большинство из нас оставляют на усмотрение компьютерных алгоритмов, которые помогут нам найти лучший маршрут, будь то с помощью автомобильного GPS или общественного транспорта и картографических приложений на своем телефоне. Тем не менее, бывают случаи, когда предлагаемый маршрут не совсем соответствует действительности. Это потому, что дорожные сети, сети общественного транспорта и другие сети не статичны. Лучший маршрут может внезапно оказаться самым медленным, например, из-за образования очереди из-за дорожных работ или аварии.

Люди, вероятно, не задумываются о сложной математике, лежащей в основе предложений маршрутизации в подобных ситуациях. Используемое программное обеспечение пытается решить вариант классической алгоритмической задачи «кратчайшего пути», кратчайшего пути в динамической сети. В течение 40 лет исследователи работали над поиском алгоритма, который мог бы оптимально решить эту математическую головоломку. Теперь Кристиан Вульф-Нильсен из факультета компьютерных наук Копенгагенского университета вместе с двумя коллегами смог расколоть орех.

«Мы разработали алгоритм, для которого теперь у нас есть математическое доказательство того, что он лучше, чем любой другой алгоритм до настоящего времени — и наиболее близок к оптимальному, который когда-либо будет, даже если мы заглянем на 1000 лет в будущее», говорит доцент Вульф-Нильсен. Результаты были представлены на конференции FOCS 2020.

Оптимально в этом контексте относится к алгоритму, который тратит как можно меньше времени и памяти компьютера на вычисление наилучшего маршрута в данной сети. Это относится не только к дорожным и транспортным сетям, но также к Интернету или любым другим типам сетей.

Сети как графики

Исследователи представляют сеть как так называемый динамический граф ». В этом контексте граф представляет собой абстрактное представление сети, состоящей из ребер, дорог, например, и узлов, представляющих, например, пересечения. Когда граф является динамическим, это означает, что он может меняться со временем.Новый алгоритм обрабатывает изменения, состоящие из удаленных краев — например, если эквивалент участка дороги внезапно становится недоступным из-за дорожных работ.

«Огромное преимущество рассмотрения сети как абстрактного графа состоит в том, что его можно использовать для представления любого типа сети. Это может быть Интернет, куда вы хотите отправлять данные по как можно более короткому маршруту, человеческий мозг или сеть дружеских отношений на Facebook. Это делает алгоритмы графов применимыми в самых разных контекстах », — объясняет Кристиан Вульф-Нильсен.

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

Чем больше данных, тем лучше алгоритмы

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

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

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

Фон

• На престижной конференции FOCS 2020 была представлена ​​исследовательская статья «Почти оптимальная декрементальная SSSP в плотных взвешенных орграфах».
• Статья написана Кристианом Вульф-Нильсеном из факультета компьютерных наук Копенгагенского университета и бывшим докторантом факультета компьютерных наук Максимилианом Пробстом Гутенбергом и доцентом Аароном Бернстайном из Университета Рутгерса.
• Версия проблемы «кратчайшего пути», которую решили исследователи, называется «декрементальной проблемой кратчайшего пути от одного источника». По сути, речь идет о поддержании кратчайших путей в изменяющейся динамической сети от одной начальной точки до всех других узлов в графе. Изменения в сети состоят из удаления краев.
• В статье приводится математическое доказательство того, что данный алгоритм по сути является оптимальным для динамических сетей. В среднем пользователи смогут менять маршруты в соответствии с расчетами, сделанными в постоянное время.