Esiste un approccio migliore per trovare il percorso più breve all'interno di una rete di traffico (veicolare)?

8

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?

    
posta Greg Kramida 22.08.2012 - 22:59
fonte

2 risposte

6

Dijkstra trova il percorso più breve tra un dato nodo e tutti altri nodi, quindi mi aspetto che sarebbe più costoso di A *. Tuttavia, sembra che tu stia provando a pre-calcolare il costo e l'amp; percorso da qualsiasi nodo a qualsiasi altro? Allora Dijkstra è la strada da percorrere.

Per una rappresentazione più semplice, mi vengono in mente alcune cose:

In molte intersezioni, puoi venire & lascia come vuoi. È solo un sottoinsieme che hai restrizioni come "nessuna svolta a sinistra". Quindi potresti usare i "listelli" solo per le intersezioni in cui ne hai effettivamente bisogno. Ciò dovrebbe ridurre notevolmente le dimensioni proprio lì.

Potresti farlo automaticamente cercando "equivalenti listelli" e combinandoli. Due listelli sono equivalenti se tutti i collegamenti che escono sono uguali. Per esempio. se "Intersection X coming from the West" e "Intersection X from the South" portano entrambi allo stesso set di altri nodi, con lo stesso costo, quindi basta unirli in un singolo nodo.

Sei sicuro di aver bisogno / vuoi precomporre il percorso migliore, invece di compilarlo online? I videogiochi tipicamente calcolano queste cose online.

Inoltre, come stai rappresentando i percorsi? Nella tua matrice, devi solo rappresentare il primo link nel percorso. Ad esempio, per passare da casa di Bob a lavoro di Bob, devi solo conoscere il primo link, dal momento che quando ci arrivano, puoi ora cercare nella tua matrice come ottenere dal primo collegamento al lavoro di Bob, che ti darà il secondo link, ecc.

    
risposta data 22.08.2012 - 23:33
fonte
1

Hai un grande grafico e lo hai reso ancora più grande. Martinc C. Martin ha consigliato l'uso dei torni solo quando necessario, quindi non entrerò in questo.

Una delle cose che potrebbe aiutarti, è trasformare il tuo grafico in grafici più piccoli.

La prima semplificazione che mi ha aiutato molto (ho lavorato con le reti stradali degli stati europei) è stata la "rimozione" dei nodi con digree 1 e 2 in modo ricorsivo. In questo modo non ci sono strade senza uscita e le intersezioni a T (in origine grado 3) diventano grado 2 e questo non è interessante, se non si sta tentando di raggiungere quel nodo o nodo in quel cull de sac rimosso.

Successivamente, puoi provare a dividere il tuo grafico in parti che hanno una grande quantità di nodi e spigoli interni, ma hanno una connessione minima con altre parti. Per trovarli, ho usato il taglio minimo in cui il sink e la source erano lontani tra loro (nei bordi) l'uno dall'altro ei bordi vicino a loro avevano un'enorme capacità ei bordi in qualche punto tra loro erano piccoli.

    
risposta data 31.03.2015 - 11:02
fonte

Leggi altre domande sui tag