Google Maps si basa su un algoritmo molto semplice ma incredibilmente efficace: l'algoritmo di Dijkstra. Esso prende il nome dal suo inventore, Edsger Dijkstra, uno dei fondatori pionieri dell'informatica moderna.
Ecco come ebbe l'intuizione: era una mattina del 1956 e Dijkstra, che allora lavorava come programmatore al Centrum Wiskunde & Informatica (CWI) di Amsterdam, stava passeggiando con la sua fidanzata per fare un po' di shopping. Quando stanchi di camminare si sedettero a un tavolino di un caffè, lo scienziato olandese ebbe un'illuminazione: in soli 20 minuti, davanti a una tazza di caffè, progettò l'algoritmo che lo avrebbe fatto entrare nella storia dell'informatica.
Egli si servì di un grafo per descrivere la mappa della città: gli archi rappresentano le strade mentre i nodi sono gli incroci, ossia tutti i punti in cui è possibile scegliere quale strada prendere.
Grazie a questo modello, dato un punto di partenza e un punto di arrivo, all'interno del grafo stesso, l'algoritmo trova il "cammino minimo" che collega i due punti, ossia la sequenza di archi che minimizza il tempo stimato di percorrenza.
Fonte:
Nessun commento:
Posta un commento