План облёта
Нужно составить план облёта: самолёт вылетает из одного города, посещает все остальные по одному разу и возвращается. Точный кратчайший маршрут для полутора тысяч городов не найдёт никто, да и не нужно: достаточно маршрута, который не длиннее эталонного больше чем на десятую часть. Эталон — тот, что строят методы из статьи.
Самолёт летит по дуге большого круга; расстояние — по формуле гаверсинуса с R = 6371 км, как в задаче «Туда на восток, обратно на запад». Третий тест — все города мира от полумиллиона жителей, четвёртый — все города с населением от 10 000 в 800 км вокруг Алматы (GeoNames).
Вход
В первой строке n (1 ≤ n ≤ 1500). Дальше n строк: широта и долгота города в градусах.
Выход
Одну строку: номера всех городов от 1 до n в порядке облёта, каждый ровно один раз. Маршрут замкнутый — после последнего города самолёт возвращается в первый. Ответ принимается, если длина маршрута не больше 1,1 длины эталонного.
Примеры
Пример 1
8 40.000 60.000 42.000 61.000 40.000 62.000 42.000 63.000 40.000 64.000 42.000 65.000 40.000 66.000 42.000 67.000
1 3 5 7 8 6 4 2
Пример 2
15 45.000 77.000 47.500 76.062 49.330 73.500 50.000 70.000 49.330 66.500 47.500 63.938 45.000 63.000 42.500 63.938 40.670 66.500 40.000 70.000 40.670 73.500 42.500 76.062 45.000 70.000 46.000 71.000 44.000 69.000
11 12 1 2 3 4 5 6 14 13 15 7 8 9 10
Ограничения
- Время · Python
- 10000 мс
- Время · Go
- 4000 мс
- Память
- 256 МБ
- Проверка
- 6 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Начните с маршрута «каждый раз в ближайший непосещённый город» и посчитайте его длину. Почему конец такого маршрута обычно плохой?
2Подсказка 2
Если два ребра маршрута пересекаются, их можно заменить двумя другими — и маршрут станет короче. Как искать такие пары быстро, не перебирая все пары рёбер?
3Идея
Построить маршрут ближайшим соседом и править его локальным поиском, как в статье: 2-opt (заменить два ребра двумя, развернув кусок между ними) и Or-opt (перенести кусок из одного–трёх городов в другое место). Перебирать все пары рёбер не нужно: новое ребро должно быть короче старого, поэтому для города a достаточно смотреть на его ближайших соседей, а списки «десять ближайших» считаются один раз. Биты «не смотреть» отправляют город на повторную проверку, только если рядом с ним что-то поменялось.
4Разбор
Расстояния считаются один раз в таблицу. Ближайший сосед — O(n²). Дальше очередь городов: достали a, для ребра к следующему городу b пробуем соседей c из списка, пока d(a, c) < d(a, b); если замена рёбер a–b, c–e на a–c, b–e выгодна, разворачиваем кусок между ними (короче — тот кусок, который меньше) и ставим четыре затронутых города в очередь. То же для ребра к предыдущему городу. Когда очередь пуста, проходим Or-opt; если он что-то перенёс — снова 2-opt.
Ближайший сосед в одиночку проигрывает эталону больше десяти процентов уже на первом примере и на всех настоящих тестах; одного 2-opt со списками соседей обычно хватает с запасом.
4+Решение
5Сложность
Таблица расстояний и списки соседей — O(n² log n), ближайший сосед — O(n²). Локальный поиск со списками соседей делает на каждый город десяток проверок за раз и на практике растёт почти линейно; разворот куска стоит до n/2 перестановок.
6Типичные ошибки
- Только ближайший сосед. На больших тестах его маршрут на 13–21 % длиннее эталона: последние города остаются разбросанными, и к ним летят через полкарты.
- 2-opt по всем парам. Верен, но каждый проход стоит n²/2 проверок; на полутора тысячах городов в Python это слишком долго.
- Сравнение без запаса. Расстояния дробные, и замена с нулевой выгодой из-за округления может казаться выгодной; без маленького запаса поиск разворачивает один и тот же кусок туда и обратно.