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.
