Algoritmo per determinare il percorso più veloce?

Naviga le tue risposte
17

Diciamo che andiamo da 1 a 5. Il percorso più breve sarà 1-4-3-5 (totale: 60 km).

Possiamousare l'algoritmo di Dijkstra per farlo.

Ora il problema è che il percorso più breve non è sempre il più veloce, a causa di ingorghi o altri fattori.

Ad esempio:

  • 1-2 è noto per gli ingorghi del traffico frequenti, quindi dovrebbe essere evitato.
  • Improvvisamente un incidente d'auto avviene lungo 4-3, quindi dovrebbe essere evitato anche.
  • Etc ...

Quindi probabilmente possiamo velocizzare il percorso 1-4-5, a causa di assenza di ingorghi / incidenti, quindi arriverà alle 5 più velocemente.

Questa è l'idea generale, e non ho ancora pensato a ulteriori dettagli.

C'è qualche algoritmo per risolvere questo problema?

    
posta anta40 19.12.2011 - 17:37
fonte

5 risposte

5

Dato che hai portato la congestione nella foto, fai attenzione a non farti prendere dal paradosso di Braess . Se tutti scelgono il percorso ottimale, il tempo di viaggio peggiore per tutti.

    
risposta data 19.12.2011 - 20:58
fonte
49

Sì: Dijkstra

Dijkstra funziona altrettanto bene per questa situazione.
Devi solo usare il tempo piuttosto che la distanza come il peso di ogni arco.

    
risposta data 19.12.2011 - 17:42
fonte
16

Sì. L'algoritmo di Dijkstra risolverà questo problema.

Il problema nel tuo caso è che tu presumi automaticamente che il percorso più breve corrisponda alla distanza percorsa, quando in realtà equivale più appropriatamente al COSTO di percorrere una rotta.

Se un percorso ha un roadblock, il suo COST dovrebbe essere più alto e l'algoritmo si applica ancora.

    
risposta data 19.12.2011 - 17:42
fonte
11

Dovresti essere in grado di sostituire la tua distanza con il tempo tra i nodi e risolverlo allo stesso modo.

    
risposta data 19.12.2011 - 17:42
fonte
10

Dijkstra

Come detto prima, non è usato solo per la distanza più breve. Credo che questa animazione dia una buona comprensione del "potere" (di mancanza di una parola migliore) di Dijkstra:

    
risposta data 19.12.2011 - 21:13
fonte

Leggi altre domande sui tag

Perché la creazione dell'istanza è così com'è? Ciclo Foreach con break / return vs. while-loop con invarianza e post-condizione esplicite