% Questo programma permette di risolvere il problema dei cammini minimi su un grafo % tramite l'algoritmo di Dijkstra. Tale algoritmo, fissato un nodo iniziale, trova % i cammini minimi da esso a ciascuno degli altri nodi. Il costo e' quadratico nel % numero dei nodi del grafo. % Commenti a cura di Beatrice Signorello % Un grafo e' costituito da un insieme di punti (NODI) uniti da linee (LINK). Ne esistono % vari tipi e possono rappresentare in modo schematico una grande quantita' di sistemi. % Per esempio un grafo puo' rappresentare una mappa stradale dove i nodi corrispondono % agli incroci ed i link alle strade. Tra le varie proprieta' di un grafo ricordiamo: % 1) la connettivita': se per ogni coppia di nodi esiste un percorso (PATH), % inteso come successione di link, che ci permette di arrivare da uno all'altro; % 2) la completezza: se da ogni nodo ho un link che lo collega a ciascuno degli altri. % In questo tipo di grafo abbiamo n*(n-1) link. % Ad ogni grafo di n nodi possiamo associare una matrice n*n, detta matrice di ADIACENZA (A): % e' una matrice i cui valori solo zero o uno; il suo generico elemento A(i,j) vale 1 se % esiste un link dal nodo i al nodo j, altrimenti vale 0. % Una classe importante di grafi e' quella dei grafi "PESATI". Per un grafo di questo tipo si ha % la matrice dei "PESI" o delle "DISTANZE": e' utile se ci interessa conoscere, oltre ai % collegamenti, un'informazione specifica per ogni singolo collegamento. Chiaramente assegneremo % un peso alla coppia (i,j) solo se esiste un link da i a j. % Il problema dei cammini minimi su un grafo connesso e' quello di trovare un percorso da un nodo % iniziale init ad uno finale fin la cui somma dei pesi sia minima, tra tutti i percorsi possibili % da init a fin. Il numero di tali percorsi aumenta all'aumentare dei nodi e delle connessioni. % Ad esempio, in un grafo completo abbiamo (n-1)! percorsi. % IDEA GENERALE DELL'ALGORITMO di Dijkstra: % L'algoritmo e' composto da n-1 iterazioni in cui visita i nodi del grafo. Alla fine di ciascuna % iterazione determina il percorso ottimale da init ad uno degli altri n-1 nodi. Se ci interessa % solo il percorso fino a fin, interromperemo l'algoritmo all'iterazione in cui questo avviene. % Completando tutte le n-1 iterazioni, avremo tutti i percorsi minimi da init a ciascuno degli % altri n-1 nodi. Il costo in entrambi i casi sara' di ordine n^2. % Alla fine di ciascuna iterazione, ciascun nodo ha associata un'etichetta: '0' se non e' stato % ancora visitato, '1' se e' stato gia' visitato ma ancora non e' stato trovato il percorso % ottimale da init ad esso, '2' se e' stato visitato ed e' stato trovato il percorso ottimale da % init fino ad esso. Inoltre a ciascun nodo e' associato il percorso migliore trovato fino ad % allora. Osservazione: le etichette ed i cammini migliori saranno mutabili nel corso % dell'algoritmo. Pero', se l'etichetta assume il valore 2 alla fine di una iterazione, esso non % cambiera' piu' alle iterazioni successive ed anche il percorso migliore rimarra' invariato. % All'inizio inizializzo tutte le etichette a 0 esclusa quella del nodo init che metto a 2 % ed il relativo percorso (init,init), con costo totale minimo fittizio nullo. % Supponiamo ora di aver finito una generica iterazione i, dove abbiamo assegnato il valore 2 % all'etichetta del nodo k_i, il cui percorso ottimale da init e' cosi' appena stato trovato. % All'inizio della successiva iterazione, prolunghiamo il cammino ottimale di k_i aggiungendo % uno degli s(k_i) link uscenti da esso, raggiungendo cosi' s(k_i) nodi. Esaminiamo ciascuno % di questo s(k_i) nodi. Se e' la prima volta che esso viene raggiunto, assegneremo il valore % 1 alla sua etichetta e memorizzeremo il cammino appena prolungato che lo raggiunge. Se invece % la sua etichetta era gia' 1, cioe' era gia' stato raggiunto da un altro percorso, andremo % a controllare se il peso totale (somma dei pesi) del nuovo percorso e' inferiore a quello % del vecchio, che era il migliore fino a quel momento. In tal caso, sostituiremo il percorso % vecchio con quello nuovo. A questo punto, consideriamo tutti i nodi che al momento hanno % 1 come etichetta. Assegneremo 2 a quello il cui percorso migliore al momento e' piu' piccolo. % Se ce n'e' piu' di uno, ne scegliamo uno di essi, come meglio crediamo. Abbiamo cosi' completato % l'iterazione e possiamo passare alla seguente. % IMPLEMENTAZIONE clear close all n=8; % numero dei nodi % Come esempio abbiamo scelto un grafo costituito da n punti equidistanti su una circonferenza. % Ogni punto e' collegato solo ai suoi due primi vicini andando cosi' a formare un poligono regolare. for i=1:n theta(i)=(i-1)*2*pi/n end % Usiamo un ciclo for per costruire il vettore theta che ha come i-esima componente l'angolo delle % coordinate polari dell'i-esimo punto x=[cos(theta);sin(theta)] % matrice 2 x n che ha come colonne le coordinate x e y di ciascun punto del poligono regolare. A=zeros(n,n); % matrice di adiacenza momentaneamente costituita solo da zeri. % La A ci dice quali sono i link. Per il nostro caso ci sono solo tra vertici adiacenti. % Ricordiamo che i nostri punti sono considerati ordinati da 1 ad n. Tutti i punti hanno un % vicino sinistro ed uno destro. Per i da 2 a n-1, essi sono i-1 ed i+1. for i=2:n-1 A(i,i-1)=1; A(i,i+1)=1; end % I vicini di 1 sono 2 ed n. A(1,n)=1; A(1,2)=1; % I vicini di n sono 1 ed n-1. A(n,1)=1; A(n,n-1)=1; % caso grafo completo % A=ones(n,n); % for i=1:n % A(i,i)=0; % end A % Scriviamo sullo schermo la matrice di adiacenza A. Per la i-esima riga, essendo indicati con 1 % i due collegamenti del punto i-esimo avremo tutti zeri tranno due "uno": uno a sinistra e % uno a destra dell'i-esima colonna. Questo per ogni riga a parte la prima e l'ultima. Notare % che A in questo esempio e' una matrice CIRCOLANTE!! dist=zeros(n,n); % MATRICE DELLE DISTANZE:la inizializziamo con tutti zeri figure hold on for i=1:n for j=1:n % Due cicli per controllare ogni coppia di punti if A(i,j) == 1 % Condizione necessaria affinche' ci sia un link tra i e j. Non avrebbe senso % altrimenti calcolare la distanza. dist(i,j)=sqrt((x(1,i)-x(1,j))^2+(x(2,i)-x(2,j))^2); % Calcoliamo la distanza eucliea tra % i punti i e j con la nota formula, avendo ogni punto due componenti contenute nella matrice x % che ha 2 righe (numero coordinate per ogni punto) ed n colonne (numero dei punti). % x(1,i)-x(1,j) e' la differenza tra la prima coordinate dei punti i e j ed analogamente % x(2,i)-x(2,j) per la seconda coordinata. plot([x(1,i) x(1,j)],[x(2,i) x(2,j)]) % Disegnamo ogni volta un segmento tra i due punti di cui % abbiamo appena calcolato la distanza. Queste operazioni vengono eseguite se e solo se % esiste un link tra i due punti esaminati! Abbiamo, cosi', disegnato il nostro poligono. end % chiudo l'if ed i due for end end axis square print -dpdf plot1.pdf class=zeros(1,n); % Questo e' il vettore delle etichette, ovvero un vettore riga con n % componenti. La i-esima componente fornisce l'etichetta del punto i-esimo. Abbiamo tre % valori per l'etichetta: '0' se il punto non e' stato ancora visitato, '1' se e' stato % visitato ma non assegnato, cioe' non e' ancora noto il percorso ottimo, ed infine '2' % se si tratta proprio di un punto visitato ed assegnato. Per adesso abbiamo solo zeri, % visto che dobbiamo ancora iniziare e nessun punto e' stato ancora esaminato. bestpath=10^10*ones(1,n); % Vettore a n componenti che utilizzeremo per memorizzare il peso % totale del percorso migliore dal punto init al punto fin. Lo inizializziamo con un numero molto grande. init=1; % Abbiamo scelto come punto init quello che ha indice 1 class(init)=2; % Diamo al punto di partenza init l'etichetta di assegnato. prec(init)=init; % Poiche' un qualsiasi sotto-percorso di un percorso ottimale e' ottimale, % per ricostruire i cammini ottimali, basta associare ad un punto appena assegnato % quello assegnato immediatamente prima. bestpath(init)=0; % Il percorso ottimale da init ad init ha peso zero. ultimo=init; % Ogni volta avremo un ultimo punto assegnato, che adesso e' init. for k=2:n % Effettuiamo le iterazioni. Avrei messo un while (ultimo diverso da fin) % se avessi voluto calcolare solo il percorso ottimale da init a fin. for j=1:n if class(j) < 2 & A(ultimo,j) > 0 % Prolunghiamo il percorso ottimale % che arrivava fino all'ultimo punto che abbiamo assegnato. Se il nostro potenziale punto % di prolungamento del percorso ancora non e' stato assegnato ed esiste il link tra l'ultimo % assegnato ed esso, prolunghiamo e calcoliamo la distanza del percorso prolungato. dd=bestpath(ultimo)+dist(ultimo,j); % calcoliamo la nuova distanza aggiungendo % alla lunghezza del percorso ottimale fino all'ultimo punto assegnato (bestpath(ultimo)), il % peso tra ultimo ed il punto di prolungamento (j). if class(j) == 0 % Se e' la prima volta che visitiamo il punto j, bestpath(j)=dd; % gli assegniamo la distanza migliore al momento da init, class(j)=1; % gli assegnamo l'etichetta 1, prec(j)=ultimo; % e come punto precedente gli assegniamo ultimo. else if dd < bestpath(j) % Se invece j e' un punto gia' visitato ma non assegnato, % allora facciamo il check seguente per evitare di scegliere un percorso piu' lungo. bestpath(j)=dd; prec(j)=ultimo; end % chiudo i tre if end end end % chiudo il secondo for ed ho fatto tutti i possibili prolungamenti. distmin=10^10; for j=1:n % Con questo ciclo determino quale punto tra quelli visitati ma non % ancora assegnati, ha la distanza minima da init. if class(j) == 1 & bestpath(j) < distmin ultimo=j; % questo e' il nostro "ultimo" punto assegnato distmin=bestpath(j); end end class(ultimo)=2; % cambiamo etichetta ad ultimo. end prec fin=6; % punto finale fin. % di seguito ricostruisco il percorso al contrario da fin ad init s=1; j=fin; path(s)=j; while abs(prec(j)-j) > 0 % questo accade solo per il punto init s=s+1; path(s)=prec(j); j=prec(j); end path figure hold on for i=1:n plot(x(1,i),x(2,i),'x')% Facciamo il plot dei nodi del grafo. Metto la 'x' % per disegnare solo i punti senza congiungerli. end for k=1:length(path)-1 % ciclo for per plottare il percorso ottimale da init a fin. plot([x(1,path(k)) x(1,path(k+1))],[x(2,path(k)) x(2,path(k+1))]) % plotta per ogni k un segmento che congiunge i due punti path(k) e path(k+1). In questo modo % disegna proprio il cammino trovato dall'algoritmo. end axis square print -dpdf plot2.pdf