ePerTutti


Appunti, Tesina di, appunto matematica

RICERCA DEGLI ALBERI DEI CAMMINI E DEI TEMPI MINIMI SU UN GRAFO PESATO



ricerca 1
ricerca 2

RICERCA DEGLI ALBERI DEI CAMMINI E DEI TEMPI MINIMI SU UN GRAFO PESATO





Il problema della determinazione degli alberi dei cammini minimi è, senza dubbio, uno degli argomenti fondamentali dell'ottimizzazione combinatoria, ma non solo: difatti, tale problema, interessa molti ricercatori e professionisti per diverse ragioni, in quanto si presenta nella pratica in una vasta gamma di applicazioni delle tecniche informatiche e delle strutture di dati ed inoltre rappresenta un caposaldo nello studio dei più complessi modelli di rete, come, ad esempio, quelli per l'analisi e la pianificazione dei sistemi di trasporto.

Sebbene la relativa semplicità del problema, la programmazione e l'analisi dei più efficienti algoritmi atti a risolvere ciò, richiede un'elevata dose d'ingegno ed abilità, l'interesse per tale argomento non è scemato, come dimostra l'enorme produzione scientifica degli ultimi decenni.

Come detto nella parte introduttiva, in questo lavoro vogliamo presentare un'applicazione della determinazione di alberi dei cammini minimi sul grafo stradale dell'Angola; ma, prima di addentrarci in tale studio, riteniamo opportuno riportare alcuni concetti fondamentali sulla teoria dei grafi ed in particolare sui principali algoritmi riguardanti i cammini minimi che abbiamo utilizzato e che, di certo, si riveleranno importanti per una chiara esposizione e comprensione del lavoro.



Ricordiamo che un 'grafo pesato' è un grafo generico G=(N,A), dove ad ogni arco a=(i,j)IA è associato un numero reale definito 'peso' ed indicato con ci,j. Ad esempio questo è un grafo pesato:







Questi pesi possono essere pensati come un 'costo' che si deve are per aver scelto un certo arco; ad esempio nel nostro grafo stradale il peso di un arco rappresenta la lunghezza della strada in considerazione.

Ricordiamo, inoltre, che Pathx,y=[Nx,y,Ax,y] è un cammino (semplice ) dal nodo origine x al nodo destinazione y se:

- in ogni nodo iINx,y, con i¹x,y, incidono un solo arco entrante ed un solo arco uscente;

- in x incida un solo arco uscente ed in y incida un solo arco entrante.

Il costo C del generico cammino , precedentemente definito, sarà dato dalla somma dei costi ( o pesi ) degli archi che formano quel cammino.

Il problema della determinazione di un albero dei cammini minimi consiste proprio nel determinare su un generico grafo G=(N,A) un cammino di costo (o peso ) minimo da un nodo r del grafo, detto radice, a ciascun altro nodo i, sotto la condizione, fondamentale ed unica, che non esistano cicli orientati di costo negativo; questo perché altrimenti esisterebbero cammini il cui costo non è limitato inferiormente.

Prima di addentrarci nell'illustrazione del nostro lavoro applicativo, è necessario riportare le seguenti condizioni di ottimalità, meglio note come condizioni di Bellman, le quali rappresentano una chiave di lettura fondamentale per l' interpretazione e l'implementazione degli algoritmi utilizzati per la ricerca dei cammini minimi.

Sia T un albero ricoprente di G=(N,A) con radice r e sia di il costo o peso dell'unico cammino da r in i, con iIT; vale il seguente teorema:

T è un albero di cammino minimo con origine r se e solo se di+ci,j-dj³0 (i,j)IA.



Algoritmi e applicazioni


