*** 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:
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
* 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))$
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.
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.
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.
h2. Observatii, indicatii, completari
References
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$}.
Visible links
1. http://acm.sgu.ru/problem.php?contest=0&problem=145
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.
