Algoritmo de búsqueda

Este artículo tiene varios problemas. Ayúdenos a mejorarlo o a discutir estos problemas en la página de discusión . ( Aprenda cómo y cuándo eliminar estos mensajes ) Este artículo se centra demasiado en ejemplos específicos .Por favor, ayude a mejorar este artículo añadiendo fuentes que lo evalúen dentro de un contexto más amplio . ( Diciembre 2014 ) Este artículo necesita citas adicionales para su verificación .Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Algoritmo de búsqueda» – noticias  · periódicos  · libros  · académico  · JSTOR ( Abril de 2016 )( Aprenda cómo y cuándo eliminar este mensaje ) ( Aprenda cómo y cuándo eliminar este mensaje )

En informática , un algoritmo de búsqueda es un algoritmo diseñado para resolver un problema de búsqueda . Los algoritmos de búsqueda funcionan para recuperar información almacenada dentro de una estructura de datos particular , o calculada en el espacio de búsqueda de un dominio de problema, con valores discretos o continuos .

Aunque los motores de búsqueda utilizan algoritmos de búsqueda, estos pertenecen al estudio de la recuperación de información , no de la algoritmia.

El algoritmo de búsqueda adecuado que se debe utilizar depende a menudo de la estructura de datos que se está buscando y también puede incluir conocimientos previos sobre los datos. Los algoritmos de búsqueda se pueden hacer más rápidos o más eficientes mediante estructuras de bases de datos especialmente construidas, como árboles de búsqueda , mapas hash e índices de bases de datos . ^{[1] [2]}

Los algoritmos de búsqueda se pueden clasificar en función de su mecanismo de búsqueda en tres tipos de algoritmos: lineal, binario y hash. Los algoritmos de búsqueda lineal comprueban cada registro en busca del asociado con una clave de destino de forma lineal. ^[3] Las búsquedas binarias, o de medio intervalo, apuntan repetidamente al centro de la estructura de búsqueda y dividen el espacio de búsqueda por la mitad. Los algoritmos de búsqueda por comparación mejoran la búsqueda lineal al eliminar sucesivamente registros en función de las comparaciones de las claves hasta que se encuentra el registro de destino, y se pueden aplicar en estructuras de datos con un orden definido. ^[4] Los algoritmos de búsqueda digital funcionan en función de las propiedades de los dígitos en las estructuras de datos mediante el uso de claves numéricas. ^[5] Finalmente, el hash asigna directamente las claves a los registros en función de una función hash . ^[6]

Los algoritmos suelen evaluarse por su complejidad computacional o tiempo máximo de ejecución teórico. Las funciones de búsqueda binaria, por ejemplo, tienen una complejidad máxima de O (log n ) o tiempo logarítmico. En términos simples, la cantidad máxima de operaciones necesarias para encontrar el objetivo de búsqueda es una función logarítmica del tamaño del espacio de búsqueda.

Las aplicaciones específicas de los algoritmos de búsqueda incluyen:

• Problemas en optimización combinatoria , como:
  • El problema de la ruta del vehículo , una forma de problema de ruta más corta
  • El problema de la mochila : dado un conjunto de elementos, cada uno con un peso y un valor, determine la cantidad de cada elemento a incluir en una colección de modo que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible.
  • El problema de la programación de las enfermeras
• Problemas en la satisfacción de restricciones , tales como:
  • El problema de la coloración del mapa
  • Completar un sudoku o crucigrama
• En la teoría de juegos y especialmente en la teoría de juegos combinatorios , elegir el mejor movimiento a realizar a continuación (como con el algoritmo minmax )
• Encontrar una combinación o contraseña entre todo el conjunto de posibilidades
• Factorización de un número entero (un problema importante en criptografía )
• Optimización de motores de búsqueda (SEO) y optimización de contenido para rastreadores web
• Optimizar un proceso industrial, como una reacción química , modificando los parámetros del proceso (como la temperatura, la presión y el pH)
• Recuperar un registro de una base de datos
• Encontrar el valor máximo o mínimo en una lista o matriz
• Comprobación de si un valor determinado está presente en un conjunto de valores

Los algoritmos para buscar espacios virtuales se utilizan en el problema de satisfacción de restricciones , donde el objetivo es encontrar un conjunto de asignaciones de valores a ciertas variables que satisfagan ecuaciones matemáticas específicas e inecuaciones /igualdades. También se utilizan cuando el objetivo es encontrar una asignación de variable que maximice o minimice una determinada función de esas variables. Los algoritmos para estos problemas incluyen la búsqueda básica de fuerza bruta (también llamada búsqueda "ingenua" o "desinformada"), y una variedad de heurísticas que intentan explotar el conocimiento parcial sobre la estructura de este espacio, como la relajación lineal, la generación de restricciones y la propagación de restricciones .

Una subclase importante son los métodos de búsqueda local , que ven los elementos del espacio de búsqueda como los vértices de un gráfico, con bordes definidos por un conjunto de heurísticas aplicables al caso; y escanean el espacio moviéndose de un elemento a otro a lo largo de los bordes, por ejemplo de acuerdo con el criterio de descenso más pronunciado o el mejor primero , o en una búsqueda estocástica . Esta categoría incluye una gran variedad de métodos metaheurísticos generales , como el recocido simulado , la búsqueda tabú , los equipos A y la programación genética , que combinan heurísticas arbitrarias de formas específicas. Lo opuesto a la búsqueda local serían los métodos de búsqueda global. Este método es aplicable cuando el espacio de búsqueda no está limitado y todos los aspectos de la red dada están disponibles para la entidad que ejecuta el algoritmo de búsqueda. ^[7]