Per la ricerca dell' albero dei cammini minimi, il primo algoritmo proposto è L-deque , ideato da D'Esopo-Pape; tale algoritmo si avvale, nella implementazione di Q (vettore contenente i nodi del grafo), di una lista a doppia entrata , conosciuta appunto con la sigla deque, in cui sono permesse le inserzioni di un elemento ad entrambe le estremità, mentre le rimozioni sono consentite solo dalla testa; per meglio capire si può intendere la deque come una lista circolare o come una fila Q' ed una pila Q'' connesse, in modo tale che la coda della pila punti alla testa della fila . In questo modo quando un nodo è inserito nella deque Q per la prima volta, viene posto in coda a Q' e lo stesso nodo, dopo esser stato rimosso, quando va reinserito in Q, viene inserito in testa a Q''; si può quindi osservare come con la deque si combinino le due strategie di esplorazione di un albero, cioè a ventaglio ed a scandaglio rispettivamente. Da osservare, inoltre, che gli elementi della deque sono rimossi dalla testa di Q'' e se Q''=Æ allora si rimuove il primo elemento di Q'.

Riportiamo qui lo pseudo-codice dell'algoritmo.



PROCEDURE L-deque;

BEGIN

Inizializza p, d, Q;

REPEAT prendi u dalla testa di Q e Q=Q

FOR EACH (u,v)IFS(U): d[u]+euv<d[v]

IF VÏQ

THEN IF d[v]=¥

THEN inserisci v nella coda di Q   

ELSE inserisci v nella testa di Q;

d[v]=d[u]+ euv;

p[v]=u;

UNTIL Q¹

END;



Il linguaggio di programmazione utilizzato per questo algoritmo è il PASCAL; riportiamo di seguito il programma completo:



program LDEQUE;

uses crt;

type vettore=array[1..900] of integer;

var Angola,OutA,Output: text;

nv,j,i,k,r,X,v,HEAD,TAIL:integer;

DA,A,D,Q,P,KM,LAB:vettore;



procedure inizializzaz(var H,p,d,lab:vettore);


var i:integer;

begin

for i:=1 to nv+1 do

begin

p[i]:=0;

lab[i]:=0;

d[i]:=10000;

end;

for i:=1 to 2*(nv+1) do

h[i]:=0;

end;


procedure prendixcanc(var head,x:integer; var lab:vettore);


begin

x:=Q[head];

Q[head]:=0;

lab[x]:=0;

if head=2*(nv+1)

then head:=1

else head:=head+1;

end;


procedure inserpila(var H,lab:vettore; var head:integer);


begin

if head=1

then head:=2*(nv+1)

else head:=head-l;

H[head]:=v;

lab[v]:=1

end;


procedure inserfila(var H,lab:vettore; var tail:integer);


begin

H[tail]:=v;

if tail=1

then tail:=1

else tail:=tail+1;

lab[v]:=1

end;


begin

clrscr;

assign(Angola,'d:/archikm.txt');

reset(Angola);

j:=0;

while not (eof(Angola)) do

begin

j:=j+1;

read (Angola,DA[j],A[j],KM[j]);


end;

close(Angola);

writeln('Inserisci il numero dei nodi del grafo');

readln(nv);

writeln('Inserisci il nodo di partenza o radice');

readln(r);

readln;

inizializzaz(Q,P,D,LAB);

P[r]:=r;

Q[1]:=r;

D[r]:=0;

HEAD:=1;

TAIL:=2;

LAB[r]:=1;

while HEAD<>TAIL do

begin

prendixcanc(HEAD,X,LAB);

for i:=1 to j-l do

begin

if DA[i]=X

then

begin

v:=A[i];

if D[X]+KM[i]<D[v]

then

begin

if LAB[v]=0

then if D[v]=10000

then inserfila(Q,LAB,TAIL)

else inserpila(Q,LAB,HEAD);

D[v]:=D[X]+KM[i];

P[v]:=X;

end;

end;

end;

end;

assign(OutA,'d:RisuA1.txt');

rewrite(OutA);  

assign(Output,'d:Risult1.txt');

rewrite(Output);

clrscr;

for k:=1 to nv do

begin


writeln(OutA,D[k]:5);

writeln(Output,'Il padre del nodo',k:4,' e`',P[k]:4,' con distanza pari a',D[k]:6,' dal nodo radice',r:4);

end;

close(OutA);

close(Output);

readln

end.



Complessità computazionale: l'algoritmo L-deque è caratterizzato da una complessità computazionale esponenziale nel caso peggiore, ma è dimostrato che per grafi sparsi quasi ari esso risulta molto efficiente.


Risultati forniti dall'algoritmo L-deque



