[Talk-it] FAQ

Federico Cozzi f.cozzi at gmail.com
Sat Aug 29 16:51:05 BST 2009


2009/8/29 Martin Koppenhoefer <dieterdreist at 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




More information about the Talk-it mailing list