Algoritmos de Búsqueda

En inteligencia artificial, los algoritmos de búsqueda resuelven problemas explorando de forma sistemática un espacio de estados: parten de un estado inicial y aplican acciones para alcanzar un estado objetivo, construyendo y recorriendo un árbol o grafo. Un problema de búsqueda se define por un estado inicial, las acciones posibles, un modelo de transición que dice a qué estado lleva cada acción, una prueba de objetivo y un coste. Conviene distinguir este sentido del de «buscar» un dato en una base de datos o en la web: aquí buscar significa hallar una secuencia de acciones hacia una meta.

Búsqueda no informada

La búsqueda no informada o «ciega» no usa ninguna pista sobre dónde está el objetivo más allá de la definición del problema. Sus estrategias clásicas son la búsqueda en anchura, que explora primero los nodos más superficiales y es completa aunque consume mucha memoria; la búsqueda en profundidad, que baja primero por una rama y usa poca memoria pero puede no terminar; la de coste uniforme, que expande siempre el nodo de menor coste acumulado y encuentra el camino óptimo; y la profundización iterativa, que combina lo mejor de las anteriores.

Búsqueda informada

La búsqueda informada o heurística usa una función que estima la cercanía al objetivo para guiar la exploración hacia las zonas más prometedoras. Sus ejemplos son la búsqueda voraz por el mejor primero y, sobre todo, el algoritmo A*, que combina el coste ya recorrido con esa estimación y encuentra el camino óptimo si la heurística cumple ciertas condiciones.

Otras familias

Existen más tipos de búsqueda. La búsqueda local —como el ascenso de colina o el recocido simulado— mejora un único estado y sirve para problemas de optimización. Y la búsqueda adversarial, como el algoritmo Minimax, se aplica a juegos de dos jugadores donde un rival responde a cada movimiento.