A*: combinación de todos

$\begin{algorithm} % latex2html id marker 1206\caption{$A^{*}$} \begin{algorith... ...dos sean de costos mayores o iguales a la meta} \end{algorithmic}\end{algorithm}$

Cuando usamos cada una?

si el tamaño de búsqueda es pequeño (rara vez), podemos hacer búsqueda exhaustiva
sin información depth-first con progressive-deepening
branch and bound en general está bien
dynamic programming cuando existen muchos posibles caminos con cruces
A* cuando podemos tener una buena subestimación

Todas estas estrategias tienen su equivalente para árboles AND-OR

Para hacer un depth first en un árbol del tipo AND - OR

$\begin{algorithm} % latex2html id marker 1225\caption{Depth-first search and u... ...backtracking} al nodo inmediato anterior \ENDIF \end{algorithmic}\end{algorithm}$

La idea se puede extender a best-first

Hay que tener cuidado con ``el mejor'' y ``el candidato''

Antes: una agenda con nodos OR
Ahora: cada nodo puede tener varios nodos asociados

En general se usan 2 funciones de estimación:

f1: evalúa sobre los nodos (como antes)
f2: evalúa sobre árboles

$\begin{algorithm} % latex2html id marker 1240\caption{Para etiquetar Soluci\'o... ...S \ELSE \STATE etiqueta N si todos son N \ENDIF \end{algorithmic}\end{algorithm}$

Similarmente para A* existe un correspondiente AO*

Como encontrar heurísticas?

analizando modelos simplificados
soluciones por descomposición: si cada submeta se puede solucionar independientement de las otras
soluciones parcialmente ordenadas
usar probabilidades

Eduardo Morales 2009-08-25