Comments 6
Звучит как чудо. Этак скоро и задачу коммивояжера осилим. И на большое О проблему нашу замахнемся)
Не вижу в тексте не описание алгоритма на пальцах, ни в псевдокоде. Невнимательно что ли читал мелкий текст)
В тексте есть ссылка
Я правильно понял текст, что фактически речь идет об иерархическом поиске, где иерархия организуется не по геометрическому принципу, а по принципу связности кластеров?
Может я невнимательно читал. А алгоритм A* разве не тоже самое?
Конечно результат интересный, но сильно преувеличен. Они нашли алгоритм работающий за O(E log^(2/3) V), что быстрее дейкстрового O(E + V log V) только для разряженных графов. Так-то есть уже другие алгоритмы, которые быстрее дейкстры для определенного класса графов. Например, тот же форд-беллман быстрее, если граф сильно связен и все кратчайшие пути в нем состоят из маленького количества ребер.
С теоретической точки зрения это интересно и дает повод надеятся, что есть алгоритмы лучше Дейкстры в общем случае, но пока даже не близко это.
Математики превзошли классический алгоритм поиска пути в графе