Москва Яндекс общество самит интересное Москва

Как ускорить A* в пробках в 10 раз

В три часа ночи A* ищет маршрут по Москве в 11 раз экономнее алгоритма Дейкстры: перебирает в 11 раз меньше перекрёстков. В половине девятого утра на тех же самых запросах от этого выигрыша остаётся 2,5 раза.

Алгоритм тот же, просто на дорогах пробки.Мне давно интересно, как навигаторы успевают за доли секунды проложить маршрут через огромный город, да ещё с учётом пробок.

DMCA