ALGORITMO AO

El algoritmo AO*

1. Hagamos que G consista solamente en el nodo que representa el estado inicial. (Llamaremos a este nodo INICIO). Calculemos h'(INICIO).

2. Repetir el siguiente procedimientohasta que INICIO quede etiquetado como RESUELTO, o hasta que el valor h' de INICIO sea más grande que FUTILIDAD:
1. Trazar los arcos marcados desde INICIO y seleccionar para expansionar uno de los nodosaun no expandidos, que aparezcan en ese camino. Llamaremos al nodo seleccionado NODO.
2. Generar los sucesores de NODO. Si no hay ninguno, asignar FUTILIDAD al valor h' de NODO. Esto es equivalente adecir que NODO no es resolvible. Si hay sucesores, entonces, para cada uno (llamado sucesor) que no sea también un antecesor de NODO, hacer lo siguiente:
a. Añadir SUCESOR al grafo G.
b. Si SUCESOR esun nodo terminal, etiquetarlo RESUELTO y asignarle un valor h' igual a O.
c. Si SUCESOR no es un nodo terminal, calcular su valor h'.

3. Propagar la información recién descubierta grafo arribahaciendo lo siguiente:
Sea S un conjunto de nodos que se han marcado RESUELTO o cuyos valores h' se han cambiado, por lo que necesitan propagar sus valores hacia atrás a sus antecesores. Inicializar S alNODO. Repetir el siguiente procedimiento hasta que S esté vacío:
1. Seleccionemos un nodo de S tal que ninguno de sus descendientes en G forme parte de S. (En otras palabras, debemos estar seguros deque para cada nodo que vayamos a procesar, lo procesamos antes que ninguno de sus antecesores.) Llamaremos a este nodo ACTUAL, y lo quitaremos de S.
2. Calcular el costo de cada uno de los arcos queemergen de ACTUAL. El coste de cada arco es igual a la suma de los valores h' de cada uno de los nodos al final del arco más el coste del arco mismo. Asignemos al nuevo valor h' de ACTUAL el mínimo delos costes que acabamos de calcular para los arcos que surgen de él.
3. Marquemos el mejor camino que sale de ACTUAL marcando el arco que tiene el mínimo costo, tal como se calculó en el paso...