Алгоритм найти 100 самых длинных склонов на земле, которые круче всего 30 градусов?

Question

Этот вопрос носит более концептуальный характер, поскольку у меня нет кода для его отображения на данный момент.Тем не менее, мне было интересно, смогу ли я получить некоторую помощь о том, как я мог бы приступить к кодированию чего-то подобного, не затрачивая на то, чтобы программа вычисляла годы.

В принципе, представьте себе, что базовому джамперу вингсьюту требуется как минимум 30 градусов.наклон, чтобы пролететь безопасную линию до его посадки.Как мы можем найти самую длинную линию полета, которую он может пройти на земле?

        |----
        |     ----
        |         ----               A slope with a 3-1 glide angle
 100m   |             ----
        |                 ----
        |_________________________
                     300m

Наша планета имеет ~ 510 миллионов км ² поверхности.Давайте предположим, что мы хотим взять точку данных каждые 200 м, что соответствует 25 точкам данных на квадратный километр.Решение n ^ 2 здесь явно недостаточно хорошо.

Вот мои мысли о возможном решении: перебрать все (510 * 25) миллионов возможных начальных точек.Соедините эти точки с соседними точками-соседями в форме графика.Поскольку теперь у нас есть сетка взаимосвязанных точек в виде графика, мы можем удалить все ребра, которые не соответствуют требованию наклона 30 градусов.Далее мы используем алгоритм, чтобы найти самый длинный путь в ориентированном ациклическом графе.

https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/

Будет ли мое решение работать?Возможно ли вычислить?Мысли о других решениях?

Answer 1

Сортировка точек по высоте.

Создание массива для самого длинного пути к каждой точке и инициализация его нулями - это путь, с которого начинается эта точка.

Обработка точекв порядке убывания высоты.Для каждой точки найдите длину самого длинного пути к ней и используйте ее, чтобы скорректировать самые длинные пути к ее нижним соседям.

Самый длинный путь к каждой точке будет правильным при обработке ее, так как онаможет зависеть только от точек более высокой отметки, которые уже были обработаны.

Запомните наибольшее число, которое вы видите, и это будет длина самого длинного пути.Если вы помните, где он находится, вы можете восстановить путь, работая в обратном направлении, многократно находя старшего соседа с самым длинным путем к нему.

Общее время равно O (N log N), в котором преобладает начальная сортировка.