Búsqueda de fuerza bruta

En informática, la búsqueda de fuerza bruta o búsqueda exhaustiva, también conocida como generar y probar, es una solución de problemas muy general. técnica y paradigma algorítmico que consiste en enumerar sistemáticamente todos los posibles candidatos a la solución y comprobar si cada candidato satisface el enunciado del problema.

Un algoritmo de fuerza bruta que encuentre los divisores de un número natural n enumeraría todos los números enteros del 1 al n y comprobaría si cada uno de ellos divide n sin resto. Un enfoque de fuerza bruta para el rompecabezas de las ocho reinas examinaría todas las disposiciones posibles de 8 piezas en el tablero de ajedrez de 64 cuadrados y, para cada disposición, comprobaría si cada pieza (reina) puede atacar a alguna otra.

Si bien una búsqueda de fuerza bruta es simple de implementar y siempre encontrará una solución, si existe, los costos de implementación son proporcionales a la cantidad de soluciones candidatas, que en muchos problemas prácticos tiende a crecer muy rápidamente a medida que aumenta el tamaño del problema. aumenta (§Explosión combinatoria). Por lo tanto, la búsqueda de fuerza bruta generalmente se usa cuando el tamaño del problema es limitado o cuando hay heurísticas específicas del problema que se pueden usar para reducir el conjunto de soluciones candidatas a un tamaño manejable. El método también se usa cuando la simplicidad de implementación es más importante que la velocidad.

Este es el caso, por ejemplo, en aplicaciones críticas donde cualquier error en el algoritmo tendría consecuencias muy graves o cuando se usa una computadora para probar un teorema matemático. La búsqueda de fuerza bruta también es útil como método de referencia cuando se comparan otros algoritmos o metaheurísticas. De hecho, la búsqueda de fuerza bruta puede verse como la metaheurística más simple. La búsqueda de fuerza bruta no debe confundirse con el retroceso, donde se pueden descartar grandes conjuntos de soluciones sin enumerarlas explícitamente (como en la solución informática del libro de texto al problema de las ocho reinas anterior). El método de fuerza bruta para encontrar un elemento en una tabla, es decir, verificar todas las entradas de este último, secuencialmente, se denomina búsqueda lineal.

Implementación de la búsqueda por fuerza bruta

Algoritmo básico

En orden candidato a P después del actual c.

1. válido ()P, c): comprobar si candidato c es una solución P.
2. Producto ()P, c): utilizar la solución c de P según corresponda a la solicitud.

El procedimiento siguiente también debe indicar cuando no hay más candidatos para la instancia P, después de la actual c. Una forma conveniente de hacerlo es devolver un 'candidato nulo', algún valor de datos convencional Λ que es distinto de cualquier candidato real. Del mismo modo, el procedimiento first debería devolver Λ si no hay ningún candidato para la instancia P. Luego, el método de fuerza bruta se expresa mediante el algoritmo

c ← primero()P)
mientras c √≥ ≥ do si válido()P,c) entonces Producto()P, c)
 c ← siguiente()P, c)
terminar mientras

Por ejemplo, al buscar los divisores de un número entero n, el dato de instancia P es el número n. La llamada first(n) debe devolver el número entero 1 si n ≥ 1, o Λ en caso contrario; la llamada siguiente(n,c) debería devolver c + 1 si c < n, y Λ en caso contrario; y válido(n,c) debería devolver verdadero si y solo si c es un divisor de n. (De hecho, si elegimos que Λ sea n + 1, las pruebas n ≥ 1 y c < n son innecesarios.) El algoritmo de búsqueda de fuerza bruta anterior llamará a salida para cada candidato que sea una solución para la instancia dada P. El algoritmo se modifica fácilmente para detenerse después de encontrar la primera solución o un número específico de soluciones; o después de probar un número específico de candidatos, o después de gastar una cantidad determinada de tiempo de CPU.

Explosión combinatoria

