En informática , la búsqueda por fuerza bruta o búsqueda exhaustiva , también conocida como generar y probar , es una técnica de resolución de problemas y un paradigma algorítmico muy general que consiste en comprobar sistemáticamente si todos los candidatos posibles satisfacen o no el planteamiento 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 a n sin resto. Un enfoque de fuerza bruta para el rompecabezas de las ocho reinas examinaría todos los arreglos posibles de 8 piezas en el tablero de ajedrez de 64 casillas y, para cada arreglo, verificaría si cada pieza (reina) puede atacar a cualquier otra. [1]
Si bien una búsqueda de fuerza bruta es fácil de implementar y siempre encontrará una solución si existe, los costos de implementación son proporcionales al número 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 de fuerza bruta se utiliza normalmente cuando el tamaño del problema es limitado o cuando existen heurísticas específicas del problema que pueden usarse para reducir el conjunto de soluciones candidatas a un tamaño manejable. El método también se utiliza cuando la simplicidad de 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 al comparar otros algoritmos o metaheurísticas . De hecho, la búsqueda por 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 para el problema de las ocho reinas anterior). El método de fuerza bruta para encontrar un elemento en una tabla (es decir, comprobar todas las entradas de esta última de forma secuencial) se llama búsqueda lineal .
En orden candidato para 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 debería 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 ) luego generar ( P , c ) c ← siguiente ( P , c ) terminar mientras
Por ejemplo, cuando se buscan los divisores de un número entero n , los datos de instancia P son el número n . La llamada first ( n ) debe devolver el número entero 1 si n ≥ 1, o Λ en caso contrario; la llamada next ( n , c ) debería devolver c + 1 si c < n y Λ en caso contrario; y valid ( 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 innecesarias). El algoritmo de búsqueda de fuerza bruta anterior solicitará resultados 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 determinada cantidad 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 describe anteriormente, el número de candidatos evaluados 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 unos 19 dígitos decimales en promedio, 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 buscamos una reordenació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, lo que representa solo un aumento del 10 % en el tamaño de los datos, multiplicará el número de candidatos por 11, 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 quintillones ; y la búsqueda durará 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 a un límite de solubilidad 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 jugaba 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 (creando así una base de mesa de 8 piezas) se considera intratable debido a la complejidad combinatoria agregada. [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 para que ninguna reina ataque a otra. Dado que cada reina puede colocarse en cualquiera de las 64 casillas, en principio hay 64 8 = 281.474.976.710.656 posibilidades a considerar. Sin embargo, debido a que todas las reinas son iguales y no se pueden colocar dos reinas en el mismo cuadrado, todas las candidatas son formas posibles de elegir un conjunto de 8 cuadrados del conjunto de 64 cuadrados; 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, 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 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 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 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 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 sumando repetidamente 417 hasta que el número supere 1.000.000, lo que requiere sólo 2.398 (= 1.000.000 ÷ 417) pasos y ninguna prueba.
En aplicaciones que requieren sólo 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, primero se deben probar 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/ taza . 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 1 bit en una cadena P determinada de 1000 bits . En este caso, las soluciones candidatas son los índices 1 a 1000, y una candidata c es válida si P [ c ] = 1 . Ahora, supongamos que el primer bit de P tiene la misma probabilidad de ser 0 o 1 , pero cada bit posterior es igual al anterior con un 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 aproximadamente 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á sólo un poco más que 2.Más En 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 algún sentido, entonces cada nuevo candidato debería estar lo más lejos posible de los anteriores, en el mismo sentido. Por supuesto, ocurre lo contrario si es probable que las soluciones se distribuyan de manera más uniforme de lo esperado por casualidad.
Hay muchos otros métodos de búsqueda, o metaheurísticas, que están diseñados para aprovechar diversos tipos de conocimiento parcial que uno pueda tener sobre la solución. La heurística también se puede utilizar para realizar 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 lenguaje, técnicas como el análisis de gráficos pueden explotar las restricciones del 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 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 por 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, podándose el árbol 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 , un ataque de fuerza bruta implica comprobar 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 cualquier 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, siendo las 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 al ofuscar los datos que se van a codificar, algo que hace que sea más difícil para un atacante reconocer cuándo ha descifrado el código. Una de las medidas de la solidez de un sistema de cifrado es cuánto tiempo, en teoría, le tomaría a un atacante montar un ataque de fuerza bruta exitoso contra él.