The Travel Tickets Problema

Question

Le dan una pila de boletos de viaje para varios transportes que lo llevarán de un punto A a un punto B a través de varias paradas en el camino. Todas las entradas están desordenadas y usted no sabe dónde comienza su viaje, ni dónde termina. Ordene las entradas en el orden correcto para completar su viaje.

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

supongo, el orden correcto es que uno:

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

Porque no hay entradas a Madrid, y ningún billete de Nueva York.

¿Cuál sería el mejor algoritmo para esa tarea?

El lenguaje es JavaScript, pero la solución independiente del idioma sería suficiente.

Actualización: me cambiaron datos de ejemplo para no ser confundido con One-way flight trip problem.

Answer 1

Si puede visitar un nodo (una ciudad) más de una vez, este es el eulerian path problem.

Here son dos algoritmos simples para resolverlo, dependiendo del tipo de gráfico que tenga. Tiene una implementación recursiva en la página 3 here.

Answer 2

¿No es solo una lista doblemente vinculada? Agregue cada elemento a la lista, vinculándolos según corresponda; Cuando hayas terminado, tendrás dos entradas con enlaces desconectados (una sin nada conectado a su nodo "desde", una sin conexión en su nodo "a". Estos son los puntos inicial y final de la cadena, y se leyó a cabo de forma secuencial, comenzando con la entrada carece de un "de" enlace, y siguiendo el enlace de una entrada a la siguiente.

Answer 3

1. Crear un grafo dirigido desde sus entradas.
2. encontrar el nodo que se tiene grado de entrada 0
3. iterar sobre todos los nodos a través de los bordes de gráficos para crear el resultado

Actualización: con la información agregada en la publicación original, esta solución no resuelve el problema correcto. Mire en cambio a IVLad's response.

Answer 4

Lo que tienes es un gráfico dirigido, y deseas encontrar un Eulerian Path en él. El artículo enlazado describe el algoritmo para encontrar uno, que es básicamente:

1. Localización de una ciudad con un menor número de rutas dentro que fuera (si no los hay, se inicia en cualquier lugar)
2. viaje por un boleto (borde) que ganó no dejes el gráfico desconectado si no está allí; a menos que tal boleto no exista, en cuyo caso use ese boleto.
3. Eliminar el billete (borde) y repetir

Usted debe terminar después de haber utilizado todas las entradas, y en el destino final.

Answer 5

El siguiente es un ejemplo de la implementación de 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));