La principal desventaja del método de fuerza bruta es que, para muchos problemas del mundo real, la cantidad de candidatos naturales es prohibitivamente grande. Por ejemplo, si buscamos los divisores de un número como se describe arriba, el número de candidatos examinados será el número dado n. Entonces, si n tiene dieciséis dígitos decimales, digamos, la búsqueda requerirá ejecutar al menos 10¹⁵ instrucciones de computadora, lo que llevará varios días en una PC típica. Si n es un número natural aleatorio de 64 bits, que tiene una media de unos 19 dígitos decimales, la búsqueda tardará unos 10 años. Este fuerte crecimiento en el número de candidatos, a medida que aumenta el tamaño de los datos, ocurre en todo tipo de problemas. Por ejemplo, si estamos buscando una reorganización particular de 10 letras, ¡entonces tenemos 10! = 3,628,800 candidatos a considerar, que una PC típica puede generar y probar en menos de un segundo. Sin embargo, agregar una letra más, que es solo un aumento del 10 % en el tamaño de los datos, multiplicará la cantidad de candidatos por 11, un aumento del 1000 %. ¡Para 20 letras, el número de candidatos es 20!, que es aproximadamente 2,4 × 10¹⁸ o 2,4 quintillones; y la búsqueda llevará unos 10 años. Este fenómeno no deseado se denomina comúnmente explosión combinatoria o maldición de la dimensionalidad.

Un ejemplo de un caso en el que la complejidad combinatoria conduce al límite de resolución es la resolución de ajedrez. El ajedrez no es un juego resuelto. En 2005 se resolvieron todos los finales de partidas de ajedrez con seis piezas o menos, mostrando el resultado de cada posición si se juega perfectamente. Se necesitaron diez años más para completar la base de la mesa con una pieza de ajedrez más, completando así una base de mesa de 7 piezas. Agregar una pieza más a un final de ajedrez (haciendo así una base de mesa de 8 piezas) se considera intratable debido a la complejidad combinatoria adicional.

Acelerar las búsquedas de fuerza bruta

Una forma de acelerar un algoritmo de fuerza bruta es reducir el espacio de búsqueda, es decir, el conjunto de soluciones candidatas, mediante el uso de heurísticas específicas para la clase de problema. Por ejemplo, en el problema de las ocho reinas, el desafío es colocar ocho reinas en un tablero de ajedrez estándar para que ninguna reina ataque a otra. Dado que cada reina se puede colocar en cualquiera de los 64 cuadrados, en principio hay 64⁸ = 281,474,976,710,656 posibilidades a considerar. Sin embargo, debido a que las reinas son todas iguales y que no se pueden colocar dos reinas en el mismo cuadrado, los candidatos son todas las formas posibles de elegir un conjunto de 8 cuadrados del conjunto de 64 cuadrados; lo que significa que 64 elige 8 = 64!/(56!*8!) = 4 426 165 368 soluciones candidatas, aproximadamente 1/60 000 de la estimación anterior. Además, ningún arreglo con dos reinas en la misma fila o en la misma columna puede ser una solución. Por lo tanto, podemos restringir aún más el conjunto de candidatos a esos arreglos.

Como muestra este ejemplo, un poco de análisis a menudo conducirá a reducciones dramáticas en la cantidad de soluciones candidatas y puede convertir un problema intratable en uno trivial.

En algunos casos, el análisis puede reducir los candidatos al conjunto de todas las soluciones válidas; es decir, puede generar un algoritmo que enumere directamente todas las soluciones deseadas (o encuentre una solución, según corresponda), sin perder tiempo con pruebas y la generación de candidatos inválidos. Por ejemplo, para el problema "encontrar todos los números enteros entre 1 y 1.000.000 que sean divisibles por 417" una solución ingenua de fuerza bruta generaría todos los números enteros en el rango, probando la divisibilidad de cada uno de ellos. Sin embargo, ese problema se puede resolver de manera mucho más eficiente comenzando con 417 y agregando 417 repetidamente hasta que el número exceda 1,000,000, lo que requiere solo 2398 (= 1,000,000 ÷ 417) pasos y ninguna prueba.

Reordenar el espacio de búsqueda