Abbiamo applicato l'algoritmo L-deque utilizzando come nodi di partenza i tre porti più importanti dell'Angola, ovvero: Luanda, Lobito e Namibe. A ciascuna di queste città l'algoritmo è stato applicato due volte: con il primo output, abbiamo ottenuto l'albero dei cammini di minima distanza ( in km ) tra le città, precedentemente considerate; la seconda applicazione è scaturita dalla volontà di prendere in considerazione il fatto che a diversi tipi di strada corrispondono differenti tempi medi di percorrenza: abbiamo così costruito l'albero dei cammini minimi rispetto al tempo.

I risultati ottenuti sono in molti casi contrastanti, giacché determinati da obiettivi non comuni quali: percorrere il minimo numero di chilometri indipendentemente dal tipo di strada, o essere disposti ad allungare il proprio cammino al fine di attraversare strade più agibili, che permettono di arrivare a destinazione nel più breve tempo possibile.

Il decisore potrà pertanto scegliere tra le due possibilità: minimizzare lo spazio o il tempo.

Illustreremo ora alcuni esempi di come i cammini cambino secondo l'obiettivo che si desidera raggiungere.




Esempio 1: Luanda Lobito


Il percorso indicatoci dall'albero dei cammini minimi rispetto alla distanza chilometrica è quello costiero, passante per le città di Barra Do Cuanza, Cabo Ledo, Porto Amboim, Sumbe, Lobito, lungo 498 Km. L'albero dei cammini minimi rispetto al tempo indica invece un percorso più lungo del precedente: ben 766 Km che ci permette di arrivare a destinazione con un tempo medio di 766 minuti passando per le seguenti città: Catete, Maria Teresa, Dondo, Quibala, Waku-Kungo, Wama, Balombo, Lobito.









Esempio 2: Luanda Luena


In questo caso i due percorsi coincidono totalmente. Si va da Luanda a Luena e viceversa percorrendo 953 Km in 1670 minuti attraversando le seguenti città: Catete, Maria Teresa, Dondo, Quibala, Andulo, Kuito, Camacupa, Luena.








Esempio 3:Lobito Namibe


Il percorso fornito dall'albero dei cammini minimi rispetto alla distanza è il seguente:  Benguela, Lucira, Lobito. Esso è lungo 490 Km, passa per la costa su una strada gialla in cui la velocità media da noi stimata è 30 Km orari; non c'è da stupirsi quindi che il percorso di tempo minimo faccia tutto un altro tragitto e cioè: Benguela, Catengue, Quilengues, Cacula, Lubango, Caraculo, Namibe Esso è percorribile in 921 minuti contro i 980 richiesti dal precedente cammino.







Esempio 4: Lobito Lubango


Per le condizioni di ottimalità di Bellman, il percorso ottimo nel senso del tempo è quello trovato nell'esempio 3, che riportiamo di seguito: Benguela, Catengue, Quilengues, Cacula, Lubango da effettuare in 734 minuti. Il cammino minimo rispetto alla distanza, invece, è molto diverso dall'esempio 3, in quanto coincide con quello minimo rispetto al tempo sebbene le città di Lubango e Namibe si trovino a soli 187 Km di distanza l'una dall'altra.




Per concludere ci sembra importante ricordare che i tempi medi di percorrenza rappresentano solamente delle stime dei tempi reali, quindi devono essere intesi come delle indicazioni e non come dei dati certi o assoluti.



Il secondo algoritmo da noi proposto è A-star, il quale sembra sia l'unico algoritmo esistente per la ricerca di un albero dei cammini (tempi) minimi, di origine e destinazione fissata; prima di discuterlo riteniamo opportuno introdurre le seguenti definizioni, per una comprensione più immediata dell'algoritmo stesso:


Def: - indichiamo con lij la lunghezza del generico arco (i,j), dove i=P(j).

indichiamo con g(i) la lunghezza del cammino minimo dall'origine s ad i

indichiamo con h(i) la lunghezza del cammino minimo da i alla destinazione t.

indichiamo con h'(i) una stima di h(i).



indichiamo con f(i) il cammino minimo da s a t passante per i, dove f(i) = g(i) + h(i).

indichiamo con f'(i) una stima di f(i), dove f'(i) = g(i) + h'(i).


