Diferente pentru al-k-lea-drum-minim intre reviziile #2 si #15

Nu exista diferente intre titluri.

Diferente intre continut:

h1. Al K-lea drum minim
 
(Creat de '_fluffy_':user/fluffy la data de _2004-11-29_ categoria _Grafuri_, autor(i) _Crestez Leonard_)
 
*Continut scurt:*
 Exista un numar mare de algoritmi pentru a calcula cel mai scurt drum intre 2 noduri intr-un graf, dar chiar si al 2-lea cel mai scurt drum este o extindere non-triviala. Vom prezenta un algoritm pentru a afla al k-lea drum minim intre a si b in 2 cazuri, daca drumurile trebuie sa fie elementare sau nu.
 
 
*Continut lung:*
Exista un numar mare de algoritmi pentru a calcula cel mai scurt drum intre 2 noduri intr-un graf, dar chiar si al 2-lea cel mai scurt drum este o extindere non-triviala. Pentru a afla al k-lea drum minim se foloseste un algoritm total diferit fata de cei pentru drum minim. Algoritmul este dificil de implementat, iar sursa rezultata este de obicei voluminoasa, asa ca acest algoritm nu prea intervine in problemele de concurs. Am considerat totusi ca este destul de interesant, si merita prezentat.
 
O nota importanta este ca nu se determina drumul cu al k-lea cost. Doua drumuri se considera diferita daca au noduri diferite, nu neaparat si cost diferit. Astfel, daca exista 5 drumuri distincte de cost minim, oricare dintre ele poate fi solutie pentru al 4-lea sau al 5-lea drum minim. Astfel, aceasta problema are de fapt mai multe solutii posibile.
 
Exista 2 cazuri pentru aceasta problema, iar algoritmul prezentat necesita mici modificari pentru a se adapta, dar ideea de baza ramane aceeasi. Cele doua cazuri sunt daca drumul trebuie neaparat sa fie elementar sau nu. Cazul in care se accepta doar drumuri elementare este mai restrictiv, si, astfel, un pic mai dificil.
 
Mod de functionare
 
Daca pentru drumul minim intre 2 noduri de obicei se calculeaza drumul minim dintre primul nod si celelalte noduri din graf, pentru a afla al k-lea drum minim se calculeaza toate primele k drumuri minime, in ordine. Un pas al algortimului consta in aflarea celul de-al k-lea drum minim cand primele k sunt cunoscute. Drumul minim este folosit de mai multe ori in algoritm, pentru a intelege acest algoritm este necesara o anumita familiaritate cu algoritmul lui Dijkstra.
 
Drumurile minime pana la k-1 sunt stocate compactate intr-un arbore de drumuri. Fiecarui nod din acel arbore ii corespunde un nod din graf, dar nu si invers, un nod din graf poate aparea de mai multe ori in arbore. Radacina arborelui corespunde nodului de start, iar toate frunzele arborelui corespund nodului de final, iar drumurile de la radacina catre frunze reprezinta fiecare cate un drum minim. Vezi in figura cum se compacteaza drumurile (1, 7, 4, 5), (1, 7, 3, 5), (1, 2, 4, 5) si (1, 2, 6, 4, 5). Drumurile sunt primele 4 drumuri din graful desenat mai sus si luat drept exemplu.
 
Al k-lea drum minim trebuie sa corespund pana intr-un anumit punct cu un drum aflat deja in arbore, chiar daca punctul acela este de fapt nodul de start. Pentru a gasi urmatorul drum minim, incercam sa "deviem" din fiecare nod din arbore. Un drum de deviatie pentru un anume nod X este un drum identic cu drumul de la radacina pana la nodul X, care apoi continua (deviaza) pe cel mai scurt drum pana la destinatie care nu a fost inca luat in cosiderare. Spre exemplu pentru nodul 4 din drumul (1, 2, 4, 5) putem sa deviem din 4 prin (7, 3, 5), formand drumul (1, 2, 4, 7, 3, 5). Este intuitiv ca, la fiecare pas, pentru fiecare nod din arbore este interesant doar cel mai scurt drum de deviatie.
 
