Pues bueno, de entre todas las técnicas de diseño de algoritmos he decidido elegir backtracking (o "vuelta atrás" en español) por gusto, luego si estoy con ganas hago más posts con el resto, como por ejemplo divide y vencerás, algoritmos voraces, programación dinámica o ramificación y poda, entre otras.
DISCLAIMER: Esto no es un post para beginners. Si quieres entenderlo, debes tener una idea básica de algoritmos, recursividad, árboles, entre otros conceptos.
El backtracking es un enfoque algorítmico constructivo. Las soluciones se obtienen mediante un proceso iterativo, donde en cada paso estamos más cerca de la solución final.
A medida que se ejecuta el algoritmo, vamos obteniendo soluciones parciales. Aquí viene la magia del backtracking (vuelta atrás), si mientras se ejecuta el código vemos que no nos sirve o hay otra mejor solución, las decisiones tomadas pueden deshacerse (volver hacia atrás) y tomar un camino distinto.
Se podría considerar que esta metodología es un refinamiento de la fuerza bruta. Se suele usar para problemas que deben satisfacer un determinado tipo de restricciones.
La diferencia con la fuerza bruta radica en que se pueden evitar muchas combinaciones, ya que, haciendo uso de las restricciones, las soluciones parciales no factibles no siguen explorándose.
Se podría considerar que al backtracking se asemeja a un recorrido en profundidad dentro de un árbol (lo denominaremos árbol de expansión o de búsqueda):
La raíz contiene el estado inicial de la solución, mientras que los nodos hoja son soluciones parciales que no tuvieron extensiones factibles y fueron desechadas.
Los hijos de los nodos representan las extensiones posibles a la solución parcial que representa el nodo.
Los nodos del último nivel representan las soluciones al problema (el nodo marcado en verde en este caso).
Entonces, mientras que en fuerza bruta, tenemos en cuenta TODOS los casos, aquí vamos podando el árbol cada vez que se hace la vuelta atrás. En el peor caso, el algoritmo tendrá que recorrer todo el espacio, por lo que puede ser equivalente a un enfoque por fuerza bruta (consideramos TODAS las combinaciones posibles).
En backtracking , se combina recursividad e iteración, por lo que mucho ojo al menejar los casos base de la recursión y las condiciones de terminación de los bucles.
Ahora sí, dejemonos de tonterías teóricas y pongámonos manos a la obra con algunos algoritmos populares que usan esta estrategia:
El problema de las n reinas
Supongamos que tenemos un tablero de ajedrez de tamaño n x n.
Queremos colocar n reinas de manera que no se ataquen entre sí, es decir:
1. Que no haya 2 reinas en la misma fila
2. Que no haya 2 reinas en la misma columna
3. Que no haya 2 reinas en la misma diagonal
Representaremos la solución mediante una lista en la que en cada posición meteremos en qué columna está cada reina. Por lo que la posición "i" de la lista representa la fila en la que está la reina y el elemento "lista" representa la columna en la que está colocada la reina.
Ejemplo de solución: l=[3,0,2,4,1]
Implementación del problema:
Ahora sí, qué se hace en cada parte?
En la primera función "reinas
" se pide que halles la solución del problema para un tablero n x n. En la variable "lista" guardamos la solución y si al final se encuentra solución(con la llamada a la función "reinas(n, lista)"), se devuelve la lista solución.
Ahora sí, la función que hace cosas importantes:
Habrá solución si ya hemos metido todas las reinas en la lista. Para un tablero n x n, puedo meter n reinas. Entonces, si en la lista solución tengo n reinas, pues tengo ya la solución completa.
Ahora sí, itero por toda la lista hasta que encuentre una solución o recorra todo el tablero. Nota: la variable "i" representa las columnas
Checkeo las 3 restricciones (la de las fila no, ya que si cada posición de la lista es una posición de la fila , pues no puedo tener más de 1 elemento en la misma posición en una lista, simplemente no es posible, por eso sólo checkeo la de las columnas y la de las diagonales).
Luego, me fijo si en cada fila , tengo la columna "i" en la lista, si la tengo paso, porque no puedo meter una reina en dos columnas.
Y también, me fijo en si se cumple que no se atacan en las diagonales, que es una función a parte que se verá luego.
Si las 2 restricciones se cumplen, meto la solución parcial en la lista, si para esa fila es factible, la dejo y pruebo con la siguiente fila , sino, la elimino y pruebo con la siguiente columna para la misma fila . Justo aquí es donde aplicamos el backtracking . Si la solución me vale, sigo. Si no me vale, podo el árbol (desecho la solución) y pruebo con otra.
Ahora la función checkeo de columnas:
Esta función es simplemente la aplicación a ordenador de la fórmula matemática |x-x'| == |y-y'| que representa si dos reinas se atacan en diagonal, siendo (x,y) y (x',y') las coordenadas de las reinas.
En el caso de la función:
- "i" es la columna de la reina actual que estamos considerando
- "j" representa la fila de la reina actual
- "k" representa la posición de la reina previamente colocada a la que hay ahora en la lista.
- "lista.get(k)" cogemos la columna en la que está esa reina.
Y eso es todo, un ejemplo del algoritmo en ejecución sería el siguiente:
Que en forma de árbol, se vería tal que así:
Recomiento mucho cualquier IDE de JetBrains que va de putísima madre.
En especial IntelliJ, que es para Java hace maravillas (que le follen a eclipse). Encima en IntellJ, hay una extensión que se llama "Java Visualizer" que hace maravillas. Para debuggear en java es ORO, absoluto ORO.
Para otros lenguajes (incluyendo Java) y códigos más cortos, puedes usar el siguiente que es del estilo e igual está muy muy bien: https://pythontutor.com/visualize.html#mode=edit
Me da pereza revisar el post, lo peor que habrá sería un fallo que he escrito algo mal pero me la pela. Cualquier cosita que querais decirme os leo.
Si os interesan los algoritmos y/o las estructuras de datos decidme y hago más posts de esto aunque no sean tan beginner friendly.
---------------------------------------------- EDIT ----------------------------------------------
A parte, con el backtracking se pueden resolver más tipos de problemas como por ejemplo problemas de enumeración o de optimización.
Voy a añadir un problema de las N reinas, pero esta vez utilizando un enfoque de enumeración, en donde en vez de solamente enseñar 1 solución válida, enseño todas.
No hay mucho que explicar, es muy parecido al otro. En el otro simplemente guardabamos en una lista una solución válida, en este tenemos una lista de listas, en la que cada lista constituye una solución válida para este problema.
En la segunda función reinas será donde iremos actualizando el valor de las listas.
Si recordais, antes dijimos que si llega al tamaño n, transformábamos el booleano para acabar ya el problema. En este caso, si llegamos al tamaño n (hemos rellenado una lista con una solución válida), meteremos esa solución a la lista de listas.
El punto en el que hacemos backtracking , no sería para cambiar el valor del booleano para saber si hay solución y saber si parar o no, sino que esa llamada recursiva a reinas(n, actual, todas); serviría para volver a aplicar el proceso de encontrar otra lista solución para poder añadirla a la lista de listas.
Si recordais, antes para un tamaño n=4, teníamos la solución [1,3,0,2], pero ahora como inspeccionamos todas las soluciones, para n=4 obtendremos lo siguiente
Y para un valor de n más grande??
Pues más que lo mismo, pero con más soluciones obviamente. Cuanto mayor sea el tamaño del tablero, más combinaciones válidas de reinas existen:
Ahora sí, espero que os haya gustado el post con este pequeño update, lo que sea, ose veo por los comentarios. Y thanks por el feedback, veo que está gustando.
PD: Anon saca más boletos de repsol que parece que a la gente le ha flipado y han volado en 1 día JAJAJ
DISCLAIMER: Esto no es un post para beginners. Si quieres entenderlo, debes tener una idea básica de algoritmos, recursividad, árboles, entre otros conceptos.
El backtracking es un enfoque algorítmico constructivo. Las soluciones se obtienen mediante un proceso iterativo, donde en cada paso estamos más cerca de la solución final.
A medida que se ejecuta el algoritmo, vamos obteniendo soluciones parciales. Aquí viene la magia del backtracking (vuelta atrás), si mientras se ejecuta el código vemos que no nos sirve o hay otra mejor solución, las decisiones tomadas pueden deshacerse (volver hacia atrás) y tomar un camino distinto.
Se podría considerar que esta metodología es un refinamiento de la fuerza bruta. Se suele usar para problemas que deben satisfacer un determinado tipo de restricciones.
La diferencia con la fuerza bruta radica en que se pueden evitar muchas combinaciones, ya que, haciendo uso de las restricciones, las soluciones parciales no factibles no siguen explorándose.
Se podría considerar que al backtracking se asemeja a un recorrido en profundidad dentro de un árbol (lo denominaremos árbol de expansión o de búsqueda):
La raíz contiene el estado inicial de la solución, mientras que los nodos hoja son soluciones parciales que no tuvieron extensiones factibles y fueron desechadas.
Los hijos de los nodos representan las extensiones posibles a la solución parcial que representa el nodo.
Los nodos del último nivel representan las soluciones al problema (el nodo marcado en verde en este caso).
Entonces, mientras que en fuerza bruta, tenemos en cuenta TODOS los casos, aquí vamos podando el árbol cada vez que se hace la vuelta atrás. En el peor caso, el algoritmo tendrá que recorrer todo el espacio, por lo que puede ser equivalente a un enfoque por fuerza bruta (consideramos TODAS las combinaciones posibles).
En backtracking , se combina recursividad e iteración, por lo que mucho ojo al menejar los casos base de la recursión y las condiciones de terminación de los bucles.
Ahora sí, dejemonos de tonterías teóricas y pongámonos manos a la obra con algunos algoritmos populares que usan esta estrategia:
El problema de las n reinas
Supongamos que tenemos un tablero de ajedrez de tamaño n x n.
Queremos colocar n reinas de manera que no se ataquen entre sí, es decir:
1. Que no haya 2 reinas en la misma fila
2. Que no haya 2 reinas en la misma columna
3. Que no haya 2 reinas en la misma diagonal
Representaremos la solución mediante una lista en la que en cada posición meteremos en qué columna está cada reina. Por lo que la posición "i" de la lista representa la fila en la que está la reina y el elemento "lista" representa la columna en la que está colocada la reina.
Ejemplo de solución: l=[3,0,2,4,1]
Implementación del problema:
Java:
public static List<Integer> reinas(int n){
List<Integer> lista = new ArrayList<>();
boolean sol = reinas(n, lista);
return sol ? lista : null;
}
public static boolean reinas(int n, List<Integer> lista){
boolean haySol = false;
if(lista.size() == n) haySol = true; // Todas las reinas se han colocado en el tablero
int i = 0;
while(!haySol && i < n){
if(!lista.contains(i) && noDiagonal(i, lista)){
lista.add(i);
haySol = reinas(n, lista);
if(!haySol) lista.remove(lista.size() -1);
}
++i;
}
return haySol;
}
public static boolean noDiagonal(int i, List<Integer> lista){
boolean noCome = true;
int j = lista.size();
int k = 0;
while(k < lista.size() && noCome){
noCome = Math.abs(j-k) != Math.abs(i - lista.get(k));
++k;
}
return noCome;
}
public static void main(String[] args) {
List<Integer> solReinas = reinas(4);
for(Integer reina : solReinas) {
System.out.println(reina+" ");
}
}En la primera función "reinas
" se pide que halles la solución del problema para un tablero n x n. En la variable "lista" guardamos la solución y si al final se encuentra solución(con la llamada a la función "reinas(n, lista)"), se devuelve la lista solución.Ahora sí, la función que hace cosas importantes:
Habrá solución si ya hemos metido todas las reinas en la lista. Para un tablero n x n, puedo meter n reinas. Entonces, si en la lista solución tengo n reinas, pues tengo ya la solución completa.
Ahora sí, itero por toda la lista hasta que encuentre una solución o recorra todo el tablero. Nota: la variable "i" representa las columnas
Checkeo las 3 restricciones (la de las fila no, ya que si cada posición de la lista es una posición de la fila , pues no puedo tener más de 1 elemento en la misma posición en una lista, simplemente no es posible, por eso sólo checkeo la de las columnas y la de las diagonales).
Luego, me fijo si en cada fila , tengo la columna "i" en la lista, si la tengo paso, porque no puedo meter una reina en dos columnas.
Y también, me fijo en si se cumple que no se atacan en las diagonales, que es una función a parte que se verá luego.
Si las 2 restricciones se cumplen, meto la solución parcial en la lista, si para esa fila es factible, la dejo y pruebo con la siguiente fila , sino, la elimino y pruebo con la siguiente columna para la misma fila . Justo aquí es donde aplicamos el backtracking . Si la solución me vale, sigo. Si no me vale, podo el árbol (desecho la solución) y pruebo con otra.
Ahora la función checkeo de columnas:
Esta función es simplemente la aplicación a ordenador de la fórmula matemática |x-x'| == |y-y'| que representa si dos reinas se atacan en diagonal, siendo (x,y) y (x',y') las coordenadas de las reinas.
En el caso de la función:
- "i" es la columna de la reina actual que estamos considerando
- "j" representa la fila de la reina actual
- "k" representa la posición de la reina previamente colocada a la que hay ahora en la lista.
- "lista.get(k)" cogemos la columna en la que está esa reina.
Y eso es todo, un ejemplo del algoritmo en ejecución sería el siguiente:
Que en forma de árbol, se vería tal que así:
Recomiento mucho cualquier IDE de JetBrains que va de putísima madre.
En especial IntelliJ, que es para Java hace maravillas (que le follen a eclipse). Encima en IntellJ, hay una extensión que se llama "Java Visualizer" que hace maravillas. Para debuggear en java es ORO, absoluto ORO.
Para otros lenguajes (incluyendo Java) y códigos más cortos, puedes usar el siguiente que es del estilo e igual está muy muy bien: https://pythontutor.com/visualize.html#mode=edit
Me da pereza revisar el post, lo peor que habrá sería un fallo que he escrito algo mal pero me la pela. Cualquier cosita que querais decirme os leo.
Si os interesan los algoritmos y/o las estructuras de datos decidme y hago más posts de esto aunque no sean tan beginner friendly.
---------------------------------------------- EDIT ----------------------------------------------
A parte, con el backtracking se pueden resolver más tipos de problemas como por ejemplo problemas de enumeración o de optimización.
Voy a añadir un problema de las N reinas, pero esta vez utilizando un enfoque de enumeración, en donde en vez de solamente enseñar 1 solución válida, enseño todas.
Código:
public static void reinas(int n, List<List<Integer>> todas){
List<Integer> actual = new ArrayList<>();
reinas(n, actual, todas);
}
public static void reinas(int n, List<Integer> actual, List<List<Integer>> todas){
if(actual.size() == n) todas.add(new ArrayList<Integer>(actual)); // copia
else{
for(int i = 0; i < n; ++i){
if(!actual.contains(i) && noDiagonal(i, actual)){
actual.add(i);
reinas(n, actual, todas);
actual.remove(actual.size() - 1);
}
}
}
}
public static boolean noDiagonal(int i, List<Integer> lista){
boolean noCome = true;
int j = lista.size();
int k = 0;
while(k < lista.size() && noCome){
noCome = Math.abs(j-k) != Math.abs(i - lista.get(k));
++k;
}
return noCome;
}
public static void main(String[] args) {
int n = 4;
List<List<Integer>> todas = new ArrayList<>();
reinas(n, todas);int cnt = 1;
for(List<Integer> list : todas){
System.out.print("Lista "+cnt+ ": [ ");
for(Integer i : list){
System.out.print(i+" ");
}
System.out.println("]");
++cnt;
}
}No hay mucho que explicar, es muy parecido al otro. En el otro simplemente guardabamos en una lista una solución válida, en este tenemos una lista de listas, en la que cada lista constituye una solución válida para este problema.
En la segunda función reinas será donde iremos actualizando el valor de las listas.
Si recordais, antes dijimos que si llega al tamaño n, transformábamos el booleano para acabar ya el problema. En este caso, si llegamos al tamaño n (hemos rellenado una lista con una solución válida), meteremos esa solución a la lista de listas.
El punto en el que hacemos backtracking , no sería para cambiar el valor del booleano para saber si hay solución y saber si parar o no, sino que esa llamada recursiva a reinas(n, actual, todas); serviría para volver a aplicar el proceso de encontrar otra lista solución para poder añadirla a la lista de listas.
Si recordais, antes para un tamaño n=4, teníamos la solución [1,3,0,2], pero ahora como inspeccionamos todas las soluciones, para n=4 obtendremos lo siguiente
Y para un valor de n más grande??
Pues más que lo mismo, pero con más soluciones obviamente. Cuanto mayor sea el tamaño del tablero, más combinaciones válidas de reinas existen:
Ahora sí, espero que os haya gustado el post con este pequeño update, lo que sea, ose veo por los comentarios. Y thanks por el feedback, veo que está gustando.
PD: Anon saca más boletos de repsol que parece que a la gente le ha flipado y han volado en 1 día JAJAJ
Última edición:
