102 подписчика
Как Uber вычисляет расчетное время прибытия
(объяснение за 2 минуты или меньше):
1. Они представляют физическую карту в виде графика.
2. Они вычисляют расчетное время прибытия, находя кратчайший путь в ориентированном взвешенном графе.
3. Они не используют алгоритм Дейкстры, потому что он не масштабируется со сложностью O(n*logn)
4. Они разбивают граф, а затем предварительно вычисляют наилучший путь внутри каждого раздела.
5. Они уменьшают временную сложность с O(n^2) до O(n) путем разбиения графа
6. Они заполняют веса ребер графа информацией о дорожном движении.
7. Они используют фильтр Kalman и алгоритм Viterbi для сопоставления карт, чтобы точно определить время прибытия.
Около минуты
5 августа 2025