ıllı Internet y Tecnologías de la Información (2018)

internet, Hosting, dominios, seo, antivirus, banco de imágenes, páginas web, tiendas online

[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):

ıllı Búsqueda de fuerza bruta wiki: info, historia y vídeos

videos internet

salud  Búsqueda de fuerza bruta 


Busca.wikiEl inconveniente de las 8 reinas puede ser resuelto a la fuerza salvaje, mas no es conveniente debido al gran número de combinaciones posibles.

En informática, la busca a la fuerza salvaje, busca combinatoria, busca pormenorizada o bien sencillamente fuerza salvaje, es una técnica trivial mas de manera frecuente utilizada, consistente en contar de forma sistemática todos y cada uno de los posibles aspirantes para la solución de un inconveniente, con el objetivo de examinar si dicho aspirante satisface la solución al mismo.


Por ejemplo, un algoritmo de fuerza bárbara para localizar el divisor de un número naturaln consistiría en contar todos y cada uno de los enteros desde 1 hasta n, examinando si cada uno de ellos de ellos divide n sin producir resto. Otro ejemplo de busca a la fuerza salvaje, en un caso así para solventar el inconveniente de las 8 reinas (posicionar 8 reinas en el tablero de ajedrez de manera que ninguna de ellas ataque al resto), consistiría en examinar todas y cada una de las combinaciones de situación para las ocho reinas (en conjunto sesenta y cuatro! /56! = 178.462.987.637.760 situaciones diferentes), verificando en todos y cada una de ellas si las reinas se atacan mutuamente.


La busca a la fuerza salvaje es fácil de incorporar y, siempre y cuando exista, halla una solución. No obstante, su costo de ejecución es proporcional al número de soluciones aspirantes, el que es exponencialmente proporcional al tamaño del inconveniente. Al contrario, la busca a la fuerza salvaje se emplea frecuentemente cuando el número de soluciones aspirantes no es elevado, o cuando este puede reducirse anteriormente utilizando algún otro procedimiento heurístico.


Es un procedimiento usado asimismo cuando es más esencial una implementación fácil que una mayor velocidad. Este puede ser el caso en aplicaciones críticas donde cualquier fallo en el algoritmo puede conllevar serias consecuencias; asimismo es útil como procedimiento "base" cuando se quiere equiparar el desempeño de otros algoritmos metaheurísticos. La busca de fuerza bárbara puede ser vista como el procedimiento metaheurístico más simple.


La busca a la fuerza bárbara no se debe confundir con backtracking, procedimiento que descarta un elevado número de conjuntos de soluciones, sin contar explícitamente cada una de exactamente las mismas.


Algoritmo básico


Para poder emplear la busca a la fuerza bárbara a un tipo concreto de inconveniente, se deben incorporar las funcionesprimero, siguiente, valido, y enseñar. Todas y cada una van a recoger el factor P señalando una instancia particularmente del problema:



  1. primero (P): produce la primera solución aspirante para P.
  2. siguiente (P, c): produce la próxima solución aspirante para P tras una solución aspirante c.
  3. valido (P, c): examina si una solución aspirante c es una solución adecuada de P.
  4. mostrar (P, c): notifica que la solución c es una solución adecuada de P.

La función siguiente debe señalar de alguna manera en qué momento no existen más soluciones aspirantes para el inconveniente P tras la última. Una forma de efectuar esto consiste en devolver un valor "nulo". De esta forma, la función primero va a devolver un valor "nulo" cuando no exista ninguna solución aspirante al inconveniente P.


Usando semejantes funciones, la busca a la fuerza salvaje se expresa a través de el próximo algoritmo:

c? primero(P)mientrasc != null sivalido(P,c) entoncesmostrar(P, c) c? siguiente(P,c)

Por ejemplo, para buscar los divisores de un entero n, la instancia del inconveniente P es el propio número n. la llamada primero (n) va a devolver 1 siempre que n= 1, y "nulo" en otro caso; la función siguiente (n,c) debe devolver c + 1 si c

Variaciones comunes en el algoritmo


El algoritmo descrito previamente llama a la función enseñar para cada solución al inconveniente. Este puede ser de forma fácil cambiado de manera que finalice una vez halle la primera solución, o tras hallar un determinado número de soluciones, tras probar con un número concreto de soluciones aspirantes, o bien tras haber consumido una cantidad fija de tiempo de CPU.


La primordial desventaja del procedimiento de fuerza salvaje es que, para la mayor parte de inconvenientes reales, el número de soluciones aspirantes es prohibitivamente elevado.


Por ejemplo, para buscar los divisores de un número n como se describe previamente, el número de soluciones aspirantes a probar va a ser de n. En consecuencia, si n consta de, afirmemos, dieciseis dígitos, la busca requerirá de cuando menos mil quince comparaciones computacionales, labor que puede tardar múltiples días en un PC. Si n es un bit de sesenta y cuatro dígitos, que más o menos puede tener hasta diecinueve dígitos decimales, la busca puede tardar del orden de diez años.


Este desarrollo exponencial en el número de aspirantes, cuando medra el tamaño del inconveniente ocurre en todo género de inconvenientes. Por servirnos de un ejemplo, si procuramos una combinación particular de diez elementos entonces deberemos estimar diez! = 3,628,800 aspirantes diferentes, lo que en un computador frecuente puede ser generado y probado en menos de un segundo. No obstante, agregar un solo elemento más —lo como supone solo un diez por ciento más en el tamaño del problema— va a multiplicar el número de aspirantes once veces — lo que supone un mil por ciento de incremento. Para veinte elementos el número de aspirantes diferentes es veinte!, esto es, más o menos 2.4×1018 o bien veinticuatro millones de millones de millones; la busca podría tardar unos diez.000 años. A este fenómeno no deseado se le llama explosión combinacional.


La fuerza bárbara lógica, consiste esencialmente en lo mismo, mas eludiendo casos que por razones demasiado obvias se sabe que quedan fuera de la solución buscada.


Este procedimiento solo se utiliza cuando el número de posibilidades a eludir es suficientemente grande y que contando con el tiempo de ejecución del código preciso para incorporarlo, reduzca extensamente el tiempo preciso para hallar el resultado aguardado.


Cuando se habla de fuerza salvaje lógica, por contraste, la contrapuesta es llamada fuerza bárbara ciega.


Con el ejemplo de arriba, cuando tratamos a la fuerza salvaje de hallar el divisor de un número naturaln contaríamos todos y cada uno de los enteros desde 1 hasta n, examinando si cada uno de ellos de ellos divide n sin producir resto. La fuerza salvaje lógica haría lo mismo mas solo con los números primos, dada una tabla de primos, o bien solo con los impares y el dos si no tenemos una tabla de primos. Puesto que sabemos que cualquier número está compuesto de primos en cualquier cantidad y esto es demasiado obvio, no es completamente preciso comprobar el 4,6,8,10,12,14,15,16 si ya hemos mirado el dos,3,5,7...


La fuerza bárbara lógica prosigue siendo fuerza salvaje, en tanto que recorre sin estrategia el espacio de posibilidades mas descartando posibilidades muy obvias y parcialmente simples de incorporar.


  ELIGE TU TEMA DE INTERÉS: 


autoayuda.es   Internet y Tecnologias 

Está aquí: Inicio > [ INTERNET ] > ıllı Búsqueda de fuerza bruta wiki: info, historia y vídeos

Las cookies nos permiten ofrecer nuestros servicios. Al utilizar nuestros servicios, aceptas el uso que hacemos de las cookies. Ver políticas