PDA

Visualizza la versione completa : [ALGORITMI] Come funzionano Viamichelin e GoogleMaps ?


FUN-BOY
08-05-2006, 17:26
Ciao a tutti,
è da un po' di tempo che mi servo dell'ottimo Viamichelin.it per organizzare vacanze, viaggi, ecc... Ultimamente ho visto che anche GoogleMaps (maps.google.com) offre la possibilità di cercare il percorso tra una sorgente e una destinazione.
Sono semplicemente affascinato dalla precisione e dall'accuratezza con cui gli algoritmi di questi due siti riescano a fornire il tragitto migliore (con relative indicazioni di vie e kilometraggio) tra una sorgente e una destinazione .
Ma qualcuno di voi sa o immagina come funzionano?

Io mi sono fatto un'idea, ma non ho molte conoscenze sull'argomento purtroppo : mi immagino un immenso Database ( geografico ?) che ragiona per coordinate : lat e long . Però mi chiedo: come fa un algoritmo a capire come è fatta una mappa geografica e a "sapere" dov'è situata una via? E a sapere che c'è un incrocio e che deve girare a destra per arrivare a destinazione?

C'entra per caso la teoria dei grafi (cammini minimi tra 2 nodi) ?

Grazie,
Fabio

pablo1986
08-05-2006, 17:28
premesso che nn so nulla di certe cose
ma non riesco ad immaginare un database che contiene una quantità talmente enorme di informazioni, ma molto probabilmente mi sbaglio......attendo il parere di esperti

gygabyte017
08-05-2006, 20:53
secondo me viene usato il classico algoritmo del commesso viaggiatore, per trovare il minimo percorso per andare da un punto A a un punto B passando per un insieme di punti I collegati tra loro di cui si sa la distanza tra un punto e un altro.

Forse usano anche gli algoritmi genetici per velocizzare i calcoli...

Loading