The Travel Ticket Problema

Question

Ti viene consegnata una serie di biglietti di viaggio per vari trasporti che ti porteranno da un punto A al punto B tramite diverse fermate lungo la strada. Tutti i biglietti sono fuori servizio e non sai dove inizia il tuo viaggio, né dove finisce. Ordina i biglietti nell'ordine giusto per completare il viaggio.

tickets = [ 
    {from: "Barcelona", to: "New York"} 
    {from: "Barcelona", to: "Gerona"}, 
    {from: "Madrid", to: "Barcelona"}, 
    {from: "Gerona", to: "Barcelona"} 
]

suppongo, il giusto ordine è che uno:

tickets = [ 
    {from: "Madrid", to: "Barcelona"}, 
    {from: "Barcelona", to: "Gerona"}, 
    {from: "Gerona", to: "Barcelona"}, 
    {from: "Barcelona", to: "New York"} 
]

Poiché non v'è alcun biglietto per Madrid, e senza biglietto da New York.

Quale sarebbe il miglior algoritmo per tale compito?

Il linguaggio è JavaScript, ma la soluzione indipendente dalla lingua sarebbe sufficiente.

Aggiornamento: ho cambiato dati di esempio da non confondere con One-way flight trip problem.

Answer 1

Se è possibile visitare un nodo (una città) più di una volta, questo è il eulerian path problem.

Here sono due semplici algoritmi per risolverlo, a seconda del tipo di grafico che hai. Si dispone di un'implementazione ricorsiva a pagina 3 here.

Answer 2

Non è solo una lista doppiamente collegata? Aggiungi ciascun elemento all'elenco, collegandoli tra loro in modo appropriato; quando hai finito, avrai due voci con collegamenti non connessi (uno senza niente connesso al suo nodo "" da ", uno senza una connessione al suo nodo" "a". Questi sono i punti di inizio e fine di la catena, e li lesse in sequenza iniziando con la voce priva di un "da" collegamento e seguendo il link da una voce all'altra.

Answer 3

1. Creare un grafo orientato da subito i biglietti.
2. trovare il nodo che ha ha indegree 0
3. iterare su tutti i nodi attraverso i bordi del grafico per creare il vostro risultato

Aggiornamento: con le informazioni aggiunte nel post originale, questa soluzione non risolve il problema giusto. Guarda invece su IVLad's response.

Answer 4

Quello che hai è un grafico diretto, e vuoi trovare un Eulerian Path in esso. L'articolo collegato descrive l'algoritmo per la ricerca di uno, che è fondamentalmente:

1. Trova una città con un minor numero di rotte in che fuori (se non ce ne sono, iniziare ovunque)
2. viaggio da un biglietto (bordo) che ha vinto lasciare il grafico scollegato se non è lì; a meno che tale biglietto non esista, nel qual caso utilizzare quel biglietto.
3. Cancella il biglietto (bordo) e ripetere

Si dovrebbe finire dopo aver utilizzato tutti i biglietti, e alla destinazione finale.

Answer 5

Quanto segue è un esempio dell'implementazione di javascript.

var un = 
[ 
{ from:'c',to:'d'}, 
{ from:'a',to:'b'}, 
{ from:'b',to:'c'}, 
{ from:'z',to:'a'}, 
{ from:'d',to:'m'}, 
] 

function buildTable(un){ 
return un.reduce(function(previousValue, currentValue, currentIndex){ 

//build the table. 
    previousValue.from[currentValue['from']] = currentValue; 
    previousValue.to[currentValue['to']] = currentValue; 

//to find start and end.  
    if(!previousValue.from[currentValue['to']]) previousValue.from[currentValue['to']]= false; 
    if(!previousValue.to[currentValue['from']]) previousValue.to[currentValue['from']]= false; 

    return previousValue; 

},{to:{},from:{}}); 


} 

function getStart(nodes){ 
//find start node indx. 
    for(var i in nodes) 
    if(!nodes[i])return i; 
} 


function print(start,nodes){ 


var sorted = []; 
//while detecting false from buildTable structure. 
    while(start){ 
     var node = nodes[start]; 
     sorted.push(node) 
     start = node['to']; 
//console.log(start) 
    } 

return sorted; 
} 

var sorted = buildTable(un); 
console.log(print(getStart(sorted.to),sorted.from));