Algoritmul mentine o multime, eventual ca un heap, de deviatii. Se tine pentru fiecare drum de deviatie nodul din care deviaza si lungimea drumului. La fiecare pas extragem drumul de deviatie minim si reconstituim drumul. Sa zicem ca drumul scos din heap este (a[1] a[2] ... a[d], a[d+1] ... a[n]), unde a[d] este nodul de unde s-a facut deviatia. Introducem acest drum in arborele de drumuri, si pentru fiecare nod de la a[d] la a[n - 1] calculam deviatia minima si o introducem in heap. Pentru restul nodurilor este evident ca deviatia minima nu se modifica.
 
Algoritmul odata inteles este relativ logic. Al k-lea drum minim trebuie sa coincida cu unul dintre cele k-1 drumuri deja existente pana intr-un anumit punct, dupa care "ia un viraj" nevizitat si continua cel mai scurt drumul inca neparcurs.
 
Dupa cum am zis mai sus, algoritmul are 2 variante, daca este necesar ca drumurile sa fie elementare sau nu. Pentru cele 2 variante se modifica modul in care se calculeaza deviatia minima dintr-un nod. Cazul cel mai simplu este atunci cand nu este necesar ca drumurile sa fie elementare. Pentru nodul X din care trebuie sa deviem, vom lua cel mai scurt drum care inca nu este in arbore. Putem sa calculam de dinainte un arbore de drumuri inversat, de la toate nodurile la destinatie, si sa luam minimul de la nodurile adiacente care NU sunt printre copii in arbore. Pentru arborele din desen, daca ar fi sa deviem din (1, 2) am putea lua in considerare doar nodul 1.
 
Daca trebuie sa luam in considerare doar drumurile elementare, algoritmul simplu de mai sus da erori. Spre exemplu, daca ar fi sa deviem din (1, 7) in desen, drumul optim ar fi prin 1, adica (1, 7, 1, 7, 4, 5), care drum nu este elementar. Pentru a scapa de drumurile elementare, este nevoie sa marcam nodurile de la radacina pana la deviatie ca "ocupate" si sa rulam un algoritm de drum minim pana la destinatie. Acest lucru creste foarte mult complexitatea in timp si in implementare.
 
 
 
Exemplu
 
Algoritmul prezentat este destul de complex, asa ca vom detalia rularea algoritmului pe graful din desen. Vom incerca sa calculam toate cele mai scurte 5 drumuri elementare intre nodurile 1 si 5. Punem si conditia ca drumurile sa fie elementare (cazul mai dificil).
 
* Primul drum minim este (1, 7, 4, 5), de lungime 9.
* Incercam sa deviem din 1. Drumul minim de la 1 la 5 care nu trece imediat prin 7 este (1, 2, 4, 5), cu cost 10.
* Incercam sa deviem din 7. Drumul minim de la 7 la 5 care nu trece imediat prin 4 este (7, 3, 5), cu cost 10. Atentie, adaugam si costul de la 1 la 7.
* Incercam sa deviem din 4. Nu exista alt drum de la 4 la 5. Ar putea fi drumul (4, 7, 3, 5), dar nu ar fi elementar, deoarece avem prefixul (1, 7), noduri pe care le-am marcat blocate.
* Din 5 nu are sens sa deviem, asa ca..
* Al doilea drum minim este (1, 2, 4, 5), de lungime 10.
* Incercam sa deviem din 1, dar nu exista drum de la 1 la 5 care sa nu o ia imediat nici prin 2 si nici prin 7.
* Incercam sa deviem din 2. Drumul minim de la 2 la 5 care nu trece imediat prin 4 este (2, 6, 4, 5), cu cost 10. Atentie, drumul trece prin 4, dar nu imediat.
* Incercam sa deviam din 4. Drumul minim de la 4 la 5 care nu trece imediat prin 5 este (4, 7, 3, 5), cu cost 15. Acest drum nu a fost valid mai inainte, dar acum prefixul lui 4 este (1, 2), asa ca drumul e valid.
* Al treilea drum minim este (1, 7, 3, 5), tot de lungime 10. Al doilea si al treilea drum minim sunt interschimbabile.
* Acest drum a fost derivat din 7, asa ca nu trebie incercam sa derivam din 1.
* Incercam sa deviem din 7, dar nu exista drum de la 7 la 5 care sa nu treaca imediat nici prin 3 nici prin 4. Ar fi (7, 1, 2, 4, 5), dar avem 1 ca prefix si marcat blocat. Astfel, evitam un drum neelementar.
* Incercam sa deviem din 3, fara succes(si fara explicatii kilometrice.).
* Al patrulea drum minim este (1, 2, 6, 4, 5), de lungime 11.
* Incercam sa deviem din 2, dar fara succes.
* Incercam sa deviem din 6, dar tot fara succes.
* Incercam sa deviam din 4. Drumul minim de la 4 la 5 care nu trece imediat prin 5 este (4, 7, 3, 5), cu cost 16. Noi am mai gasit odata acest drum, dar de data asta e cu un alt prefix, si alt cost. Drumul complet este (1, 2, 6, 4, 7, 3, 5), nu (1, 2, 4, 7, 3, 5).
* Al cincilea drum minim este (1, 2, 4, 7, 3, 5), de lungime 15.
* Astfel se termina exemplul nostru. Puteti sa incercati, nu mai exista deviatii posibile. Al 6-lea si ultimul drum este (1, 2, 6, 4, 7, 3, 5) , care se intample sa fie si cel mai lung drum, si hamiltonian.
 