Inoltre si richiede, per h', che siano verificate le proprietà di:

Ammissibilità: h' è una stima ammissibile di h se h'(i) £ h(i) i

Consistenza: h' è una stima consistente per h se h'(i) £ lij + h'(j)  i,j


Es: Una stima ammissibile e consistente di una distanza geografica è la distanza "in linea d'aria".


Il nostro problema, spiegato in questi termini appena introdotti, può scriversi come la ricerca di:


Min [g(i) + lij + h'(j)]


che rappresenta il cammino minimo da s a t passante per i.


Siamo ora in grado di introdurre lo pseudo-codice di A-Star (si considerino le stime h'(.) ottenute dall'output dell'algoritmo L-deque) su un grafo di n nodi, considerando s come origine e t come destinazione:


Program A-Star;

begin

for i=1 to n do

begin

P(i)=-l;

g(i)=¥

end;

P(s)=0; g(s)=0; Q=Q È s

while Q ¹ Æ do

begin

seleziona u da Q con min f'(i); Q=Q u

if u=t then STOP;

for each (u,v)I F(u) do

if g(u) + luv< g(v) then

begin

g(v)=g(u) + luv;

if v Ï Q then Q=Q È v

P(v)=u;

f'(v)=g(v)+h'(v);

end;

end;

end.



Si osservi che l'istruzione cardine del programma è la scelta del nodo u per il quale è minima, di iterazione in iterazione, la quantità f'(i); si procede poi alla visita della "stella uscente" di u e, qualora sia soddisfatta la condizione di Bellmann g(u) + luv<g(v), all'aggiornamento dei vettori p, g e f.

Questo programma, così snello nella sua forma pseudo-codice, ha richiesto nella codifica Pascal quasi 200 righe di istruzioni, che sono qui sotto riportate:



program A_Star;

uses crt;

type vettore=array[1..486] of integer;

var archi,stime,output:text;

Q:array[1..200] of integer;

maxint,somma,i,j,orig,dest,posmin,u,tail,top:integer;

z,A,L,carichi,tempi,tipo:vettore;

P,h,g,f,lab:array[1..413] of integer;



procedure leggigrafo;

begin

assign(archi,'a:archi.txt');

reset(archi);

i:=1;

while i<=486 do

begin

read(archi,z[i],A[i],tipo[i],L[i],tempi[i],carichi[i]);

i:=i+1;

end;

close(archi);

end;





procedure leggistime;

begin

assign(stime, 'a:luandakm.txt'); (******)

reset(stime);

i:=1;

while i<=413 do

begin

read(stime,h[i]);

i:=i+1;

end;

close(stime);

end;






procedure scrivigrafo;

begin

writeln('Il grafo da visitare è:');

writeln('Nodi.Archi(lunghezze)');

for j:=1 to 486 do 

begin

writeln(z[j],':---',A[j],'..(',L[j],')');

end;

writeln('Stime');

for j:=1 to 413 do

begin

writeln(h[j]);

end;

end;




procedure quest;

begin

writeln('Scrivi il nodo origine');

read(orig);

writeln('Scrivi il nodo destinazione');

read(dest);

end;




procedure inizializza;

begin

maxint:=10000; somma:=orig; u:=orig; Q[1]:=orig; tail:=200; top:=6000;

for i:=1 to 413 do

begin

P[i]:=-l;

g[i]:=maxint;

f[i]:=maxint;

lab[i]:=0;

end;

P[orig]:=0; g[orig]:=0; f[orig]:=h[orig]; lab[orig]:=1;

for i:=2 to 200 do begin Q[i]:=0; end;

end;





procedure scandaglia_Q;

begin

somma:=0;

for i:=1 to 200 do

somma:=somma+Q[i];

end;






procedure seleziona2; (* per cercare u nelle iterazioni successive alla prima *)

begin

top:=6000;

for j:=1 to 486 do

begin

if A[j]=u

then begin

L[j]:=maxint; (* questo perchè non succeda di tornare nei nodi già visitati *)

f[A[j]]:=maxint;

end;

end;

for i:=1 to 486 do

begin

if z[i]=u

then begin

if f[A[i]]<top

then begin

top:=f[A[i]];

posmin:=A[i];

end;

end;

end;

u:=posmin;

for i:=1 to 200 do begin

if Q[i]=u then

begin

Q[i]:=0;

lab[u]:=0;

end;

end;

end;






procedure stampa;

begin

somma:=0;

assign(output,'a:risultati.txt');

rewrite(output);

for i:=1 to 413 do

begin

if P[i]<>-l then

writeln(output,'il padre di ',i,' è: ',P[i]);

end;

close(output);

readln;

end;





begin (*Main*)

clrscr;

leggigrafo; leggistime;

quest;

inizializza;

(* 'Scrivigrafo' è una procedura opzionale *)

Q[1]:=0;

lab[orig]:=0;


while somma<>0 do begin

if u=dest then stampa

else for i:=1 to 486 do

begin

if z[i]=u then begin

if g[z[i]]+L[i]<g[A[i]]

then begin

g[A[i]]:=g[z[i]]+L[i];

if lab[A[i]]=0 then



begin

Q[tail]:=A[i];

tail:=tail-l;

lab[A[i]]:=1;

end;

P[A[i]]:=u;

f[A[i]]:=g[A[i]]+h[A[i]];

(* NB: maxint va scelto di modo che sia sempre f=g+h

< 32767 *)

end;

end;

end;

seleziona2; scandaglia_Q;

end;

stampa;

readln;

end. (*Main*)




Complessità computazionale: si dimostra che la complessità di questo algoritmo è lineare nel numero di iterazioni.


Risultati forniti dall'algoritmo A-star


Questo programma stampa in output, visualizzabile solo sul floppy nel file 'risultati.txt', i 'padri' generati dal programma A-Star applicato alla tabella degli 'archi'.

Si osservi, in particolare, l'istruzione di assign seguita da (******): questa è l'unica istruzione che è necessaria modificare secondo la destinazione prescelta, infatti, il file a:luandakm.txt contiene le stime h' (chiamate semplicemente h nel programma), ottenute attraverso l'applicazione del programma L-Deque, delle distanze di tutti i nodi dalla destinazione Luanda; se, ad esempio, vogliamo trovare l'albero dei cammini minimi da una certa città a Lobito, basterà sostituire, al posto di assign(stime, 'a:luandakm.txt'), l'istruzione assign(stime, 'a:lobitokm.txt'), già ottenute con un'altra applicazione di L-Deque.

Ad esempio, volendo trovare il cammino minimo da Malanje a Luanda, basta fare eseguire il programma sopra, dopodichè sarà chiesto, in output, di scrivere l'origine e la destinazione desiderati (avendo cura di controllare l'esistenza del nodo origine nella tabella degli archi); inseriamo, dunque, i rispettivi codici identificativi, ossia 263 e 229. Il programma stamperà su floppy l'output a:risultati.txt contenente i nodi che sono stati presi in considerazione (infatti A-Star ha come proprietà ottimale il fatto di non considerare tutti i nodi del grafo, ma solo gli u) ed i rispettivi "padri"; da questo vettore di risultati possiamo, infine, costruire il cammino minimo cercato dalla destinazione, osservando che il padre di 229 (Luanda) è 103 (Catete), il padre di 103 è 267 (Maria Teresa), il padre di 267 è 317 (N'Dalatando), il padre di 317 è 42 (Cacuso), il padre di 42 è 263 (Malanje) ed il padre di 263 è 0 poiché Malanje è l'origine del cammino.

