Algoritmo de búsqueda
En ciencias de la computación , un algoritmo de búsqueda es un algoritmo (que generalmente involucra una multitud de otros algoritmos más específicos [1] ) que resuelve un problema de búsqueda . Los algoritmos de búsqueda funcionan para recuperar información almacenada dentro de alguna estructura de datos , o calculada en el espacio de búsqueda de un dominio de problema, con valores discretos o continuos .
Si bien los problemas de búsqueda descritos anteriormente y la búsqueda en la web son problemas en la recuperación de información, generalmente se estudian como subcampos separados y se resuelven y evalúan de manera diferente. Los problemas de búsqueda web generalmente se centran en filtrar y encontrar documentos que son más relevantes para las consultas humanas. Los algoritmos de búsqueda clásicos generalmente se evalúan en función de la rapidez con la que pueden encontrar una solución y si se garantiza que esa solución sea óptima. Aunque los algoritmos de recuperación de información deben ser rápidos, la calidad de la clasificación y si se han omitido los buenos resultados y se han incluido los malos, es más importante.
El algoritmo de búsqueda apropiado 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 . [2] [ se necesita cita completa ] [3]
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. [4] Las búsquedas binarias o de medio intervalo se dirigen repetidamente al centro de la estructura de búsqueda y dividen el espacio de búsqueda por la mitad. Los algoritmos de búsqueda de comparación mejoran la búsqueda lineal al eliminar sucesivamente registros basados en comparaciones de claves hasta que se encuentra el registro de destino, y se pueden aplicar en estructuras de datos con un orden definido. [5] Los algoritmos de búsqueda digital funcionan basándose en las propiedades de los dígitos en estructuras de datos que utilizan claves numéricas. [6] Finalmente,El hash asigna directamente las claves a los registros en función de una función hash . [7]
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. Esto significa que 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.
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 y desigualdades / 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 propagación de restricciones.
