Logistica

PAII-26: algoritmos glotones
Dr. J.B. Hayet
´ ´ CENTRO DE INVESTIGACION EN MATEMATICAS

Mayo 2008

, J.B. Hayet Programaci´n, Mayo 2008 o 1 / 26

Outline

1

Unos ejemplos

2

Unintento de caracterizaci´n o

, J.B. Hayet Programaci´n, Mayo 2008 o 2 / 26

Algoritmos glotones

a veces programaci´n din´mica puede ser demasiado para un o a problema: puede existir manera deresolverla mucho mas sencilla en particular, puede funcionar (pero puede, solo) lo de no construir una soluci´n globalmente optima sino construir la o soluci´n por elecciones localmente optimas quellegan a este o optimo global eso es el prop´sito de los algoritmos glotones o no siempre posible pero muy poderoso cuando se puede

, J.B. Hayet Programaci´n, Mayo 2008 o 3 / 26

Unos ejemplosOutline

1

Unos ejemplos

2

Un intento de caracterizaci´n o

, J.B. Hayet Programaci´n, Mayo 2008 o 4 / 26

Unos ejemplos

Ejemplo: selecci´n de actividades o
Consideremos: Nactividades ai que podamos realizar durante un recorrido tur´ ıstico cada actividad empieza en ei y termina en ti cual es el conjunto m´ximo de actividades que podemos tomar a de tal manera que los intervalosde tiempo de las actividades seleccionadas no se traslapan? Vamos a ver que existe una resoluci´n por programaci´n din´mica o o a pero que se puede hacer aun mejor con un algoritmo glot´n o

, J.B.Hayet Programaci´n, Mayo 2008 o 5 / 26

Unos ejemplos

Ejemplo: selecci´n de actividades o
Estructura de la soluci´n: o naturalmente la caracterizaci´n de los problemas tiene que o incluir lasactividades y sus rangos sean los sub-problemas i, j definidos por buscar actividades que no se traslapan entre: Tij = {ak , ti ≤ ek < tk ≤ ej } o sea “las actividades que se puedan hacer sin problemadespu´s de la i y antes de la j” e poner t0 = 0 y eN+1 = ∞
, J.B. Hayet Programaci´n, Mayo 2008 o 6 / 26

Unos ejemplos

Ejemplo: selecci´n de actividades o
Estructura de la soluci´n: o tal...