www.wired.com/story/new-method-is-the-fa...ind-the-best-routes/
A New Algorithm Makes It Faster to Find the Shortest Paths
Каноническая задача в информатике — поиск кратчайшего пути к каждой точке сети. Новый подход превосходит классический алгоритм, изучаемый в учебниках.
Если вы хотите решить сложную задачу, часто помогает организация. Например, можно разбить задачу на части и начать с самых простых. Но такая сортировка имеет свою цену. Вы можете потратить слишком много времени на раскладывание частей по порядку.
Эта дилемма особенно актуальна для одной из самых известных задач в информатике: поиска кратчайшего пути от заданной начальной точки сети до любой другой точки. Это как улучшенная версия задачи, которую приходится решать каждый раз при переезде: найти оптимальный маршрут от нового дома до работы, спортзала и супермаркета.
Интуитивно понятно, что проще всего найти кратчайший путь к ближайшим пунктам назначения. Поэтому, если вы хотите разработать максимально быстрый алгоритм для задачи поиска кратчайшего пути, кажется разумным начать с поиска ближайшей точки, затем следующей по близости и так далее. Но для этого вам потребуется многократно определять, какая точка ближе всего.
Вы будете сортировать точки по расстоянию по мере продвижения. Существует фундаментальное ограничение скорости для любого алгоритма, использующего этот подход: вы не можете двигаться быстрее времени, необходимого для сортировки.
Сорок лет назад исследователи, разрабатывавшие алгоритмы поиска кратчайших путей, столкнулись с этим «барьером сортировки». Теперь группа исследователей разработала новый алгоритм, который его преодолевает . Он не сортирует, но работает быстрее любого алгоритма, который это делает.
..........
