Java - somma massima in percorso attraverso una matrice 2D

Question

Fondamentalmente ho un problema che va qualcosa di simile a questo:

C'è un giardino di piante di fragola rappresentati da un 2D, matrice quadrata. Ogni pianta (ogni elemento) ha un numero di fragole. Si inizia nell'angolo in alto a sinistra dell'array e si può solo spostarsi a destra o in basso. Devo progettare un metodo ricorsivo per calcolare i percorsi attraverso il giardino e quindi produrre quello che produce il maggior numero di fragole.

Penso di avere una comprensione dei problemi di ricorsione davvero molto semplici, ma questo problema mi è passato in testa. Non sono davvero sicuro da dove cominciare o dove andare fino alla creazione di un metodo ricorsivo.

Qualsiasi aiuto correlato al codice o che mi aiuti a comprendere il concetto alla base di questo problema è molto apprezzato. Grazie.

Answer 1

Come dasblinkenlight Detto questo, il modo più efficace per farlo è usare un Memoizzazione o tecnica di programmazione dinamica. Tendo a preferire la programmazione dinamica, ma userò la ricorsione pura qui.

La risposta è incentrata sulla risposta a una domanda fondamentale: "Se sono nel quadrato della riga r e colonna c sul mio campo, come posso valutare il percorso dall'angolo in alto a sinistra in modo tale che il numero di le fragole sono massimizzate? "

La chiave per capire è che ci sono solo due modi per ottenere il grafico nella riga r e colonna c: o posso arrivare da sopra, usando il grafico nella riga r-1 e colonna c, o posso ottenere lì di lato, usando il grafico nella riga r e nella colonna c-1. Dopo di che, è sufficiente per assicurarsi di sapere i vostri casi di base ... che significa, fondamentalmente, la mia versione puramente ricorsiva sarebbe qualcosa di simile:

int[][] field;  
int max(int r, int c) { 
    //Base case 
    if (r == 0 && c == 0) { 
     return field[r][c]; 
    } 
    //Assuming a positive number of strawberries in each plot, otherwise this needs 
    //to be negative infinity 
    int maxTop = -1, maxLeft = -1; 
    //We can't come from the top if we're in the top row 
    if (r != 0) { 
     maxTop = field[r-1][c]; 
    } 
    //Similarly, we can't come from the left if we're in the left column 
    if (c != 0) { 
     maxLeft = field[r][c-1]; 
    } 
    //Take whichever gives you more and return.. 
    return Math.max(maxTop, maxLeft) + field[r][c]; 
} 

chiamata max (r-1, c-1) a ottieni la tua risposta Si noti che qui c'è molta inefficienza; farai molto meglio usando la programmazione dinamica (che fornirò di seguito) o la memoizzazione (che è già stata definita). La cosa da ricordare, però, è che entrambe le tecniche di DP e di memoizzazione sono semplicemente modi più efficienti che derivano dai principi ricorsivi qui usati.

DP:

int maxValue(int[][] field) { 
    int r = field.length; 
    int c = field[0].length; 
    int[][] maxValues = new int[r][c]; 
    for (int i = 0; i < r; i++) { 
     for (int j = 0; j < c; j++) { 
      if (i == 0 && j == 0) { 
       maxValues[i][j] = field[i][j]; 
      } else if (i == 0) { 
       maxValues[i][j] = maxValues[i][j-1] + field[i][j]; 
      } else if (j == 0) { 
       maxValues[i][j] = maxValues[i-1][j] + field[i][j]; 
      } else { 
       maxValues[i][j] = Math.max(maxValues[i][j-1], maxValues[i-1][j]) + field[i][j]; 
      } 
     } 
    } 
    return maxValues[r-1][c-1]; 
} 

In entrambi i casi, se si desidera ricreare il percorso effettivo, basta tenere una tavola 2D di booleani che corrisponde con "vengo al di sopra oa sinistra"? Se la maggior parte del percorso della fragola proviene da sopra, metta il vero, altrimenti metta falso. Ciò può consentire di rintracciare la patch dopo il calcolo.

Si noti che questo è ancora ricorsivo in linea di principio: ad ogni passaggio, stiamo guardando indietro ai nostri risultati precedenti. Abbiamo appena memorizzato nella cache i risultati precedenti, quindi non sprechiamo un sacco di lavoro e stiamo attaccando i sottoproblemi in un ordine intelligente in modo che possiamo sempre risolverli. Per ulteriori informazioni sulla programmazione dinamica, vedere Wikipedia.

Answer 2

È possibile farlo utilizzando memoization. Ecco pseudodoce di tipo Java (memo, R e C sono considerate variabili di istanza disponibili per il metodo max).

int R = 10, C = 20; 
int memo[][] = new int[R][C]; 
for (int r=0 ; r != R ; r++) 
    for (int c = 0 ; c != C ; c++) 
     memo[r][c] = -1; 
int res = max(0, 0, field); 

int max(int r, int c, int[][] field) { 
    if (memo[r][c] != -1) return memo[r][c]; 
    int down = 0; right = 0; 
    if (r != R) down = max(r+1, c, field); 
    if (c != C) right = max(r, c+1, field); 
    return memo[r][c] = (field[r][c] + Math.max(down, right)); 
} 

Answer 3

È possibile risolvere questo problema con il metodo di tabulazione DP, con il quale è possibile risparmiare spazio da O (m * n) a solo O (n). Con Memorizzazione DP, è necessario m * n matrice per memorizzare valori intermedi. Di seguito è riportato il mio codice Python. Spero che possa aiutare.

def max_path(field): 
    dp = [sum(field[0][:i]) for i in range(1, len(field[0]) + 1)] 
    for i in range(1, len(field)): 
     for j in range(len(dp)): 
      dp[j] = min(dp[j], dp[j - 1] if j > 0 else float('inf')) + field[i][j] 
    return dp[-1]