Algoritmo de búsqueda

Los algoritmos para la búsqueda en 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 e inecuaciones matemáticas específicas . También se utilizan cuando el objetivo es encontrar una asignación de variables que maximice o minimice una función determinada de esas variables. Los algoritmos para estos problemas incluyen la búsqueda básica por 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 algoritmos de búsqueda local que consideran los elementos del espacio de búsqueda como los vértices de un grafo, con aristas definidas por un conjunto de heurísticas aplicables al caso; y exploran el espacio moviéndose de un elemento a otro a lo largo de las aristas, por ejemplo, según el criterio de descenso más pronunciado o ^de búsqueda primero en amplitud , 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 [ ^{7 ]} y la programación genética , que combinan heurísticas arbitrarias de maneras 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. ^{[ 8 ]}

Los algoritmos de búsqueda en árboles son algoritmos de búsqueda en grafos locales diseñados para funcionar eficientemente en grafos dirigidos acíclicos con una única raíz o nodo inicial ( árboles ). Estos algoritmos recorren los nodos de un árbol en un orden específico, prescrito por un algoritmo diseñado para una aplicación particular. Ejemplos de algoritmos de búsqueda en árboles incluyen métodos exhaustivos como la búsqueda en profundidad y la búsqueda en amplitud , así como algoritmos de poda de árboles basados ​​en heurísticas , como el retroceso , la ramificación y acotación y la poda alfa-beta . A diferencia de los algoritmos metaheurísticos , que solo pueden prescribir un orden de recorrido que sea óptimo en algún sentido probabilístico, muchos métodos de búsqueda en árboles garantizan encontrar la solución óptima exacta, si se les da el tiempo suficiente. En matemáticas y lógica, esto se denomina garantía de " completitud ".

Otra subclase importante la constituyen los algoritmos para explorar el árbol de juego de juegos multijugador, como el ajedrez o el backgammon , cuyos nodos representan todas las situaciones de juego posibles que podrían derivarse de la situación actual. El objetivo en estos problemas es encontrar la jugada que ofrezca la mejor probabilidad de victoria, teniendo en cuenta todas las posibles jugadas del oponente o oponentes. Problemas similares surgen cuando humanos o máquinas deben tomar decisiones sucesivas cuyos resultados no están completamente bajo su control, como en la guía de robots o en la planificación de estrategias de marketing , financieras o militares . Este tipo de problema —la búsqueda combinatoria— se ha estudiado ampliamente en el contexto de la inteligencia artificial . Ejemplos de algoritmos de esta clase son el algoritmo minimax , la poda alfa-beta y el algoritmo A* y sus variantes.

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 son 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 , así como 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 computadoras cuánticas , como el algoritmo de Grover , que son teóricamente más rápidos que la búsqueda lineal o por fuerza bruta, incluso sin la ayuda de estructuras de datos o heurísticas. 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. ^{[ 9 ]}