El documento describe el algoritmo de backtracking y cómo se puede aplicar para resolver problemas como encontrar el camino a través de un laberinto. Backtracking implica probar soluciones tentativas y retroceder a un punto de decisión anterior cuando una solución falla, para probar otras opciones. El algoritmo para resolver un laberinto usa backtracking al marcar celdas a medida que avanza, y desmarcar y probar otras direcciones cuando llega a un callejón sin salida.
0 calificaciones0% encontró este documento útil (0 votos)
37 vistas9 páginas
El documento describe el algoritmo de backtracking y cómo se puede aplicar para resolver problemas como encontrar el camino a través de un laberinto. Backtracking implica probar soluciones tentativas y retroceder a un punto de decisión anterior cuando una solución falla, para probar otras opciones. El algoritmo para resolver un laberinto usa backtracking al marcar celdas a medida que avanza, y desmarcar y probar otras direcciones cuando llega a un callejón sin salida.
El documento describe el algoritmo de backtracking y cómo se puede aplicar para resolver problemas como encontrar el camino a través de un laberinto. Backtracking implica probar soluciones tentativas y retroceder a un punto de decisión anterior cuando una solución falla, para probar otras opciones. El algoritmo para resolver un laberinto usa backtracking al marcar celdas a medida que avanza, y desmarcar y probar otras direcciones cuando llega a un callejón sin salida.
El documento describe el algoritmo de backtracking y cómo se puede aplicar para resolver problemas como encontrar el camino a través de un laberinto. Backtracking implica probar soluciones tentativas y retroceder a un punto de decisión anterior cuando una solución falla, para probar otras opciones. El algoritmo para resolver un laberinto usa backtracking al marcar celdas a medida que avanza, y desmarcar y probar otras direcciones cuando llega a un callejón sin salida.
Introducción • Supongamos que tenemos que tomar una serie de decisiones pero… • No disponemos de suficiente información como para saber cuál elegir. saber cuál elegir. • Cada decisión nos lleva a un nuevo conjunto de decisiones. • Alguna secuencia de decisiones (y puede que más de una) puede solucionar nuestro problema. • Necesitamos un método de búsqueda Necesitamos un método de búsqueda que nos permita encontrar una solución… Definición • Backtracking es un estrategia recursiva, la cual realiza la búsqueda de una opción óptima, a través de un conjunto de posibilidades. • Consiste en: • El algoritmo realiza tentativamente elecciones, de tal forma de volver atrás a un punto de decisión anterior, así podemos explorar otras posible opciones. Fase de backtracking • Se realiza movimientos hacia el camino original, hasta alcanzar un punto de decisión próximo, donde se rechaza el camino sin salida, y se prueba el siguiente camino alternativo. • Algoritmos que usan esta idea de testear posibles soluciones y regresar punto de decisión previo cuando falla el intento se conoce como Algoritmos de Backtracking. Problema del Laberinto • El problema central es encontrar (marcar) el camino, dada una representación del Laberinto, las coordenadas de entrada y salida. A través de la generación de un diagrama, en el que un de las posibles soluciones se marque. • Para desarrollar un el algoritmo, que resuelve el problema del laberinto es necesario adoptar una aproximación sistemática, que explora cada posible camino, hasta encontrar la solución. • Algunos caminos conducirán a callejones sin salida, en este caso será necesario volver atrás (para tratar otra opción), cuando ya no sea posible un progreso. Algoritmo de Backtracking 1. Empezar en la celda de etiquetada con ‘S’ 2. Dibujar ‘+’ en cada celda por donde se pase, continuar por el camino actual hasta encontrar una de las siguientes situaciones: a) Si encontramos ‘F’, hemos terminado y el camino correcto esta marcado con la cadena de ‘+’. b) Si estamos en un punto de decisión, se debe considerar todas las posibles direcciones en un orden sistematizado. Repetir el proceso a lo largo del camino, si estamos forzados a regresar, elegir la siguiente posible dirección. Si se ha intentado con todas las posibles direcciones sin encontrar una solución, estamos en un callejón sin salida y seguiremos con el punto d) Continuación…. c) Si alcanzamos una celda marcada, entonces el laberinto contiene un loop. Para evitar ingresar en un ciclo infinito es necesario considerar la situación de los callejones sin salida d) Si se alcanza un callejón sin salida, regresar al punto de decisión anterior y tratar la siguiente posible dirección. A medida que se regresa a un punto de decisión anterior, eliminar la marca ‘+’ a lo largo del camino. Si no hay un punto de decisión anterior, el algoritmo no tiene solución. ‘ ’ celda libre ‘#’ pared ‘+’ celda marcada ‘F’ fin public boolean solveMaze(int x, int y) public boolean solveMaze(int x, int y) { { if (la celda actual es la celda de fin) if (Laberinto[x][y]=='F') return true; return true; else else if( la celda actual es una pared o ya esta if( Laberinto[x][y]=='#' || Laberinto[x][y]=='+') marcada) return false; return false; else else { { Laberinto[x][y]=='+'; Marcar la celda actual con el signo + if (solveMaze(x,y+1))return true; Recursivamente tratar cada direccion de las 4 if (solveMaze(x+1,y))return true; posibles: si alguna es exito, return true; if (solveMaze(x,y-1))return true; Desmarcar la celda actual if (solveMaze(x- 1,y))return true; return false; Laberinto[x][y]==' '; //Desmarcar la celda actual } return false; } } } Algoritmo de resolución del Laberinto public boolean solveMaze(int x, int y)
if (solveMaze(x0,y0)) { if (la celda actual es la celda de fin) mostrarLaberinto(); return true; else else if( la celda actual es una pared o ya esta marcada) return false; System.out.println("El else laberinto no tiene solucion"); { Marcar la celda actual con el signo + Recursivamente tratar cada direccion de las 4 posibles: si alguna es exito, return true; Desmarcar la celda actual return false; } }
