Visita in ampiezza->albero dei cammini minimi

[giuliomontenero]

Salve ragazzi come faccio a dimostrare che una visita in ampiezza genera un albero dei cammini minimi?
Grazie

[AndreaNobili1]

Dovrebbe essere piuttosto semplice (anche io stò studiando algoritmi per il mega mostro di algoritmi e strutture dati 2 in questi giorni...)

Allora, vedila così:

Parti da un nodo s (sorgente) e di volta in volta visiti tutti i nodi a distanza 1.

Per dimostrare la proprietà che afferma che una visita per ampiezza genera un albero dei cammini minimi devi dimostrare 2 cose:

1) SE IL NODO SORGENTE s È CONNESSO A t (un qualsiasi altro nodo), ALLORA L'ALGORITMO RESTITUISCE UN CAMMINO DA t AD s

Quindi al momento stiamo solo dimostrando che se s è connesso a t, allora l'algoritmo restituisce un genercio cammino che da s porta in t (non stò ancora dimostrando che è minimo)

Per dimostrare tale proprietà suppongo per assurdo che s sia connesso a t ma che l'algoritmo non restituisca un cammino. Questa cosa pottrebbe accadere solamente nel caso in cui l'algoritmo di visita BFS (visita per ampiezza, NB: è implementato mediante l'uso di una CODA) trova la coda vuota.
Quindi praticamente considera un nodo x come l'ultimo nodo nel cammino da s a t (che sappiamo esistere ma che l'algoritmo per assurdo non trova) come l'ULTIMO NODO NEL CAMMINO DA s A t RAGGIUNTO DALL'ALGORITMO.

Facciamo conto che x sia direttamente connesso ad y e che y sia il nodo successivo ad x nel cammino, graficamente avresti una cosa del genere:

P(s,t) = s ---> u1 ---> u2 ---> ............ ---> x ---> y ---> ............. ---> t

In pratica P(s,t) è il tuo cammino minimo da s a t (che esiste).
Supponi per assurdo che l'algoritmo non lo trovi, quindi si deve bloccare ad un certo punto perchè la coda Q della visita BFS è vuota. Supponi, dunque che l'ultimo nodo del cammino trovato è x, quindi il nodo y non verrebbe mai raggiunto ma ciò è IMPOSSIBILE perchè per costruzione dell'algoritmo di visita BFS se x viene raggiunto allora tutti i suoi vicini vengono aggiunti alla coda Q.

2) Si vuole ora dimostrare che per ogni nodo t, tutti i cammini P(s,t) che vengono restituiti dall'algoritmo sono minimi.
Tu in pratica vuoi quindi dimostrare che I NODI PIÙ VICINI AD s VENGONO VISITATI PER PRIMA DALL'ALGORITMO

Per capirlo basta che pensi un po' a come funziona la visita per ampiezza...

La DISTANZA TRA 2 NODI è la lunghrzza d(u,v) del cammino minimo che congiunge u e v

Se d(s,u) < d(s,v) allora u viene visitato prima di v

La dimostrazione di tale proprietà la si fà per INDUZIONE sulla distanza tra 2 nodi

CASO BASE: Hai 2 nodi s, v collegati dal singolo arco e=(s,v) con s: nodo sorgente; v= nodo destinazione

Quindi d(s,s)=0 < d(s,v)=1 Quindi s viene visitato prima di v perchè è il primo nodo ad essere visitato, CASO BASE OK

PASSO INDUTTIVO:

HP INDUTTIVA: Suppongo che la proprietà sia vera per d(x,y) < l (quindi suppongo che per nodi che distano meno di l è vero che i nodi più vicini ad s vengono visitati prima di quelli più lontani)

Considera ora il seguente caso:

Hai il tuo nodo sorgente s ed i seguenti cammini: P(s, v') e P(s, u') aventi le seguenti distanze:

d(s, v') == (l-1) (esiste un cammino che collega il nodo sorgente s al nodo v' con un cammino lungo esattament (l-1), quindi su tale cammino vale l'hp induttiva, quindi in questo cammino posso affermare che è vero che vengono visitati prima i nodi più vicini ad s e poi quelli più lontani)

(s, u') < (l-1) (vale lo stesso discorso, è un cammino sicuramente più breve di l, quindi anche quì vale l'ipotesi induttiva quindi in questo cammino posso affermare che è vero che vengono visitati prima i nodi più vicini ad s e poi quelli più lontani)

Graficamente (ovviamente s è comune...non sò come disegnarlo meglio sul forum...):
s ---> x1 ---> ....... ----> v'
s ---> y1 ---> ....... ----> u'

Per quanto detto u' sarà visitato PRIMA di v'

Ora considera il caso in cui v' è collegato ad un nodo v ed u' è collegato ad un nodo u, graficamente:

s ---> x1 ---> ....... ----> v' ---> v
s ---> y1 ---> ....... ----> u' ---> u

Come abbiamo detto v' è a distanza esattamente (l-1) da s, mentre u' è a distanza MINORE di (l-1), quindi abbiamo detto che u' è sicuramente esplorato dall'algoritmo prima di v'.

Ora ti devi chiedere cosa succede e come si comporta l'algoritmo. L'algoritmo esplora v' e per costruzione mette in CODA tutti i vicini di u' tra cui u. In pratica u viene messo in coda sicuramente prima di v, quindi u verrà visitato prima di v

E così hai dimostrato che i nodi più vicini ad s sono esplorati prima di quelli più lontani.

Finito

Spero di essere stato abbastanza chiaro, comunque questa è una dimostrazione abbastanza semplice che dovresti trovare anche altrove

Ciao
Andrea