Взвешенная матрица кратчайшего пути

Найдите кратчайший путь от любого элемента в крайней левой части заданной матрицы размера n x n до любого элемента в крайней правой части матрицы.

Движение: движение может быть только одним квадратом за раз. Вы можете перемещаться влево, вправо, вверх-влево, вверх-вправо, вниз-влево и вниз-вправо.

Вес: Стоимость перехода от элемента X к Y в матрице составляет | Y - X |

Время выполнения: разработанный алгоритм должен быть не более O (n 2)

Пример:

Пример

Пробовал пока:

Пробовали

Проблема с этим решением.

Время выполнения - O (n 2 Log n 2), что медленнее, чем O (n 2).


c++ path algorithm matrix shortest-path
person Sergio Checo Nuñez    schedule 13.12.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете использовать это, когда рассматриваете ребра в вашем графе как ориентированные, ваш граф является ациклическим и имеет (частичный) топологический порядок. В этом случае вы можете просто вычислить расстояние слева для каждого узла слева направо, то есть столбец за столбцом.

В первом столбце это расстояние равно 0 для всех узлов, то есть d (вверху слева) = 0, d (слева посередине) = 0, d (слева внизу) = 0.

Во втором (и всех последующих) столбцах у вас есть не более трех возможных значений, из которых можно выбрать минимум, например, d (верхний средний) = MIN [d (верхний левый) + 4, d (средний левый) +2. ] = 2.

То есть вычисление значений слева направо занимает только постоянное время для каждого узла, Theta (n ^ 2) в целом. В более общем смысле, для N узлов и M ребер это занимает O (NM) для вычисления кратчайшего пути с одним источником.

[Edit: я удалил ссылку на динамическое программирование, так как это больше сбивает с толку, чем помогает. Добавлен пример.]

person Bastian J    schedule 13.12.2016
comment
Я немного запутался, как будет называться динамическое решение? Каким будет базовый вариант и другие условия? Что бы представляли строки и столбцы? - person Sergio Checo Nuñez; 14.12.2016