Algoritmos de búsqueda

algoritmos de búsqueda

Los algoritmos de búsqueda de soluciones se suelen dividir en dos tipos que son los siguientes: estrategias de búsqueda no informada y estrategias de búsqueda informada.

Algoritmos de búsqueda no informada

Los métodos de búsqueda no informados son estrategias de búsqueda en los cuales se evalúa el siguiente estado sin conocer a priori si este es mejor o peor que el anterior.

El término quiere decir que no se tiene información adicional acerca de los estados más allá de la que proporciona la propia definición del problema.

A continuación, describiremos los algoritmos de búsqueda no informada más importantes que existen.

Búsqueda en anchura

La búsqueda en anchura es una estrategia bastante sencilla en la que se expande primero el nodo raíz y después se van expandiendo todos los sucesores a este nodo. Cuando expandimos el nodo seguiremos por la expansión de los sucesores del siguiente y así sucesivamente.

búsqueda en anchura árbol

Esta estrategia de búsqueda se puede implementar con una frontera vacía que sea una cola FIFO (primero en entrar /  primero en salir).

La búsqueda en anchura es óptima si el costo del camino es una función no decreciente de la profundidad del nodo como por ejemplo cuando todas las acciones tienen el mismo coste. También es completo porque encontrará siempre una solución si es que la hay.

La complejidad tanto espacial como temporal es exponencial y está en O(n^p), siendo n el número medio de sucesores y p el nivel donde se alcanza la solución. Por ello, esta estrategia es solo aplicable a problemas no demasiado grandes.

Búsqueda de costo uniforme

El algoritmo de búsqueda mediante costo uniforme es una extensión sencilla del anterior algoritmo, ya que podemos hacer que el algoritmo sea óptimo con cualquier función costo. Esto lo conseguimos expandiendo el nodo n con el camino de costo más pequeño. Cuando todos los costos son iguales el algoritmo sería igual que la estrategia en anchura.

Podemos garantizar que la estrategia es completa si el costo de cada paso es igual o mayor a una pequeña constante positiva que llamaremos Ɛ.

El tiempo para el peor caso y la complejidad espacial es O(b1 + C*/ε), donde C* es el costo de la solución óptima y b es el factor de ramificación. Cuando todos los costos entre los nodos son iguales, esto se convierte en O(bd + 1).

Búsqueda en profundidad

El algoritmo de búsqueda en profundidad siempre expande el nodo más profundo en la frontera actual del árbol de búsqueda.

búsqueda en anchura

La búsqueda procede al nivel más profundo del árbol de búsqueda donde los nodos no tienen ningún sucesor. Cuando estos nodos se han expandido se quitan de la frontera, así la búsqueda vuelve atrás, al siguiente nodo más superficial que todavía tenga sucesores sin explorar.

Esta estrategia de búsqueda se puede implementar con una cola LIFO (último en entrar / primero en salir), es decir una pila tradicional.

El algoritmo es completo si solo usamos búsqueda basada en grafos en espacios de estado finitos, pues todos los nodos serán expandidos.

Sin embargo, en ningún caso asegura la optimalidad, pues puede encontrar una solución más profunda que otra en una rama que todavía no ha sido expandida.

La complejidad temporal en el peor caso, es O(b^m), siendo b el factor de ramificación (número promedio de ramificaciones por nodo) y m la máxima profundidad del espacio de estados.

La complejidad espacial es, O(b^d) siendo d la profundidad de la solución menos costosa, pues cada nodo generado permanece en memoria, almacenando la mayor cantidad de nodos en el nivel objetivo.

Algoritmos de búsqueda informada

Los algoritmos de búsqueda informada utilizan el conocimiento específico del problema más allá de la definición del problema en sí mismo.

Una componente clave de estos algoritmos es una función heurística h(n) que toma un nodo n como entrada. La función se podría definir como coste estimado del camino más barato desde el nodo n a un nodo objetivo.

Búsqueda voraz

El algoritmo de búsqueda voraz expande el nodo más cercano al objetivo suponiendo que probablemente conduzca más rápido al nodo objetivo. Dicho de otro modo la función que evalúa la elección de un nodo u otro depende exclusivamente de h(n). 

Esta estrategia de búsqueda no es óptima ni completa. La complejidad temporal y espacial en el peor de los casos, es O(b^m), donde m es la máxima profundidad del espacio de estados.

Búsqueda A*

La estrategia de búsqueda A* evalúa los nodos combinando el coste de alcanzar el nodo (g(n)) y la heurística (h(n))

Si tratamos de encontrar la solución más barata es razonable elegir el nodo con el valor más bajo de g(n) + h(n).

Cuando la función heurística h(n) sea admisible este algoritmo de búsqueda se puede considerar completo y excelente. La heurística se considera admisible si no se sobreestima el coste de alcanzar el objetivo.

La complejidad temporal del algoritmo está íntimamente relacionada con la calidad de la heurística que se utilice en el problema. En el peor caso con una heurística de pésima calidad, la complejidad será exponencial, mientras que en el mejor caso el algoritmo se ejecutará en tiempo lineal.

La complejidad espacial es su mayor problema. Dado que tiene que almacenar todos los posibles siguientes nodos de cada estado, la cantidad de memoria que requerirá será exponencial con respecto al tamaño del problema.

Comparación de algoritmos de búsqueda

AlgoritmoCompletaÓptimaFunción (f(n))
Anchuraprofundidad de n
Coste uniformecoste de n
ProfundidadNo1/(prof. n +1)
VorazNo Noh(n)
A*g(n)+h(n)

Deja un comentario