Backtracking. Problema del laberinto

Oct 25, 2008 Codigos C# Tutoriales C# 21 comentarios

La búsqueda recursiva de soluciones de un problema, es esencialmente una estrategia de tanteo. O sea, cuando no conocemos un algoritmo específico que nos permita dar con la o las soluciones del problema, siempre queda la opción de generar todas las combinaciones posibles, y verificar cuales son realmente soluciones.

Algo que cabe destacar dentro de esta estrategia es que hay que tener en cuenta la mayor cantidad de restricciones posibles al generar cada combinación para disminuir el tiempo de ejecución y evitar cálculos redundantes.

Para que se entienda mejor, veamos un primer ejemplo:

El problema de las 8 reinas

Este problema consiste en determinar si se pueden colocar 8 damas en un tablero de ajedrez de 64 casillas, de tal manera que no queden amenazadas.

Si fuéramos a resolver este problema con fuerza bruta, tendríamos que analizar todas las ubicaciones posibles de 8 reinas en el tablero hasta que nos encontremos con una combinación en la que ninguna reina esté amenazada o hayamos realizado todas las ubicaciones posibles.

Para la colocación de la primera dama hay 64 casillas disponibles. Cuando colocamos ésta, quedarían 63 casillas posibles para la segunda dama. Y así sucesiva y recursivamente hasta que llegaríamos a un total de “combinaciones” posibles de 64 * 63 * 62 * 61* 60 * 59 * 58 * 57, para un total de 200 000 millones de combinaciones.

Una computadora muy rápida trabajando día y noche demoraría más de medio año solamente para obtener todas las combinaciones, eso sin analizarlas. Por lo que evidentemente esta es una solución muy costosa y puede mejorarse como se verá a continuación.

Sabemos que si podemos ubicar 8 reinas sin que se amenacen, entonces solo puede haber una reina por columna, ya que dos reinas en una misma columna estarían amenazándose. Por tanto el algoritmo de este problema consiste en:

1 – Si n es cero, entonces ya no quedan reinas por poner y el problema tiene solución.

2 – Se intenta ubicar una reina en cada columna de izquierda a derecha.

3 – Se intenta colocar la reina en cada celda de la columna y se verifica si desde esta posición se amenaza a las reinas ubicadas en las columnas a la izquierda. Si no se amenazan las reinas anteriores, entonces trataremos de colocar las reinas restantes en las columnas de la derecha (aproximación recursiva al caso base).

4 – Si ninguna celda de la columna satisface el paso 3, no se puede ubicar una reina en la columna y se vuelve atrás para intentar ubicar en otra posición a la reina ubicada en la columna anterior. Si estamos en la primera columna, entonces el problema no tiene solución.

ubicareinas1 Backtracking. Problema del laberinto

Este método lo único que hace es verificar si se ha recibido un tablero correcto (es cuadrado y tiene todas las celdas en false). Luego llama al método privado UbicaReinas que es el que intenta ubicar k reinas a partir del ancho del tablero.

ubicareinas2 Backtracking. Problema del laberinto

El método Amenaza sería el encargado de verificar si se amenaza alguna otra dama, recorriendo el array de forma vertical, horizontal y diagonal, a partir de la posición
[i , j]. Además de implementar este método como ejercicio, puede mejorar un poco más el algoritmo. Fíjese que dos reinas no pueden ubicarse en la misma fila.

Buscar la salida en un laberinto

Al menos para mi este problema es el ideal para demostrar el poder del backtracking. Se trata de encontrar la salida dentro de un laberinto. La estrategia a seguir para salir de un laberinto es primeramente, explorar hacia delante un posible camino y ver si conduce a una solución. Si no conduce a una solución, hay que desandar el camino y volver atrás para intentar con otro.

Considere un laberinto representado por un array rectangular (bidimensional) de bool, en el que una celda con valor false significa que hay un obstáculo por el que no se puede atravesar. Y una celda con valor true es una celda por la que se puede pasar.

El problema consiste por ejemplo en suponer que entramos por la celda en la posición 0,0 y se quiere encontrar en camino hasta la posición m,n donde m es la cantidad de filas del array y n la cantidad de columnas. Puede resolverse de igual forma si se empieza y se termina por otras celdas.

El método C# HaySalida es el siguiente:

haysalida Backtracking. Problema del laberinto

Como se ha visto en los ejemplos anteriores, este primer método es el que se encarga de llamar al otro método privado y recursivo de igual nombre. Veamos ahora el código y luego lo comentamos.

haysalida2 Backtracking. Problema del laberinto

