Búsqueda de fuerza bruta

Búsqueda de fuerza bruta

Búsqueda de fuerza bruta

Para otros usos de este término, véase Búsqueda.

En informática, la búsqueda por fuerza bruta, búsqueda combinatoria, búsqueda exhaustiva o simplemente fuerza bruta, es una técnica trivial pero a menudo usada, que consiste en enumerar sistemáticamente todos los posibles candidatos para la solución de un problema, con el fin de chequear si dicho candidato satisface la solución al mismo.

Por ejemplo, un algoritmo de fuerza bruta para encontrar el divisor de un número natural n consistiría en enumerar todos los enteros desde 1 hasta n, chequeando si cada uno de ellos divide n sin generar resto. Otro ejemplo de búsqueda por fuerza bruta, en este caso para solucionar el problema de las ocho reinas (posicionar ocho reinas en el tablero de ajedrez de forma que ninguna de ellas ataque al resto), consistiría en examinar todas las combinaciones de posición para las 8 reinas (en total 64! /56! = 178.462.987.637.760 posiciones diferentes), comprobando en cada una de ellas si las reinas se atacan mutuamente.

La búsqueda por fuerza bruta es sencilla de implementar y, siempre que exista, encuentra una solución. Sin embargo, su coste de ejecución es proporcional al número de soluciones candidatas, el cual es exponencialmente proporcional al tamaño del problema. Por el contrario, la búsqueda por fuerza bruta se usa habitualmente cuando el número de soluciones candidatas no es elevado, o bien cuando éste puede reducirse previamente usando algún otro método heurístico.

Es un método utilizado también cuando es más importante una implementación sencilla que una mayor rapidez. Este puede ser el caso en aplicaciones críticas donde cualquier error en el algoritmo puede acarrear serias consecuencias, o también en aplicaciones destinadas a . Bor rute-force search is also useful as "baseline" method when benchmarking other algorithms or metaheuristics. Indeed, brute-force search can be viewed as the simplest metaheuristic.

La búsqueda por fuerza bruta no se debe confundir con backtracking, método que descarta un gran número de conjuntos de soluciones, sin enumerar explícitamente cada una de las mismas.

Contenido

Implementación de la búsqueda por fuerza bruta

Algoritmo básico

Para poder utilizar la búsqueda por fuerza bruta a un tipo especifico de problema, se deben implementar las funciones primero, siguiente, valido, y mostrar. Todas recogerán el parámetro P indicando una instancia en particular del problema:

  1. primero (P): genera la primera solución cadidata para P.
  2. siguiente (P, c): genera la siguiente solución candidata para P después de una solución candidata c.
  3. valido (P, c): chequea si una solución candidata c es una solución correcta de P.
  4. mostrar (P, c): informa que la solución c es una solución correcta de P.

La función siguiente debe indicar de alguna forma cuándo no existen más soluciones candidatas para el problema P después de la última. Una forma de de realizar esto consiste en devolver un valor "nulo". De esta misma forma, la función primero devolverá un valor "nulo" cuando no exista ninguna solución candidata al problema P.

Usando tales funciones, la búsqueda por fuera bruta se expresa mediante el siguiente algoritmo:

c \gets primero(P)
mientras c != null
  si valido(P,c) entonces mostrat(P, c)
  c \gets siguiente(p,c)

Por ejemplo, para buscar los divisores de un entero n, la instancia del problema P es el propio número n. la llamada primero (n) devolverá 1 siempre y cuando n \geq 1, y "nulo" en otro caso; la función siguiente (n,c) debe devolver c + 1 si c < n, y "nulo" caso contrario; valido (n,c) devolverá verdadero si y solo si c es un divisor de n.

Variaciones comunes en el algoritmo

El algoritmo descrito anteriormente llama a la función mostrar para cada solución al problema. Éste puede ser fácilmente modificado de forma que termine una vez encuentre la primera solución, o bien después de encontrar un determinado número de soluciones, después de probar con un número especifico de soluciones candidatas, o después de haber consumido una cantidad fija de tiempo de CPU.

Explosión combinacional

