Búsqueda por fuerza bruta

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 todos los candidatos posibles para determinar si cada uno de ellos satisface o no el enunciado del problema.

Un algoritmo de fuerza bruta que encuentra los divisores de un número natural n enumeraría todos los enteros del 1 al 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 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 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 por fuerza bruta se suele utilizar cuando el tamaño del problema es limitado o cuando existen heurísticas específicas que permiten reducir el conjunto de soluciones candidatas a un tamaño manejable. Este 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 usa una computadora para demostrar un teorema matemático . La búsqueda por fuerza bruta también es útil como método de referencia al evaluar otros algoritmos o metaheurísticas . De hecho, la búsqueda por fuerza bruta puede considerarse la metaheurística más simple. La búsqueda por 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 mencionado anteriormente). 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 .  

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 . Así, si n tiene dieciséis dígitos decimales, digamos, la búsqueda requerirá ejecutar al menos 10¹⁵ ^{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 rápido 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 reordenación 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, añadir una letra más —lo que supone un aumento de tan solo el 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!, que es aproximadamente 2,4 × 10¹⁸ ^o 2,4 quintillones ; y la búsqueda tardará unos 10 años. Este fenómeno indeseado se conoce comúnmente como explosión combinatoria o maldición de la dimensionalidad .  

Un ejemplo de un caso donde la complejidad combinatoria conduce a un límite de resolubilidad es en la resolución del 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 jugara a la perfección. Se necesitaron diez años más para completar la base de datos con una pieza de ajedrez adicional, completando así una base de datos de 7 piezas. Agregar una pieza más a un final de ajedrez (creando así una base de datos de 8 piezas) se considera intratable debido a la complejidad combinatoria adicional. ^{[ 3 ] [ 4 ] [ 5 ]}

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 consiste en colocar ocho reinas en un tablero de ajedrez estándar de manera que ninguna reina ataque a otra. Dado que cada reina puede colocarse en cualquiera de las 64 casillas, en principio hay 64 × ⁸ = 281.474.976.710.656 posibilidades a considerar. Sin embargo, debido a que todas las reinas son iguales y que no se pueden colocar dos reinas en la misma casilla, las candidatas son todas las formas posibles de elegir un conjunto de 8 casillas del conjunto de las 64 casillas; lo que significa 64 sobre 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 conlleva una reducción drástica 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 inválidos. Por ejemplo, para el problema "encontrar todos los enteros entre 1 y 1.000.000 que sean divisibles por 417", una solución ingenua de fuerza bruta generaría todos los enteros en el rango, comprobando la divisibilidad de cada uno. Sin embargo, ese problema se puede resolver de forma mucho más eficiente comenzando con 417 y sumándole repetidamente 417 hasta que el número supere 1.000.000 , lo que requiere solo 2398 pasos (= 1.000.000 ÷ 417) y ninguna prueba. 

En aplicaciones que requieren solo una solución, en lugar de todas las soluciones, el tiempo de ejecución esperado de una búsqueda por fuerza bruta a menudo dependerá del orden en que se prueben los candidatos. Como regla general, se deben probar primero los candidatos más prometedores. Por ejemplo, al buscar un divisor propio de un número aleatorio n , es mejor enumerar los divisores candidatos en orden ascendente, 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, consideremos el problema de encontrar un bit 1 en una cadena P de 1000 bits dada . En este caso, las soluciones candidatas son los índices del 1 al 1000, y un candidato c es válido 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 una probabilidad del 90%. Si los candidatos se enumeran en orden ascendente, del 1 al 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á solo un poco más de 2. En términos más generales, el espacio de búsqueda debe enumerarse de tal manera que el siguiente candidato tenga la mayor probabilidad de ser válido, dado que los ensayos anteriores no lo fueron . Así, 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 contrario se aplica, por supuesto, si es probable que las soluciones estén distribuidas de manera más uniforme de lo esperado por azar. 

Existen muchos otros métodos de búsqueda, o metaheurísticas, diseñados para aprovechar diversos tipos de conocimiento parcial sobre la solución. Las heurísticas también pueden utilizarse para descartar partes de la búsqueda en una etapa temprana. Un ejemplo de esto es el principio minimax para la búsqueda en árboles de juego, que elimina muchos subárboles en una fase inicial. En ciertos campos, como el análisis sintáctico de lenguajes, técnicas como el análisis de gráficos pueden explotar las restricciones del problema para reducir un problema de complejidad exponencial a uno 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 lenguajes de programación de restricciones . El espacio de búsqueda para los problemas también puede reducirse 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 de la partida, se calcula un árbol más limitado de posibilidades minimax, podando el árbol en un cierto número de movimientos, y el resto del árbol se aproxima mediante 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 correcta. ^{[ 6 ]} En teoría, esta estrategia puede utilizarse contra cualquier dato cifrado ^{[ 7 ]} (excepto una clave 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; las claves más largas son exponencialmente más difíciles de descifrar que las más cortas. Los ataques de fuerza bruta pueden reducirse ofuscando los datos que se van a codificar, lo que dificulta que un atacante reconozca cuando ha descifrado el código. Una de las medidas de la robustez de un sistema de cifrado es el tiempo que, en teoría, tardaría un atacante en realizar un ataque de fuerza bruta exitoso contra él.

• Un algoritmo de fuerza bruta para resolver puzles de Sudoku.
• Ataque de fuerza bruta
• Notación Big O
• Iteración#Computación