CS
Задачник Базовый курс EN

Задача

Маршрут по кривой Гильберта

сортировка точки на плоскости геоданные эвристика битовые трюки

Курьеру нужно объехать n точек на квадратной карте 65 536 × 65 536. Искать кратчайший маршрут — задача коммивояжёра, и для больших n её точно не решить. Но есть быстрый способ получить неплохой маршрут: пронумеровать клетки карты вдоль кривой Гильберта и объезжать точки по возрастанию номера их клетки.

Кривая Гильберта порядка 16 обходит все клетки карты по одному разу. Номер клетки (x, y) вычисляется так: начинаем с d = 0 и для s = 215, 214, …, 1 по очереди делаем шаг:

  • rx = 1, если бит s в x установлен, иначе 0; так же ry для y;
  • d увеличивается на s² · ((3·rx) XOR ry);
  • если ry = 0: при rx = 1 заменить x на s − 1 − x и y на s − 1 − y; затем поменять x и y местами.

Упорядочьте точки по номеру клетки (точки с одинаковым номером — в порядке входа) и выведите длину ломаной, которая проходит их в этом порядке. Расстояния — обычные, по прямой; возвращаться в начало не нужно.

Вход

В первой строке n (1 ≤ n ≤ 2·10⁵). Дальше n строк с координатами x и y (0 ≤ x, y < 65 536).

Выход

Длина маршрута. Ответ принимается с относительной погрешностью 10⁻⁶.

Примеры

Пример 1

Вход
6
0 0
65535 0
0 65535
65535 65535
32768 32768
100 30000
Выход
223750.086

Ограничения

Время · Python
9000 мс
Время · Go
1500 мс
Память
256 МБ
Проверка
6 тестов

Разбор

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

1Подсказка 1

Номер клетки зависит только от её координат. Посчитайте его для каждой точки, отсортируйте — и сложите длины отрезков.

2Идея

Ключ сортировки — пара (номер клетки на кривой, номер точки во входе). Номер считается за 16 шагов — по шагу на бит, как в условии. Сортировка — O(n log n), длина маршрута — один проход с math.hypot.

3Разбор

Почему такой маршрут хорош: соседние номера на кривой Гильберта — соседние клетки карты, и точки, которые оказались рядом в порядке обхода, почти всегда рядом и на карте. Кривая заходит в каждую четверть карты один раз и обходит её целиком, прежде чем выйти, — так же внутри каждой четверти четверти. Так строить маршрут предложили Джон Бартольди и Лорен Платцман в 1980-х; у них была кривая Серпинского, но свойства у таких кривых похожи: на случайных точках маршрут выходит примерно на четверть длиннее кратчайшего, а в худшем случае отношение растёт лишь как логарифм числа точек.

Четвёртый тест — все 19 073 землетрясения M5+ за 2015–2025 годы на сетке мира. Маршрут вдоль кривой Гильберта — около 2,77 млн клеток. Если объезжать их в Z-порядке, как сортирует geohash, выйдет в 1,3 раза длиннее: Z-кривая прыгает между четвертями. В порядке каталога, то есть по времени, — в 171 раз длиннее, а в случайном порядке — в 209 раз.

Подробнее о кривых и о том, где ими пользуются базы данных, — в статье «Кривые Гильберта и geohash».

3+Решение
4Сложность

O(n log n): по 16 шагов на номер и сортировка.

5Типичные ошибки
  • Z-порядок вместо Гильберта. Перемешать биты x и y проще, но это другая кривая и другой маршрут — уже на примере.
  • Забыть поворот. Без замены и перестановки координат в шаге номер получается не гильбертовым: кривая рвётся на границах четвертей.
  • Неустойчивая сортировка. Точки в одной клетке нужно брать в порядке входа — третий тест.

Алгоритмы задачи

GEO Приём Кривые Гильберта и geohash Пронумеровать плоскость так, чтобы соседи на карте стояли рядом в одномерном индексе: Z-порядок, geohash, Гильберт. O(k) на номер 1 задача GRA Алгоритм Задача коммивояжёра Кратчайший объезд всех точек: ближайший сосед, 2-opt со списками соседей, Or-opt, оценка Хелда — Карпа. NP-трудна; точно O(2ⁿ · n²) 2 задачи
Каталог алгоритмов