Recursividad y Backtracking!!!!

Iniciado por bwsr, 28 Mayo 2007, 15:30 PM

0 Miembros y 1 Visitante están viendo este tema.

bwsr

Hola.

Tengo el siguiente problema, tengo que hacer un programa que me calcule todos los caminos posibles de un tren para que este llegue a su destino pudiendo hacer transbordo en las estaciones con mismo nombre y asi pasar a otras lineas.

Lo que quiero es guardar cada recorrido válido en una lista de listas List<List<String>> estoy programando en java.

Estas podían ser las lineas de los trenes. (guardadas en otra List<List<String>>)

Estación 1 -----> Estación 2 -----> Estación 3 -----> Estación 4

Estación 2 -----> Estacion 4

Estación 0 ----> Estación 2 ----> Estación 4

Estación 2-----> Estación 4 -----> Estación 5



Mi información :

      Parada origen : Estación 1
      
      Parada destino : Estación 4

Como se podría calcular todos los caminos válidos usando recursividad?¿?

Si alguien me pudiera hechar una mano se lo agradecería mucho....

Un saludo y gracias.

Ragnarok

A ver si esto te inspira algo, la sintaxis está inspirada en java y el "enhanced" for.

Caminos calcularCamino(Nodo nodo){
   Caminos res;
   for (Nodo h : nodo.hijos())
         for (Camino c : calcularCamino(h))
              res.append(h + c);
}
No olvidéis leer las normas generales, además de las específicas de cada tablón.sgae, ladrones

bwsr

A ver yo tengo un Lista que es esta :

List<List<String>> lineasDeLosTrenes = new Vector<List<String>>();  //Aquí estan los nombres de las estaciones ordenados

Estación 1 Estación 2 Estación 3 Estación 4

Estación 2  Estacion 4

Estación 0 Estación 2  Estación 4

Estación 2 Estación 4 Estación 5

Para poder acceder a los nombres de cada linea, primero hay que cargar en una lista normal cada linea:

List<String> temporal = lineasDeLosTrenes.get(i);  //donde "i" es la linea a explorar



Mi problema es que quiero guardar en otra lista de listas( List<List<String>> todasLosCaminosPosibles = new Vector<List<String>>(); )  todas las posibilidades que hay de ir de una

estación origen hasta destino pudiendo hacer transbordo en las estaciones con mismo nombre y asi llegar a destinos pertenecientes a lineas en las que el origen no está.

Por ejemplo:

Origen : Estacion 0

Destino : Estacion 5

Si me hechaseis una mano os lo agradecería en el alma, gracias Ragnarok por tu respuesta pero no soy capaz de sacar nada en claro......