Основа QA

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