Максимальная стоимость обхода в матрице с использованием динамического программирования

Ответ 1

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

Это требует от нас определения "состояния", чтобы проблема могла быть записана в терминах решения n-way, которое выводит нас в новое состояние, которое, в свою очередь, представляет собой новую, меньшую версию той же проблемы.

Подходящим выбором для состояния является текущая позиция обхода плюс целое число со знаком f, которое говорит, где и сколько неверных (я буду называть их "свободными" ) строками, которые находятся в текущем столбце. Мы можем записать это как тройку [i, j, f].

Значение f говорит нам, хорошо ли двигаться вверх и/или вниз. (Если мы не находимся в правой колонке, всегда можно двигаться вправо, и никогда не удастся сдвинуться влево.) Если f отрицательно, есть f свободных строк "выше" текущей позиции, которая может обернуться вокруг матрицы дно. Если положительный, ниже f свободных строк. Заметим, что f = m-1 и f = 1-m означают одно и то же: все строки свободны, кроме текущей позиции. Для простоты мы будем использовать f == m-1 для представления этого случая.

Единственное целое число f - это все, что нам нужно для описания свободных пространств, потому что мы можем двигаться только по шагам размера 1, и мы никогда не двигаемся влево. Ergo не может быть несмежных групп свободных пространств в одном столбце.

Теперь решение DP "является 4-сторонним выбором:

• Постоять на текущем квадрате: действителен только в последнем столбце.
• Перемещение вверх: действует только при наличии свободного места.
• Перейти вниз: только действительный, если есть свободное место ниже.
• Переместить вправо: допустимо, за исключением последнего столбца.

Пусть C (t) - функция максимальной стоимости в DP, где t - тройка [i, j, f]. Тогда максимальная стоимость, которую мы можем достичь, - это стоимость A [i, j] из матрицы, добавленной к стоимости остальной части обхода после принятия оптимального решения с 1 по 4 выше. Оптимальное решение - это только тот, который производит самую высокую стоимость!

Все это делает C максимальным числом, в котором все элементы являются условными.

