Branch and Bound

Trabaja como best-first pero en cuanto se encuentra una solución sigue expandiendo los nodos de costos menores al encontrado

$\begin{algorithm} % latex2html id marker 1173\caption{Branch and Bound search}... ...dos sean de costos mayores o iguales a la meta} \end{algorithmic}\end{algorithm}$

Mejoras: usar estimaciones de los costos/distancias que faltan junto con los costos/distancias acumuladas

estim(total) = costo(camino recorrido) +
estim(camino que falta)

Las estimaciones no son perfectas, por lo que se usan sub-estimaciones

subestim(total) = costo(camino recorrido) + subestim(camino que falta)

De nuevo expande hasta que los demás tengan sub-estimaciones más grandes (e.g., subestimaciones de distancias entre ciudades pueden ser lineas rectas)

$\begin{algorithm} % latex2html id marker 1187\caption{Branch and Bound mejorad... ...dos sean de costos mayores o iguales a la meta} \end{algorithmic}\end{algorithm}$

Eduardo Morales 2009-08-25