Analiza complexitatii
 
Complexitatea algoritmului este diferita in cele 2 variante. In ambele cazuri putem considera la lugimea fiecarui drum este de O(n), si ca heap-ul contine O(k * n) valori. Luam cazul cel mai defavorabil, cu graf complet, si consideram ca un algoritm de drumuri minime necesita timp O(n * n). Astfel, daca nu este nevoie ca drumurile sa fie elementare:
 
Precalculam drumurile de la orice nod la destinatie, O(n * n).
 
La fiecare dintre cei k pasi.
Extragem din heap, O(log(k * n))
Reconstituim drumul, O(n)
 
Pentru fiecare dintre cele maxim n noduri din drum:
Vedem cel mai scurt drum de continuare, O(n)
Il adaugam in heap, O(log(k * n))
 
Complexitatea ajunge astfel la O(k * n * (n + log(k * n))). Trebuie avut in vedere ca in general drumurile minime vor avea noduri relativ putine, asa ca algorimtul e mai rapid decat pare. Daca punem conditia ca drumurile determinate sa fie elementare, complexitatea creste:
 
La fiecare dintre cei k pasi.
Extragem din heap, O(log(k * n))
Reconstituim drumul, O(n * n) (il calculam iarasi)
Blocam nodurile de la start pana la nodul de deviatie, O(n)
 
Pentru fiecare dintre cele maxim n noduri din drum:
Vedem cel mai scurt drum de continuare, O(n * n)
Il adaugam in heap, O(log(k * n))
 
Complexitatea ajunge acum la O(k * n * (n * n + log(k * n))), aproximativ O(k * n^3). Iarasi, algoritmul se comporta mai bine in practica decat pare in complexitate.
 
Observatii, indicatii, completari
 
Algoritmul poate fi mai incet sau mai rapid. Se poate folosi ceva mai simplu de implementat in loc de heap, sau un algoritm de drumuri minime mai evoluat. Daca va intrebati daca algoritmul poate fi folosit pentru a determina un drum hamiltonian, raspunsul este da, dar asta necesita determinarea tuturor drumurile lor dintre 2 muchii, care este exponential in functie de n.
 
Daca sunteti interesati si, bineinteles, daca "va tine", incercati se rezolvati problema [1]SGU 145 , de unde a pornit de fapt acest articol. Se cere cazul cel dificil, cu drumuri elementare.
 
References
 
Visible links
1. http://acm.sgu.ru/problem.php?contest=0&problem=145
 
h1. Al K-lea drum minim
 
(Categoria _Algoritmi_, Autor _Leonard Crestez_)
 
