Inteligencia Computacional

Primero veremos los mecanismos de búsqueda a ciegas y luego veremos la búsqueda respaldada con información. La búsqueda a ciegas es aquella que si bien realiza la búsqueda utilizando los operadores (acciones) disponibles, no utiliza ningún conocimiento sobre el dominio del problema. 

La búsqueda a ciegas no utiliza conocimiento o información específica del dominio del problema.

Sigamos con el ejemplo de ir desde A hasta E. El estado inicial es A, comparamos el estado actual con la meta (E) para saber si resolvimos el problema. En este caso A no es la meta entonces debemos buscar cuales son los operadores disponibles (o acciones posibles)  en el estado A. La aplicación de los operadores al  estado A genera un nuevo conjunto de estados (en este caso C y B). La aplicación de todos los operadores a un estado la denominamos función de estados sucesores. El proceso de aplicar la función de estados sucesores a un estado se denomina expansión  del estado.

Ahora tenemos dos estados a los cuales es posible aplicarle la función de estados sucesores: C y B. Debemos elegir uno. La elección es un paso crítico en la búsqueda. La forma de elegir un estado se denomina estrategia de búsqueda Supongamos que elegimos C. Primero verificamos si C es o no la solución, como no lo es se expande  en tres estados A, D y F. Este proceso (elección, prueba, expansión) se repite hasta encontrar la solución o hasta que no haya más estados (nodos) para expandir.

Como vemos en la figura, el proceso de búsqueda va generando un árbol que denominamos árbol de búsqueda. La raíz del  árbol corresponde al estado inicial y las hojas a nodos que aún no han sido expandidos o que no tienen sucesores.

¿Cómo representar un nodo? La elección de la estructura de datos que representa un nodo en el árbol de búsqueda puede variar, básicamente nosotros trabajaremos con cinco componentes: el estado, el padre (nodo que genera éste), operador aplicado para llegar al nodo, profundidad (cuantos nodos hay desde la raíz para llegar a éste), costo del camino hasta el nodo.

Si bien asociamos nodos a estados, no son lo  mismo. Los nodos son estructuras de datos útiles computacionalmente, mientras los estados pertenecen al dominio del problema. La función de estados sucesores generará un nuevo nodo con todos sus campos completos. De todas formas, mientras no haya confusión hablaremos indistintamente de nodos y estados (ya que cada nodo corresponde a uno y sólo un estado).

Expansión de Arbol de Búsqueda

Algunas de las preguntas que deberán responderse al elegir una estrategia de búsqueda son:

• ¿Es completa? Es decir: ¿garantiza que si existe una solución la encuentra?
• ¿Cuál es el tiempo necesario para encontrar una solución?
• ¿Cuánta memoria se necesita para encontrar la solución?
• ¿Se encuentra la mejor solución?

Los ítems 2 y 3 se refieren al costo computacional asociado a determinada estrategia de búsqueda. Se debe pensar en los recursos que consumiría un árbol de búsqueda muy grande. 

La búsqueda ancho primero (breadth-first) es una de las estrategias más sencillas. Esta estrategia se basa en expandir primero los nodos que se encuentran en igual profundidad en el árbol de búsqueda.

Primero se expande la raíz (el estado inicial) luego todos los sucesores de aquel generando un nuevo conjunto de nodos, que son todos expandidos, y así sucesivamente. Se puede decir que siempre se elige un nodo de profundidad d  antes que uno de profundidad d+1. En este proceso se ignoran los estados ya expandidos anteriormente (para evitar caer en círculos).

En nuestro ejemplo de ir de A hasta E, la figura anterior muestra la expansión hasta C. Con la estrategia primero con amplitud deberíamos elegir B que se expande en E y A. Ahora el algoritmo cuenta con los nodos {E, D, F}(omitimos las A ya que fueron visitadas) y debe expandirlos, en este caso en el momento que intente expandir E verá que es la solución y finalizará la búsqueda. En gráfico vemos la continuación ancho primero del árbol de la figura anterior

Expansión ancho primero

Con respecto a las preguntas dadas anteriormente puede decirse que la búsqueda ancho primero es completa, si existe una solución la hallará. Además, si el costo de cada acción es el mismo entonces encuentra la mejor solución (la más cercana). Dado que esta estrategia empieza primero con los nodos de distancia 1, luego los de distancia 2 y así hasta llegar a la solución (si existe).

El problema de esta estrategia se encuentra en el costo computacional de la misma. Si dado un estado se producen b nuevos estados mediante la aplicación de la función de estados sucesores, entonces se dice que b es el factor de ramificación del árbol de búsqueda. Si el factor de ramificación no es igual para cada estado, se puede tomar un factor de ramificación promedio. Supongamos b dicho factor de ramificación para un árbol dado y supongamos que la solución se encuentra en la profundidad p . Entonces en la profundidad uno tenemos b nodos, en la profundidad dos tenemos b nodos más por cada uno de los anteriores b2 y en profundidad tres b3 y en profundidad cuatro b4. En definitiva la cantidad de nodos expandidos para encontrar una solución de profundidad p es:

