Минимальная стоимость пути от (0,0) до (N, N) в 2D сетке

Question

У меня проблема с 2D-сеткой, где вы пытаетесь найти кратчайший путь от (0, 0) до (N, N), где 1

Во время путешествия вы можете идти только вверх или к правильно. Точно так же ярлыки никогда не сместят вас вниз или влево.

Пример: Вы находитесь на (0, 0) и пытаетесь достичь (3, 3). Есть два ярлыка: один перемещает вас от (0, 1) к (0, 2), а другой перемещает вас от (1, 2) к (2, 3).

Лучший путь:

Перейти от (0,0) к (0,1) (1 единица). Ярлык к (0,2). Перейти от (0,2) до (1,2) (1 единица). Ярлык к (2,3). Перейдите от (2,3) к (3,3) (1 единица).

Таким образом, общая длина составит 3 единицы.

Временной интервал также составляет 2 секунды.

РЕДАКТИРОВАТЬ 1: У меня была идея использовать динамическое c программирование, чтобы сделать матрицу затрат. Матрица [i] [j] = общая стоимость пути для достижения (i, j). Однако сетка огромна, и матрица будет иметь 10 ^ 18 слотов, что слишком велико и не умещается во временные рамки.

РЕДАКТИРОВАТЬ 2: Следующей идеей было использование алгоритма Дейкстры; просто сделайте конец, начало и ярлыки всех узлов в графе. Тем не менее, это становится решением O (N ^ 2) (есть не более 10 ^ 10 ребер!)

РЕДАКТИРОВАТЬ 3: Я придумал другое решение O (N ^ 2). По сути, вы бы отсортировали все ярлыки в зависимости от их расстояния от источника. Затем вы найдете кратчайший путь к каждому ярлыку, просматривая все ярлыки, которые вы уже обработали. Вы найдете минимум (distTo (каждый ярлык) + manhattan_distance (each_shortcut, текущий ярлык)). В конце вы должны обработать точку (N, N), как если бы это был ярлык, чтобы найти ваше окончательное решение.

Однако это все еще слишком медленно - есть ли способ дальнейшей оптимизации моего решения или лучше?

Answer 1

Заметим, что мы можем посчитать расстояние от точки A до точки B в постоянное время abs (ax - bx) + abs (ay - by). Мы можем отсортировать все точки по его согласованию. После того, как мы запустим что-то вроде dp -> dist для точки x, будут минимальные оценки dist от порталов с i.x <= x.x && i.y <= x.x, где i - выход из портала, + dist от выхода к точке x. (учитывайте только x, если это начало или конец массива). Нам также необходимо удалить ранее рассмотренные точки и заменить их новой «виртуальной» точкой с наилучшей оценкой, если точка имеет худшую оценку в координатах по координате x, если мы считаем x нашей секундой для l oop.

Answer 2

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

Предполагая, что быстрое очень хорошее решение предпочтительнее, это мой подход:

Сортируйте ярлыки в соответствии с тем, насколько они хороши: то есть расстояние до Манхэттена, которое они вас спасают.

Для верхних ярлыков М, где М - небольшая дробь (возможно, 1/100 или даже 1). / 1000) из доступных ярлыков, вы будете рассчитывать «очень хороший» путь, который использует этот ярлык. Затем просто выберите лучший из этих путей.

Для каждого из тестируемых ярлыков используйте рекурсию, чтобы найти «очень хороший» путь для прямоугольника, определенного от начала до его входа, и и определенного своим выходом до конца. Поскольку вы уже отсортировали ярлыки, теперь вы находите верхние ярлыки М, которые находятся внутри меньших прямоугольников. Посчитайте их, как вы go через них, так что вы снова используете верхнюю маленькую дробь из них.

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

Как только вы закончите sh рекурсию и выберете лучший путь, вы должны повторить рекурсию, чтобы иметь возможность сказать, что это был за путь, но каждый шаг будет предварительно обрезать, так что на самом деле это будет очень тонкое «дерево» (в кавычках, потому что оно никогда не ветвится).