карты и навигация

Статьи

DS Структура данных Система непересекающихся множеств Слить два множества и узнать, в одном ли элементы, — почти за O(1): лес ссылок на родителя и два приёма. O(α(n)) 2 задачи GRA Приём Как хранить граф Матрица, списки, массив рёбер и CSR: память, скорость и какие вопросы каждая запись задаёт дёшево.

соседи вершины: O(n) у матрицы, O(deg) у списков и CSR; есть ли ребро: O(1) у матрицы, O(deg) у списков

O(V + E) — жадно в данном порядке и «наименьший последним»; O((V + E) log V) — DSatur с кучей

2 задачи GRA Алгоритм Венгерский алгоритм Кому какую работу при наименьшей общей цене: потенциалы, честные пары и увеличивающие пути за O(n³). O(n³) 2 задачи GRA Алгоритм Поток наименьшей стоимости Поток с наименьшей суммарной ценой: круги отрицательной стоимости, кратчайшие пути с потенциалами, транспортная задача 1930 года. O(F · E log V) 2 задачи GRA Алгоритм Эйлеров путь Пройти каждое ребро ровно раз: правило нечётных вершин и алгоритм Хирхольцера за O(E). O(V + E) 3 задачи DP Приём Динамическое программирование Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице. состояния × переходы 2 задачи DP Приём Динамика по маскам Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю. O(2ⁿ · n²) для коммивояжёра 2 задачи DP Алгоритм Алгоритм Витерби Самая правдоподобная цепочка скрытых состояний по шумным наблюдениям: улицы по GPS, участки генома, сообщение по битам. O(T · S²) 2 задачи NUM Алгоритм Китайская теорема об остатках Число по остаткам от нескольких модулей: алгоритм Гарнера и точные вычисления по многим простым. O(k²) операций с машинными числами 2 задачи GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи GEO Алгоритм Точка в многоугольнике Луч из точки пересекает границу нечётное число раз — точка внутри; число оборотов — то же со знаками. O(n) на точку 2 задачи GEO Алгоритм Площадь многоугольника Площадь по координатам вершин: сумма xᵢyᵢ₊₁ − xᵢ₊₁yᵢ, а её знак — направление обхода. O(n) 2 задачи GEO Приём Заметающая прямая Упростите берега мира до 0,2° — и в 72 местах они пересекутся. Прямая с запада на восток найдёт их все, сравнив только соседей. O((n + k) log n) 3 задачи GEO Алгоритм Триангуляция Делоне и диаграмма Вороного Зоны ближайшей точки и треугольники с пустыми окружностями: две стороны одной структуры. O(n log n) в среднем 2 задачи GEO Структура данных k-d дерево Двоичное дерево, которое делит пространство по осям по очереди: ближайшая точка — за десятки шагов вместо перебора. O(n log n) построение; O(log n) на запрос в среднем 1 задача GEO Структура данных R-дерево Окно карты 10° × 5°: из 58 987 отрезков берега R-дерево проверяет 847 прямоугольников. И находит город, дальше всех от моря. окно — число открытых узлов × M; ближайший — обычно O(log n) узлов 1 задача GEO Приём Вращающиеся калиперы У 971 из 2679 кварталов центра Алматы наименьший прямоугольник повёрнут на 4–8°: сетка улиц смотрит не строго на север. O(n) после оболочки, O(n log n) с ней 2 задачи GEO Алгоритм Упрощение линий Рамера — Дугласа — Пекера Упростить ломаную без потери формы: точка, дальше всех от хорды, остаётся, если она дальше допуска. O(n log n) в типичном случае, O(n²) в худшем 2 задачи ML Алгоритм k ближайших соседей Отвечает так, как ответило большинство из k самых похожих известных примеров. O(n · d) на вопрос 2 задачи RND Приём Случайные блуждания Шаг наугад на каждом перекрёстке: √t, время до цели, «кто первый» и 2-SAT случайным блужданием. O(1) на шаг 2 задачи RND Алгоритм Имитация отжига Локальный поиск, который принимает ухудшения с вероятностью e^(−Δ/T) и постепенно остывает. O(S · c) 2 задачи

Задачи

Есть ли такой участок Район по соседям Во сколько раз длиннее по улицам Заехать по пути Маршрут курьера Маршруты без шагов назад Ночные перекрытия Перекрёсток: внутри, снаружи или на границе Пересекаются ли отрезки Разъезд со стадиона Станции проката Упростить тропу Честная подсказка Где поставить новую часть Граница без петель Запросы по ярусам Карта на всех масштабах Курьеры и заказы Ленивый турист Маршруты без общих перекрёстков Меньше поворотов Мосты и тоннели Навигатор без тригонометрии Недостающие улицы Перекрытия улиц Перекрёсток на ремонте Пожарные части Покрытие снимками Самый короткий круг Сколько кругов Частоты для вышек Что попало в окно Электромобиль в горах Запасной маршрут Никто не едет далеко Снегоуборщик

Часто рядом

классика 26 граф 13 собеседования 11 геоданные 11 олимпиады 9 точки на плоскости 9 взвешенный граф 8 кратчайший путь 7 оптимизация 6 многоугольник 6 куча 5 эвристика 5