Algoritmul folosit în Google Maps are aproape 60 de ani

Unele dintre cele mai folosite aplicații din ziua de azi se bazează pe niște algoritmi vechi de zeci de ani, așa cum este și cazul lui Google Maps.

După cum ar spune și Edsger Dijkstra, matematica se regăsește în orice, în fiecare aspect al vieții, iar în anumite situații poate oferi soluții extrem de simple la probleme care ar părea de nerezolvat. După cum scriu într-un articol recent și cei de la Motherboard, Dijkstra este autorul unuia dintre cele mai importanți algoritmi din domeniul informaticii.

În anul 1956, Dijkstra era implicat în proiectul pentru crearea ARMAC, unul dintre primele calculatoare care s-au aflat în posesia statului olandez. El era responsabil cu programarea calculatorului pentru lansarea oficială și trebuia să creeze un program care să scoată în evidență capacitățile sale extraordinare. ”Pentru o demonstrație în fața unor oameni care nu programează, este nevoie de o problemă pe care și cei ce nu sunt matematicieni o pot înțelege”, a declarat Dijkstra. ”Chiar și soluția trebuie înțeleasă. Așa că am creat un program ce poate identifica ruta cea mai scurtă între două orașe din Olanda”.

Problemele de acest fel pot deveni foarte dificile într-un timp foarte scurt. Prin adăugarea câtorva noduri într-un grafic, numărul posibilităților poate crește enorm, iar timpul necesar pentru efectuarea calculelor ar crește exponențial.

De ce liliecii își țin capul în jos atunci când dorm. Explicația este mai simplă decât ai fi crezut

Iustina de la Insula Iubirii a născut. Prima fotografie cu fetița ei și a lui Cornel Luchian

Ilustrația de mai sus a fost folosită pentru a explica într-un mod cât mai simplu principiul. Fiecărui segment i-a fost atribuit un număr care reprezintă distanța sau orice alt fel de de resursă consumată. Practic, cu cât numărul este mai mic, cu atât traseul este mai eficient. Un bun exemplu este traseul dintre S și T. Cel mai simplu drum dintre aceste două puncte ar trece fie prin A șiB, fie prin C și D. În primul caz, valoarea totală ar fi 12, în al doilea, 13. Un traseu prin A și C ar fi mult mai scurt, având valoarea 4, însă este mult mai complicat.

Ilustrația evidențiază cele două variabile pe care o aplicație precum Google Maps trebuie să le ia în considerare atunci când propune traseul ideal: eficiența și complexitatea. Deși probabil este mult mai complex, algoritmul din spatele Google Maps se bazează pe o variație a creației lui Edsger Dijkstra din 1956.