Búsqueda Fuerza Bruta
Páginas: 5 (1026 palabras)
Publicado: 28 de junio de 2012
Búsqueda de fuerza bruta
La búsqueda por fuerza bruta, que también es llamada búsqueda combinatoria o búsqueda exhaustiva, 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 brutapara 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 todaslas 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 exponencialmenteproporcional 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 aplicacionescríticas donde cualquier error en el algoritmo puede acarrear serias consecuencias; también es útil como método "base" cuando se desea comparar el desempeño de otros algoritmos metaheurísticos. La búsqueda de fuerza bruta puede ser vista como el método metaheurístico más simple.
Rabin Karp
Es un Algoritmo de búsqueda de subcadenas simple enunciado por Michael Oser Rabin y RichardManning Karp en 1987.1 Este algoritmo se basa en tratar cada uno de los grupos de m caracteres del texto (siendo m el número de símbolos del patrón) del texto como un índice de una tabla de valores hash (la llamaremos tabla de dispersión), de manera que si la función hash de los m caracteres del texto coincide con la del patrón es posible que hayamos encontrado un acierto. para verificarlo hay quecomparar el texto con el patrón, ya que la función hash elegida puede presentar colisiones.
La función hash tiene la forma d(k)=xk mod q donde q es un número primo grande que será el tamaño de la tabla de dispersión y xk se calcula de la forma indicada más abajo.
Para transformar cada subcadena de m caracteres en un entero lo que hacemos es representar los caracteres en una base B que en elplanteamiento original coincide con el tamaño del alfabeto. Por tanto el entero xi correspondiente a la subcadena de texto Ci...Ci+m-1 sería:
xi=Ci×Bm-1+Ci-1×Bm-2+...+Ci+m-1
podemos calcular el valor de xi+1 en función de xi
xi+1=xi×B-Ci×Bm+Ci+m
Es decir, si la cadena es un número en base B, el nuevo valor será el resultado de multiplicar por la base el valor anterior eliminado el dígitode mayor peso (ya que no está en la cadena) y añadiendo como componente de menor peso el valor del nuevo símbolo.
Siguiendo este planteamiento, y dependiendo de la longitud del patrón, el xi podría superar el rango de enteros representable por el computador. Para que esto no suceda se usa la función módulo (resto de la división). Como la función módulo es asociativa, podemos calcular elxi+1incrementalmente a partir de cada xi.
Bexer Mort
Kruth Morris Pratt
El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella...
La búsqueda por fuerza bruta, que también es llamada búsqueda combinatoria o búsqueda exhaustiva, 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 brutapara 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 todaslas 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 exponencialmenteproporcional 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 aplicacionescríticas donde cualquier error en el algoritmo puede acarrear serias consecuencias; también es útil como método "base" cuando se desea comparar el desempeño de otros algoritmos metaheurísticos. La búsqueda de fuerza bruta puede ser vista como el método metaheurístico más simple.
Rabin Karp
Es un Algoritmo de búsqueda de subcadenas simple enunciado por Michael Oser Rabin y RichardManning Karp en 1987.1 Este algoritmo se basa en tratar cada uno de los grupos de m caracteres del texto (siendo m el número de símbolos del patrón) del texto como un índice de una tabla de valores hash (la llamaremos tabla de dispersión), de manera que si la función hash de los m caracteres del texto coincide con la del patrón es posible que hayamos encontrado un acierto. para verificarlo hay quecomparar el texto con el patrón, ya que la función hash elegida puede presentar colisiones.
La función hash tiene la forma d(k)=xk mod q donde q es un número primo grande que será el tamaño de la tabla de dispersión y xk se calcula de la forma indicada más abajo.
Para transformar cada subcadena de m caracteres en un entero lo que hacemos es representar los caracteres en una base B que en elplanteamiento original coincide con el tamaño del alfabeto. Por tanto el entero xi correspondiente a la subcadena de texto Ci...Ci+m-1 sería:
xi=Ci×Bm-1+Ci-1×Bm-2+...+Ci+m-1
podemos calcular el valor de xi+1 en función de xi
xi+1=xi×B-Ci×Bm+Ci+m
Es decir, si la cadena es un número en base B, el nuevo valor será el resultado de multiplicar por la base el valor anterior eliminado el dígitode mayor peso (ya que no está en la cadena) y añadiendo como componente de menor peso el valor del nuevo símbolo.
Siguiendo este planteamiento, y dependiendo de la longitud del patrón, el xi podría superar el rango de enteros representable por el computador. Para que esto no suceda se usa la función módulo (resto de la división). Como la función módulo es asociativa, podemos calcular elxi+1incrementalmente a partir de cada xi.
Bexer Mort
Kruth Morris Pratt
El algoritmo KMP es un algoritmo de búsqueda de subcadenas simple y por lo tanto su objetivo es buscar la existencia de una subcadena dentro de una cadena. Para ello utiliza información basada en los fallos previos, aprovechando la información que la propia palabra a buscar contiene de sí (sobre ella...
Leer documento completo
Regístrate para leer el documento completo.