Exista un numar mare de algoritmi pentru a calcula cel mai scurt drum intre $2$ noduri intr-un graf, dar chiar si al {$2$}-lea cel mai scurt drum este o extindere non-triviala. Pentru a afla al {$k$}-lea drum minim se foloseste un algoritm total diferit fata de cei pentru drum minim. Algoritmul este dificil de implementat, iar sursa rezultata este de obicei voluminoasa, asa ca acest algoritm nu prea intervine in problemele de concurs. Am considerat totusi ca este destul de interesant, si merita prezentat.
 
O nota importanta este ca nu se determina drumul cu al {$k$}-lea cost. Doua drumuri se considera diferita daca au noduri diferite, nu neaparat si cost diferit. Astfel, daca exista $5$ drumuri distincte de cost minim, oricare dintre ele poate fi solutie pentru al {$4$}-lea sau al {$5$}-lea drum minim. Astfel, aceasta problema are de fapt mai multe solutii posibile.
 
Exista $2$ cazuri pentru aceasta problema, iar algoritmul prezentat necesita mici modificari pentru a se adapta, dar ideea de baza ramane aceeasi. Cele doua cazuri sunt daca drumul trebuie neaparat sa fie elementar sau nu. Cazul in care se accepta doar drumuri elementare este mai restrictiv, si, astfel, un pic mai dificil.
 
h2. Mod de functionare
 
Daca pentru drumul minim intre $2$ noduri de obicei se calculeaza drumul minim dintre primul nod si celelalte noduri din graf, pentru a afla al {$k$}-lea drum minim se calculeaza toate primele $k - 1$ drumuri minime, in ordine. Un pas al algortimului consta in aflarea celul de-al {$k$}-lea drum minim cand primele $k$ sunt cunoscute. Drumul minim este folosit de mai multe ori in algoritm, pentru a intelege acest algoritm este necesara o anumita familiaritate cu algoritmul lui Dijkstra.
 
Drumurile minime pana la $k-1$ sunt stocate compactate intr-un arbore de drumuri. Fiecarui nod din acel arbore ii corespunde un nod din graf, dar nu si invers, un nod din graf poate aparea de mai multe ori in arbore. Radacina arborelui corespunde nodului de start, iar toate frunzele arborelui corespund nodului de final, iar drumurile de la radacina catre frunze reprezinta fiecare cate un drum minim. Vezi in figura cum se compacteaza drumurile ({$1, 7, 4, 5$}), ({$1, 7, 3, 5$}), ({$1, 2, 4, 5$}) si ({$1, 2, 6, 4, 5$}). Drumurile sunt primele $4$ drumuri din graful desenat mai sus si luat drept exemplu.
 
!Al-K-lea-drum-minim?kshortest_graph.png!
!Al-K-lea-drum-minim?kshortest_tree.png!
 
Al {$k$}-lea drum minim trebuie sa corespund pana intr-un anumit punct cu un drum aflat deja in arbore, chiar daca punctul acela este de fapt nodul de start. Pentru a gasi urmatorul drum minim, incercam sa "deviem" din fiecare nod din arbore. Un drum de deviatie pentru un anume nod $X$ este un drum identic cu drumul de la radacina pana la nodul {$X$}, care apoi continua (deviaza) pe cel mai scurt drum pana la destinatie care nu a fost inca luat in cosiderare. Spre exemplu pentru nodul $4$ din drumul ({$1, 2, 4, 5$}) putem sa deviem din $4$ prin ({$7, 3, 5$}), formand drumul ({$1, 2, 4, 7, 3, 5$}). Este intuitiv ca, la fiecare pas, pentru fiecare nod din arbore este interesant doar cel mai scurt drum de deviatie.
 
Algoritmul mentine o multime, eventual ca un heap, de deviatii. Se tine pentru fiecare drum de deviatie nodul din care deviaza si lungimea drumului. La fiecare pas extragem drumul de deviatie minim si reconstituim drumul. Sa zicem ca drumul scos din heap este ({$a{~1~} a{~2~} ... a{~d~}, a{~d+1~} ... a{~n~}$}), unde $a{~d~}$ este nodul de unde s-a facut deviatia. Introducem acest drum in arborele de drumuri, si pentru fiecare nod de la $a{~d~}$ la $a{~n-1~}$ calculam deviatia minima si o introducem in heap. Pentru restul nodurilor este evident ca deviatia minima nu se modifica.
 
