Sssss ssss

Algoritmos Greedy
Dante Zanarini

25 de junio de 2009

Dante Zanarini

Algoritmos Greedy

La estrategia a seguir

Un algoritmo greedy elige, en cada paso, una soluci´n local o o ´ptima

En general, son bastante sencillos de programar

¿desafortunadamente?, no siempre conducen al ´ptimo o

Dante Zanarini

Algoritmos Greedy

Algunos ejemplos

Si tenemos que dar un vuelto,elegir la moneda (o billete) de mayor denominaci´n que no supere el monto a devolver o En el problema del ´rbol recubridor minimal, elegir la arista de a menor peso que no cierre ciclos En el problema del viajante, elegir la ciudad m´s cercana a la a actual Al armar el c´digo de Huffman, elegir los dos sub´rboles de o a menor frecuencia y “unirlos”

Dante Zanarini

Algoritmos Greedy

¿Puedosiempre aplicar una estrategia greedy?

Para un problema de optimizaci´n, es bastante f´cil encontrar o a una estrategia greedy Las estrategias greedy encuentran una soluci´n maximal al o problema. La soluci´n que tenemos no se puede mejorar, a menos, claro o est´, que volvamos atr´s y revisemos las elecciones que a a hicimos. La cuesti´n est´ en ver si esa soluci´n maximal es realmente o a om´xima a

Dante Zanarini

Algoritmos Greedy

Ejemplo, el problema de la mochila fraccionario y 0-1

1 kilo, $60

3kilos, $120 capacidad: 5 kilos 2 kilos, $100

Dante Zanarini

Algoritmos Greedy

Problemas que encuentran el optimo siguiendo alguna ´ estrategia greedy

´ Arbol recubridor minimal Algoritmo del camino m´s corto a Problema de la mochila fraccionaria Construcci´n delc´digo de Huffman o o Problemas de asignaci´n de tareas (algunos) o Problema del cambio (con algunas denominaciones)

Dante Zanarini

Algoritmos Greedy

Problemas que no encuentran el optimo siguiendo una ´ estrategia greedy

Matching Problema del viajante SAT Coloreo Paginaci´n o Problema del cambio (con algunas denominaciones)

Dante Zanarini

Algoritmos Greedy

La pregunta del d´ ıa¿C´mo me puedo dar cuenta si una estrategia o greedy encuentra el ´ptimo? o
Veremos dos enfoques sobre este asunto

Dante Zanarini

Algoritmos Greedy

Dise˜ando un algoritmo greedy optimo n ´

1

Pensemos el problema P como uno en el cual, en cada paso, hay que tomar una decisi´n (greedy) y luego resolver un o subproblema P de P. Demostramos que siempre hay una soluci´n optima del o´ problema que “toma” la elecci´n greedy. Por lo tanto, esta o elecci´n es “segura” o Demostramos que, una vez que realizamos la elecci´n greedy, o lo que queda es un subproblema tal que, si combinamos su soluci´n con la elecci´n greedy, entonces obtenemos una o o soluci´n del problema original (subestructura ´ptima!) o o

2

3

Dante Zanarini

Algoritmos Greedy

Un ejemplo

Tenemosn tareas S = {a1 , . . . , an } que requieren acceso exclusivo a un recurso. Cada tarea tiene un tiempo de comienzo si y un tiempo de finalizaci´n fi . o Dos tareas ai , aj son compatibles si si ≥ fj o sj ≥ fi Hay que elegir el m´ximo n´mero de tareas compatibles dos a a u dos

Dante Zanarini

Algoritmos Greedy

Una instancia del problema:

i si fi

1 1 4 ↑

2 3 5 ↑

3 0 6 ↑

4 5 7↑

5 3 8

6 5 9

7 6 10

8 8 11 ↑

9 8 12 ↑

10 2 13

11 12 14 ↑

Algunas soluciones maximales: {a3 , a9 , a11 } {a1 , a4 , a8 , a11 } {a2 , a4 , a9 , a11 }

Dante Zanarini

Algoritmos Greedy

Tratemos de pensar una estrategia greedy...
Inicialmente, el problema es sobre el conjunto S0 = S Para resolver Sj , elijo la tarea que termine lo antes posible (la idea es dejar lamayor cantidad de tiempo para las que quedan). Es decir, elijo i tal que fi = min {fk | ak ∈ Sj } Supongamos que es la tarea i, entonces, el subproblema que me queda es elegir el n´mero m´ximo de tareas entre u a Si = {ak ∈ S | fi ≤ sk }

1 2

3

Elecci´n greedy o Subestructura
Dante Zanarini Algoritmos Greedy

Veamos c´mo trabaja el algoritmo en el ejemplo o

i si fi

1 1 4 ↑...