Estructuras de datos dinámicas/Algoritmos de búsqueda

El proceso de un Algoritmo de Búsqueda es la consecución de ubicar información en una colección de datos. Lo que interesa de su uso, es saber si un elemento pertenece o no a la colección; y en caso de pertenecer, saber el ÍNDICE DE LA LISTA en el cual está el elemento.

Introducción

Los algoritmos de búsqueda que se exponen a continuación se aplican a árboles. Como se verá, muchos problemas de optimización pueden modelarse de manera de generar un árbol cuyos nodos constituyen posibles soluciones o pasos intermedios a la solución del problema; cada uno de estos algoritmos define un orden en el cual se generarán los nodos del árbol, y una forma en la cual se encontrará la solución buscada.

Definiciones

Costo

Los algoritmos de optimización por búsqueda trabajan con el concepto de costo, que es la función que debe ser optimizada. Cada paso en el camino que constituye la solución óptima, tendrá asociado un costo en sí mismo, y el costo global será función de los costos de cada uno de esos pasos.

Criterio de parada

Es el criterio que se toma para decidir que la búsqueda ha llegado a su fin. En este punto se puede devolver una solución, o determinar que no hay solución posible.

Criterio de camino agotado

Es el criterio que se toma para decidir que la búsqueda desde el nodo actual no puede llevar a una solución, de manera que, de quedar otros caminos posibles, debería continuar por alguno de ellos.

Expansión de nodos repetidos

Frecuentemente, en los problemas que se modelan, es posible llegar a una solución posible o intermedia a través de varios caminos. Esto hace que un algoritmo de búsqueda pueda generar más de una vez el mismo nodo. Los problemas que devienen de la expansión reiterada de un mismo nodo van desde una ligera carga extra hasta la no convergencia del algoritmo, dependiendo de la naturaleza del problema y del algoritmo utilizado. Se debe evitar la expansión repetida, deberá guardarse pista de los nodos ya expandidos. En algunos casos, tales como una búsqueda en profundidad que genere un número limitado de nodos, pero que puedan repetirse, pueden generarse bucles en una rama, de manera que para evitarlos, sólo se debe guardar pista de los nodos expandidos en la rama atual.

Aristas de costo negativo

Una arista de costo negativo, en la semántica del problema, significará que uno de los pasos posibles en el camino de una solución, contribuye mejorar solución. Esto es un problema para los algoritmos que evitan caminos del árbol de búsqueda basándose en el costo que tiene alcanzar cada nodo, porque esto no prevé que en futuros pasos la función costo puede mejorar.

Búsqueda en anchura

Definición

Un algoritmo de búsqueda en anchura recorre todos los nodos de un árbol de manera uniforme. Expande cada uno de los nodos de un nivel antes de continuar con el siguiente.

Complejidad computacional

Si la solución se encuentra en el nivel n, y la cantidad máxima de hijos de un nodo es i, habrá que expandir, en el peor de los casos, la cantidad de nodos de un árbol de orden i y de altura n:

$C={\cfrac {i^{n+1}-1}{i-1}}$

Por lo tanto, tanto el tiempo de procesamiento como el requerimiento de memoria tendrán un orden exponencial, tanto si evita o no expansiones repetidas.

Ventajas y desventajas

Expandir los nodos de forma uniforme garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna, de manera que apenas se encuentre una solución, puede devolverse, porque será la mejor, o bien expandir todo el nivel en el cual se hubiere encontrado, para obtener todas las soluciones posibles.

La desventaja principal es el alto orden de complejidad computacional, que hace que, de no mantenerse muy limitados los parámetros i y n del problema, crezcan rápidamente los requerimientos y se vuelvan inaceptables.

Búsqueda en profundidad

Definición

Un algoritmo de búsqueda en profundidad recorre todos los nodos de un árbol de manera ordenada, pero no uniforme. Consiste en ir expandiendo cada uno de los nodos a medida que los encuentra, empezando siempre por el primer nodo hijo no visitado del nodo actual; cuando ya no quedan más nodos hijos que visitar en el actual, regresa (backtracking), y el padre del nodo pasa a ser el nodo actual. El criterio de camino agotado debe ser elegido cuidadosamente, de manera de evitar la expansión indefinida de nodos. Asimismo, para garantizar la convergencia, en muchos casos debe evitarse la expansión de nodos repetidos, al menos en un mismo camino.

Ventajas y desventajas

Expandir un camino hasta su máxima profundidad puede ser útil para acotar la solución en problemas de optimización. Esto es, si se ha encontrado una solución posible con determinada valoración, no se admitirá expandir nodos con una valoración peor, y así el algoritmo puede ir eliminando ramas sin la carga de procesamiento de recorrerlas. Además, el requerimiento de memoria es limitado, aun si se garantiza que no cicle, ya que sólo hace falta guardar los datos de la rama actual.

Complejidad computacional

La cantidad mínima de nodos a ser expandidos para garantizar la mejor solución es la misma que en la búsqueda en anchura, es decir

$C={\cfrac {i^{n+1}-1}{i-1}}$

La diferencia es que en este caso no tendremos certeza de haber encontrado la mejor solución hasta que se hayan expandido todas las ramas hasta el nivel de la mejor solución encontrada (siempre hablando de problemas con costo uniforme), y, aunque el problema tenga la mejor solución en un nivel n, el algoritmo podría explorar por otra rama hasta una profundidad mucho mayor, incluso indefinidamente, por lo cual la complejidad computacional en el peor de los casos está determinada por la profundidad a la cual se encuentra la solución más costosa de todas las ramas.

Búsqueda en profundidad iterativa

Definición

