Алгоритм обхода сетки, собирающей как можно больше точек

Рассмотрим двумерную сетку m*n, в которой каждая ячейка может содержать либо 1, либо 0. Найдите наибольшее значение, которое может получить обход, перемещаясь по этой сетке. Значение можно увеличить, пройдя по диагонали через 1 ячейку. Обход сетки подчиняется следующим правилам:

  1. Начните с верхней левой ячейки.
  2. В каждой ячейке обход может двигаться вниз на одну сетку, перемещаться на одну сетку вправо или двигаться по диагонали (перемещаться на одну сетку вниз и двигаться на одну сетку вправо). Если ячейка содержит 1 и обход движется по диагонали, то значение обхода увеличивается на 1.
  3. Обход не может выйти за пределы сетки (если на правом краю нельзя двигаться вправо, если на нижнем краю нельзя двигаться вниз).
  4. Конец в правом нижнем углу.

Наивный алгоритм рассмотрит все 3*m*n обходов и выберет наибольшее значение. Может ли кто-нибудь помочь мне найти лучшее решение? Есть ли алгоритм, решающий подобную задачу?

Это не вопрос интервью, мне нужно это, чтобы попытаться оптимизировать алгоритм Смита-Уотермана.

Примеры:

Следующая сетка имеет максимальное значение 2:

введите здесь описание изображения

Этот имеет максимальное значение 7:

введите здесь описание изображения


algorithm math graph-algorithm discrete-mathematics dna-sequence
person Wayne Hong    schedule 09.03.2014    source источник
comment
Вот несколько примеров. Следующая сетка имеет максимальное значение 2 imgur.com/bT3ROru Эта сетка имеет максимальное значение 7. imgur.com/55jU5XJ   -  person Wayne Hong    schedule 09.03.2014
comment
Уверен, вам нужно динамическое программирование. Пусть f(x,y) будет максимальным значением пути, который заканчивается в ячейке (x,y). Его можно вычислить из значений f(x-1,y), f(x,y-1) и f(x,y), поэтому его можно решить в O(n*m), что кажется оптимальным, поскольку это размер ввода.   -  person Niklas B.    schedule 09.03.2014
comment
Вам нужно немного уточнить вопрос, потому что критерии для получения балла кажутся мне расплывчатыми. Предположим, вы перемещаетесь из ячейки [x,y] в [x+1,y+1] (движение по диагонали), а также предположим, что шаг до этого и после этого не являются диагональными, делает ли значение 1 в ячейке [x,y ] дает вам право набрать 1 балл, или значение 1 в ячейке [x+1,y+1] дает вам право на получение 1 балла?   -  person firemana    schedule 25.03.2014

Ответы (3)


arrow_upward
3
arrow_downward

Используйте динамическое программирование:

dp[i, j] = maximum value obtainable from [1, 1] to [i, j]
dp[1, _] = dp[_, 1] = 0 -> we cannot get to any of these diagonally
dp[i, j] = max(dp[i - 1, j], -> come from above
i, j > 1       dp[i, j - 1], -> come from the left
               dp[i - 1, j - 1] + v[i, j] -> come diagonally and add what is at [i, j]
              )

Ответ будет в dp[m, n].

Сложность равна O(n*m), что является оптимальным, поскольку столько времени требуется только для чтения ввода.

Примечание.

Наивный алгоритм рассмотрит все 3*m*n обходов и выберет наибольшее значение.

На самом деле это должно быть 3 to the power of (n*m), потому что для каждой ячейки у вас будет 3 возможности, если вы переборщите.

person IVlad    schedule 09.03.2014
comment
Я чувствую, что этот алгоритм принципиально не отличается от Смита-Уотермана. Что я пытаюсь сделать, так это сделать алгоритм высокопараллельным, и этот подход вновь вводит сильную зависимость данных между ячейками. - person Wayne Hong; 10.03.2014
comment
Его наивный алгоритм означает алгоритм Смита-Уотермана, который также является O(n*m). ссылка - person gloompisces; 10.03.2014
comment
Это вообще не следует из вашего вопроса. Вы должны отредактировать свой вопрос и сказать, что вас интересуют способы сделать алгоритм параллельным. - person IVlad; 10.03.2014

arrow_upward
1
arrow_downward

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

все ваши ребра имеют вес 0, кроме тех, которые представляют диагональный ход, начинающийся с 1 клетки.

Теперь вы преобразовали свою проблему в задачу о самом длинном пути на направленном ациклическом графе (DAG). Это эквивалентно решению задачи о кратчайшем пути в DAG с отрицательными эквивалентными весами (т. е. все ребра с весом 1 превращаются в вес -1).

Для кратчайшего пути в DAG с отрицательным весом используйте алгоритм Беллмана-Форда. http://en.wikipedia.org/wiki/Bellman-Ford_algorithm

person firemana    schedule 25.03.2014

arrow_upward
0
arrow_downward

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

Я задал этот вопрос для распараллеливаемого алгоритма Смита-Уотермана, и в конце концов я собираюсь использовать этот http://biochem218.stanford.edu/Projects%202002/Byang.pdf

person Wayne Hong    schedule 09.03.2014