Algoritmul odata inteles este relativ logic. Al {$k$}-lea drum minim trebuie sa coincida cu unul dintre cele $k-1$ drumuri deja existente pana intr-un anumit punct, dupa care "ia un viraj" nevizitat si continua cel mai scurt drumul inca neparcurs.
 
Dupa cum am zis mai sus, algoritmul are $2$ variante, daca este necesar ca drumurile sa fie elementare sau nu. Pentru cele $2$ variante se modifica modul in care se calculeaza deviatia minima dintr-un nod. Cazul cel mai simplu este atunci cand nu este necesar ca drumurile sa fie elementare. Pentru nodul $X$ din care trebuie sa deviem, vom lua cel mai scurt drum care inca nu este in arbore. Putem sa calculam de dinainte un arbore de drumuri inversat, de la toate nodurile la destinatie, si sa luam minimul de la nodurile adiacente care NU sunt printre copii in arbore. Pentru arborele din desen, daca ar fi sa deviem din ({$1, 2$}) am putea lua in considerare doar nodul {$1$}.
 
Daca trebuie sa luam in considerare doar drumurile elementare, algoritmul simplu de mai sus da erori. Spre exemplu, daca ar fi sa deviem din ({$1, 7$}) in desen, drumul optim ar fi prin {$1$}, adica ({$1, 7, 1, 7, 4, 5$}), care drum nu este elementar. Pentru a genera doar drumurile elementare, este nevoie sa marcam nodurile de la radacina pana la deviatie ca "ocupate" si sa rulam un algoritm de drum minim pana la destinatie. Acest lucru creste foarte mult complexitatea in timp si in implementare.
 
h2. Exemplu
 
Algoritmul prezentat este destul de complex, asa ca vom detalia rularea algoritmului pe graful din desen. Vom incerca sa calculam toate cele mai scurte $5$ drumuri elementare intre nodurile $1$ si {$5$}. Punem si conditia ca drumurile sa fie elementare (cazul mai dificil).
 
* Primul drum minim este ({$1, 7, 4, 5$}), de lungime {$9$}.
* Incercam sa deviem din {$1$}. Drumul minim de la $1$ la $5$ care nu trece imediat prin $7$ este ({$1, 2, 4, 5$}), cu cost {$10$}.
* Incercam sa deviem din {$7$}. Drumul minim de la $7$ la $5$ care nu trece imediat prin $4$ este ({$7, 3, 5$}), cu cost {$10$}. Atentie, adaugam si costul de la $1$ la {$7$}.
* Incercam sa deviem din {$4$}. Nu exista alt drum de la {$4$} la {$5$}. Ar putea fi drumul ({$4, 7, 3, 5$}), dar nu ar fi elementar, deoarece avem prefixul ({$1, 7$}), noduri pe care le-am marcat blocate.
* Din $5$ nu are sens sa deviem, asa ca..
* Al doilea drum minim este ({$1, 2, 4, 5$}), de lungime {$10$}.
* Incercam sa deviem din {$1$}, dar nu exista drum de la $1$ la $5$ care sa nu o ia imediat nici prin $2$ si nici prin {$7$}.
* Incercam sa deviem din {$2$}. Drumul minim de la $2$ la $5$ care nu trece imediat prin $4$ este ({$2, 6, 4, 5$}), cu cost {$10$}. Atentie, drumul trece prin {$4$}, dar nu imediat.
* Incercam sa deviam din {$4$}. Drumul minim de la $4$ la $5$ care nu trece imediat prin $5$ este ({$4, 7, 3, 5$}), cu cost {$15$}. Acest drum nu a fost valid mai inainte, dar acum prefixul lui $4$ este ({$1, 2$}), asa ca drumul e valid.
* Al treilea drum minim este ({$1, 7, 3, 5$}), tot de lungime {$10$}. Al doilea si al treilea drum minim sunt interschimbabile.
* Acest drum a fost derivat din {$7$}, asa ca nu trebie incercam sa derivam din {$1$}.
* Incercam sa deviem din {$7$}, dar nu exista drum de la $7$ la $5$ care sa nu treaca imediat nici prin $3$ nici prin {$4$}. Ar fi ({$7, 1, 2, 4, 5$}), dar avem $1$ ca prefix si marcat blocat. Astfel, evitam un drum neelementar.
* Incercam sa deviem din {$3$}, fara succes(si fara explicatii kilometrice.).
* Al patrulea drum minim este ({$1, 2, 6, 4, 5$}), de lungime {$11$}.
* Incercam sa deviem din {$2$}, dar fara succes.
* Incercam sa deviem din {$6$}, dar tot fara succes.
* Incercam sa deviam din {$4$}. Drumul minim de la $4$ la $5$ care nu trece imediat prin $5$ este ({$4, 7, 3, 5$}), cu cost {$16$}. Noi am mai gasit odata acest drum, dar de data asta e cu un alt prefix, si alt cost. Drumul complet este ({$1, 2, 6, 4, 7, 3, 5$}), nu ({$1, 2, 4, 7, 3, 5$}).
* Al cincilea drum minim este ({$1, 2, 4, 7, 3, 5$}), de lungime {$15$}.
* Astfel se termina exemplul nostru. Puteti sa incercati, nu mai exista deviatii posibile. Al {$6$}-lea si ultimul drum este ({$1, 2, 6, 4, 7, 3, 5$}) , care se intample sa fie si cel mai lung drum, si hamiltonian.
 
