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

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


directed-acyclic-graphs algorithm language-agnostic directed-graph
person null0pointer    schedule 13.05.2012    source источник
comment
Значения с плавающей запятой - это веса ребер? Похоже на проблему динамического программирования.   -  person Vaughn Cato    schedule 14.05.2012
comment
Алгоритм @AljoshaBre Ли кажется немного медленным. Я вижу, как это будет работать, но сложность O(MN) не идеальна, тем более что я буду иметь дело с M, N > 1000.   -  person null0pointer    schedule 14.05.2012
comment
@VaughnCato Я уверен, что есть хорошее решение для динамического программирования, но я не знаю, что это такое.   -  person null0pointer    schedule 14.05.2012

Ответы (1)


arrow_upward
1
arrow_downward

  • Пункт списка

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

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

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

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

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

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

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

person svinja    schedule 14.05.2012