Quale algoritmo dovrei usare per trovare il percorso più breve in questo grafico?

Naviga le tue risposte
8

Ho un grafico con circa un miliardo di vertici, ognuno dei quali è collegato a circa 100 altri vertici a caso.

Voglio trovare la lunghezza del percorso più breve tra due punti. Non mi interessa il vero percorso utilizzato.

Note:

  • A volte i bordi saranno tagliati o aggiunti. Questo accade circa 500 volte meno spesso delle ricerche. È anche ok per raggruppare le modifiche agli edge se ti consente di ottenere prestazioni migliori.
  • I possibile pre-elaborare il grafico.
  • Se sono necessari più di 6 passaggi, puoi tornare indietro con infinito.
  • È accettabile sbagliare lo 0,01% delle volte, ma solo restituendo una lunghezza troppo lunga.
  • Tutti i bordi hanno una lunghezza di 1.
  • Tutti i bordi sono bidirezionali.

Sto cercando un algoritmo. Psuedocode, descrizioni in inglese e codice reale sono tutti fantastici.

Potrei usare A *, ma sembra ottimizzato per il path-finding.
Ho pensato di utilizzare l'algoritmo Dijkstra , ma ha un passo che richiede l'impostazione dell'attributo più breve percorso di ogni vertice all'infinito

(Se ti stai interrogando sul caso d'uso, è per il Concorso C subdolo.)

    
posta Nick ODell 03.04.2013 - 07:40
fonte

3 risposte

6

Algoritmo di base

Mantenere due serie di nodi che è possibile raggiungere dal nodo iniziale e finale. In modo alternato, fai tre passi da entrambi i lati. Ogni volta che sostituisci il tuo set con i nodi puoi raggiungere un ulteriore passaggio. Dopo ogni passaggio, controlli i due set per i nodi comuni.

Ottimizzazioni

Assicurati di poter iterare i set come ordinati in modo da poter cercare nodi comuni in un'unica operazione: un'operazione O (n + m). Gli elenchi saranno fino a un milione di nodi ciascuno.

Per estendere un set con un solo passaggio, devi interrogare tutte le connessioni dei nodi nel set originale e unirle in un nuovo set ordinato. L'unione di 2 elenchi ordinati può essere eseguita nuovamente in un'unica operazione. Quindi vuoi anche assicurarti di poter interrogare le connessioni di un nodo come ordinate. (Potrebbe essere pre-elaborato).

Negli ultimi due passaggi ogni nuovo set è il risultato dell'unione fino a 10000 di questi risultati di query. È meglio farlo unire adattivo (unendo blocchi di dimensioni uguali). In questo modo, la struttura dei dati dell'insieme ordinato può essere una semplice lista collegata.

In questo modo l'intero algoritmo diventa O (6 * n + 6 * n * log n) dove n è max. 1.000.000.

    
risposta data 03.04.2013 - 09:17
fonte
2

Usa la prima ricerca del respiro (non serve l'alg di Dijkstra perché tutti i bordi hanno una lunghezza uniforme) (e come ha detto Kris Van Bael, eseguilo da entrambi i lati)

    
risposta data 03.04.2013 - 14:32
fonte
0

"All edges have a length of 1" Questo è uno scenario ottimale che rende Algoritmo di Dijkstra una scelta di algoritmo avido perfetto. Anche usando l'algoritmo Floyd-Warshall che implica la moltiplicazione della matrice veloce funziona bene.

    
risposta data 03.04.2013 - 14:35
fonte

Leggi altre domande sui tag

Test delle unità su strutture di visualizzazione (grafica 3D) Progettazione software basata su plug-in