Как найти Путь наименьшей стоимости в 2D-матрице

Question

У меня задача Задача - получить самую низкую стоимость пути. Путь может проходить по горизонтали или по диагонали. не вертикально. как показано ниже. и первая и последняя строки также смежны.

для примера см ниже матриц:

output for 1st matrix : 
16 
1 2 3 4 4 5-->path row number 

output for second matrix: 
11 
1 2 1 5 4 5-->path row number 

делает это в Java, я получаю самый низкий путь, но я не получает путь для печати пути, используя строку номера.

int minCost(int cost[r][r], int m, int n) 
{ 
    if (n < 0 || m < 0) 
     return Integer.MAX_VALUE;; 
    else if ((m == r-1 && n == c-1)|| n+1>=c) 
     return cost[m][n]; 
    else 
     return cost[m][n] + min(minCost(cost, m+1>=r?r-1:m+1,n+1), 
             minCost(cost, m,n+1), 
           minCost(cost, m-1>=0?m-1:r-1,n+1)); 
    } 
// calling it 
minCost(cost, 0, 0); 

Как получить номера строк для кратчайшего пути?

Answer 1

Попробую расширить комментарий Фабиана:

Это ясно, что ваша minCost функция будет возвращать те же значения, при вызове с теми же аргументами. В вашем алгоритме он действительно называется много раз с одинаковыми значениями. Каждый вызов для нулевого столбца будет генерировать 3 вызова для столбца 1, которые, в свою очередь, генерируют 9 вызовов для столбца 2 и т. Д. Последний столбец получит огромное количество вызовов (3^r как указатель на фабиан), большинство из которых пересчитывает одинаковые значения для других вызовов.

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

После этого вы можете оптимизировать использование пространства, заменив вторую матрицу только на два столбца, так как вам не понадобится столбец n-1, если у вас есть столбец n полностью рассчитан. Это может быть немного сложно, поэтому, если вы не уверены, я рекомендую использовать полный массив в первый раз.

Answer 2

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

8 6 
7 4 
9 5 
2 6 
2 3 

Если теперь мы на ячейку со значением 8, следующим шагом может быть 6/4/3. Конечно, мы выбираем 3, потому что хотим меньшую стоимость. Если теперь мы на ячейку со значением 7, следующим шагом может быть 6/4/5, мы выберем 4. Таким образом, две колонки можно объединить в одну колонку:

11 //8+3 
11 //7+4 
13 //9+4 
5 //2+3 
5 //2+3 

Теперь повторить последние два столбца :

2 11 
2 11 
9 13 
3 5 
1 5 

И наконец, матрица будет объединена в один столбец, наименьшее значение в столбце будет иметь самую низкую стоимость.