En informática , la búsqueda de fuerza bruta o búsqueda exhaustiva , también conocida como generar y probar , es una técnica de resolución de problemas muy general y un paradigma algorítmico que consiste en comprobar sistemáticamente todos los candidatos posibles para comprobar si cada uno satisface o no 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 de 1 a n y comprobaría si cada uno de ellos divide a n sin dejar resto. Un enfoque de fuerza bruta para el rompecabezas de las ocho reinas examinaría todas las posibles disposiciones de las 8 piezas en el tablero de ajedrez de 64 casillas y, para cada disposición, comprobaría si cada pieza (reina) puede atacar a cualquier otra. [1]
Si bien la búsqueda por fuerza bruta es sencilla 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 (§Explosión combinatoria). [2] Por lo tanto, la búsqueda por fuerza bruta se utiliza normalmente cuando el tamaño del problema es limitado o cuando existen heurísticas específicas del problema que se pueden utilizar para reducir el conjunto de soluciones candidatas a un tamaño manejable. El método también se utiliza cuando la simplicidad de la implementación es más importante que la velocidad de procesamiento.
Este es el caso, por ejemplo, en aplicaciones críticas donde cualquier error en el algoritmo tendría consecuencias muy graves o cuando se utiliza una computadora para demostrar un teorema matemático . La búsqueda de fuerza bruta también es útil como método de referencia cuando se evalúan otros algoritmos o metaheurísticas . De hecho, la búsqueda de fuerza bruta puede considerarse 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 de computadora 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 esta última, secuencialmente, se llama búsqueda lineal .
Para candidato a P después del actual c .
El siguiente procedimiento también debe indicar cuándo 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 sea distinto de cualquier candidato real. Del mismo modo, el primer procedimiento debe devolver Λ si no hay ningún candidato para la instancia P . El método de fuerza bruta se expresa entonces mediante el algoritmo
c ← primero ( P ) mientras c ≠ Λ hacer si es válido ( P , c ) entonces salida ( P , c ) c ← siguiente ( P , c ) fin mientras
Por ejemplo, cuando se buscan los divisores de un entero n , los datos de instancia P son el número n . La llamada first ( n ) debe devolver el entero 1 si n ≥ 1, o Λ en caso contrario; la llamada next ( n , c ) debe devolver c + 1 si c < n , y Λ en caso contrario; y valid ( n , c ) debe devolver true 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 innecesarias). El algoritmo de búsqueda de fuerza bruta anterior llamará a la 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 dada de tiempo de CPU .
La principal desventaja del método de fuerza bruta es que, para muchos problemas del mundo real, el número de candidatos naturales es prohibitivamente grande. Por ejemplo, si buscamos los divisores de un número como se describió anteriormente, el número de candidatos probados será el número dado n . Entonces, si n tiene dieciséis dígitos decimales, digamos, la búsqueda requerirá ejecutar al menos 10 15 instrucciones de computadora, lo que tomará varios días en una PC típica . Si n es un número natural aleatorio de 64 bits , que tiene alrededor de 19 dígitos decimales en promedio, la búsqueda tomará alrededor de 10 años. Este crecimiento pronunciado 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 un reordenamiento particular de 10 letras, entonces tenemos 10! = 3,628,800 candidatos para considerar, que una PC típica puede generar y probar en menos de un segundo. Sin embargo, si se añade una letra más (lo que supone un aumento de tan solo el 10 % del tamaño de los datos), el número de candidatos se multiplicará por 11, es decir, un aumento del 1000 %. Para 20 letras, el número de candidatos es 20, lo que equivale aproximadamente a 2,4 × 10 18 o 2,4 trillones ; y la búsqueda tardará unos 10 años. Este fenómeno indeseado 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 a un límite de resolubilidad es la resolución de ajedrez . El ajedrez no es un juego resuelto . En 2005, se resolvieron todos los finales de ajedrez con seis piezas o menos, mostrando el resultado de cada posición si se jugaba perfectamente. Se necesitaron diez años más para completar la tabla base con una pieza de ajedrez más añadida, completando así una tabla base de 7 piezas. Añadir una pieza más a un final de ajedrez (haciendo así una tabla base de 8 piezas) se considera intratable debido a la complejidad combinatoria añadida. [3] [4]
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 de modo que ninguna reina ataque a ninguna otra. Dado que cada reina se puede colocar en cualquiera de las 64 casillas, en principio hay 64 8 = 281.474.976.710.656 posibilidades a considerar. Sin embargo, como todas las reinas son iguales y no se pueden colocar dos reinas en la misma casilla, las candidatas son todas formas posibles de elegir de un conjunto de 8 casillas del conjunto de las 64 casillas; lo que significa que 64 eligen 8 = 64!/(56!*8!) = 4.426.165.368 soluciones candidatas, aproximadamente 1/60.000 de la estimación anterior. Además, ninguna disposición 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 esas disposiciones.
Como muestra este ejemplo, un poco de análisis a menudo conducirá a reducciones drásticas en el número 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 producir 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 no vá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 de fuerza bruta ingenua generaría todos los números enteros en el rango, probando cada uno de ellos para determinar su divisibilidad. Sin embargo, ese problema se puede resolver de manera mucho más eficiente comenzando con 417 y sumando 417 repetidamente hasta que el número exceda 1.000.000, lo que requiere solo 2398 (= 1.000.000 ÷ 417) pasos y ninguna prueba.
En aplicaciones que requieren una sola 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 los candidatos más prometedores. Por ejemplo, cuando se busca 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 los intentos fallidos 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 siguiente es igual al anterior con una probabilidad del 90%. Si los candidatos se enumeran en orden creciente, de 1 a 1000, el número t de candidatos examinados antes del éxito será de alrededor de 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 mayor que 2. De manera más general, el espacio de búsqueda debe enumerarse de tal manera que el próximo candidato tenga más probabilidades de ser válido, dado que los ensayos anteriores no lo fueron . Por lo tanto, si es probable que las soluciones válidas estén "agrupadas" en algún sentido, entonces cada nuevo candidato debe estar lo más alejado posible de los anteriores, en ese mismo sentido. Lo inverso se cumple, por supuesto, si es probable que las soluciones estén distribuidas de manera más uniforme de lo esperado por casualidad.
Existen muchos otros métodos de búsqueda, o metaheurísticas, que están diseñados para aprovechar varios tipos de conocimiento parcial que uno puede tener sobre la solución. Las heurísticas también se pueden utilizar para hacer un corte temprano 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 lenguajes, técnicas como el análisis de gráficos pueden explotar las restricciones en el problema para reducir un problema de complejidad exponencial a un problema de complejidad polinómica. En muchos casos, como en los problemas de satisfacción de restricciones , se puede reducir drásticamente el espacio de búsqueda por medio de la propagación de restricciones , que se implementa de manera eficiente en los lenguajes de programación con 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 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, podándose el árbol en una cierta cantidad de movimientos y aproximándose el resto del árbol mediante una función de evaluación estática .
En criptografía , un ataque de fuerza bruta implica verificar sistemáticamente todas las claves posibles hasta encontrar la clave correcta. [5] En teoría, esta estrategia puede usarse contra cualquier dato cifrado [6] (excepto un bloc de un solo uso ) por un atacante que no pueda aprovechar ninguna debilidad en un sistema de cifrado 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, ya que las claves más largas son exponencialmente más difíciles de descifrar que las más cortas. Los ataques de fuerza bruta pueden volverse menos efectivos si se ofuscan los datos que se van a codificar, lo que hace que sea más difícil para un atacante reconocer que ha descifrado el código. Una de las medidas de la solidez de un sistema de cifrado es el tiempo que, en teoría, le llevaría a un atacante montar un ataque de fuerza bruta con éxito contra él.