Как увеличить значение пути?

Question

Нам задана сетка N * N. И мы сначала находимся в верхнем левом углу сетки. Каждый квадрат сетки имеет некоторое значение, привязанное к нему, то есть, если кто-то достигает этой площади, он выигрывает сумму денег в долларах, равную стоимости, прикрепленной к квадрату. Теперь правовые шаги - это один шаг вправо или один шаг к основанию. Мы должны достигнуть нижнего правого угла сетки по пути, чтобы мы могли максимизировать сумму выигранных денег. Очевидно, мы должны оставаться внутри сетки и не можем ее покинуть. Я начал эту проблему с жадного подхода, который на каждом шаге мы смотрим на непосредственный правый квадрат и ближайший квадрат ниже занимаемого квадрата, и на каждом шаге выбираем квадрат с более высоким значением. Но это не дает правильного результата все время. Например, в следующей сетке,

{ 6, 9, 18, 1 } 
{ 2, 10, 0, 2 } 
{ 1, 100, 1, 1 } 
{ 1, 1, 1, 1 } 

здесь мой алгоритм дает максимальный оцененный путь как

6 -> 9 -> 18 -> 1 -> 2 -> 1 -> 1 

, который составляет до 37, но мы могли бы заработали больше на пути

6 -> 9 -> 10 -> 100 -> 1 -> 1 -> 1 

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

#include <iostream> 
#include <queue> 
using namespace std; 
int main() 
{ int n; cin >> n; 
int a[n+1][n+1], b[n+1][n+1]; 
for (int i=0;i<n;i++) 
{ 
for (int j=0;j<n;j++) 
{ 
    cin >> a[i][j]; b[i][j]=a[i][j]; 
} 
} 

queue <int> q; int u,v,m=0; 
q.push(0);q.push(0); 
while (q.size()!=0) 
{ 
    u=q.front(); q.pop(); v=q.front(); q.pop(); 
    if (v<n-1) 
    { 
     m=b[u][v]+a[u][v+1]; 
     if (m>b[u][v+1]) 
     { b[u][v+1]=m; } 
     q.push(u);q.push(v+1); 
    } 
    if (u<n-1) 
    { 
     m=b[u][v]+a[u+1][v]; 
     if (m>b[u+1][v]) 
     { b[u+1][v]=m; } 
     q.push(u+1);q.push(v); 
    } 
} 
cout << b[n-1][n-1]; 
return 0; 
} 

Answer 1

На самом деле это проблема, которая разрешима с использованием динамического программирования. Вам нужно всего лишь адаптировать алгоритм для вычисления расстояния редактирования, позволяющего варьировать вознаграждения. Алгоритм описан, например, в https://web.stanford.edu/class/cs124/lec/med.pdf

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

Answer 2

Проблема может быть решена с помощью следующего подхода. Каждая ячейка в позиции (i,j) ассоциируется со значением val(i,j), которое является максимальным общим значением, достигаемым при достижении его с описанными правовыми ходами (снизу, справа), начиная с позиции (0,0). Значение в позиции (0,0) - это значение из сетки, в дальнейшем называемое grid(i,j) за каждые i, j in {0,...,N-1}. Получает follwing рекуррентного соотношения

val(i,j) = grid(i,j) + max{ val(i-1,j), // path coming from upper cell 
          val(i,j-1) // path coming from left cell 
          } 

где мы предполагаем, что показатели за пределами {0,...,N-1} * {0,...N-1} дают величину отрицательной бесконечности и никогда реально не используются. Рекуррентное соотношение справедливо, поскольку для достижения ячейки требуется не более двух случаев, а именно от ее верхнего соседа или его левого соседа (за исключением клеток на границе, которые, возможно, могут быть достигнуты только у одного соседа).

Ключевым моментом для эффективной оценки val является организация вычисления значений в последовательности, так что все необходимые соседи уже оцениваются; это может быть сделано путем успешного поиска в самой левой ячейке, для которой val еще не рассчитан и работает оттуда вверх-вправо, пока не будет достигнут верхний ряд. Это повторяется до тех пор, пока не будет оценена позиция val(N-1,N-1), что даст желаемый результат.

Если дополнительно требуется конкретный путь к (N-1,N-1), то для сохранения того, как вычисляется значение в вышеуказанном соотношении повторения, то есть, какой-либо термин дает максимальный результат, необходимо использовать либо обратную трассировку, либо некоторую дополнительную структуру данных.

Редактировать

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