Búsqueda exhaustiva: Fuerza bruta y backtracking

En muchísimos problemas, existe un espacio de potenciales candidatos, entre los cuales solamente algunos cumplen ciertas condiciones, que los hacen válidos. Algunas cosas muy comunes que se pueden querer hacer en estos casos son:

• Encontrar alguna solución válida.
• Contar o enumerar todas las soluciones válidas.
• Encontrar la mejor de todas las soluciones válidas (el criterio o “la cuenta” para determinar cuál de todas las soluciones es la mejor depende de cada problema)

Todos los problemas que tengan esta estructura podremos encararlo mediante el enfoque de búsqueda exhaustiva, que consiste en considerar exhaustivamente todos los potenciales candidatos. De esta forma podemos enumerar todos aquellos que son válidos y nos interesan, y si podemos enumerarlos también podemos contarlos o elegir el mejor.

Como primer ejemplo podemos poner el segundo problema del nacional CYM 2015, nivel 1: http://www.oma.org.ar/enunciados/cym15r4.htm. Allí se piden hallar enteros positivos $x,y,z$ que cumplan $x^2 + y^2 = z^2$ y también $28x +10y+2015z = 448103$. En principio hay infinitas posibilidades, ya que hay infinitos números naturales, pero podemos notar mirando la segunda ecuación que $x$ debe estar entre $1$ y $\frac{448103}{28} = 16003,7$, $y$ debe estar entre $1$ y $\frac{448103}{10}=44810,3$ y $z$ debe estar entre $1$ y $\frac{448103}{2015} = 222,4$. Si fueran más grandes, la suma total del lado izquierdo se pasaría de 448103. Entonces ahora tenemos justamente un conjunto de posibles candidatos, que son todas las ternas $(x,y,z)$ con $1 \leq x \leq 16003$, $1 \leq y \leq 44810$ y $1 \leq z \leq 222$. De todos estos candidatos, son únicamente válidas las ternas que cumplan ambas ecuaciones. Una variante del problema sería, en lugar de hallar cualquier terna válida, encontrar la que tenga la suma $x+y^2+z^3$ mínima (o cualquier otro criterio).

Un segundo ejemplo podría ser decidir si dados $n$ números enteros positivos, es posible elegir algunos de ellos de manera tal que la suma sea un cierto entero positivo dado $T$. Los $2^n$ subconjuntos posibles forman todos los posibles candidatos en este caso, pero solamente serán válidos aquellos en los que la suma sea $T$. Existe una variante de este problema muy similar en la que cada número tiene un cierto “valor”, y entonces no solamente queremos alguna solución válida (que sus números sumen $T$), sino que de todas ellas, queremos aquella en la cual la suma de los valores asignados a sus números sea lo más grande posible.

Finalmente, el ejemplo más clásico utilizado para enseñar las técnicas de búsqueda exhaustiva lo constituye el problema de las $n$ damas ($n$-queen problem en inglés), en cual se deben ubicar $n$ damas en un tablero de ajedrez de $n \times n$, de modo tal que no exista ningún par que se ataquen entre sí: es decir, no debe haber nunca dos damas en la misma columna, ni en la misma fila, ni en una misma diagonal del tablero.

Utilizaremos estos tres ejemplos para explicar las dos técnicas fundamentales de búsqueda exhaustiva: fuerza bruta y backtracking.

El método de fuerza bruta consiste en iterar directamente todos los candidatos que hemos predeterminado, y por cada uno de ellos, verificar individualmente su validez. Si resulta válido, podemos imprimir ese candidato, insertarlo en una lista, sumar uno a un contador, o computar su “valor” de acuerdo al criterio que sea y verificar si es mejor que la mejor solución encontrada hasta el momento, según exactamente qué necesitemos hacer en nuestro problema. Si resulta ser inválido, directamente se saltea y se pasa al siguiente candidato.

Serán muy útiles para la implementación de fuerza bruta las técnicas para iterar ciertas estructuras matemáticas habituales:

• Iterar subconjuntos
• Iterar subconjuntos de un tamaño fijo dado
• Iterar permutaciones
• Iterar las rotaciones de una cadena

Poner links a explicaciones de cómo generar los anteriores!

Para este problema, habíamos identificado como candidatos todas las ternas de enteros en $[1,16003] \times [1, 44810] \times [1,222]$. Podemos generarlas con un triple for, y luego simplemente verificar cada una para ver que cumpla ambas ecuaciones, como indica el método de fuerza bruta:

#include <iostream>
 
using namespace std;
 
int main()
{
    for (long long x = 1; x <= 16003; x++)
    for (long long y = 1; y <= 44810; y++)
    for (long long z = 1; z <= 222; z++)
    if (x*x + y*y == z*z && 28*x+10*y+2015*z == 448103)
        cout << x << " " << y << " " << z << endl;
    return 0;
}

