Guarda, non è semplice da spiegare a parole ma se provi a farti una rappresentazione grafica con una scacchiera di dimensioni fisse scelte da te, vedi che non è poi tanto difficile da capire.
Preliminariamente ti dico che forse c'è un errore.
Questa riga
deve esserecodice:for j = n − 2 downto 0
Il "forse" è per la serie "di sicuro c'è solo la morte", ma seguendo la logica dell'algoritmo direi proprio che lì ci va il numero di righe meno due (quindi m-2) e non quello delle colonne...codice:for j = m − 2 downto 0
Detto questo, in sostanza quest'algoritmo utilizza una matrice V per fare i calcoli che ha esattamente le stesse dimensioni della scacchiera (quindi m-1 x n-1).
Col primo ciclo for, all'ultima riga della matrice V vengono assegnati esattamente gli stessi valori dell'ultima riga della scacchiera M.
Coi due cicli for annidati successivi, poi, la scacchiera M viene percorsa dal basso verso l'alto, più precisamente dalla penultima riga m-2 (visto che l'ultima l'abbiamo già analizzata ~ e comunque è proprio per questo che ti dicevo che c'è un errore) alla prima della scacchiera, e ovviamente ognuna di queste viene letta da sinistra verso destra, dalla prima all'ultima colonna (come si fa sempre per le matrici, in sostanza).
Praticamente l'algoritmo non fa nient'altro che il cammino a ritroso e per ogni casella va a calcolare (con quella somma) il valore massimo del cammino che si avrebbe da quella casella fino alla fine della scacchiera (sommando al valore presente in quella casella il massimo tra i valori delle due caselle possibili su cui ci si può spostare alla riga successiva), per cui alla fine la matrice V avrà - per ogni riga - le somme dei numeri posizionati su tutti i possibili cammini dalla corrispondente riga della scacchiera M fino alla fine.
Esempio: siamo arrivati alla riga tre della scacchiera (provenendo dal basso).
La riga 3 corrispondente della matrice V contiene i valori numerici che sono la somma di tutti i numeri posti su tutti i possibili cammini dalla riga 3 della scacchiera fino all'ultima, quindi se vuoi sapere qual è il cammino legale con il massimo valore dalla terza riga della scacchiera fino alla fine, non devi fare altro che determinare il massimo di quella riga della matrice V.
Data questa proprietà, avremo che alla fine la prima riga della matrice V conterrà le somme dei numeri di tutti i possibili cammini dalla prima riga della scacchiera M (visto che stiamo considerando la prima della matrice V) fino alla fine, per cui a quel punto ti basta fare una semplice ricerca del massimo sulla prima riga (ricerca che viene fatta nell'ultimo for dell'algoritmo) e avrai appunto quello che l'algoritmo deve determinare come output, ossia
Mi rendo conto che è un casino a spiegarlo per iscritto... ti consiglio - come ti dicevo - di provare a vederlo con un esempio pratico, magari sfruttando questa piccola spiegazione... e se c'è qualche punto in particolare che non comprendi... beh, chiedi pureil valore massimo di un cammino legale in M.
Rispondi quotando