In conclusione, il cammino minimo (ovvero di distanza minima) tra Malanje e Luanda è: MalanjeàCacusoàN'DalatandoàMaria TeresaàCateteàLuanda.


Per ottenere i cammini dei tempi minimi da una certa origine ad una certa destinazione basta considerare, come stime h' (fornite da L-Deque), quelle stime costruite non sulle lunghezze ma sui tempi (misurati in minuti) di percorrenza degli archi; ad esempio, per calcolare i tempi minimi per giungere a Lobito basta scrivere, al posto di (******), assign(stime, 'a:lobitotp.txt').



Alberi Dei Cammini Minimi



destinazione LUANDA


KuitoàAnduloàQuibalaàDondoàMaria TeresaàCateteàLuanda


HuamboàWamaàWaku KongoàQuibalaàDondoàMaria TeresaàCateteàLuanda


MalanjeàCacusoàN'DalatandoàMaria TeresaàCateteàLuanda


LubangoàCaculaàQuilenguesàCatengueàBenguelaàLobitoàSumbeàPorto Amboimà

àCabo LedoàBarra do CuanzaàLuanda


MavengueàNankovaàLongaàMenongueàChitemboàKuitoàAnduloàQuibalaà

àDondoàMaria TeresaàCateteàLuanda


destinazione LOBITO


