Hoy presentaremos los algoritmos de búsqueda informada. Los algoritmos de búsqueda informada utilizan información del dominio del problema para guiar la búsqueda durante la exploración. Para ilustrar la diferencia entre los algoritmos de búsqueda ciega y de búsqueda informada, vamos a utilizar el siguiente diagrama. En este diagrama hemos incluido el estado inicial y el estado final. Los algoritmos de búsqueda ciega de tipo DFS hacen búsquedas en profundidad. Deciden sobre una dirección de búsqueda y aumentan la profundidad en esa dirección. Es muy probable que este tipo de búsquedas no se encuentren con la solución en un tiempo razonable o, definitivamente, no encuentren la solución. Por otro lado, los algoritmos basados en el algoritmo BFS hacen una exploración exhaustiva alrededor del estado inicial, incrementando la profundidad. La desventaja de este tipo de algoritmos es que consumen mucha memoria. El problema con los algoritmos de búsqueda ciega es que sólo utilizan información de los nodos que han descubierto durante la búsqueda. AquÃ, en el diagrama, observamos que las curvas ilustran puntos que son igualmente atractivos para el algoritmo, ya sea porque tienen la misma profundidad empezando en el nodo inicial o porque tienen el mismo costo, como es el caso del algoritmo UCS. Para los algoritmos de búsqueda informada vamos a utilizar una función heurÃstica. La idea es crear un sesgo en el espacio de estados que nos oriente en la dirección del objetivo o la meta. Estas curvas anisotrópicas ilustran el tipo de sesgo que queremos lograr con los algoritmos de búsqueda informada. Las curvas se construyeron como la suma de dos cantidades. La primera es la distancia desde el nodo inicial al punto. La segunda es el producto de un pequeño escalar por la distancia al nodo meta. Este producto está simulando lo que harÃa la heurÃstica, es decir, una estimación de lo que nos falta por recorrer. Mejores aproximaciones crean sesgos más pronunciados. Estos sesgos más pronunciados son mejores para los algoritmos, pues los llevan más rápido a la meta y, por lo tanto, consumen menos recursos computacionales. Para hablar de la definición de heurÃstica, vamos a citar a Judea Pearl. En su libro "Intelligent search strategies for computer problem solving", dice lo siguiente. "Las heurÃsticas son criterios, métodos o principios para decidir cuál entre las múltiples alternativas de lÃneas de acción promete ser la más efectiva para alcanzar una meta. Representan un balance entre dos requerimientos: la necesidad de hacer los criterios simples y, al mismo tiempo, el deseo de que discriminen correctamente entre elecciones buenas y malas." Algo que queremos enfatizar de la definición es que deben ser criterios simples. Computacionalmente, esto significa que deben calcularse rápidamente. En los humanos, las heurÃsticas serÃan lo que se denomina "el sentido común", "las reglas de oro", "las buenas prácticas", etcétera. Veamos algunos ejemplos de cómo construir heurÃsticas. Consideremos como ejemplo un vehÃculo autónomo que desea encontrar la ruta óptima para llegar a la ciudad de Colima desde la Ciudad de México. Sin mayor información, tendrÃa que explorar en todas direcciones descubriendo las carreteras y sus costos en el camino. Una heurÃstica podrÃa ser implementada con el uso de una brújula. Si el agente ahora sabe que Colima está en el occidente del paÃs y que la Ciudad de México, en el centro, la brújula le proporcionarÃa información valiosa para ir en la dirección correcta. Aún mejor, heurÃstica podrÃa definirse utilizando información de un dispositivo GPS. Este dispositivo le darÃa la latitud y longitud de cualquier lugar en el que se encuentre. Si sabemos las coordenadas de Colima, ésto puede guiar la búsqueda. Una heurÃstica muy buena puede ser construida con la información de coordenadas GPS. La distancia en lÃnea recta puede servir para crear una preferencia de dirección. El agente tratarÃa de minimizar la distancia a la meta. Pasemos, ahora, al juego del 15. Si conocemos la configuración de la meta, podemos dar preferencia a una configuración sobre otra dependiendo de qué tanto se parece a esta meta. En este caso, una función heurÃstica se puede definir como el número de fichas que están fuera de su lugar respecto de la meta. Aquà vemos que la configuración de "A" tiene siete fichas fuera de su lugar, mientras que la configuración de "B" sólo tiene dos. Esto es información suficiente para el algoritmo para preferir la segunda. En este ejemplo, conocido como el mundo de bloques, el robot tiene que mover los bloques hasta conseguir la configuración objetivo. Es posible definir una heurÃstica que nos permita discriminar estados más cercanos a la meta que otros. En este caso, "A" es más cercano que "B", y la función heurÃstica deberÃa asignar un valor menor a "A" que a "B". Para los algoritmos que vamos a presentar, vamos a considerar que la función heurÃstica es una estimación del costo de un estado al estado meta. Aquà lo vamos a denotar con la letra "H". Como recomienda Pearl, la función heurÃstica debe calcularse de manera eficiente y debe ser informativa para la correcta discriminación de los estados.
