Пекинские ученые сделали то, что почти 70 лет считалось невозможным: придумали способ искать кратчайшие пути в графах быстрее, чем классический алгоритм Дейкстры, и пробили так называемый «барьер сортировки». Почему это важно? Дейкстра — легенда компьютерной науки. Мы храним вершины в приоритетной очереди, каждый раз берём ближайшую, проверяем рёбра и обновляем расстояния. Всё упирается в поддержание очереди в строго упорядоченном виде — а это и есть тот самый барьер, который десятилетиями казался непробиваемым. Что сделали авторы В новой методике, которую они назвали BMSSP, упор сделали на экономию сил при сортировке: В итоге сложность алгоритма упала с O(m + n log n) у Дейкстры до O(m log^(2/3) n) у BMSSP — логарифм растёт заметно медленнее, и на больших графах это ощутимо. Зачем это нужно ИИ На первый взгляд — чистая теория. Но на практике алгоритм Дейкстры скрыт почти везде: Теперь у ИИ и всех, кто работает с графами, есть инструмент, который экономит миллионы операций и даёт фору там, где раньше считалось: «Быстрее не получится».