La principal desventaja del método de fuerza bruta es que, para la mayoría de problemas reales, el número de soluciones candidatas es prohibitivamente elevado.

Por ejemplo, para buscar los divisores de un número n tal y como se describe anteriormente, el número de soluciones candidatas a probar será de n. Por tanto, si n consta de, digamos, 16 dígitos, la búsqueda requerirá de al menos 1015 comparaciones computacionales, tarea que puede tardar varios días en un ordenador personal tipo. Si n es un bit de 64 dígitos, que aproximadamente puede tener hasta 19 dígitos decimales, la búsqueda puede tardar del orden de 10 años.

Este crecimiento exponencial en el número de candidatos, cuando crece el tamaño del problema ocurre en todo tipo de problemas. Poe ejemplo, si buscamos una combinación particular de 10 elementos entonces tendremos que considerar 10! = 3,628,800 candidatos diferentes, lo cual en un PC habitual puede ser generado y probado en menos de un segundo. Sin embargo, añadir un único elemento más — lo cual supone solo un 10% más en el tamaño del problema — multiplicará el número de candidatos 11 veces — lo que supone un 1000% de incremento. Para 20 elementos el número de candidatos diferentes es 20!, es decir, aproximadamente 2.4×1018 o 2.4 millones de millones de millones; la búsqueda podría tardar unos 10.000 años. A este fenómeno no deseado se le denomina explosión combinacional.

Véase también

Obtenido de "B%C3%BAsqueda de fuerza bruta"

Wikimedia foundation. 2010.

Игры ⚽ Нужна курсовая?

Mira otros diccionarios:

  • Fuerza bruta — puede referirse a: En informática Ataque de fuerza bruta. Búsqueda de fuerza bruta La compañía teatral Argentina Fuerzabruta. La película Fuerza bruta, dirigida por Jules Dassin en 1947. Esta …   Wikipedia Español

  • Ataque de fuerza bruta — Saltar a navegación, búsqueda Para otros usos de este término, véase Ataque. La DES Cracking Machine construida por la EFF a un costo de USD 250.000 contiene más de 1800 chips especialmente diseñados y puede romper por fuerza bruta una clave DES… …   Wikipedia Español

  • Ataque de fuerza bruta — En criptografía, se denomina ataque de fuerza bruta a la forma de recuperar una clave probando todas las combinaciones posibles de caracteres hasta encontrar aquella que permite el acceso. También se define al procedimiento en el que a partir del …   Enciclopedia Universal

  • Búsqueda — Saltar a navegación, búsqueda Búsqueda puede hacer referencia a: Busca, acción de buscar. Motor de búsqueda, sistema informático que indexa archivos almacenados en servidores web gracias a su «spider» (o Web crawler). Búsqueda binaria o Algoritmo …   Wikipedia Español

  • Vuelo 571 de la Fuerza Aérea Uruguaya — Foto del lugar del desastre, donde se divisan algunos supervivientes Fecha 13 de octubre de 1972 23 de diciembre de 1972 …   Wikipedia Español

  • Deportes de fuerza — Saltar a navegación, búsqueda Deportes de fuerza son deportes en los cuales los participantes deben demostrar su fuerza de diferentes formas. En algunos de estos deportes solo deben demostrar su fuerza bruta (como el Levantamiento de potencia), y …   Wikipedia Español

  • Arimaa — Saltar a navegación, búsqueda Arimaa Un elefante de Arimaa Autor: Omar Syed Jugadores: 2 Preparación: < 1 minuto Duración: 15 minutos 2 horas Complejidad …   Wikipedia Español

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Teoría de Ramsey — Según la teoría de Ramsey, del total de estrellas del cielo nocturno, siempre podemos seleccionar un subconjunto de ellas para dibujar diferentes objetos como: un triángulo, un cuadrilátero, un paraguas o un pulpo. La teoría de Ramsey, llamada… …   Wikipedia Español

  • Un nuevo tipo de ciencia — Una nueva clase de ciencia (en inglés, A New Kind of Science) es un libro de Stephen Wolfram, publicado en 2002. Contiene un estudio empírico y sistemático de los sistemas computacionales tales como los autómatas celulares. Wolfram denomina… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”