C[i,j,f] = max { A[i,j] if j==n-1, // the "stand pat" case
               { A[i,j]+C[i,j+1,m-1] if j<n-1  // move right
               { A[i,j]+C[i+1,j,f-1] if f>0    // move down
               { A[i,j]+C[i-1,j,2-m] if f==m-1 // first move in col is up
               { A[i,j]+C[i-1,j,f+1] if f<0    // other moves up

Иногда слова яснее алгебры. Случай "вниз" будет...

Одна потенциальная максимальная стоимость пути от позиции [i, j] до цели (правый столбец) - это значение матрицы A [i, j] плюс максимальная стоимость, доступная при перемещении вниз к позиции [i + 1, j]. Но мы можем двигаться вниз, только если там есть свободные пространства (f > 0). После того, как он движется вниз, есть еще один из них (f-1).

Это объясняет, почему рекурсивное выражение C [i + 1, j, f-1]. Другими случаями являются лишь вариации этого.

Также обратите внимание, что "базовые случаи" неявны выше. Во всех состояниях, где f = 0 и j = n-1, вы их имеете. Рекурсия должна прекратиться.

Чтобы получить окончательный ответ, вы должны рассмотреть max над всеми действительными начальными позициями, которые являются первыми элементами столбца, и со всеми остальными элементами в столбце: max C[i,0,m-1] для я = 0..m-1.

Поскольку вам не удалось найти DP, вот код построения таблицы, чтобы показать, что он работает. Зависимости в DP требуют осторожности при выборе порядка оценки. Конечно, параметр f может быть отрицательным, а параметр строки обертывается. Я позаботился об этом в двух функциях, которые настраивают f и i. Хранение - O (m ^ 2):

import java.util.Arrays;

public class MaxPath {
  public static void main(String[] args) {
    int[][] a = {
      {2, 3, 17},
      {4, 1, -1},
      {5, 0, 14}
    };
    System.out.println(new Dp(a).cost());
  }
}

class Dp {
  final int[][] a, c;
  final int m, n;

  Dp(int[][] a) {
    this.a = a;
    this.m = a.length;
    this.n = a[0].length;
    this.c = new int[2 * m - 2][m];
  }

  int cost() {
    Arrays.fill(c[fx(m - 1)], 0);
    for (int j = n - 1; j >= 0; j--) {
      // f = 0
      for (int i = 0; i < m; i++) {
        c[fx(0)][i] = a[i][j] + c[fx(m - 1)][i];
      }
      for (int f = 1; f < m - 1; f++) {
        for (int i = 0; i < m; i++) {
          c[fx(-f)][i] = max(c[fx(0)][i], a[i][j] + c[fx(1 - f)][ix(i - 1)]);
          c[fx(+f)][i] = max(c[fx(0)][i], a[i][j] + c[fx(f - 1)][ix(i + 1)]);
        }
      }
      // f = m-1
      for (int i = 0; i < m; i++) {
        c[fx(m - 1)][i] = max(c[fx(0)][i], 
            a[i][j] + c[fx(m - 2)][ix(i + 1)], 
            a[i][j] + c[fx(2 - m)][ix(i - 1)]);
      }
      System.out.println("j=" + j + ": " + Arrays.deepToString(c));
    }
    return max(c[fx(m - 1)]);
  }
  // Functions to account for negative f and wrapping of i indices of c.
  int ix(int i) { return (i + m) % m; }
  int fx(int f) { return f + m - 2; }
  static int max(int ... x) { return Arrays.stream(x).max().getAsInt(); }
}

Здесь вывод. Если вы понимаете DP, вы можете увидеть, что он строит оптимальные пути назад из столбца j = 2 в j = 0. Матрицы индексируются через f = -1,0,1,2 и я = 0,1,2.

j=2: [[31, 16, 14], [17, -1, 14], [17, 13, 31], [31, 30, 31]]
j=1: [[34, 35, 31], [34, 31, 31], [34, 32, 34], [35, 35, 35]]
j=0: [[42, 41, 44], [37, 39, 40], [41, 44, 42], [46, 46, 46]]
46

Результат показывает (j = 0, столбец f = m-1 = 2), что все элементы, если первый столбец одинаково хороши в качестве отправных точек.

Ответ 2

Это тяжело. Обратите внимание: поскольку ваш путь не может повторять посещенные ячейки, ваши возможные пути будут иметь поведение типа "змея", например:

Идея состоит в том, чтобы сохранить в f[j][i] максимальную длину путей, которые заканчиваются в ячейке (j, i). Теперь скажем, что мы хотим перейти от f[j][i-1] в f[j'][i]. Таким образом, мы можем либо перейти от ячейки (j, i) к ячейке (j', i) напрямую, либо мы могли бы перейти от ячейки (j, i) к ячейке (j', i), обернув верхний/верхний край. Таким образом, обновление для f[j][i], тогда, может быть рассчитано как:

где

Здесь a - заданный массив.

Теперь проблема заключается в том, как эффективно вычислять sum(a[j..j'][i], так как в противном случае время выполнения будет O(m^3n). Вы можете решить эту проблему, используя временную переменную tmp_sum для sum(a[j..j'][i]), которую вы увеличиваете по мере увеличения j. Тогда runitme алгоритма будет O(m^2 n).

Вот пример реализации:

package stackoverflow;

public class Solver {

    int m, n;
    int[][] a, f;

    public Solver(int[][] a) {
        this.m = a.length;
        this.n = a[0].length;
        this.a = a;
    }

    void solve(int row) {
        f = new int[m][n];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                f[i][j] = Integer.MIN_VALUE;

        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = 0; j < m; ++j)
                sum += a[j][i];
            for (int j1 = 0; j1 < m; ++j1) {
                int tmp_sum = 0;
                boolean first = true;
                for (int j2 = j1; j2 != j1 || first; j2 = (j2+1)%m) {
                    if (first)
                        first = false;
                    tmp_sum += a[j2][i];
                    int best_sum = Math.max(tmp_sum, sum - tmp_sum +a[j1][i]+a[j2][i]);
                    if (j1 == j2)
                        best_sum = a[j1][i];
                    int prev = 0;
                    if (i > 0)
                        prev = f[j1][i-1];
                    f[j2][i] = Math.max(f[j2][i], best_sum + prev);
                }
            }
        }

        System.out.println(f[row][n-1]);
    }

    public static void main(String[] args) {
        new Solver(new int[][]{{2, 3, 17}, {4, 1, -1}, {5, 0, 14}}).solve(0); //46
        new Solver(new int[][]{{1, 1}, {-1, -1}}).solve(0); //2
    }
}

Ответ 3

Спасибо всем за ваши вклады.

Я придумал решение, используя метод recursive, используя system stack. Я думаю, что мое решение относительно легче понять.

Здесь мой код:

import java.util.Scanner;

public class MatrixTraversal {

    static int[][] cost;
    static int m, n, maxCost = 0;

    public static void solve(int currRow, int currCol, int[][] isVisited, int currCost) {

        int upperRow, lowerRow, rightCol;
        isVisited[currRow][currCol] = 1;

        currCost += cost[currRow][currCol];             //total cost upto current position

        if( currCol == (n - 1)                          //if we have reached the last column in matrix
            && maxCost < currCost )                     //and present cost is greater than previous maximum cost
            maxCost = currCost;

        upperRow = ((currRow - 1) + m) % m;             //upper row value taking care of teleportation
        lowerRow = (currRow + 1) % m;                   //lower row value taking care of teleportation
        rightCol = currCol + 1;                         //right column value

        if( isVisited[upperRow][currCol] == 0 )     //if upper cell has not been visited
            solve(upperRow, currCol, isVisited, currCost);

        if( isVisited[lowerRow][currCol] == 0 )     //if lower cell has not been visited
            solve(lowerRow, currCol, isVisited, currCost);

        if( rightCol != n &&                            //if we are not at the last column of the matrix
            isVisited[currRow][rightCol] == 0 )     //and the right cell has not been visited
            solve(currRow, rightCol, isVisited, currCost);

        isVisited[currRow][currCol] = 0;

    }

    public static void main(String[] args) {

        int[][] isVisited;
        int i, j;

        Scanner sc = new Scanner(System.in);

        System.out.print("Enter the no.of rows(m): ");
        m = sc.nextInt();

        System.out.print("Enter the no.of columns(n): ");
        n = sc.nextInt();

        cost = new int[m][n];
        isVisited = new int[m][n];

        System.out.println("Enter the cost matrix:");
        for(i = 0; i < m; i++)
            for(j = 0; j < n; j++)
                cost[i][j] = sc.nextInt();              //generating the cost matrix

        for(i = 0; i < m; i++)
            solve(i, 0, isVisited, 0);                  //finding maximum traversal cost starting from each cell in 1st column 

        System.out.println(maxCost);

    }

}

Однако я не уверен, является ли это лучшим и самым быстрым способом вычисления решения.

Пожалуйста, дайте мне знать ваши взгляды. Я приму это как ответ соответственно.

Ответ 4

Одна из возможных оптимизаций состоит в том, что нам нужно всего лишь вычислить различные параметры (отличные от полной суммы) для столбцов с отрицательными числами или последовательностей неотрицательных столбцов меньше m по длине, заключенных в столбцы с отрицаниями. Нам нужен один столбец и (концептуальная) матрица для вычисления max для последовательности таких столбцов; матрицу для текущего столбца, которая преобразуется в столбец максимумов для каждой точки выхода. Каждая матрица представляет собой максимальную сумму для входа в y и выход в y' в сочетании с предыдущим максимумом, непосредственно предшествующим точке входа (для каждого из них есть две возможности, в зависимости от направления пути). Матрица симметрично отражается по диагонали (значение sum entry...exit = sum exit...entry) до тех пор, пока не будут добавлены различные предыдущие максимумы для каждой точки входа.

Добавив в пример дополнительный столбец с отрицательными числами, мы можем увидеть, как могут применяться кумулятивные суммы:

2  3  17  -3
4  1  -1  15
5  0  14  -2

(Мы проигнорируем первые два неотрицательных столбца и добавим 15 позже.)

Third column:

 y' 0  1  2
y 
0   17 30 31
1   30 -1 30
2   31 30 14

Для четвертой матрицы столбцов каждая точка входа должна сочетаться с максимумом для одной и той же точки выхода из предыдущего столбца. Например, точка входа 0 добавляется с помощью max(17,30,31):

 y' 0  1  2
y 
0   -3 12 10  + max(17,30,31)
1   12 15 13  + max(30,-1,30)
2   10 13 -2  + max(31,30,14)

       =

    28 43 41
    42 45 43
    41 44 29

Мы можем видеть, что последний max имеет (вход, выход) (1,1) и решение:

15 + (0,1) or (2,1) + (1,1)

Ответ 5

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

a = {{17, -3}
    ,{-1, 15}}

Грубая сила будет перемещаться и сравнивать все пути:

17,-3
17,-3,15
17,-1,15
17,-1,15,-3

-1,15
-1,15,-3
-1,17,-3
-1,17,-3,15

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

Варианты выбора в рекурсивном решении, предлагаемые Gene, приводят к аналогичному обходу, найденному в циклах в решении svs, что означает, что выбор между входом и выходом в том же столбце будет сокращен. Посмотрите еще раз на наш пример:

a = {{17, -3}
    ,{-1, 15}}

f(-1) -> max(15,15 - 3)
      -> 17 -> max(-3,-3 + 15) 

f(17) -> max(-3,-3 + 15)
      -> -1 -> max(15,15 - 3) 

Нет необходимости проверять полную сумму пути -1,15,-3 или проверять как 17 - 1 + 15, так и 17 - 1 + 15 - 3, поскольку в каждом случае мы уже знаем, какое окончание будет больше, благодаря функции max: 17 - 1 + 15.

Решения матричной матрицы работают несколько иначе, чем рекурсивные, но с аналогичным эффектом. Мы фокусируемся только на перемещении между столбцами j to j + 1, что может произойти только в одном месте, и мы решили добавить только лучшую сумму до j, когда вычисляем j + 1. Посмотрите на пример:

a = {{17, -3}
    ,{-1, 15}}

Вычислите матрицу наилучших сумм для точек выхода вдоль столбца j = 0, в O(m^2) время:

17
16

Теперь для j = 1 мы вычисляем наилучшие пути, достижимые только вдоль столбца j = 1 с точками выхода вдоль столбца j = 1, не забывая добавить к точкам входа эти точки лучше всего (это означает, что число из столбца сразу влево, обозначается символом *):

best exit at -3 = max(-3 + 17*, 15 - 3 + 16*) = 28
best exit at 15 = max(15 + 16*, -3 + 15 + 17*) = 31

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