[Algoritmi] Matrice distanza minima
Ciao a tutti! Sto cercando di risolvere il seguente esercizio: consiste in poche parole nel cercar di trovare per una matrice quadrata A di dimensioni NxN contenente in ogni cella il peso corrispondente - numero intero, la sequenza di peso minimo che riesca a portarmi dalla prima cella A[1,1] alla cella desiderata A[j,i] in tempo $O(N^2)$ spostandomi solo verso il basso o verso destra (quindi da una cella all'altra posso spostarmi alla cella adiacente a destra, oppure a quella adiacente giù e non verso le altre).
Io ho provato a farlo creando quindi una matrice nuova che in ogni cella la sua distanza da A[1,1] facendo questo ragionamento:
1. la prima riga ha celle alle quali si può arrivare solo da sinistra e la prima colonna solo da sopra quindi basta ogni volta sommare a loro il contenuto iterativamente di quelle precedenti sulla stessa riga o colonna a seconda.
2. le altre celle avranno iterativamente minima distanza contenuta nelle celle $A[k,r]= \min(A[k-1,r], A[k,r-1])+A[k,r]$. Così si arriva a qualcosa del genere, per esempio:
Dopo per la cella A[j,i] che mi interessa basta tornare sulle orme come nell'immagine prendendo ogni volta il contenuto minimo... Insomma secondo me è giusto e pare che sia O(N^2). Per chi conosce l'algoritmo di Dijkstra, il ragionamento che ho fatto credo che sia banale... non so se ho fatto però quello che vuole l'esercizio, perché non capisco la seguente domanda:
Si enunci e si dimostri una proprietà di sottostruttura ottima per il problema e si derivi una ricorrenza dalla proprietà enunciata.
Io ho praticamente risposto alla seconda domanda ma questa è la prima, non la capisco sinceramente, qualcuno mi può aiutare per favore?
Io ho provato a farlo creando quindi una matrice nuova che in ogni cella la sua distanza da A[1,1] facendo questo ragionamento:
1. la prima riga ha celle alle quali si può arrivare solo da sinistra e la prima colonna solo da sopra quindi basta ogni volta sommare a loro il contenuto iterativamente di quelle precedenti sulla stessa riga o colonna a seconda.
2. le altre celle avranno iterativamente minima distanza contenuta nelle celle $A[k,r]= \min(A[k-1,r], A[k,r-1])+A[k,r]$. Così si arriva a qualcosa del genere, per esempio:
Dopo per la cella A[j,i] che mi interessa basta tornare sulle orme come nell'immagine prendendo ogni volta il contenuto minimo... Insomma secondo me è giusto e pare che sia O(N^2). Per chi conosce l'algoritmo di Dijkstra, il ragionamento che ho fatto credo che sia banale... non so se ho fatto però quello che vuole l'esercizio, perché non capisco la seguente domanda:
Si enunci e si dimostri una proprietà di sottostruttura ottima per il problema e si derivi una ricorrenza dalla proprietà enunciata.
Io ho praticamente risposto alla seconda domanda ma questa è la prima, non la capisco sinceramente, qualcuno mi può aiutare per favore?
Risposte
La proprietà in questione è \[\displaystyle D_{i\,j} = A_{i\,j} + \begin{cases} 0 & \text{per } i = 0,\, j = 0 \\ D_{0, j-1} & \text{per } i = 0 \\ D_{i-1, 0} & \text{per } j = 0 \\ \min\bigl( D_{i-1\,j}, D_{i\,j-1} \bigr) & \text{altrimenti} \end{cases} \] dove \(\displaystyle D \) è la matrice della distanza minima tra \(\displaystyle (1,1) \) e \(\displaystyle (i,j) \).
Considerando che pre-calcolare \(\displaystyle D \) ha un costo \(\displaystyle O(N^2) \) e da quella è possibile ricavare il percorso in \(\displaystyle O(N) \) operazioni, io suggerirei di usare questo approccio se la matrice è di dimensione accettabile e i \(\displaystyle 2N\max{\lvert A\rvert}\) è sufficientemente piccolo.
Usare direttamente la proprietà per ricavare il percorso senza usare alcuna memoria aggiuntiva richiede un numero di operazioni doppio dispetto a calcolare \(\displaystyle D \). Pertanto, asintoticamente parlando, usare una memoria di appoggio è una mossa vincente anche se va calcolato un singolo percorso.
Considerando che pre-calcolare \(\displaystyle D \) ha un costo \(\displaystyle O(N^2) \) e da quella è possibile ricavare il percorso in \(\displaystyle O(N) \) operazioni, io suggerirei di usare questo approccio se la matrice è di dimensione accettabile e i \(\displaystyle 2N\max{\lvert A\rvert}\) è sufficientemente piccolo.
Usare direttamente la proprietà per ricavare il percorso senza usare alcuna memoria aggiuntiva richiede un numero di operazioni doppio dispetto a calcolare \(\displaystyle D \). Pertanto, asintoticamente parlando, usare una memoria di appoggio è una mossa vincente anche se va calcolato un singolo percorso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo