2009/8/29 Martin Koppenhoefer <dieterdre...@gmail.com>: > sai come funziona il routing? Inizia da sopra e poi scende, quindi > solo se non trova una strada unclassified che ti porta cerca nelle > residential, altrimenti non le guarda proprio, quindi cambia. (Al meno > quello è come qn ha scritto una volta in una delle ML).
Mi spiace deluderti, ma è falso :-) A parte che non ha senso parlare de IL routing perché di algoritmi di routing ne esistono vari. Comunque la maggior parte degli algoritmi comunemente usati (uno dei più comuni è A*) non funzionano così. Ecco perché. Provare dapprima le combinazioni usando solo primary, poi se fallisce usando secondary ecc. richiede innanzitutto back-tracking (con enorme occupazione di memoria per percorsi lunghi) e impone di tentare tutte le combinazioni: questo è un approccio con complessità esponenziale, cioè richiede tempi enormi all'allungarsi del percorso. L'approccio pratico si basa su un algoritmo euristico, cioè non dà la garanzia di trovare IL MIGLIOR routing, ma uno buono abbastanza. Dapprima si provano tutte le possibili uscite dal punto di partenza, poi ai punti così raggiunti si assegna un peso sommando due fattori: la lunghezza della strada fatta per raggiungere quel punto (e questa è stata calcolata correttamente) + la lunghezza ipotetica della strada per raggiungere la destinazione, e questa spesso viene approssimata con la distanza in linea d'aria dalla destinazione (qui appunto sta l'euristica). A questo punto tutti i punti intermedi raggiunti vengono ordinati in ordine di bontà, cioè si prova a proseguire il percorso partendo dal punto più promettente (quello col peso minore) e così si itera finché non si trova un routing. Fin qui l'algoritmo "shortest route". Per l'algoritmo "fastest route" in pratica si fa la stessa cosa, ma invece di considerare la lunghezza effettiva della way la si pesa con la categoria di strada, cioè si usano i tempi invece della distanze, ma si minimizza nello stesso modo. Ciao _______________________________________________ Talk-it mailing list Talk-it@openstreetmap.org http://lists.openstreetmap.org/listinfo/talk-it