Claramente la complejidad de la búsqueda ancho primero es exponencial tanto en tiempo como en uso de memoria. Russel y Norvig[1]  muestran una tabla ejemplo de lo que pasaría con un árbol cuyo factor de ramificación es b =10 consumiendo un milisegundo cada expansión y cien bytes cada nodo:

Claramente resulta inadmisible esperar 3500 años y usar 11.111 terabytes de memoria para resolver un problema cuya solución se haya en la profundidad 14.

Una estrategia similar es la denominada búsqueda de costo uniforme, a diferencia de ancho primero en esta búsqueda se expande siempre el nodo de menor costo de camino.  Si llamamos g(n) al costo del camino para el nodo n , se puede ver que la búsqueda ancho primero es una búsqueda de costo uniforme donde g(n) es igual a la profundidad de n. Es el caso en el cual todas las operaciones tienen igual costo. La búsqueda por costo uniforme encuentra siempre la mejor solución a no ser que el costo del camino disminuya al aumentar la profundidad del nodo.  Esto último no ocurre si el costo de los operadores no es negativo.

Esta búsqueda expande siempre el nodo más profundo en el árbol. Una vez que un nodo no puede ser expandido se vuelve hacia atrás para buscar otro nodo a ser expandido.

Como se habrá notado ésta es la estrategia que utiliza Prolog. Se expande la raíz, se toma un nodo de los recién expandidos (supongamos el primero) se expande éste, luego nuevamente se toma un nodo de estos últimos, y así hasta llegar a un nodo que es la meta o no se pueda expandir más. En este último caso se retrocede (backtracking) hasta el nodo más reciente que tenga una alternativa sin explorar.

Sigamos nuestro ejemplo anterior con profundidad primero: Se expande A que es la raíz del árbol, luego tenemos B y C como los nuevos nodos. Elegimos C para expandir, que genera D y F. Ahora a diferencia de ancho primero (donde deberíamos elegir B) elegimos uno de los nuevos (D o F), supongamos D, este genera a E. Ahora elegimos a E (de los últimos generados) y finalizamos porque es la meta.

 En el proceso descrito hemos obviado los nodos repetidos, es decir si ya fue visitado no lo generamos (por ejemplo cuando expandimos C obviamos A). La siguiente figura muestra el árbol de búsqueda para profundidad primero.

Arbol de búsqueda de profundidad primero

Puede darse el caso de que una rama del árbol de búsqueda sea infinita. En esta situación el algoritmo de ancho primero no tendría inconvenientes ya que al alejarse paso a paso cubriendo primero los más cercanos, si hay una solución entonces la encuentra, pero en la estrategia de profundidad primero si se elige una rama infinita el algoritmo de búsqueda podría no terminar nunca. Para evitar eso existe una estrategia asociada a la profundidad primero llamada búsqueda limitada por profundidad. Se establece una profundidad límite más allá de la cual no se sigue expandiendo y se fuerza el backtraking. Supongamos, en nuestro ejemplo, que no obviamos los nodos repetidos. En ese caso es posible entrar en un circuito, pero si limitamos la profundidad al número total de ciudades estaremos seguros de hallar un camino si éste existe. Ese es un ejemplo de un buen número de profundidad límite.

En la búsqueda limitada por profundidad, la estimación del límite de profundidad es un aspecto crítico ya que el algoritmo puede, si se subestima el límite, pasar a ser no completo. Por ejemplo si la distancia del camino mínimo a la solución es cinco y el límite se fija en cuatro el algoritmo de búsqueda no encuentra la solución. Por otro lado, si se sobreestima estaríamos desperdiciando recursos. En nuestro ejemplo la distancia máxima entre dos ciudades cualesquiera es 3, por lo tanto ese sería un buen límite para el problema de ir de una ciudad a otra. Ese valor se conoce como diámetro del espacio de estados. El diámetro es el máximo de los caminos mínimos entre los estados del espacio de estados.

El descenso iterativo consiste en realizar búsquedas profundidad primero sucesivas, aumentando en cada paso la profundidad límite (que comienza en uno) hasta hallar la solución. Las siguientes figuras nos muestran como se arma el árbol, en un proceso de descenso iterativo para nuestro ejemplo.

La búsqueda limitada por profundidad es completa pero no es óptima, no garantiza que el camino encontrado sea el mejor. Por otra parte la búsqueda profundidad primero tiene en general menos uso de memoria que la búsqueda ancho primero.

 Arbol de la  búsqueda Descenso Iteractivo

En este caso sólo hubo dos iteraciones, la primera con nivel de profundidad uno, expandió A. Luego con nivel de profundidad 2 se realizó la búsqueda profundidad primero y se encontró E. Esta búsqueda cuenta con las ventajas de la búsqueda ancho primero y profundidad primero. Es óptima y completa como ancho primero, pero utiliza la memoria de profundidad primero.