En aplicaciones que requieren solo una solución, en lugar de todas las soluciones, el tiempo de ejecución esperado de una búsqueda de fuerza bruta a menudo dependerá del orden en que se prueben los candidatos. Como regla general, uno debe probar primero a los candidatos más prometedores. Por ejemplo, al buscar un divisor adecuado de un número aleatorio n, es mejor enumerar los divisores candidatos en orden creciente, de 2 a n − 1, que al revés, porque la probabilidad de que n sea divisible por c es 1/c. Además, la probabilidad de que un candidato sea válido a menudo se ve afectada por las pruebas fallidas anteriores. Por ejemplo, considere el problema de encontrar un bit 1 en una cadena dada de 1000 bits P. En este caso, las soluciones candidatas son los índices 1 a 1000, y un candidato c es válido si P[c] = 1. Ahora, suponga que el primer bit de P tiene la misma probabilidad de ser 0 o 1, pero cada bit posterior es igual al anterior con 90% de probabilidad. Si los candidatos se enumeran en orden creciente, de 1 a 1000, el número t de candidatos examinados antes del éxito será de unos 6, en promedio. Por otro lado, si los candidatos se enumeran en el orden 1,11,21,31...991,2,12,22,32 etc., el valor esperado de t será solo un poco más de 2. De manera más general, el espacio de búsqueda debe enumerarse de tal manera que el siguiente candidato tenga más probabilidades de ser válido, dado que las pruebas anteriores no lo fueron. Entonces, si es probable que las soluciones válidas estén "agrupadas" en cierto sentido, entonces cada nuevo candidato debe estar lo más alejado posible de los anteriores, en ese mismo sentido. Lo contrario es válido, por supuesto, si es probable que las soluciones se distribuyan de manera más uniforme de lo esperado por casualidad.

Alternativas a la búsqueda por fuerza bruta

Hay muchos otros métodos de búsqueda, o metaheurísticas, que están diseñadas para aprovechar varios tipos de conocimiento parcial que uno puede tener sobre la solución. La heurística también se puede utilizar para hacer un corte anticipado de partes de la búsqueda. Un ejemplo de esto es el principio minimax para buscar árboles de juegos, que elimina muchos subárboles en una etapa temprana de la búsqueda. En ciertos campos, como el análisis de lenguaje, técnicas como el análisis de gráficos pueden aprovechar las restricciones del problema para reducir un problema de complejidad exponencial a un problema de complejidad polinomial. En muchos casos, como en los problemas de satisfacción de restricciones, se puede reducir drásticamente el espacio de búsqueda mediante la propagación de restricciones, que se implementa de manera eficiente en los lenguajes de programación de restricciones. El espacio de búsqueda de problemas también se puede reducir reemplazando el problema completo con una versión simplificada. Por ejemplo, en el ajedrez por computadora, en lugar de calcular el árbol minimax completo de todos los movimientos posibles para el resto del juego, se calcula un árbol más limitado de posibilidades minimax, con el árbol siendo podado en un cierto número de movimientos, y el resto del árbol siendo aproximado por una función de evaluación estática.

En criptografía

En criptografía, un ataque de fuerza bruta implica comprobar sistemáticamente todas las claves posibles hasta encontrar la clave correcta. En teoría, esta estrategia puede ser utilizada contra cualquier dato encriptado (excepto un bloc de notas de un solo uso) por un atacante que no puede aprovechar ninguna debilidad en un sistema de encriptación que de otro modo facilitaría su tarea.

La longitud de la clave utilizada en el cifrado determina la viabilidad práctica de realizar un ataque de fuerza bruta, con claves más largas exponencialmente más difíciles de descifrar que las más cortas. Los ataques de fuerza bruta pueden volverse menos efectivos ofuscando los datos que se van a codificar, algo que dificulta que un atacante reconozca cuando ha descifrado el código. Una de las medidas de la fuerza de un sistema de encriptación es cuánto tiempo le tomaría teóricamente a un atacante montar un ataque exitoso de fuerza bruta contra él.