Al momento de escribir esto, este código se ejecutó en 150 segundos (2 minutos y medio), recorriendo todas las posibilidades. Imprime la única solución que existe muy rápidamente, porque tuvimos suerte y empezamos a probar por la $x$ y la solución resulta tener un $x$ pequeño. Si hubiéramos empezado con la $z$, como la única solución tiene $z=221$, hubiéramos tenido que recorrer casi todos los candidatos hasta llegar, y el proceso toma 150 segundos. Lo mismo ocurriría si tuviéramos que encontrar todas las soluciones o contarlas, en lugar de dar una cualquiera: con este método, nos veríamos obligados a recorrer todas las posibilidades, para estar seguros de que no nos perdimos ninguna.

Notar entonces que salvo en el caso de que queramos dar únicamente una solución válida cualquiera, el orden en que se generen los candidatos no tiene importancia en el método de fuerza bruta, puesto que igualmente se van a generar y verificar todos individualmente, sin aprovechar ninguna relación entre las distintas ternas.

Explicar!

Explicar!

El método de backtracking se basa en especificar más precisamente cómo se van a explorar exhaustivamente los candidatos: en lugar de quedar a criterio del programador como en fuerza bruta (porque en ese caso igualmente se van a analizar todos uno por uno), el método de backtracking requiere definir un proceso de construcción de solución en etapas. La cantidad de etapas y la elección que hay que hacer en cada etapa pueden variar de problema en problema, de maneras muy complicadas, pero este método siempre requiere que definamos etapas o pasos incrementales que concluyen finalmente en un candidato bien construido.

Desde la situación inicial, en la cual todavía no hemos elegido nada ni realizado ningún paso, a cada candidato posible podemos llegar mediante una serie de elecciones diferentes. Es la secuencia de elecciones que realizamos lo que va a definir exactamente a qué candidato llegamos.

La clave está en que el método de backtracking nos exige verificar que el candidato que estamos construyendo sea válido no solamente al final (como en fuerza bruta) cuando ya está totalmente construido, sino en cada paso de la construcción. Lógicamente, no vamos a poder en general estar 100% seguros acerca de la validez con un candidato que solamente está parcialmente construido. Sin embargo, en la inmensa mayoría de los casos, existen secuencias de elecciones parciales que violan alguna restricción de nuestro problema, de manera que mirando solamente esas primeras elecciones ya podemos estar seguros de que ningún candidato que se obtenga agregando más elecciones podrá resultar válido al final, porque “ya empezamos mal”.

Entonces, lo que pide la búsqueda por backtracking es que en esa rama no exploremos más elecciones, y volvamos hacia atrás (de allí “backtrack” en inglés) a probar otras elecciones del paso anterior que puedan funcionar.

Para este problema, habíamos identificado como candidatos todas las ternas de enteros en $[1,16003] \times [1, 44810] \times [1,222]$. Podemos generarlas con un triple for, como antes, en tres pasos: Primero elegimos $x$, luego elegimos $y$, y luego elegimos $z$. La diferencia será que, luego de cada for (o sea, en cada paso), agregaremos los correspondientes if verificando que las elecciones que tenemos hasta el momento sean viables, y no nos hayan ya “condenado” a fallar.

Luego de la primera elección, tenemos fijado $x$, así que sabemos el primer elemento de nuestra terna, pero no los últimos dos. ¿Tenemos algún chequeo que podamos realizar que nos garantice que es imposible que ese $x$ funcione? La ecuación $x^2 + y^2 = z^2$ no nos ayuda demasiado, ya que no conocemos aún ni $y$ ni $z$. Pero hay algo interesante en la última ecuación: se puede reescribir como $5(2y+403 z) = 448103 - 28x$. Esto nos muestra que $448103 - 28x$ ¡debe ser sí o sí un múltiplo de 5! Podemos verificar esto y si resulta que no lo es, directamente descartar esa elección.

Similarmente, una vez que tenemos elegidos $x$ e $y$, como la última ecuación se puede ver también como $2015 z = 448103 - 28x-10y$, tenemos que el número $448103 - 28x-10y$ tiene que ser múltiplo de $2015$.

Agregando estos dos if al código anterior:

#include <iostream>
 
using namespace std;
 
int main()
{
    for (long long x = 1; x <= 16003; x++)
    if ((448103 - 28 * x) % 5 == 0)
    for (long long y = 1; y <= 44810; y++)
    if ((448103 - 28 * x - 10 * y) % 2015 == 0)
    for (long long z = 1; z <= 222; z++)
    if (x*x + y*y == z*z && 28*x+10*y+2015*z == 448103)
        cout << x << " " << y << " " << z << endl;
    return 0;
}