Esta clase también incluye varios algoritmos de búsqueda de árboles , que ven los elementos como vértices de un árbol y recorren ese árbol en un orden especial. Ejemplos de estos últimos incluyen los métodos exhaustivos como la búsqueda en profundidad y la búsqueda en amplitud , así como varios métodos de poda de árboles de búsqueda basados ​​en heurísticas como el backtracking y el branch and bound . A diferencia de las metaheurísticas generales, que en el mejor de los casos funcionan solo en un sentido probabilístico, muchos de estos métodos de búsqueda de árboles tienen la garantía de encontrar la solución exacta u óptima, si se les da suficiente tiempo. Esto se llama " completitud ".

Otra subclase importante consiste en algoritmos para explorar el árbol de juego de juegos de varios jugadores, como ajedrez o backgammon , cuyos nodos consisten en todas las posibles situaciones de juego que podrían resultar de la situación actual. El objetivo en estos problemas es encontrar el movimiento que proporcione la mejor posibilidad de victoria, teniendo en cuenta todos los movimientos posibles del oponente o los oponentes. Problemas similares ocurren cuando los humanos o las máquinas tienen que tomar decisiones sucesivas cuyos resultados no están completamente bajo el control de uno, como en la guía de robots o en la planificación de estrategias de marketing , financieras o militares . Este tipo de problema ( búsqueda combinatoria ) se ha estudiado ampliamente en el contexto de la inteligencia artificial . Ejemplos de algoritmos para esta clase son el algoritmo minimax , la poda alfa-beta y el algoritmo A* y sus variantes.

El nombre "búsqueda combinatoria" se utiliza generalmente para algoritmos que buscan una subestructura específica de una estructura discreta dada , como un gráfico, una cadena , un grupo finito , etc. El término optimización combinatoria se utiliza normalmente cuando el objetivo es encontrar una subestructura con un valor máximo (o mínimo) de algún parámetro. (Dado que la subestructura suele estar representada en el ordenador por un conjunto de variables enteras con restricciones, estos problemas pueden considerarse casos especiales de satisfacción de restricciones u optimización discreta; pero normalmente se formulan y resuelven en un entorno más abstracto en el que no se menciona explícitamente la representación interna).

Una subclase importante y ampliamente estudiada son los algoritmos de grafos , en particular los algoritmos de recorrido de grafos , para encontrar subestructuras específicas en un grafo dado, como subgrafos , caminos , circuitos, etc. Algunos ejemplos incluyen el algoritmo de Dijkstra , el algoritmo de Kruskal , el algoritmo del vecino más cercano y el algoritmo de Prim .

Otra subclase importante de esta categoría son los algoritmos de búsqueda de cadenas , que buscan patrones dentro de las cadenas. Dos ejemplos famosos son los algoritmos Boyer-Moore y Knuth-Morris-Pratt , y varios algoritmos basados ​​en la estructura de datos de árbol de sufijos .

En 1953, el estadístico estadounidense Jack Kiefer ideó la búsqueda de Fibonacci , que puede utilizarse para encontrar el máximo de una función unimodal y tiene muchas otras aplicaciones en la informática.

También existen métodos de búsqueda diseñados para ordenadores cuánticos , como el algoritmo de Grover , que teóricamente son más rápidos que la búsqueda lineal o de fuerza bruta incluso sin la ayuda de estructuras de datos o heurísticas. Si bien las ideas y aplicaciones detrás de los ordenadores cuánticos aún son completamente teóricas, se han realizado estudios con algoritmos como el de Grover que replican con precisión las versiones físicas hipotéticas de los sistemas de computación cuántica. ^[8]

• Inducción regresiva  : proceso de razonamiento hacia atrás en secuencia.
• Memoria direccionable por contenido  : tipo especial de memoria de computadora utilizada en ciertos hardware de aplicaciones de búsqueda de muy alta velocidad.
• Evolución en dos fases  : proceso que impulsa la autoorganización dentro de sistemas adaptativos complejos
• Problema de búsqueda lineal  – Problema de búsqueda computacional
• No hay almuerzo gratis en búsqueda y optimización  : el costo promedio de la solución es el mismo con cualquier método
• Sistema de recomendación  : sistema de filtrado de información para predecir las preferencias de los usuarios, también utiliza métodos estadísticos para clasificar los resultados en conjuntos de datos muy grandes.
• Motor de búsqueda (informática)  – Sistema para ayudar a buscar información
• Juego de búsqueda  : juego de suma cero para dos personas
• Algoritmo de selección  : método para encontrar el k-ésimo valor más pequeño
• Solver  – Software para una clase de problemas matemáticos
• Algoritmo de ordenación  : algoritmo que organiza listas en orden, necesario para ejecutar ciertos algoritmos de búsqueda.
• Motor de búsqueda web  : sistema de software para encontrar información relevante en la Web.Páginas que muestran descripciones breves de los objetivos de redireccionamiento

Categorías:

• Categoría:Algoritmos de búsqueda

• Knuth, Donald (1998). Ordenación y búsqueda . El arte de la programación informática . Vol. 3 (2.ª ed.). Reading, MA: Addison-Wesley Professional.

• Beame, Paul; Fich, Faith (agosto de 2002). "Límites óptimos para el problema del predecesor y problemas relacionados". Revista de Ciencias de la Computación y de Sistemas . 65 (1): 38–72. doi : 10.1006/jcss.2002.1822 . S2CID  1991980.
• Schmittou, Thomas; Schmittou, Faith E. (1 de agosto de 2002). "Límites óptimos para el problema del predecesor y problemas relacionados". Revista de Ciencias de la Computación y de Sistemas . 65 (1): 38–72. doi : 10.1006/jcss.2002.1822 .