Título: [Reto] Backtracking - Laberinto Publicado por: hadree en 22 Noviembre 2010, 17:17 pm ************************************
Hola a todos, soy nuevo en el foro y se ma ha ocurrido la idea de este hilo para explicar como realizar el algoritmo de "backtracking" para calcular el camino de ida desde la entrada de un laberinto, hasta la salida del mismo (en caso de haberla). Os propongo realizar un pequeño programa que cumpla lo siguiente: Código:
Código:
Os animáis a intentarlo :cool: ?? Código: //El código lo pondré en unos días, a ver si la gente participa...:D . Título: Re: [Reto] Backtracking - Laberinto Publicado por: [D4N93R] en 23 Noviembre 2010, 05:30 am Hola,
Excelente idea. Me tomé la molestia de modificar un poquito el títle del post :P Y bueno, a ver quién se anota!! Título: Re: [Reto] Backtracking - Laberinto Publicado por: hadree en 23 Noviembre 2010, 22:27 pm Gracias, me parece bien así...."reto" suena más interesante....jajajaja
Título: Re: [Reto] Backtracking - Laberinto Publicado por: diego_lp en 24 Noviembre 2010, 16:35 pm La idea esta muy buena!
Yo me anoto! En cuanto tenga un rato libre lo voy a intentar ;-) Saludos. Título: Re: [Reto] Backtracking - Laberinto Publicado por: ghastlyX en 24 Noviembre 2010, 18:57 pm El enunciado tiene muchas imprecisiones. Cuando dice la primera solución, entiendo que se refiere a la primera que encuentre el backtracking, pero no queda claro ni especifica qué criterio usar.
Lo segundo que pide es, bajo mi punto de vista, erróneo. Con el enunciado actual no se prohíben los ciclos, de forma que existen infinitos caminos para la gran mayoría de laberintos. Se tendría que especificar una longitud máxima o bien exigir que no haya ciclos. Lo tercero es correcto, pero en lugar de un backtracking puede resolverse mediante Dijkstra, cuya complejidad para un grafo G = (V, E) es O((V + E)logV) mientras que el backtracking no es polinómico. He picado Dijkstra en C++ para el problema, he probado un par de ejemplos y los resuelve bien. El código es simple así que no debería ser problema pasarlo a otro lenguaje sabiendo un poco de C++. Código
Título: Re: [Reto] Backtracking - Laberinto Publicado por: .::IT::. en 24 Noviembre 2010, 21:44 pm No se porque paso por mi mente que podría ser una tarea jaja en fin esta interesante
Título: Re: [Reto] Backtracking - Laberinto Publicado por: hadree en 25 Noviembre 2010, 16:57 pm El enunciado tiene muchas imprecisiones. Cuando dice la primera solución, entiendo que se refiere a la primera que encuentre el backtracking, pero no queda claro ni especifica qué criterio usar. Lo segundo que pide es, bajo mi punto de vista, erróneo. Con el enunciado actual no se prohíben los ciclos, de forma que existen infinitos caminos para la gran mayoría de laberintos. Se tendría que especificar una longitud máxima o bien exigir que no haya ciclos. Lo tercero es correcto, pero en lugar de un backtracking puede resolverse mediante Dijkstra, cuya complejidad para un grafo G = (V, E) es O((V + E)logV) mientras que el backtracking no es polinómico. He picado Dijkstra en C++ para el problema, he probado un par de ejemplos y los resuelve bien. El código es simple así que no debería ser problema pasarlo a otro lenguaje sabiendo un poco de C++. 1) Por supuesto lo de la primera solución se refiere a la primera solución es decir la primera encontrada, no me parece que haya ninguna duda... 2) En cuanto a los ciclos, si la verdad es que no lo había puesto, pero se da por hecho ya que realizando los movimientos básicos comentados se quedaría atascado si intentase pasar de nuevo por una casilla ya recorrida. 3) Se puede resolver con Dijkstra, pero la idea original era que fuera por backtracking y con una representación matricial que no que fuera considerada como un grafo. 4) El código no lo he probado pero parece tener buena pinta... :rolleyes: **************************************************************** No se porque paso por mi mente que podría ser una tarea jaja en fin esta interesante PD: Yo ya lo tengo resuelto y pensaba ponerlo más adelante simplemente quería saber si había gente dispuesta a intentarlo... ::) **************************************************************** . Título: Re: [Reto] Backtracking - Laberinto Publicado por: pisa2 en 17 Diciembre 2010, 13:35 pm hola
pues a mi me iría genial la solución de este "maldito" problema en java!! ;D si la pones, me habrás hecho el regalo de navidad perfecto ;-) |