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

Habr · · g524901

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

В три часа ночи A* ищет маршрут по Москве в 11 раз экономнее алгоритма Дейкстры: перебирает в 11 раз меньше перекрёстков. В половине девятого утра на тех же самых запросах от этого выигрыша остаётся 2,5 раза. Алгоритм тот же, просто на дорогах пробки. Мне давно интересно, как навигаторы успевают за доли секунды проложить маршрут через огромный город, да ещё с учётом пробок. Чтобы разобраться, я собрал свой простой вариант на настоящей карте Москвы и упёрся ровно в эту проблему. Тогда захотелось проверить, можно ли вернуть A* в час пик его ночную форму. Попробовал две поправки: таблицу из 96 чисел и крошечную нейросеть на 169 параметров. Обе поднимают выигрыш в час пик до 10–12 раз, а маршрут выходит в среднем на 1–2% дольше идеального. Дальше расскажу, как это устроено, и покажу цифры по 1800 запросам. Смотреть цифры и карты

Источник: Habr