Empezamos desde la línea 2 donde se indica el caso base de la recursividad. O sea, si se ha llegado a la celda de salida y esta es true. Después comprobamos si estamos en una celda por la cual no se puede pasar, en caso de que no se pueda pasar retornamos false. Si se puede pasar por esa casilla, la ponemos en false para garantizar que no pasaremos de nuevo por ella en caso que el camino no conduzca a una salida.

Luego, en las próximas llamadas recursivas se intenta averiguar si hay salida desde las casillas vecinas y se retorna true en caso de encontrar la salida. Si se llega a la última línea es porque desde ninguna de las celdas vecinas hay salida, y por tanto no hay salida desde la celda actual, por lo que se retorna false.

El método HaySalida solamente nos dice si existe o no salida del laberinto, pero no nos da la respuesta de cual es la salida, o sea, el camino a seguir para llegar a la salida. Intenta hacer un método SalidaLaberinto que devuelva un array con los puntos por los que se debe pasar para llegar a la salida mas corta.

En este caso para estar seguros de encontrar el camino más corto, habría que explorar todos los caminos posibles y compararlos. Note que en el método HaySalida, primero se explora el camino que va en dirección diagonal y luego los caminos más cercanos a esta, lo cual no quiere decir que se encuentre el camino más corto. Esto es lo que se conoce como heurística, que consiste en mejorar los algoritmos basados en la experiencia, el conocimiento y el sentido común.

Solo agregar que esta técnica de backtracking o Vuelta Atrás, es muy utilizada en juegos, ya que ante una determinada situación del juego se exploran los diferentes caminos a seguir según las posibles jugadas del contrario y así sucesivamente, decidiendo las jugadas, hasta que se conduce a la victoria.

Bueno, hasta aquí este pequeño tutorial de recursividad en C#. Seguro faltaron muchas cosas por tratar en este tema, ya que no soy un experto ni mucho menos.

Para aprender recursividad lo más importante es practicar, leer y copiar código. Aquí dejo algunos ejercicios. Si quieres luego debatimos las soluciones.

1- Escriba un método recursivo string Invierte (string s) que devuelva el reverso de la cadena s.

2- Implemente un método que demuestre que con un caballo se pueden recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por una misma casilla.

3- Escriba el método static long Factorial(int n) que devuelva el factorial del número n.

0! = 1, y para n ≥ 1, n! = n * (n – 1)!

4- Escriba el método static bool EsPalíndromo(string s) que diga si el string s es palíndromo. Un string es palíndromo si se lee de la misma forma de izquierda a derecha que de derecha a izquierda.

5- Implemente el método static void DescomposicionSumandos(int n) que muestre en la pantalla todas las formas posibles de descomponer el número n en sumandos. Por ejemplo, para n=5, en la pantalla se muestra:

1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
1 4
2 3
5

6- El Taxista: Un taxista se desplaza en su taxi por una ciudad en la cual sólo está permitido conducir hacia el ESTE y hacia el SUR.
Implemente el método static int CantidadCaminos(int xOrig, int yOrig, int xDest, int yDest) que devuelva la cantidad de caminos diferentes por los que se puede llegar desde el punto (xOrig, yOrig) hasta el punto (xDest, yDest). Asuma que xDest ≥ xOrig y que yDest ≥ yOrig.

Compartir:

Relacionados

algunos artículos que te pueden interesar

21 comentarios

Forma parte de nuestra discusión y síguela de cerca

Buena interpretación de las clases de Katrib. Los ejercicios estan un librito chiquito escrito por el con los ejemplos en Delphi. Estudia bastante brother pa que llegues a 5to.
Saludos desde España
Graduado en 2004.

Autor: PapasxMalangas | Fecha: Dic 2, 2008.

Katrib te dio bastante vista no???. De veras que tienes que estudiar para que llegues a 5to.
Saludoss
Graduada del 2007

Autor: tomateRojo | Fecha: Feb 10, 2009.

public int Factorial(int k)
{
      if(k==1) return 1;
      return k*Factorial(k-1)
}

Disculpa por escoger el mas fácil pero es que no estaba para escribir mucho, a propósito, suponiendo k mayor que 0.

Autor: Paulo | Fecha: Jun 8, 2009.

[...] Recursividad con C# (3) [...]

Autor: Combinaciones posibles. Recursividad C# | PuntoPeek.com | Fecha: Sep 6, 2009.

[...] con C# 2da parte Recursividad con C# 3ra parte [...]

