Matriz mapa de distancias.

Iniciado por brunojuy, 11 Octubre 2012, 04:59 AM

0 Miembros y 2 Visitantes están viendo este tema.

brunojuy

   A     B    C      D      E      F
A 0     2   0   1   0   3
B 2     0   3   0   3   2
C 0     3   0   2   0   1
D 1     0   2   0   0   1
E  0     3   0   0   0   1
F  3     2   1   1   1   0

Hola, tengo el siguiente problema, no quiero que me den el ejercicio resuelto, solo que no se como encarar la lógica del mismo. Consiste en lo siquiente: guardar en una pila las distancias y los pueblos requeridos, por ejemplo si el usuario ingresa Origen = A y destino = E
Salida:
Camino posible:A,B,C,D,F,E
Longitud: 2+3+2+1+1= 9
En realidad ya le di mil vueltas para tratar de encarar la logica pero no se x dnd empezar, si alguien puede darme una idea estaria muy agradecido.

la matriz viene a ser como un mapa de distancias entre ciudades.

pasajero

Probaste con los algoritmos de Grafos?? Dijkstra por ejemplo?
Digo que uses algoritmos ya hechos porque no le veo el chiste a reinventar la rueda  :huh:

do-while

Cita de: pasajero en 11 Octubre 2012, 07:19 AM
Probaste con los algoritmos de Grafos?? Dijkstra por ejemplo?
Digo que uses algoritmos ya hechos porque no le veo el chiste a reinventar la rueda  :huh:

Incorrecto. Si no trabajas por ti mismo los algoritmos ni desarrollaras la logica, ni tendras herramientas para enfrentarte a futuros problemas...

Si piensas un poco, cada columna es un punto de partida y cada elemento de esa columna es un destino. Por lo tanto tendras que recorrer las distintas columnas buscando elementos no nulos que te indiquen a que columna puedes deplazarte para continuar la busqueda de la solucion en dicha columna (lo cual sugiere un algoritmo recursivo). Tendras que tener en cuenta que de una columna no puedes volver a una por la que ya hayas pasaso ya que entrarias en un bucle infinito. De esta forma encontrarias una solucion. Si llevas un recuento de la distancia que ya has recorrido podras descartar los caminos que sean mas largos que las soluciones que ya hayas encontrado y podras dar la solucion de minima distancia.

Esto solo es una solucion. Espero que te sirva.

¡Saludos!
- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!

pasajero

Cita de: do-while en 11 Octubre 2012, 09:06 AM
Incorrecto. Si no trabajas por ti mismo los algoritmos ni desarrollaras la logica, ni tendras herramientas para enfrentarte a futuros problemas...

Si piensas un poco, cada columna es un punto de partida y cada elemento de esa columna es un destino. Por lo tanto tendras que recorrer las distintas columnas buscando elementos no nulos que te indiquen a que columna puedes deplazarte para continuar la busqueda de la solucion en dicha columna (lo cual sugiere un algoritmo recursivo). Tendras que tener en cuenta que de una columna no puedes volver a una por la que ya hayas pasaso ya que entrarias en un bucle infinito. De esta forma encontrarias una solucion. Si llevas un recuento de la distancia que ya has recorrido podras descartar los caminos que sean mas largos que las soluciones que ya hayas encontrado y podras dar la solucion de minima distancia.

Esto solo es una solucion. Espero que te sirva.

¡Saludos!

No he dicho que no desarrolle la logica, claramente hay que entender el algoritmo para poder usarlo y lograr transcribirlo a codigo; sino que digo eso porque esos algoritmos son usados ampliamente; entender los algoritmos y saber cuando usarlos creo que es la mejor herramienta. Claro que se podria hacer un algoritmo propio para este caso especifico.