Un algoritm revoluționar

Probabil e prima dată când auziți de  Edsger Dijkstra sau Robert Tarjan, asta cu toate că zi de zi clăpăciți GPS-ul. Faptul că atunci când căutați să ajungeți într-o localitate(sau la o adresă) GPS-ul vă întoarce prompt drumul cel mai rapid li se datorează. Povestea e fascinantă. În 1952, un programator olandez, Edsger Dijkstra, scrie prima versiune a algoritmului care calculează cel mai scurt drum într-un graf(harta este reprezentată în memoria computerului ca un graf). Algoritmul a fost atât de reușit încât a fost botezat cu numele creatorului său. 

În 1984, Robert Tarjan a revoluționat eficiența algoritmului prin introducerea unei structuri de date numită Fibonacci Heap. Iar acel algoritm este cel cu ajutorul căruia, între altele, programele de hărți găsesc azi drumul cel mai scurt. 

Totul părea că a ajuns la final. Doar că recent, o echipă de la Universitatea Tsinghua, coordonată de matematicianul Ran Duan, a reușit o îmbunătățire revoluționară a algoritmului Dijkstra. Cu toate că mulți nu sunt interesați, o să explic pe scurt în ce constă îmbunătățirea deoarece pe mine efectiv m-a fermecat.

Toate versiunile anterioare ale algoritmului lui Dijkstra(inclusiv cea optimizată de Tarjan) se bazează pe sortarea nodurilor în funcție de distanță. Bazându-se pe acest element era demonstrat că algoritmul nu poate fi mai eficient decât limita necesară sortării nodurilor implicate. Cei de la Tsinghua au mai departe, găsind o cale de calcul fără a mai fi necesară sortarea tuturor nodurilor. Cum au făcut-o? Printr-o combinare inteligentă a unei tehnici de clustering(în loc să verifice fiecare nod individual, algoritmul grupează nodurile vecine în "clustere" și procesează doar reprezentanții „cei mai importanți” ai acestora) cu o tehnică de identificare a nodurilor critice, care nu necesită sortare.

Probabil vă întrebați cam ce îmbunătățire oferă algoritmul chinezilor. Pe grafurile rare, de tipul hărților, se obține o îmbunătățire de 15 ori a timpului de calcul. Asta înseamnă că metoda va fi introdusă urgent în toate softurile deoarece economisind timp de calcul(iterații), economisești bani. 

Încă o dovadă a înapoierii chinezilor!

Mai multe detalii aici: https://arxiv.org/pdf/2504.17033