 |  |
| |
 |
matematica |
|
|||||
|
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.
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.
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.
 |  |
|
Privacy
|
© ePerTutti.com : tutti i diritti riservati
:::::
Condizioni Generali - Invia - Contatta
