[MÚSICA] [MÚSICA] Vamos a presentar el algoritmo A*. Las entradas para el algoritmo son las siguientes. Primero, el estado inicial, So. La segunda entrada es la función de paro y esta función de paro la definimos, como que va de los estados a, cierto falso. Una función de costo que denotamos con c y ésta nos va servir para denotar el costo de una transición de un estado a otro. Entonces c mapea los reales y también la función heurística h, la estimación del costo al objetivo, h aquí, va de S a R. El algorimo va a verificar la condición trivial. Entonces si tenemos que la función de paro se satisface para el estado inicial, terminamos. Bueno, lo siguiente, vamos a ver el costo del estado inicial va a ser 0, eso lo vamos a denotar de la siguiente manera. Vamos a agregar el estado inicial a la agenda y ahora sí vamos a entrar al ciclo de iteración. Mientras la agenda tenga elementos, vamos a repetir los siguientes pasos. Primero vamos a sacar el de menor costo. Recordemos que la agenda es una cola de prioridad, entonces a ese nodo lo vamos a llamar n. Ahora vamos a verificar si es el objetivo, y de ser así, regresamos la ruta. Bueno, si no es el objetivo, el siguiente paso es expandir el nodo. Entonces vamos a hacer para cada uno de los hijos. Los hijos son sucesores del nodo n, los vamos a denotar como n'. Estos, sucesores van a acumular el costo, entonces vamos a denotar eso de la siguiente manera. El costo acumulado del nodo n' es el costo de su nodo predecesor más el costo de ir del nodo n a n'. Bueno you que tenemos actualizado el costo del hijo, ahora sí vamos a agregarlo a la agenda siempre que no se haya expandido. Entonces, eso lo verificamos si el nodo n' no está en la lista de expandidos que vamos a denotar como X, entonces lo agregamos a la agenda. Pero entonces calculamos la función f. Esta va a ser g de n' más h de n'. Y ahora sí, lo agregamos a la agenda. [AUDIO_EN_BLANCO] Y eso es básicamente al algorimo estrella. Bueno, algo que, que es interesante es que, si nosotros hacemos h de n igual a 0, para todo n, tendríamos el algorimo de costo uniforme. Ahora, ¿qué pasa si hacemos g de n igual a 0? Bueno, eso sería equivalente a que el algoritmo no tome en cuenta los costos acumulados, ¿no? Ese algoritmo se conoce como algoritmo voraz primero en profundidad. En inglés sería Greedy Best First Search. Este algoritmo simplemente considera el costo aproximado a la meta. No considera los costos acumulados y no nos garantiza una solución óptima. [MÚSICA] [MÚSICA] [MÚSICA]
