Компьютерщики разработали превосходный алгоритм поиска кратчайшего маршрута

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

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

Сети в виде графиков

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

Подписывайтесь на наш youtube канал!

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

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

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

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

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

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

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

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

Подписывайтесь на наш канал Яндекс Дзен!

P.S. И помните, всего лишь изменяя свое потребление - мы вместе изменяем мир! © econet