Hasta el momento, hemos considerado "optimalidad", medida como el número de pasos que le toma a la gente llegar del estado inicial al estado meta. Hoy, vamos a generalizar este tratamiento para considerar que las acciones tienen costos, y estos costos pueden ser diferentes para cada una de ellas. En un grafo pesado, la trayectoria óptima no necesariamente es la que tiene menos pasos. En este ejemplo, lo que observamos es que la trayectoria más corta tiene dos pasos, y el costo total sobre la trayectoria es la suma de los costos de cada una de las acciones. En este caso, seis más cuatro da diez. Sin embargo, existe una trayectoria más larga, que tiene cuatro pasos, cuyo costo es menor. La suma de los costos sobre la trayectoria da nueve. El algoritmo que vamos a presentar hoy se denomina "búsqueda de costo uniforme", o UCS, por sus siglas en inglés, que significan "uniform cost search". El algoritmo UCS es una modificación al algoritmo "búsqueda primero en anchura", o BFS. Aquà vamos a tener dos modificaciones al algoritmo BFS. La primera consiste en modificar la estructura de datos con la que implementamos la agenda. En BFS utilizamos una cola. En este algoritmo vamos a utilizar una cola de prioridad. En una cola de prioridad, el elemento de menor costo se encuentra al frente. La segunda modificación consiste en que el algoritmo no se detiene cuando encuentra el estado meta, sino hasta que este estado se encuentre al frente de la cola de prioridad. Vamos a ver el algoritmo UCS en funcionamiento para el ejemplo de encontrar la ruta de la estación Bellas Artes a la estación Pino Suárez del metro. Nos interesa la ruta óptima, entendida no como el número de pasos o acciones, sino como la ruta cuya suma de costo sobre la trayectoria sea mÃnima. El costo que estamos considerando es la distancia entre las estaciones. Primero, ingresamos el estado inicial a la agenda. UCS utiliza una cola de prioridad. El nodo de menor costo siempre es el primero en salir. Expandimos a "B", lo agregamos al conjunto de expandidos. Al agregar los nodos, anotamos no sólo de dónde vienen, como lo hemos estado haciendo, también indicamos con un superÃndice el costo acumulado de la trayectoria desde el estado inicial. En este caso, son las distancias directas de la estación inicial en metros. Al sacar de la agenda, el estado que sale es "A", la estación más cercana. Expandimos "A", se agrega "Z". Su costo es la suma del costo acumulado en "A", que es de 387, y la distancia de "A" a "Z", que es de 602. El siguiente nodo en salir es "H". Agregamos tres sucesores, "R", "J" y "V". Cada uno acumula el costo de "H" con el de la transición respectiva. Ahora, "S" es el de menor costo. Expandimos "S" agregando el estado "O". El estado de menor costo ahora es "G", lo sacamos. Al expandirlo, agregamos a "L" y a "R". El siguiente nodo en salir es "J". Lo expandimos, agregamos a "D". Ahora "O" es el de menor costo, lo sacamos. Al expandir a "O", agregamos a "I" y a "D". El que está al frente ahora es "Z", lo sacamos. Encontramos el estado meta "P", pero no hemos terminado, lo vamos a agregar a la agenda. Terminaremos cuando el estado meta esté al frente de la cola de prioridad. Ahora, el frente tiene a "V", lo expandimos, pero no genera sucesores que no se hayan expandido previamente. En este paso, el estado de menor costo es "L", lo sacamos. Agregamos a su sucesor, "T". Al frente queda "R", lo sacamos. Agregamos al estado "U". El siguiente al frente es "R", lo acabamos de expandir, por lo tanto no se agregan estados. Es el turno de "I". Nos encontramos nuevamente con el estado meta "P", tampoco terminamos, lo agregamos y vamos a continuar. Al frente queda "D", lo sacamos, agregamos a "C". El de menor costo es nuevamente "D", se desecha. El siguiente en salir de la agenda es "P", nuestra meta. Estamos listos para recuperar la ruta óptima. La ruta encontrada por el algoritmo es "B", "S", "O", "I", "P". Tiene un costo total de 1.575 metros. Observamos que, en la agenda, la primera ruta encontrada al estado meta es de 1.734 metros. UCS nos encontró la ruta óptima en distancia. Desde luego, en una aplicación de la vida real, tendrÃamos que incluir los costos de los transbordos para cambiar de lÃnea del metro. Aún en este pequeño mapa, se puede apreciar que UCS toma mucho tiempo y requiere de mucha memoria. Ahora, vamos a analizar el desempeño del algoritmo "búsqueda de costo uniforme". Para poder presentar el desempeño, necesitamos, primero, definir dos parámetros adicionales. El primero lo vamos a denotar con una "C" mayúscula, y representa el costo de la trayectoria más corta a la meta. El segundo, con la letra "épsilon", y lo que va a representar es el mÃnimo de los costos para las acciones en el grafo de estados-acciones. El primer aspecto que vamos a considerar es el de memoria. Observamos que la complejidad del algoritmo es "O", "b" elevado a la uno, más "C" entre "épsilon". Podemos entender "C" entre "épsilon" como el número de pasos que le tomarÃa llegar a la meta, considerando que cada una de esas acciones es de costo mÃnimo. El segundo aspecto que vamos a considerar es el tiempo. Lo que podemos ver es que el algoritmo consume tanto tiempo como memoria. Sin embargo, aquà quiero hacer una anotación. Generalmente, no se considera como parte de la complejidad del algoritmo la complejidad de las operaciones realizadas sobre la estructura de datos. Estamos valiéndonos de una cola de prioridad y sacar el elemento mÃnimo de la cola tiene un costo logarÃtmico sobre el tamaño de la estructura de datos. Entonces, estrictamente, tendrÃamos que multiplicar ese número por su logaritmo. En cuanto a la calidad, el algoritmo nos regresa a la solución óptima. Y el algoritmo, además, es completo. En este módulo, vimos un conjunto de algoritmos a los que, originalmente, denominamos "algoritmos de búsqueda ciega o búsqueda no informada". Tras el análisis asintótico de los algoritmos, identificamos que la mayorÃa de ellos consume muchos recursos computacionales, especialmente, cuando queremos soluciones óptimas. Lo que esto significa es que la aplicabilidad de los algoritmos está limitada a problemas con grafos pequeños. Si queremos trabajar con problemas más grandes, necesitamos introducir conocimiento del dominio del problema. Esto nos va a llevar a los algoritmos denominados "algoritmos de búsqueda informada". Estos algoritmos utilizan funciones heurÃsticas que los guÃan en el espacio de estados, para encontrar la meta más rápidamente.
