Qualcuno può aiutarmi a capire quest'algoritmo in pseudocodice?

[nadiaT]

Ciao!Qualcuno può aiutarmi a capire quest'algoritmo in pseudocodice?

Questa è la traccia:
Si consideri una scacchiera M di m righe (numerate 0, . . . ,m − 1) ed n colonne
(numerate 0, . . . , n − 1) in cui la cella (i, j) contiene l’intero positivo M(i, j). Un
cammino legale sulla scacchiera `e un cammino da una casella della riga 0 ad una
casella della riga m − 1 che ha la seguente caratteristica: se ci si trova nella casella
(i, j) (riga j e colonna i) con j < m − 1, al prossimo passo si pu`o visitare o la casella
((i − 3) mod n, j + 1) o la casella ((i + 3) mod n, j + 1). Il valore di un cammino
legale `e semplicemente la somma degli interi nelle caselle visitate.
Si progetti un algoritmo che riceve in input una scacchieraM e calcola il valore massimo
di un cammino legale in M.

SOLUZIONE:

Scacchiera(M)
for i = 0 to n − 1
V (i,m − 1) = M(i,m − 1);
for j = n − 2 downto 0
for i = 0 to n − 1
V (i, j) = M(i, j) + max{V ((i − 3) mod n, j + 1), V ((i + 3) mod n, j + 1)}.
Vmax= V (0, 0);
for i = 1 to n − 1
Vmax= max{Vmax, V (i, 0)};
return Vmax;

[YuYevon]

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

for j = n − 2 downto 0

deve essere

for j = m − 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...

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

il valore massimo di un cammino legale in M.

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 pure

[nadiaT]

Ti ringrazio davvero tanto!dopo cerco di provare con lo schema! Non riesco a capire che fa il primo ciclo for!!

[YuYevon]

Originariamente inviato da nadiaT
Non riesco a capire che fa il primo ciclo for!!

Beh, se hai compreso il resto dell'algoritmo, il primo ciclo for risponde allo stesso concetto:

copia l'ultima riga della scacchiera M nell'ultima della matrice V.

Perché?

Perché in effetti... quale sarebbe il massimo camminio legale (per ogni casella) dall'ultima riga della scacchiera... fino all'ultima riga della scacchiera? Ovviamente sono proprio i valori presenti nell'ultima riga, ecco perché questi vengono copiati per pari-pari nell'ultima riga della matrice V.