KuitoàAnduloàQuibalaàGabelaàSumbeàLobito


HuamboàWamaàBalomboàLobito


MalanjeàCacusoàN'DalatandoàDondoàMumbondoàPorto AmboimàSumbeàLobito


LubangoàCaculaàQuilenguesàCatengueàBenguelaàLobito


MavengueàCuangaràCaiundoàKuvangoàCuimaàHuamboàWamaàBalomboàLobito



destinazione NAMIBE


KuitoàChitemboàMenongueàKuvangoàDongoàMatalaàQuipungoàLubangoà

àCaraculoàNamibe


HuamboàCuimaàCacondaàCaluquembeàCaculaàLubangoàCaraculoàNamibe


MalanjeàCacusoàN'DalatandoàDondoàMumbondoàPorto AmboimàSumbeà

àLobitoàBenguelaàLuciraàNamibe


LubangoàCaraculoàNamibe


MavengueàCuangaràCaiundoàKuvangoàDongoàMatalaàQuipungoàLubangoà



àCaraculoàNamibe




Alberi Dei Tempi Minimi



destinazione LUANDA


KuitoàAnduloàQuibalaàDondoàMaria TeresaàCateteàLuanda


HuamboàWamaàWaku KongoàQuibalaàDondoàMaria TeresaàCateteàLuanda


MalanjeàCacusoàN'DalatandoàMaria TeresaàCateteàLuanda


LubangoàCaculaàCaluquembeàCacondaàCuimaàHuamboàWamaàWaku Kungoà

àQuibalaàDondoàMaria TeresaàCateteàLuanda


MavengueàCaiundoàKuvangoàCuimaàHuamboàWamaàWaku KungoàQuibalaà

àDondoàMaria TeresaàCateteàLuanda


destinazione NAMIBE


KuitoàAnduloàQuibalaàWaku KongoàWamaàHuamboàCuimaàCacondaà

àCaluquembeàCaculaàLubangoàCaraculoàNamibe


HuamboàCuimaàCacondaàCaluquembeàCaculaàLubangoàCaraculoàNamibe


MalanjeàCacusoàN'DalatandoàDondoàQuibalaàWaku KongoàWamaàHuamboà

àCuimaàCacondaàCaluquembeàCaculaàLubangoàCaraculoàNamibe


LubangoàCaraculoàNamibe


MavengueàCaiundoàOndjivaàXangongoàHumbeàCahamaàChibembaàChibiaà

àLubangoàCaraculoàNamibe


destinazione LOBITO


KuitoàAnduloàQuibalaàWaku KungoàWamaàBalomboàLobito


HuamboàWamaàBalomboàLobito


MalanjeàCacusoàN'DalatandoàDondoàQuibalaàWaku KungoàWamaàBalomboà

àLobito


LubangoàCaculaàQuilenguesàCatengueàBenguelaàLobito


MavengueàCaiundoàKuvangoàCuimaàHuamboàWamaàBalomboàLobito





Come si può vedere, non sempre un albero dei cammini minimi coincide con il corrispondente dei tempi minimi: è logico, infatti, che una se una certa strada rappresenta il collegamento più breve, in termini di distanza, tra due località, tuttavia può non essere la via più rapida tra queste. Ad esempio, se due città sono collegate tra loro da una strada asfaltata di 100 km e da una non asfaltata di 80 km, allora è logico che, in termini di cammino minimo, è preferibile la seconda, ma in termini di tempo minimo è preferibile la prima.









Galleria di foto e immagini per: ricerca







Privacy

© ePerTutti.com : tutti i diritti riservati
:::::
Condizioni Generali - Invia - Contatta