Al momento de escribir esto, este código funciona exactamente igual que el de fuerza bruta anteriormente dado, pero se ejecutó en solamente 4 décimas de segundo (en lugar de 150 segundos). Es posible mejorarlo aún más, notando que de hecho en el último paso no hace falta recorrer todas las opciones de $z$, pues de la ecuación surge que tiene que ser $z = \frac{448103 - 28x-10y}{2015}$. Esto borra un for, dejando solamente dos!

#include <iostream>
 
using namespace std;
 
int main()
{
    for (long long x = 1; x <= 16003; x++)
    if ((448103 - 28 * x) % 5 == 0)
    for (long long y = 1; y <= 44810; y++)
    if ((448103 - 28 * x - 10 * y) % 2015 == 0)
    {
        long long z = (448103 - 28 * x - 10 * y) / 2015;
        if (x*x + y*y == z*z)
            cout << x << " " << y << " " << z << endl;
    }
    return 0;
}

Sin embargo, prácticamente no hay diferencia con el anterior: este código ejecutó en 3 décimas de segundo. Ya todo el “trabajo duro” lo hizo el método de backtracking, cuando descartamos lo antes posible, en cada paso, las elecciones incorrectas que ya podíamos estar seguros de que no conducen a candidatos que terminen siendo válidos o interesantes.

Notar que a diferencia de lo que pasaba con el método de fuerza bruta, el orden en que se realizan las elecciones puede importar. Esto se ve en el código: no podríamos permutar los fors arbitrariamente, pues los chequeos de los ifs dependen fuertemente del orden en que están. A modo de ejemplo, podríamos dar otro algoritmo de backtracking para este problema que vaya eligiendo las variables en el orden inverso:

#include <iostream>
 
using namespace std;
 
int main()
{
    for (long long z = 1; z <= 222; z++)
    if ((448103 - 2015 * z) % 2 == 0) 
    for (long long y = 1; y <= 44810; y++)
    if ((448103 - 2015 * z - 10 * y) % 28 == 0)
    for (long long x = 1; x <= 16003; x++)
    if (x*x + y*y == z*z && 28*x+10*y+2015*z == 448103)
        cout << x << " " << y << " " << z << endl;
    return 0;
}

En este caso, el algoritmo tardó 4.5 segundos, ¡una gran diferencia! Si agregamos como antes la idea de despejar la ultima variable, en lugar de iterarla:

#include <iostream>
 
using namespace std;
 
int main()
{
    for (long long z = 1; z <= 222; z++)
    if ((448103 - 2015 * z) % 2 == 0) 
    for (long long y = 1; y <= 44810; y++)
    if ((448103 - 2015 * z - 10 * y) % 28 == 0)
    {
        long long x = (448103 - 2015 * z - 10 * y) / 28;
        if (x*x + y*y == z*z)
            cout << x << " " << y << " " << z << endl;
    }
    return 0;
}

Obtenemos un código que se ejecuta en una centésima de segundo, es decir, es la más rápida de todas las versiones que hicimos.

Lo que podemos observar es que el orden del proceso de construcción de la solución es muy importante en el método de backtracking, ya que este orden determina qué podas (los chequeos de los if) podremos hacer, y estas determinarán a su vez cuántos candidatos nos ahorraremos de generar explícitamente.

Explicar!

Explicar!

Tiene el esquema “for for for for if if if if” (aunque es habitual cambiar los for por recursión en la implementación, cuando no está prefijado de antemano cuántos for se necesitarán).

Ventaja: Es más fácil de pensar y programar que un backtracking.

Desventaja: Es mucho menos eficiente que backtracking.

Tiene el esquema “for if for if for if for if” (aunque es habitual cambiar los for por recursión en la implementación, cuando no está prefijado de antemano cuántos for se necesitarán).

Ventaja: Es mucho más eficiente que fuerza bruta. Un buen backtracking en la mayoría de los casos disminuye mucho la complejidad asintótica del algoritmo resultante comparado a un algoritmo similar de fuerza bruta; es decir, reduce el tiempo en más que un factor constante (habitualmente elimina por completo el costo del chequeo de cada solución, ya que al repartirse el chequeo entre todas las etapas de construcción, queda absorbido en la misma complejidad de generar los candidatos).

Desventaja: Es claramente más difícil de programar que fuerza bruta. Adicionalmente al planteo de candidatos que hay que hacer para fuerza bruta, es necesario determinar también un proceso de construcción de solución en etapas: elegir el orden y las etapas que se utilizarán es algo que puede realizarse de muchas maneras posibles, y no siempre es fácil saber cuál es la más eficiente a priori sin estudiar cada problema en particular y pensar las podas viables. A veces puede calcularse y predecirse de antemano la reducción de complejidad por las podas realizadas, pero muchas veces es necesario experimentar para ver los resultados.

Tener link a Branch and Bound en la wiki!

• https://es.wikipedia.org/wiki/Ramificaci%C3%B3n_y_poda
• https://en.wikipedia.org/wiki/Branch_and_bound