Causas y consecuencias de la perdida de valores en la sociedad venezolana

Ramificación y acotación
v Introducción: (1) Ramificación… 2
v Un primer ejemplo: El juego del 15 7
v Aplicación a problemas de
optimización 19
v Introducción: (2) … y acotación 24
v Un problema de planificación
de tareas a plazo fijo 28
v El problema de la mochila 0-1 43
v El problema del viajante
de comercio 55
v Consideraciones finales
sobre eficiencia 73
J. Campos - C.P.S.Esquemas algorítmicos - Ramificación y acotación Pág. 2
Introducción:
(1) Ramificación…
v Al igual que los métodos de búsqueda
con retroceso:
– se aplica a problemas de optimización con
restricciones,
– se genera el espacio de soluciones,
organizándolo en un árbol (en general en un
grafo),
– no se genera el espacio de soluciones completo,
sino que se podan bastantes estados.
v Terminología:– Nodo vivo: nodo del espacio de soluciones del
que no se han generado aún todos sus hijos.
– Nodo muerto: nodo del que no se van a generar
más hijos porque:
u no hay más
u no es completable, i.e., viola las restricciones
u no producirá una solución mejor que la
solución en curso
– Nodo en curso (o en expansión): nodo del que se
están generando hijos
J. Campos - C.P.S. Esquemasalgorítmicos - Ramificación y acotación Pág. 3
v Diferencia fundamental con el método
de búsqueda con retroceso:
– Búsqueda con retroceso:
Tan pronto como se genera un nuevo hijo del
nodo en curso, este hijo pasa a ser el nodo en
curso.
– Ramificación y acotación:
Se generan todos los hijos del nodo en curso
antes de que cualquier otro nodo vivo pase a ser
el nuevo nodo en curso.
v Enconsecuencia:
– Búsqueda con retroceso:
Los únicos nodos vivos son los que están en el
camino de la raíz al nodo en curso.
– Ramificación y acotación:
Puede haber más nodos vivos.
Se deben almacenar en una estructura de datos
auxiliar: lista de nodos vivos.
Introducción:
(1) Ramificación…
J. Campos - C.P.S. Esquemas algorítmicos - Ramificación y acotación Pág. 4
v Diferentes estrategias deelegir el siguiente nodo
de la lista de nodos vivos
Þ Distintos órdenes de
recorrido del árbol de
soluciones
– FIFO: la lista de nodos vivos es una cola
Þ recorrido por niveles (en anchura)
– LIFO: la lista de nodos vivos es una pila
Þ » recorr. en profundidad (D–búsqueda)
– Mínimo coste: la lista es una cola con prioridades
Þ recorrido “extraño”
La prioridad de un nodo se calcula deacuerdo
con una función de estimación que mide cuánto
de “prometedor” es un nodo.
Introducción:
(1) Ramificación…
J. Campos - C.P.S. Esquemas algorítmicos - Ramificación y acotación Pág. 5
v Primer punto clave de los métodos de
ramificación y acotación:
Encontrar un buen orden de recorrido
(o ramificación) de los nodos,
es decir,
definir una buena función de prioridad
de los nodosvivos,
para que las soluciones buenas se
encuentren rápidamente.
Introducción:
(1) Ramificación…
J. Campos - C.P.S. Esquemas algorítmicos - Ramificación y acotación Pág. 6
v El esquema es el siguiente:
repetir
expandir el nodo vivo más prometedor;
generar todos sus hijos;
una vez generados, el padre se mata;
para cada hijo hacer
si tiene un coste esperado peor que
el de la mejor soluciónen curso
entonces se mata sino
si tiene un coste esperado mejor
que el de la mejor solución en
curso y no es solución
entonces se pasa a la lista de
nodos vivos
sino {tiene un coste esperado mejor que
el de la mejor solución en curso
y es solución (el coste no es
estimado sino real)}
pasa a ser la mejor solución en
curso y se revisa toda la lista
de nodos vivos, eliminando los
queprometen algo peor de lo
conseguido fsi fsi
fpara
hasta que la lista está vacía
repetir
expandir el nodo vivo más prometedor;
generar todos sus hijos;
una vez generados, el padre se mata;
para cada hijo hacer
si tiene un coste esperado peor que
el de la mejor solución en curso
entonces se mata sino
si tiene un coste esperado mejor
que el de la mejor solución en
curso y no es...