Autor: Recursividad con C# (1) | PuntoPeek.com | Fecha: Sep 19, 2009.

excelente post, pero me gustaría ver resuleto de estta manera el problema del tour del caballo en el tablero de ajedrez, tiene mayor complejidad.

Autor: alonso | Fecha: Ago 10, 2010.

Hola alonso, el problema del tour del caballo es un clásico de la recursividad, la primera vez que vi la solución no podía creer que funcionara, jejeje.

Ahora estoy corto de tiempo, pero un poco más adelante prepararé una 4ta entrega con algunos ejercicios más interesantes y complejos.

Autor: Tomas | Fecha: Ago 13, 2010.

Gracias por el tutorial, podras ya publicar el 4?

Autor: angedu | Fecha: Sep 8, 2010.

necesito ayuda para realizar un proceso recursivo que devuelva el n-esimo elemento de menor valor en una secuencia de enteros positivos. Por ejemplo, si la secuencia contiene los valores 12, 7, 3, 9, 1, 5, 21 y n = 1 devuelve 1, si n = 2 devuelve 3, si n = 5 devuelve 9 y si n = 28 devuelve -1, que indica que ha habido un error.

Autor: yoshimar | Fecha: Oct 5, 2010.

Yo creo que la mejor forma de hacer esto es usando el algoritmo Quick Sort con una pequeña modificación… ahora te dejo un poco para que pienses como hacerlo. La clave está en hacer bien la partición. El algoritmo sería O(nlogn).

Autor: Tomy | Fecha: Oct 6, 2010.

Mira, hola necesito saber como hacer el problema de “que camino tomar en el laberinto”

Autor: Esta | Fecha: May 26, 2011.

Hola como resulevo este ejercicio, soy nuevo en java y la verdad no se
5- Implemente el método static void DescomposicionSumandos(int n) que muestre en la pantalla todas las formas posibles de descomponer el número n en sumandos. Por ejemplo, para n=5, en la pantalla se muestra:

1 1 1 1 1
1 1 1 2
1 2 2
1 1 3
1 4
2 3
5

Autor: Victor Fuarte | Fecha: Sep 29, 2011.

hola espero que me pudieras ayudar mira yo estoy haciendo un laberinto pero no me sale asi que si no es mucho pedir si me podrias decir como hacer lo que le falta la tuyo ya que al mio le falta lo mismo pero no me acuerso como realizarlo

Autor: maribel | Fecha: Oct 9, 2011.

desearía que me envíen con los los formularios y que herramientas a utilizar gracias..

Autor: Holger Shig | Fecha: Feb 16, 2012.

hola quiero saber como hacer que el programa encuentre la salida de un laberinto pero enta hecho en c# aplicaciones para windows quiero que el programa lea los 1 como camino y las paredes con 0 ayudenme porfaaaa..

Autor: angel | Fecha: Mar 4, 2012.

este es mi correo a.i.s.m92@hotmail.com para poder contactarnos gracias…..

Autor: angel | Fecha: Mar 4, 2012.

disculpa me encantaria pooder ponerme en contacto contigo es que la verdad ese lenguaje no se me da… se me complica un poco……digo para saber si me puedes ayudar

Autor: Esther | Fecha: Mar 25, 2012.

hola de casualidad no sabes hacer en c# este juego:

El juego de stop que consiste en que el servidor da una pista para que los clientes completen con nombre de personas, paises, ciudades, objetos, animales, los clientes deben completar la información en el menor tiempo posible y el servidor valida las respuestas y anuncia cual es el ganador de acuerdo al tiempo en que responden,
ejemplo el servidor anuncia: inicia con A y termina con A, los clientes responden:

Pais: Argentina
Animal: Aguila
Nombre: Amanda
Fruta: Almendra
Objeto: Agenda
etc,etc

Saludos.

Aka de dejo mi mail cualkier ayuda ;)

Autor: laura | Fecha: Ago 7, 2012.

Hola ,
Me podrían pasar el código completo del programa de Buscar la salida en un laberinto por favor
saludos y gracias

Autor: Enrique Morales | Fecha: Oct 1, 2012.

Hola amigos, la verdad no tengo mucho tiempo para ayudarlos personalmente, pero si tuvieran una pregunta más puntual, ya sería otra cosa. Por favor, traten de ser más específicos en sus preguntas.

Autor: Tomy | Fecha: Ene 8, 2013.

Podrias por favor subir el codigo del laberinto modificado de manera tal que devuelva un IEnumerable que sea el camino hasta la salida???

Autor: Amy | Fecha: Jun 10, 2013.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.