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 enumerar sistemáticamente a todos los posibles candidatos para la solución y verificar si cada candidato satisface la declaración del problema. .
Un algoritmo de fuerza bruta para encontrar los divisores de un número natural n enumeraría todos los enteros de 1 a 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, su costo es proporcional 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 ). [1] Por lo tanto, la búsqueda de fuerza bruta se usa típicamente 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 serias; 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 enumerarlos 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 de fuerza bruta [ editar ]
Algoritmo básico [ editar ]
Para aplicar la búsqueda de fuerza bruta a una clase específica de problemas, uno debe implementar cuatro procedimientos , primero , siguiente , válido y de salida . Estos procedimientos deben tomar como parámetro los datos P para la instancia particular del problema que se va a resolver, y deben hacer lo siguiente:
- primera ( P ): generar una primera solución candidato para P .
- next ( P , c ): genera el próximo candidato para P después del actual c .
- válido ( P , C ): comprobar si candidato c es una solución para P .
- salida ( P , c ): use 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 del 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 se expresa luego por el algoritmo
Por ejemplo, al buscar los divisores de un número entero n , los datos de instancia P son el número n . La llamada primero ( n ) debe devolver el entero 1 si n ≥ 1, o Λ de lo contrario; la siguiente llamada ( n , c ) debería devolver c + 1 si c < n , y Λ de lo contrario; y válido ( n , c ) debería devolver verdadero si y solo si c es un divisor de n . (De hecho, si elegimos Λ para ser n + 1, las pruebasn ≥ 1 y c < n son innecesarios.) El algoritmo de búsqueda de fuerza bruta anteriormente llamará de salida para cada candidato que es una solución a 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 pasar una cantidad determinada de tiempo de CPU .
Explosión combinatoria [ editar ]
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 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 aleatorio de 64 bitsnúmero natural, que tiene aproximadamente 19 dígitos decimales en promedio, la búsqueda llevará unos 10 años. Este fuerte crecimiento en el número de candidatos, a medida que aumenta el tamaño de los datos, se produce 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á 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 quintillones ; y la búsqueda llevará unos 10 años. Este fenómeno no deseado comúnmente se llama explosión combinatoria, o la maldición de la dimensionalidad .
Un ejemplo de un caso en el que la complejidad combinatoria conduce al límite de solvencia es la resolución del ajedrez . El ajedrez no es un juego resuelto . En 2005 se resolvieron todos los finales del juego 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 tabla con una pieza de ajedrez más agregada, completando así una base de tabla de 7 piezas. Agregar una pieza más a un final de ajedrez (haciendo una base de tabla de 8 piezas) se considera intratable debido a la complejidad combinatoria añadida. [2] [3]
Acelerando las búsquedas de fuerza bruta [ editar ]
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 de 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 ninguna 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, dado que las reinas son todas iguales y que no se pueden colocar dos reinas en la misma casilla, las candidatas son todas formas posibles de elegirde un conjunto de 8 cuadrados del conjunto, todos 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 la misma columna puede ser una solución. Por lo tanto, podemos restringir aún más el conjunto de candidatos a esos acuerdos.
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 insoluble 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 enumera directamente todas las soluciones deseadas (o encuentra una solución, según corresponda), sin perder tiempo con las pruebas y la generación de candidatos no vá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, probando la divisibilidad de cada uno de ellos. Sin embargo, ese problema puede resolverse 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 sin pruebas.
Reordenando el espacio de búsqueda [ editar ]
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 evalúen los candidatos. Como regla general, primero se deben evaluar 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 los ensayos fallidos anteriores. Por ejemplo, considere el problema de encontrar un 1bits en una cadena dada 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 es igualmente probable que sea 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 tserá solo un poco más de 2. Más generalmente, el espacio de búsqueda debe enumerarse de tal manera que el próximo candidato sea más probable que sea 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 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 de fuerza bruta [ editar ]
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. 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 de lenguaje, las técnicas como el análisis de gráficos pueden explotar las restricciones en el problema para reducir un problema de complejidad exponencial en 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 restricción. 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 informático , 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 podado en un cierto número de movimientos, y el resto del árbol se aproxima por una función de evaluación estática .
En criptografía [ editar ]
En criptografía , un ataque de fuerza bruta implica verificar sistemáticamente todas las claves posibles hasta encontrar la clave correcta. [4] En teoría, esta estrategia puede ser utilizada contra cualquier dato encriptado [5] (excepto una libreta de un solo uso ) por un atacante que no puede aprovechar ninguna debilidad en un sistema de encriptación que de otra manera 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 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 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.
D * (pronunciado "D star") es cualquiera de los siguientes tres algoritmos de búsqueda incremental relacionados :
- El D * original, [1] de Anthony Stentz, es un algoritmo de búsqueda incremental informado.
- Focussed D * [2] es un algoritmo de búsqueda heurística incremental informado de Anthony Stentz que combina ideas de A * [3] y el D * original. D * enfocado resultó de un mayor desarrollo del D * original.
- D * Lite [4] es un algoritmo de búsqueda heurística incremental de Sven Koenig y Maxim Likhachev que se basa en LPA * , [5] un algoritmo de búsqueda heurística incremental que combina ideas de A * y Dynamic SWSF-FP. [6]
Los tres algoritmos de búsqueda resuelven los mismos problemas de planificación de ruta basados en suposiciones, incluida la planificación con la suposición de espacio libre, [7]donde un robot tiene que navegar a las coordenadas de la meta dada en un terreno desconocido. Hace suposiciones sobre la parte desconocida del terreno (por ejemplo: que no contiene obstáculos) y encuentra una ruta más corta desde sus coordenadas actuales hasta las coordenadas de la meta bajo estas suposiciones. El robot luego sigue el camino. Cuando observa nueva información del mapa (como obstáculos previamente desconocidos), agrega la información a su mapa y, si es necesario, reemplaza una nueva ruta más corta desde sus coordenadas actuales a las coordenadas de la meta dada. Repite el proceso hasta que alcanza las coordenadas del objetivo o determina que no se pueden alcanzar las coordenadas del objetivo. Al atravesar terreno desconocido, se pueden descubrir nuevos obstáculos con frecuencia, por lo que esta replanificación debe ser rápida. Algoritmos de búsqueda incrementales (heurísticos)acelerar las búsquedas de secuencias de problemas de búsqueda similares utilizando la experiencia con los problemas anteriores para acelerar la búsqueda del actual. Suponiendo que las coordenadas del objetivo no cambien, los tres algoritmos de búsqueda son más eficientes que las búsquedas repetidas de A *.
D * y sus variantes se han utilizado ampliamente para robots móviles y navegación autónoma de vehículos . Los sistemas actuales generalmente se basan en D * Lite en lugar del D * original o D * enfocado. De hecho, incluso el laboratorio de Stentz usa D * Lite en lugar de D * en algunas implementaciones. [8] Tales sistemas de navegación incluyen un sistema prototipo probado en los rovers Opportunity and Spirit de Marte y el sistema de navegación de la entrada ganadora en el DARPA Urban Challenge , ambos desarrollados en la Universidad Carnegie Mellon .
El D * original fue introducido por Anthony Stentz en 1994. El nombre D * proviene del término "Dinámico A *", porque el algoritmo se comporta como A *, excepto que los costos del arco pueden cambiar a medida que se ejecuta el algoritmo.
Operación [ editar ]
El funcionamiento básico de D * se describe a continuación.
Al igual que el algoritmo de Dijkstra y A *, D * mantiene una lista de nodos para evaluar, conocida como la "Lista ABIERTA". Los nodos están marcados como teniendo uno de varios estados:
- NUEVO, lo que significa que nunca se ha colocado en la lista ABIERTA
- ABIERTO, lo que significa que está actualmente en la lista ABIERTA
- CERRADO, lo que significa que ya no está en la lista ABIERTA
- AUMENTAR, lo que indica que su costo es más alto que la última vez que estuvo en la lista ABIERTA
- INFERIOR, lo que indica que su costo es menor que la última vez que estuvo en la lista ABIERTA
Expansión [ editar ]
El algoritmo funciona seleccionando iterativamente un nodo de la lista ABIERTA y evaluándolo. Luego propaga los cambios del nodo a todos los nodos vecinos y los coloca en la lista ABIERTA. Este proceso de propagación se denomina "expansión". A diferencia del canónico A *, que sigue el camino de principio a fin, D * comienza buscando hacia atrás desde el nodo objetivo. Cada nodo expandido tiene un indicador de retroceso que se refiere al siguiente nodo que conduce al objetivo, y cada nodo conoce el costo exacto para el objetivo. Cuando el nodo de inicio es el siguiente nodo que se expandirá, el algoritmo estará listo y la ruta hacia el objetivo se puede encontrar simplemente siguiendo los puntos de referencia.
Manejo de obstáculos [ editar ]
Cuando se detecta una obstrucción a lo largo de la ruta prevista, todos los puntos afectados se vuelven a colocar en la lista ABIERTA, esta vez marcada como SUBIDA. Sin embargo, antes de que un nodo AUMENTADO aumente de costo, el algoritmo verifica a sus vecinos y examina si puede reducir el costo del nodo. De lo contrario, el estado RAISE se propaga a todos los descendientes de los nodos, es decir, nodos que tienen backpointers. Luego se evalúan estos nodos y se pasa el estado de ELEVACIÓN, formando una onda. Cuando se puede reducir un nodo LEVANTADO, su puntero de retroceso se actualiza y pasa el estado INFERIOR a sus vecinos. Estas ondas de los estados de SUBIR y BAJAR son el corazón de D *.
En este punto, las olas impiden que toda una serie de otros puntos sean "tocados". Por lo tanto, el algoritmo solo ha funcionado en los puntos afectados por el cambio de costo.
Se produce otro punto muerto [ editar ]
Esta vez, el punto muerto no puede pasarse por alto tan elegantemente. Ninguno de los puntos puede encontrar una nueva ruta a través de un vecino al destino. Por lo tanto, continúan propagando su aumento de costos. Solo se pueden encontrar puntos fuera del canal, que pueden conducir al destino a través de una ruta viable. Así es como se desarrollan dos ondas inferiores, que se expanden como puntos marcados de forma inalcanzable con nueva información de ruta.
No hay comentarios:
Publicar un comentario