Algoritmo de búsqueda
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, pertenecen al estudio de la recuperación de información, no a la algorítmica.
El algoritmo de búsqueda adecuado a menudo depende de la estructura de datos que se busca 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.
Los algoritmos de búsqueda se pueden clasificar según su mecanismo de búsqueda en tres tipos de algoritmos: lineal, binario y hash. Los algoritmos de búsqueda lineal verifican cada registro en busca del asociado con una clave de destino de forma lineal. 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 eliminando sucesivamente registros basados en comparaciones de las claves hasta que se encuentra el registro de destino, y se pueden aplicar en estructuras de datos con un orden definido. 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. Por último, el hash asigna directamente las claves a los registros en función de una función hash.
Los algoritmos a menudo se evalúan por su complejidad computacional o el tiempo de ejecución teórico máximo. 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, el número máximo de operaciones necesarias para encontrar el objetivo de búsqueda es una función logarítmica del tamaño del espacio de búsqueda.
Aplicaciones de algoritmos de búsqueda
Las aplicaciones específicas de los algoritmos de búsqueda incluyen:
- Problemas en la optimización combinatoria, tales como:
- El problema de la ruta del vehículo, una forma de problema de ruta más corto
- El problema knapsack: Dado un conjunto de elementos, cada uno con un peso y un valor, determinar el número de cada artículo a incluir en una colección de modo que el peso total sea inferior o igual a un límite determinado y el valor total es lo más grande posible.
- El problema de la enfermera
- Problemas de satisfacción restrictiva, tales como:
- El problema de coloración del mapa
- Filling en un sudoku o crucigrama
- En la teoría del juego y especialmente la teoría del juego combinatorial, eligiendo el mejor movimiento para hacer siguiente (como con el algoritmo minmax)
- Encontrar una combinación o contraseña de todo el conjunto de posibilidades
- Factorización de un entero (un problema importante en la criptografía)
- Optimizar un proceso industrial, como una reacción química, cambiando los parámetros del proceso (como temperatura, presión y pH)
- Recuperar un registro de una base de datos
- Encontrar el valor máximo o mínimo en una lista o matriz
- Comprobando para ver si un valor dado está presente en un conjunto de valores
Clases
Para espacios de búsqueda virtuales
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 e inecuaciones/igualdades específicas. También se utilizan cuando el objetivo es encontrar una asignación de variable que maximizará o minimizará 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 "no informada") 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 escanear el espacio moviéndose de un elemento a otro a lo largo de los bordes, por ejemplo según 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 recocido simulado, búsqueda tabú, equipos A y 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.
Esta clase también incluye varios algoritmos de búsqueda de árboles, que ven los elementos como vértices de un árbol y atraviesan ese árbol en un orden especial. Ejemplos de estos últimos incluyen los métodos exhaustivos, como la búsqueda primero en profundidad y la búsqueda primero en amplitud, así como varios métodos de poda de árbol de búsqueda basados en heurística, como backtracking y branch andbound. A diferencia de las metaheurísticas generales, que en el mejor de los casos funcionan solo en un sentido probabilístico, se garantiza que muchos de estos métodos de búsqueda de árboles encontrarán 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 juegos de múltiples jugadores, como el ajedrez o el backgammon, cuyos nodos consisten en todas las situaciones de juego posibles que podrían resultar de la situación actual. El objetivo de estos problemas es encontrar el movimiento que proporcione la mejor oportunidad de ganar, teniendo en cuenta todos los movimientos posibles de 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 militares, financieras o de marketing. Este tipo de problema, la 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.
Para subestructuras de una estructura dada
El nombre "búsqueda combinatoria" se usa 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 usa típicamente cuando el objetivo es encontrar una subestructura con un valor máximo (o mínimo) de algún parámetro. (Dado que la subestructura generalmente se representa en la computadora mediante un conjunto de variables enteras con restricciones, estos problemas pueden verse como casos especiales de satisfacción de restricciones u optimización discreta; pero generalmente se formulan y resuelven en un entorno más abstracto donde el la representación interna no se menciona explícitamente).
Una subclase importante y ampliamente estudiada son los algoritmos de grafos, en particular, los algoritmos transversales de grafos, para encontrar subestructuras específicas en un grafo determinado, como subgrafos, rutas, circuitos, etc. Los 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 de Boyer-Moore y Knuth-Morris-Pratt, y varios algoritmos basados en la estructura de datos del árbol de sufijos.
Buscar el máximo de una función
En 1953, el estadístico estadounidense Jack Kiefer ideó la búsqueda de Fibonacci que se puede utilizar para encontrar el máximo de una función unimodal y tiene muchas otras aplicaciones en informática.
Para computadoras cuánticas
También hay métodos de búsqueda diseñados para computadoras cuánticas, 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ística. Si bien las ideas y aplicaciones detrás de las computadoras cuánticas 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.
Optimización de motores de búsqueda
Los algoritmos de búsqueda que se utilizan en un motor de búsqueda como Google ordenan los resultados de búsqueda relevantes en función de una miríada de factores importantes. La optimización de motores de búsqueda (SEO) es el proceso en el que cualquier resultado de búsqueda dado funcionará junto con el algoritmo de búsqueda para obtener orgánicamente más tracción, atención y clics en su sitio. Esto puede ir tan lejos como intentar ajustar el algoritmo de los motores de búsqueda para favorecer más un resultado de búsqueda específico, pero la estrategia que gira en torno al SEO se ha vuelto increíblemente importante y relevante en el mundo de los negocios.