Búsqueda por fuerza bruta - Brute-force search
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 muy general y un paradigma algorítmico que consiste en enumerar sistemáticamente todos los posibles candidatos para la solución y comprobar si cada candidato satisface el planteamiento 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 verificaría si cada uno de ellos divide 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 cuadrados y para cada arreglo, verificaría si cada pieza (reina) puede atacar a cualquier 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 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 ). Por lo tanto, la búsqueda por fuerza bruta se usa generalmente 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 utiliza 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 por 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 por fuerza bruta no debe confundirse con el retroceso , donde grandes conjuntos de soluciones pueden descartarse sin ser enumerados 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, verificar todas las entradas de este último, secuencialmente, se llama búsqueda lineal .
Implementando la búsqueda por fuerza bruta
Algoritmo basico
En orden candidato para P después del actual c .
- válido ( P , C ): comprobación de si el candidato c es una solución para P .
- salida ( P , c ): utilice la solución c de P según corresponda a la aplicación.
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. Asimismo, el primer procedimiento debería regresar Λ si no hay candidatos en absoluto para la instancia P . El método de fuerza bruta es luego expresado por el algoritmo
c ← first(P)
while c ≠ Λ do
if valid(P,c) then
output(P, c)
c ← next(P, c)
end while
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 ) debería 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 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 llamará a la salida para cada candidato que sea una solución para la instancia P dada . 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, 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 evaluados será el número n dado . 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 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, que es 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 !, que es aproximadamente 2,4 × 10 18 o 2,4 trillones ; y la búsqueda tardará unos 10 años. Este fenómeno no deseado se denomina comúnmente explosión combinatoria o la maldición de la dimensionalidad .
Un ejemplo de un caso en el que la complejidad combinatoria conduce a un límite de capacidad de solución es la resolución de ajedrez . El ajedrez no es un juego resuelto . En 2005, se resolvieron todos los finales de las 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 agregada, 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 agregada.
Acelerar las búsquedas por 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 del 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 8 = 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, las candidatas son todas formas posibles de elegir entre un conjunto de 8 cuadrados del conjunto de los 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 drásticas en el número de posibles soluciones y puede convertir un problema insoluble en uno trivial.
En algunos casos, el análisis puede reducir a 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 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 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 repetidamente 417 hasta que el número exceda 1,000,000, lo que requiere solo 2398 (= 1,000,000 ÷ 417) pasos y ninguna prueba.
Reordenando 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, se debe probar primero a 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 ensayos fallidos anteriores. Por ejemplo, considere el problema de encontrar un 1 bit en una cadena P dada de 1000 bits . En este caso, las soluciones candidatas son los índices de 1 a 1000, y una candidata c es válida si P [ c ] = 1 . Ahora, suponga que el primer bit de P tiene la misma probabilidad de ser 0 o 1 , pero cada bit a partir de entonces 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á solo un poco más de 2. en 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 . Entonces, si es probable que las soluciones válidas estén "agrupadas" en algún sentido, entonces cada nuevo candidato debe estar lo más lejos posible de los anteriores, en ese mismo sentido. Lo contrario es válido, por supuesto, si es probable que las soluciones se distribuyan de forma 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ñados para aprovechar varios 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 juego, que elimina muchos subárboles en una etapa temprana de la búsqueda. En ciertos campos, como el análisis sintáctico de idiomas, técnicas como el análisis sintáctico de gráficos pueden aprovechar las limitaciones 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, podando el árbol en un cierto número de movimientos, y el resto del árbol aproximado por una función de evaluación estática .
En criptografía
En criptografía , un ataque de fuerza bruta implica verificar sistemáticamente todas las claves posibles hasta que se encuentre la clave correcta. En teoría, esta estrategia puede ser utilizada contra cualquier dato cifrado (excepto un bloc de notas de un solo uso ) por un atacante que no puede 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, 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 al ofuscar los datos que se van a codificar, algo que hace que sea más difícil para un atacante reconocer cuando ha descifrado el código. Una de las medidas de la fuerza de un sistema de cifrado es cuánto tiempo, teóricamente, le tomaría a un atacante montar un ataque de fuerza bruta exitoso contra él.