Búsqueda AO*
PREGUNTA:
No acabo de entender el algoritmo Y/O*. ¿Podría
aclarármelo?
RESPUESTA:
En un grafo Y/O (A/O en inglés) cada nodo
representa un problema o tarea que hay que
resolver. En ocasiones, un problema puede
ser dividido en varios subproblemas. La
unión de las soluciones a los subproblemas puede
servir para encontrar la solución al problema
inicial. Por tanto, en este tipo de grafos existen
enlaces Y, además de los enlaces O que aparecían
en el caso del algoritmo Y* (A* en inglés).
Una tarea inicial queda resuelta cuando se encuentra
un subgrafo suyo donde todos los nodos terminales estén
resueltos. Por tanto, ahora en general no se busca
un camino solución, como en el caso del algoritmo A*,
sino un subgrafo solución. El coste de cada subgrafo
no es la suma de los costes de sus arcos, sino
que se calcula de forma recursiva, tal como se
indica en el libro "Problemas resueltos de IA
aplicada: búsqueda y representación".
Tal como se muestra en este libro (ver
págs. 43-48 y problemas 2.8 y 2.9), el algoritmo
YO* (AO* en inglés) repite dos operaciones
iterativamente:
- Una descendente en la que se sigue el mejor
subgrafo parcial actual y se expande uno de
los nodos hoja del mismo.
- Otra ascendente basada en la siguiente consideración:
como consecuencia de la acción descendente anterior,
se pueden haber reducido los costes de los subgrafos
que cuelgan de los nodos antecesores --en el subgrafo
parcial actual-- del nodo hoja expandido. Por tanto,
hay que averiguar si es necesario actualizar los costes
asociados a esos nodos. Para decidir qué nodo antecesor
del nodo hoja expandido hay que visitar, se utiliza un
conjunto S, que al principio sólo contiene el nodo
expandido. El proceso que hay que seguir para gestionar
el conjunto S es el siguiente:
Sacar un elemento de S tal que ninguno de sus
descendientes esté también en S. Si el coste del
subgrafo que cuelga del nodo sacado es actualizado,
se incluirán en S sus padres. El proceso anterior
se repite hasta que el conjunto S quede vacío.