La búsqueda es una técnica fundamental en inteligencia artificial y se utiliza para encontrar soluciones a una amplia variedad de problemas. En la búsqueda, el objetivo es encontrar una solución óptima o satisfactoria a un problema, a través de la exploración sistemática de un espacio de estados.

Existen diferentes estrategias para la búsqueda, desde estrategias no informadas, como la búsqueda en profundidad o en anchura, hasta estrategias informadas o heurísticas, como la búsqueda A* y la búsqueda de costo uniforme (UCS).

En las búsquedas no informadas, el algoritmo no tiene información adicional sobre el espacio de estados y explora todos los posibles caminos a partir del nodo inicial, hasta que encuentra una solución. La búsqueda en profundidad y en anchura son dos ejemplos de búsquedas no informadas, y cada una tiene sus ventajas y desventajas en términos de eficiencia y espacio de memoria.

Por otro lado, en las búsquedas informadas, el algoritmo utiliza información adicional, generalmente en forma de una función heurística, para guiar la exploración hacia la solución. La búsqueda A* y la búsqueda UCS son dos ejemplos de búsquedas informadas y pueden ser más eficientes que las búsquedas no informadas en algunos casos.

En este artículo, exploraremos estas diferentes estrategias de búsqueda y analizaremos su eficiencia y ventajas en diferentes contextos.

Búsquedas no informadas

Búsqueda por profundidad primero

El método de búsqueda en profundidad primero (DFS, por sus siglas en inglés) es una estrategia utilizada para recorrer y buscar en un árbol o grafo. En este método, se comienza en el nodo raíz y se exploran todas las ramas posibles hasta alcanzar un nodo hoja, antes de retroceder y explorar la siguiente rama. Es decir, se profundiza en el árbol lo máximo posible antes de retroceder.

Este método se puede implementar mediante la utilización de una pila (stack) para almacenar los nodos que se van visitando, y se utiliza un enfoque de LIFO (last-in, first-out) para mantener el orden de visitas.

El DFS es una técnica de búsqueda utilizada en numerosas aplicaciones, como en la búsqueda de caminos en un grafo, en la resolución de laberintos y en la optimización de juegos. Una de las desventajas del DFS es que puede quedar atrapado en ciclos infinitos si el grafo no es un DAG (Directed Acyclic Graph).

El método de búsqueda en profundidad primero fue introducido por Charles Pierre Trémaux en 1859. Desde entonces, se ha convertido en una técnica fundamental en la teoría de grafos y la inteligencia artificial.

Búsqueda por anchura primero

El método de búsqueda por anchura primero (BFS) es otra estrategia utilizada para buscar un nodo en un árbol o grafo. En este método, se comienza desde el nodo raíz y se exploran todos los nodos del mismo nivel antes de avanzar al siguiente nivel. De esta manera, se va "ensanchando" el árbol hasta alcanzar el nodo objetivo.

El algoritmo BFS se puede implementar utilizando una cola para almacenar los nodos que se van visitando. El proceso comienza con la inserción del nodo raíz en la cola. Luego, se saca el primer nodo de la cola y se exploran todos sus nodos hijos, insertándolos al final de la cola. Este proceso se repite hasta que se encuentra el nodo objetivo o se visita todo el árbol.

Una de las principales ventajas del BFS es que siempre encuentra el camino más corto desde el nodo raíz hasta el nodo objetivo, si existe uno. Sin embargo, su principal desventaja es que requiere más memoria que el DFS, ya que debe almacenar todos los nodos de un nivel antes de avanzar al siguiente.

En resumen, el método de búsqueda por anchura primero es otra estrategia utilizada para buscar nodos en un árbol o grafo. En lugar de "profundizar" en el árbol como lo hace el DFS, el BFS "ensancha" el árbol para encontrar el nodo objetivo.

Búsquedas informadas

Método de búsqueda de costo uniforme (UCS)

El método de búsqueda de costo uniforme (UCS) es un algoritmo de búsqueda informada que expande los nodos con el menor costo de ruta acumulado. A diferencia de la búsqueda en anchura (BFS) que se enfoca en la búsqueda en capas en un árbol de búsqueda, la búsqueda de costo uniforme tiene en cuenta los costos de los arcos entre los nodos y siempre expande el nodo con el costo de ruta acumulado más bajo.

UCS es especialmente útil en problemas donde el costo de la solución es importante, como en la planificación de rutas o en la optimización de redes. Sin embargo, UCS puede ser ineficiente si hay muchos nodos con el mismo costo de ruta acumulado, lo que puede resultar en la expansión innecesaria de nodos similares.

Búsqueda A*

La búsqueda A* es un algoritmo de búsqueda informada que utiliza una función heurística para estimar el costo de alcanzar el objetivo desde cada nodo. La función heurística estima el costo restante de la ruta desde un nodo dado al objetivo, lo que permite al algoritmo seleccionar el mejor camino a seguir en función del costo actual de la ruta y la estimación del costo restante.

El algoritmo A* mantiene una lista de nodos no visitados y una lista de nodos visitados, comenzando con el nodo de inicio. En cada iteración, se selecciona el nodo con el costo total más bajo, que se define como la suma del costo acumulado de la ruta desde el nodo de inicio y la estimación del costo restante de la ruta al objetivo. Luego, se expande el nodo seleccionado y se agregan sus vecinos a la lista de nodos no visitados, actualizando sus costos totales.

La función heurística debe ser admisible, lo que significa que no debe sobreestimar el costo restante de la ruta al objetivo. Si la función heurística es admisible, el algoritmo A* encuentra siempre la solución óptima, es decir, la ruta más corta desde el nodo de inicio al objetivo.

Resumen de los tipos de búsquedas

Búsquedas informadas (heurísticas)

·         Utilizan información adicional, generalmente una función heurística, para guiar la búsqueda hacia la solución.

·         A menudo son más eficientes que las búsquedas no informadas, ya que pueden evitar explorar caminos que no conducen a la solución.

·         Pueden encontrar soluciones subóptimas si la función heurística es inadecuada o si la solución no es única.

·         Ejemplos: búsqueda A*, búsqueda de costo uniforme.

Búsquedas no informadas

·         No utilizan información adicional, sino que exploran sistemáticamente todas las posibilidades hasta encontrar la solución.

·         A menudo son menos eficientes que las búsquedas informadas, ya que pueden explorar caminos que no conducen a la solución.

·         Siempre encuentran soluciones óptimas si existen.

·         Ejemplos: búsqueda en anchura, búsqueda en profundidad.

Referencias de la bibliografía del curso

Stuart Russell, Peter Norvig, "Artificial Intelligence: A Modern Approach", Third Edition.

Referencias externas

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). The MIT Press.