Close
07 июля 2022, Четверг
Читайте самые интересные новости в мире.

Математик решил задачу, над которой исследователи бились 40 лет

18.03.2021 Разместил: Редакция ESOREITER / Источник: POPMECH.RU 1469

Математик решил задачу, над которой исследователи бились 40 летФото из открытых источников

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

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

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

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

Исследователи представили сеть в виде так называемого динамического графа. Он представляет собой абстрактное представление сети, состоящей из ребер и узлов. Если переводить это на транспортную аналогию, то ребрами будут дороги, а узлами — перекрестки. Динамичный граф может изменяться с течением времени, поэтому новый алгоритм способен учитывать такие изменения.

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

Исследование было представлено на конференции IEEE Symposium on Foundations of Computer Science.

‹ Назад
Вперед ›
Метки:
Время
Разные интересные новости в мире
В США суд обязал женщину платить алименты насильнику
17.06.2022 1629

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

Скрытую экосистему обнаружили подо льдами Антарктиды
14.06.2022 1473
Ученые выяснили, как рост человека влияет на его здоровье
04.06.2022 1444
Внезапное решение сделало мужчину богатым
22.06.2022 1432
В Ноябрьске выловили пиранью с «человеческими» зубами
16.06.2022 1410