|
Título: Matriz mapa de distancias. Publicado por: brunojuy en 11 Octubre 2012, 04:59 am 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. Título: Re: Matriz mapa de distancias. Publicado por: 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: Título: Re: Matriz mapa de distancias. Publicado por: do-while en 11 Octubre 2012, 09:06 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! Título: Re: Matriz mapa de distancias. Publicado por: pasajero en 11 Octubre 2012, 18:03 pm 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. |