Un algoritmo de búsqueda en profundidad iterativa recorre los nodos de un árbol en profundidad, pero con un valor de profundidad restringido, que aumentará en cada iteración. Esto evita el riesgo de internarse indefinidamente en una rama no finita, y evita también la necesidad de guardar pista de todos los nodos expandidos (sólo hace falta guardar los de la rama actual).

Ventajas y desventajas

La búsqueda en profundidad iterativa aprovecha ventajas de la búsqueda en anchura y de la búsqueda en profundidad:

• El requerimiento limitado de memoria.
• La uniformidad al expandir los nodos, que garantiza encontrar la mejor solución de un problema de costo uniforme antes que ninguna.

Complejidad computacional

La complejidad temporal para el caso peor es igual a la cantidad máxima de nodos generados hasta una profundidad $d$ (profundidad de la solución con menor profundidad). Resolviendo la serie, la complejidad resulta de $O\left(b^{d}\right)$. En tanto, la complejidad espacial está determinada por la profundidad de la solución, ya que sólo deben guardarse los nodos del camino actual y sus hermanos, que serán $b.d$, de manera que la complejidad espacial será de $O\left(b.d\right)$

Búsqueda de costo fijo

Definición

Un algoritmo de búsqueda de costo fijo tiene asociada una función de costo que se aplica cada nodo, que representará el costo del mejor camino conocido para llegar desde el nodo inicial hasta el nodo en cuestión. El algoritmo de optimización deberá obtener el mejor camino entre el nodo inicial y un nodo caracterizado como el nodo de destino. En cada iteración, la expansión a realizar será la del nodo cuyo costo resulte menor, excepto si éste fuera una solución, en cuyo caso, se tratará de la solución óptima, por no haber ningún nodo con menor costo que pueda expandirse para encontrar una solución mejor. Si el costo de los movimientos es uniforme, la búsqueda seguirá el mismo orden de expansiones que la búsqueda en anchura ^[1].

La función de costo

La función de costo de un nodo representa el costo del mejor camino conocido para llegar desde el nodo inicial hasta el nodo. Para el nodo inicial deberá valer 0.

Complejidad computacional

La complejidad temporal para el caso peor es igual a la cantidad máxima de nodos generados hasta un costo de $C^{*}$ (costo óptimo), es decir, hasta una profundidad de ${\frac {C^{*}}{\epsilon }}$, siendo $\epsilon$ el costo más pequeño aplicable a una acción. Resolviendo la serie, la complejidad resulta de $O\left(b^{\frac {C^{*}}{\epsilon }}\right)$. La complejidad espacial será también de $O\left(b^{\frac {C^{*}}{\epsilon }}\right)$, ya que deben almacenarse al menos todos los nodos de la frontera.

Búsqueda heurística

Definición

El nodo que más conviene expandir es el nodo a través del cual pasa el camino con menor costo. Sería útil contar con la información del costo total del camino que significaría atravesar cada nodo. La búsqueda de costo fijo estima este valor con el costo parcial de llegar a este nodo. En muchos casos, esto no es suficiente. No se puede contar con el valor exacto, esto implicaría tener el problema resuelto. Lo que puede hacerse es estimar el costo desde el nodo actual hasta el nodo final, de manera de expandir primero el nodo a través del cual se estime que se llegará a la solución con costo óptimo.

La función de costo

La función de costo es equivalente a la función de costo en la búsqueda de costo fijo.

La función heurística

La función heurística debe estimar la función de costo desde el nodo actual hasta el nodo objetivo. Debe ser optimista, ya que si la estimación fuera superior al valor real, un nodo que llega a la solución óptima puede quedar excluido de la búsqueda. Mientras más se ajuste la heurística al valor real, se expandirán menos nodos innecesariamente.

Complejidad computacional

Para la búsqueda A*, la complejidad temporal y espacial para el caso peor ($h()=cte.=0$) es la misma que la complejidad de la búsqueda de costo uniforme; esto es evidente ya que en el caso peor, la función heurística devuelve siempre 0, haciendo que la búsqueda sea en todo sentido igual a la búsqueda de costo fijo.

Implementación

El algoritmo de búsqueda genérico

Para implementar tanto la búsqueda en profundidad, como la búsqueda en anchura, la de costo fijo y la heurística, puede utilizarse un algoritmo genérico:

1. Colocar el nodo inicial en la lista abierta.
2. Elegir el próximo elemento de la lista abierta a extraer, y realizar la extracción.
3. Si se corresponde con un estado final, devolver el elemento o la secuencia de acciones correspondiente, si no, continuar.
4. Explandirlo, colocando los descendientes que correspondan en la lista abierta.
5. Colocarlo en la lista cerrada y volver a 2.

De las características de la estructura de datos utilizada como lista abierta, dependerán las características del algoritmo:

Si la estructura es una pila, el algoritmo elegirá siempre el último nodo generado, y a partir de ese nodo generará nuevos nodos, que serán agregados a la pila, y el primero será elegido, y así sucesivamente; es decir que la búsqueda será en profundidad.

Si la estructura es una cola, los nodos se expandirán en el orden que se generen, de manera que todos los nodos de un nivel deberán ser expandidos antes de comenzar a expandir los del siguiente; la búsqueda será en anchura.

Si la estructura es una cola de prioridad, y la función de ordenamiento es la función costo, de manera que el elemento elegido sea siempre el de menor costo, la búsqueda será de costo uniforme. Si la función de ordenamiento combina la función de costo con una función heurística, la búsqueda será heurística.

---

^ Para el caso de la búsqueda de costo fijo, nótese que si se agrega a la lista abierta un nodo correspondiente a un estado que ya está allí, pero con un valor de costo diferente, no habrán expansiones repetidas, ya que una vez en la lista cerrada, cuando se tome de la lista abierta el nodo con estado repetido, será siempre con un mayor valor de costo, y se descartará.