Кратчайшие пути для ориентированных ациклических графов

Question

Так что, в основном, у меня есть массив значений по-равным n по m, и я пытаюсь найти кратчайший путь между любой из первой строки значений и любой из m-й строки значений , Узел (i, j) на графике есть дети {(i, j+1), (i-1, j+1), i+1, j+1)} для любого узла, который не находится на краю (0 < i < n-1) и не находится в нижней строке (j < m-1). Я ищу алгоритм для решения этой конкретной проблемы заблаговременно. Моя текущая мысль движется вокруг поиска A *, но дайте мне знать, что вы думаете.

Answer 1

• элемент списка

Динамические решения O (NM) или O (M^2). И это не может пойти под этим - вот контрпример для любого лучшего решения. Предположим, вы хотите найти путь между самым левым элементом первой строки и самым левым элементом последней строки. Давайте посмотрим на матрице этой формы:

10000000000000 
11000000000000 
11100000000000 
11110000000000 
11111000000000 
11111100000000 
11111110000000 
11111111000000 
11111110000000 
11111100000000 
11111000000000 
11110000000000 
11100000000000 
11000000000000 
10000000000000 

«1s» являются элементами, которые вы могли бы потенциально пройти через на пути от источника к элементу назначения. «0s» - это элементы, которые вы не можете пройти.

Число «1s» от NM/4 порядка, поэтому O (NM) (фактически, Min (NM, M^2), см. Ниже). Таким образом, алгоритм, который считывает каждый из 1s в этой матрице, будет иметь сложность> = O (NM).

Алгоритм, который не считывает все «1s», с другой стороны, будет неправильным.

Доказательство: Пусть числа в матрице будут весами. Выберите «1», который алгоритм не читает. Измените значение от 1 до 0,5. Алгоритм терпит неудачу для этого ввода, так как оптимальный путь теперь проходит через элемент, который он никогда не читает (поскольку ни один из элементов, которые он читал в первый раз, не изменился, на этот раз он будет читать те же элементы, если он не недетерминирован, и в этом случае это случайная вероятность, будет ли она работать, что также делает ее неправильной).

Однако хорошие решения O (NM) должны работать нормально только для матриц 1000x1000 (в секунду). Вы можете оптимизировать его до Min (M^2, MN), если вы только когда-нибудь нажмете на элементы, которые вы должны ударить (например, в моей примерной матрице, если ширина увеличена до 10000000, вам не нужно читать добавленные элементы). Аналогично, если высота увеличена до 10000000, у вас не будет чтения порядка M^2, потому что вы не выходите за границы матрицы. Однако, как вы говорите, оба измерения очень велики, это мало помогает, я думаю.