Come si elabora l'attraversamento?

Question

Ho recentemente avviato un progetto che prevede l'utilizzo di dati da un set di dati di Ungerground di Londra, al fine di trovare percorsi che sono n minuti di una determinata stazione.

Finora sono stato in grado di analizzare i dati dal set di dati e creare possibili percorsi tra ciascuna stazione. Ora ho un elenco di oggetti di percorso che hanno le seguenti proprietà:

Parent - the first station 
Child - the next linked station 
Line - whichever line the station is on 
Time - the time between the two stations 

i dati Al momento ho, utilizzando VICTORIA come stazione di partenza è:

ho formattato il mio output per rendere più facile leggi, ma ogni linea è una rappresentazione di un oggetto di percorso. Quindi hai la stazione di partenza, l'ora, la stazione successiva e la linea.

VICTORIA => 1 <= PIMLICO : Victoria 
VICTORIA => 2 <= GREEN PARK : Victoria 
VICTORIA => 2 <= ST JAMES PARK : Circle 
VICTORIA => 2 <= SLOANE SQUARE : Circle 
PIMLICO => 2 <= VAUXHALL : Victoria 
GREEN PARK => 2 <= OXFORD CIRCUS : Victoria 
GREEN PARK => 1 <= WESTMINSTER : Jubilee 
GREEN PARK => 2 <= BOND STREET : Jubilee 
GREEN PARK => 1 <= PICCADILLY CIRCUS : Piccadilly 
GREEN PARK => 1 <= HYDE PARK CORNER : Piccadilly 
ST JAMES PARK => 1 <= WESTMINSTER : Circle 
SLOANE SQUARE => 1 <= SOUTH KENSINGTON : Circle 
VAUXHALL => 2 <= STOCKWELL : Victoria 
VAUXHALL => 2 <= PIMLICO : Victoria 
OXFORD CIRCUS => 1 <= PICCADILLY CIRCUS : Bakerloo 
OXFORD CIRCUS => 2 <= REGENTS PARK : Bakerloo 
OXFORD CIRCUS => 2 <= TOTTENHAM COURT ROAD : Central 
OXFORD CIRCUS => 1 <= BOND STREET : Central 
OXFORD CIRCUS => 2 <= GREEN PARK : Victoria 
OXFORD CIRCUS => 1 <= WARREN STREET : Victoria 

Quale sarebbe il metodo migliore per raccogliere tutti i percorsi possibili, da VICTORIA?

Ad esempio:

VICTORIA > GREEN PARK > WESTMINSTER 
VICTORIA > GREEN PARK > BOND STREET 
VICTORIA > PIMLICO > VAUXHALL 

Answer 1

suona come un problema teoria dei grafi. Il mio preferito!

Il problema con la ricerca di "tutti i percorsi possibili" è che, con i dati che hai fornito (o qualsiasi set di dati realistico in questa situazione), incontrerai dei loop. Pertanto, per ogni percorso specificato, dovrai assicurarti che ogni stazione venga visitata solo una volta.

Poiché si dispone di un unico punto di partenza, si consiglia di Djikstra's Alogrithm. Questo troverà un percorso (in realtà, il percorso più breve) da VICTORIA a tutte le altre stazioni. Almeno, ogni altra stazione che è raggiungibile. Questo è un algoritmo noto, veloce e relativamente facile da implementare. Funziona normalmente in tempo O (n^2), ma può essere massaggiato in O (m + nlogn) con qualche struttura di dati jimmying.

Speriamo che almeno ti metta sulla buona strada!