Cari colleghi programmatori,
Stiamo sviluppando un software che simula il traffico veicolare. Parte del processo chiamato "assegnazione" riguarda l'assegnazione di veicoli ai loro percorsi e deve utilizzare una sorta di algoritmo di individuazione del percorso più breve.
Tradizionalmente, le persone lo fanno con Dijkstra, e certa letteratura scientifica sembra indicare che A * e altre alternative non apportano alcun miglioramento significativo, forse a causa della natura del grafico.
Quindi, stiamo usando anche Dijkstra. Un piccolo problema è emerso dal fatto che, se si trattano i collegamenti di traffico (span di strade tra intersezioni) come spigoli e intersezioni come nodi, non è possibile ottenere un grafico unidirezionale classico: quando ti avvicini a un'intersezione, dove puoi girare frequentemente dipende da dove vieni, mentre in un grafico tradizionale puoi prendere qualsiasi spigolo da un nodo.
Abbiamo risolto questo problema abbastanza facilmente rappresentando una coppia di link-intersezione (chiamiamola "lath") come nodo. Dal momento che dovresti attraversare un link per arrivare a qualsiasi "lath" o punto di scelta successivo, allora verrà definito un bordo come questo attraversamento, e otterrai un grafico tipico.
I risultati vengono quindi memorizzati in una semplice tabella, N x N, dove N è il numero di "laths".
Ecco l'inconveniente (inevitabile?). Se una rete tipica per la nostra simulazione può avere, ad esempio, 2000 intersezioni, avrà circa 6000 collegamenti, vale a dire N = 3V. Ovviamente, se contati in termini di intersezioni (V), siamo ora fino a O (log (3V) * (3V + E)).
Si potrebbe sostenere che 3 (o 9) è un fattore costante, ma dal punto di vista pratico, rallenta un po 'le cose e aumenta lo spazio di archiviazione a 3 V x 3 V.
Qualcuno ha idea di come possiamo ristrutturarlo per migliorare le prestazioni? Non necessariamente un algoritmo alternativo, forse rimodellare le strutture dati per adattarle a un grafico in un altro modo?