2.2.5 Búsqueda en grafos AND/OR

Next: 2.3 Búsqueda con Información Up: 2.2 Búsqueda ciega o Previous: 2.2.4 Evitando Estados Repetidos

2.2.5 Búsqueda en grafos AND/OR

Tanto breadth-first como depth-first pueden ser adaptados para buscar en grafos AND/OR. Las diferencias están sobretodo en determinar las condiciones de terminación.

En lugar de involucrar las propiedades de un solo nodo, pueden involucrar un conjunto de nodos.

Se puede usar el algoritmo de propagación de etiquetas:

Si es nodo terminal, etiquétalo
Si en nodo OR no terminal, etiquétalo si existe al menos una etiqueta
Si en nodo AND no terminal, etiquétalo si todos estan etiquetados

Breadth-first transmite el impacto a todo el grafo, backtracking transmite a su camino de travesia (traversal path)

**Figura 2.2:** Arbol And - Or
$\begin{figure}\vspace*{1cm} \par \centerline{\hbox{ \psfig{figure=andor.ps,height=7cm} }}\end{figure}$

A veces, algunos subproblemas se encuentran repetidos en el grafo. Para ésto se tendría que guardar sus soluciones para aprovecharlas o volver a generar las soluciones.

Eduardo Morales Manzanares 2004-11-02