h2. Analiza complexitatii
 
Complexitatea algoritmului este diferita in cele $2$ variante. In ambele cazuri putem considera la lugimea fiecarui drum este de {$O(n)$}, si ca heap-ul contine $O(k * n)$ valori. Luam cazul cel mai defavorabil, cu graf complet, si consideram ca un algoritm de drumuri minime necesita timp {$O(n * n)$}. Astfel, daca nu este nevoie ca drumurile sa fie elementare:
 
* Precalculam drumurile de la orice nod la destinatie, {$O(n * n)$}.
* La fiecare dintre cei k pasi.
** Extragem din heap, $O(log(k * n))$
** Reconstituim drumul, $O(n)$
** Pentru fiecare dintre cele maxim $n$ noduri din drum:
*** Vedem cel mai scurt drum de continuare, $O(n)$
*** Il adaugam in heap, $O(log(k * n))$
 
Complexitatea ajunge astfel la {$O(k * n * (n + log(k * n)))$}. Trebuie avut in vedere ca in general drumurile minime vor avea noduri relativ putine, asa ca algorimtul e mai rapid decat pare. Daca punem conditia ca drumurile determinate sa fie elementare, complexitatea creste:
 
* La fiecare dintre cei $k$ pasi.
** Extragem din heap, $O(log(k * n))$
** Reconstituim drumul, $O(n * n)$ (il calculam iarasi)
** Blocam nodurile de la start pana la nodul de deviatie, $O(n)$
** Pentru fiecare dintre cele maxim $n$ noduri din drum:
*** Vedem cel mai scurt drum de continuare, $O(n * n)$
*** Il adaugam in heap, $O(log(k * n))$
 
Complexitatea ajunge acum la {$O(k * n * (n * n + log(k * n)))$}, aproximativ {$O(k * n^3^)$}. Iarasi, algoritmul se comporta mai bine in practica decat pare in complexitate.
 
h2. Observatii, indicatii, completari
 
Algoritmul poate fi mai incet sau mai rapid. Se poate folosi ceva mai simplu de implementat in loc de heap, sau un algoritm de drumuri minime mai evoluat. Daca va intrebati daca algoritmul poate fi folosit pentru a determina un drum hamiltonian, raspunsul este da, dar asta necesita determinarea tuturor drumurile lor dintre $2$ muchii, care este exponential in functie de {$n$}.
 
Daca sunteti interesati si, bineinteles, daca "va tine", incercati se rezolvati problema "SGU 145":http://acm.sgu.ru/problem.php?contest=0&problem=145 , de unde a pornit de fapt acest articol. Se cere cazul cel dificil, cu drumuri elementare.
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
3695