Algoritmos y Complejidad - Algoritmos greedyprf/teaching/AyC14/downloads/Teoria/Algoritmos... · I se usan generalmente para resolver problemas deoptimización. I en general son algoritmos

Algoritmos y Complejidad

Algoritmos y ComplejidadAlgoritmos greedy

Pablo R. Fillottrani

Depto. Ciencias e Ingeniería de la ComputaciónUniversidad Nacional del Sur

Primer Cuatrimestre 2014


Algoritmos greedy

Generalidades

Problema de la mochila

Caminos más cortos

Árbol minimal de cubrimiento

Scheduling de procesos

Problema del viajante


Generalidades

Generalidades

I los algoritmos greedy son algoritmos que toman decisiones decorto alcance, basadas en información inmediatamentedisponible, sin importar consecuencias futuras.

I se usan generalmente para resolver problemas de optimización.

I en general son algoritmos eficientes y fáciles de implementar, sies que funcionan (no siempre son correctos!!).


Generalidades

Ejemplo

Problema: Dado un conjunto de monedas, ¿cuál es la mínimacantidad de monedas necesarias para pagar n centavos?.Solución greedy: Dar en lo posible monedas de denominación grande.


Generalidades

Características generales de todo algoritmo greedy

I se dispone de un conjunto C de candidatos de los cuales se debeseleccionar un subconjunto que optimice alguna propiedad.

I a medida que avanza el algoritmo, se van seleccionandocandidatos y se los coloca en el conjunto S de candidatosaceptados, o R de candidatos rechazados.


Generalidades

Características generales de todo algoritmo greedy

I existe una función esSolución() que determina si unconjunto de candidatos es una solución, no necesariamenteoptimal, del problema.

I existe una función esViable() que determina si un conjuntode candidatos es posible de ser extendido para formar unasolución, no necesariamente optimal, del problema.

I existe una función selección() que devuelve el candidatomás promisorio del conjunto de aquellos que todavía no han sidoconsiderados.


Generalidades

Esquema general para un algortimo greedy

C ::= conjunto de candidatos; S ::= {}WHILE (C != {} and ! esSolución(S))

x ::= selección(C)C ::= C - {x}IF esViable(S + {x})

S ::= S + {x}ENDIF

ENDWHILEIF esSolución(S)

RETURN SELSE

RETURN "No encontré soluciones"ENDIF




Problema: se tienen n objetos (cada objeto i tiene un peso wi y unvalor vi ); y una mochila con capacidad máxima de W . Se pretendeencontrar la manera de cargar la mochila de forma que se maximice elvalor de lo transportado y se respete su capacidad máxima.

I se quiere encontrar valores xi ,0≤ xi ≤ 1 de forma que

maximicen

∑i=1

xivi siempre quen

∑i=1

xiwi ≤W



I claramente, si ∑ni=1 wi ≤W entonces xi = 1 es optimal.

I los casos interesantes aparecen cuando ∑ni=1 wi > W .

I se puede implementar un algoritmo greedy con diversasestrategias de selección.



Algoritmo greedy

I datos de entrada: arreglos w[1..n], y v[1..n] contienencon los pesos y valores de los objetos.

I datos de salida: arreglo x[1..n] con la porción de cadaelemento que se carga en la mochila.

I x[i]=1 significa que el objeto i se lleva completo; x[i]=0que nada se lleva del objeto i; y x[i]=r, 0 < r < 1 significaque el elemento i se lleva fraccionado.



Algoritmo greedy

FOR i ::=1 TO nx[i] ::= 0

ENDFORpeso ::= 0WHILE peso<W

i ::= seleccion() //no definido cómoIF peso+w[i]<W

x[i] ::= 1; peso ::= peso+w[i]ELSE

x[i] ::= (W-peso)/w[i]; peso ::= WENDIF

ENDWHILERETURN x



I la función selección() no está especificada.I para definirla se pueden considerar tres estrategias diferentes:

1. seleccionar el elemento de mayor valor2. seleccionar el elemento de menor peso3. seleccionar el elemento que tenga mayor valor por unidad de peso



Ejemplo de aplicación

I sea n = 5,W = 100 y objetos con los siguientes pesos y valores:

obj. 1 obj. 2 obj. 3 obj. 4 obj. 5w 10 20 30 40 50v 20 30 66 40 60

I las soluciones con las tres estrategias de selección son:

obj. 1 obj. 2 obj. 3 obj. 4 obj. 5 ValorMax vi 0 0 0 1 0 0,5 0 1 146Min wi 0 1 0 1 0 1 0 1 0 156Max vi/wi 0 1 0 1 0 1 0 0 0,8 164



I el ejemplo anterior demuestra que las dos primeras estrategiasresultan en algoritmos que no son correctos.

I ¿es correcta la tercer estrategia?



Correctitud

TeoremaEl algoritmo greedy para el problema de la mochila con selección pormayor vi/wi siempre encuentra una solución optimal.

Prueba.Sea X = (x1,x2, . . . ,xn) la solución que encuentra el algoritmo, yY = (y1,y2, . . . ,yn) cualquier otra solución viable (o sea tal que∑

ni=1 yiwi ≤W ). Se prueba que valor(X)− valor(Y )≥ 0, luego X es

una solución optimal.



Análisis del tiempo de ejecución

I si se ordenan los elementos antes del ciclo greedy, la selecciónen cada iteración puede hacerse en tiempo constante y elalgoritmo es entonces de Θ(n logn), determinado por elordenamiento.

I si se usa un heap ordenado por la estrategia de selección, eltiempo de inicialización cae a Θ(n), pero cada selección obliga amantener la estructura (heapify) por lo que el algoritmo tambiénresulta de Θ(n logn).

I ¿Cuál de estas dos implementaciones es más conveniente?


Caminos más cortos

Caminos más cortos

I sea G = 〈N,A〉 un grafo dirigido, con pesos no negativos, endonde existe un nodo distinguido llamado origen.

I se define el problema de hallar los caminos más cortos desde elorigen hasta cada uno de los restantes nodos.

I consideraremos el grafo representado con una matriz deadyacencia G, con nodos 1..n, y al nodo origen etiquetado con 1.G[i, j] contiene el peso del arco (i, j) si (i, j) ∈ A, o G[i, j] = ∞ siel arco no existe.

I atacaremos primero el problema de encontrar las distanciasmínimas, y después el de los caminos que la implementan.


Caminos más cortos

Algoritmo de Dijsktra

I el algoritmo de Dijsktra es un algoritmo greedy para resolverCAMINOS MÁS CORTOS.

I consiste en mantener en S al conjunto de nodos cuyas distanciasmínimas ya se conoce, y en C a aquellos que todavía faltacalcular.

I en cada paso se selecciona el elemento de C más cercano alorigen.

I datos de entrada: G[1..n, 1..n] el grafo; se supone que elorigen es el nodo 1.

I datos de salida: d[1..n] un arreglo donde d[i] es ladistancia más corta posible entre 1 y i.


Caminos más cortos

array d[1..n]FOR i ::= 1 TO n

d[i] ::= G[1,i]ENDFORS ::= {1}; C ::= {2, ..., n}FOR j ::= 1 TO n-2

v ::= el elemento de C que minimiza d[v]S ::= S + {v}; C ::= C-{v}FOR cada w en C

d[w] ::= min{d[w],d[v]+G[v,w])ENDFOR

ENDFORRETURN d


Caminos más cortos


T (n) = an + b +n−2

∑j=1

n−j

∑k=1

c +n−2

∑j=1

d +

+n−2

∑j=1

n−j−1

∑k=1

e =

∈ Θ(n2)


Caminos más cortos

Ejemplo de aplicación

Paso v C d

0 – {2,3,4,5} [50,30,100,10]1 5 {2,3,4} [50,30,20,10]2 4 {2,3} [40,30,20,10]3 3 {2} [35,30,20,10]


Caminos más cortos

Para obtener los caminos más cortos:

I es suficiente con mantener un arreglo auxiliar p[1...n],inicializado en 1, que contiene el último nodo en el camino máscorto entre 1 y i

I luego se reemplaza la sentencia interna del segundo ciclo FORpor

IF d[w]>d[v]+G[v,w]d[w] ::= d[v]+G[v,w]p[w] ::= v

ENDIF


Caminos más cortos

I ¿cómo se obtienen los caminos más cortos a partir de p?

I ¿cambia el orden del tiempo de ejecución?


Caminos más cortos

Alternativas de implementación para el mismo algoritmo

Ejercicio:

I se pueden evitar los excesivos accesos a g[i,j] cuandoG[i,j]=∞ si el grafo es ralo (a << n2) representando al grafocon una lista de adyacencia.

I para seleccionar el próximo candidato se puede usar un heap;pero será necesario actualizarlo cada vez que se elimina elelemento y cada vez que se modifica alguna distancia en d .

I el tiempo total es de Θ((a + n) logn) = Θ(a logn). ¿porqué?


Caminos más cortos

Correctitud

TeoremaEl Algoritmo de Dijsktra es correcto.

I para la demostración se necesitará usar

DefiniciónSea S ⊂ N. Un camino desde el origen a cualquier otro nodo esespecial con respecto a S si todos los nodos intermedios pertenecena S.

I es claro que un camino especial con respecto al conjunto N detodos los nodos del grafo, es simplemente un camino del grafo.


Caminos más cortos

TeoremaEl Algoritmo de Dijsktra es correcto.

Prueba.Se prueba por inducción sobre la cantidad de iteraciones i que paratodo w ∈ N:

1. si w ∈ Si entonces d [w ]i almacena la menor longitud de uncamino desde el origen hasta w .

2. si w 6∈ Si entonces d [w ]i almacena la menor longitud de uncamino especial c.r.a. Si desde el origen hasta w .

Luego la menor longitud de un camino especial con respecto a N es lamenor longitud de cualquier camino en G, por lo que cuando elalgoritmo termina d [v ] contiene la menor longitud de cualquier caminode 1 a v .



Subgrafos de cubrimiento

I sea G = 〈N,A〉 un grafo no dirigido, conexo y con pesos.

Definiciónun subgrafo de cubrimiento es un subgrafo G′ = 〈N,A′〉,A′ ⊆ A, quetambién es conexo.

Definiciónun subgrafo de cubrimiento es minimal si la suma de los arcos de A′

es minimal entre todos los grafos de cubrimiento de G.

I los subgrafos minimales de cubrimiento son interesantes decalcular porque representan una forma óptimal de mantenerconectados todos los nodos de un grafo



Árboles minimales de cubrimientoLemaSea G un grafo no dirigido, conexo y con pesos, entonces todosubgrafo minimal de cubrimiento de G es un árbol (no tiene ciclos).

LemaSea G un grafo no dirigido, conexo y con pesos, entonces todo árbolminimal de cubrimiento de G tiene n−1 arcos, siendo n la cantidadde nodos.

LemaSea G un grafo no dirigido, conexo y con pesos, entonces siempreposee al menos un árbol minimal de cubrimiento.

I las demostraciones quedan como ejerciciosI se define entonces ÁRBOL DE CUBRIMIENTO MINIMAL al

problema computacional de, dado un tal G, encontrarle un árbolminimal de cubrimiento.



I un algoritmo greedy para solucionar este problema tendría comoconjunto de candidatos a A.

I un conjunto es una solución si contiene n−1 arcos (es un árbol ycubre todos los nodos).

I el control de viable se puede realizar controlando por la noexistencia de ciclos (los candidatos deben siempre formar unárbol).

I de acuerdo a distintas funciones de selección se definen dosalgoritmos para este problema: Kruskal y Prim.



I se puede demostrar que tanto el algoritmo de Kruskal como el dePrim son correctos ( esto es muy inusual para algoritmos greedy!)

I para ambas demostraciones de correctitud se necesitará:

Definiciónsea T ⊆ A, T es promisorio si está incluido en una solución optimal, iesi está incluido en un árbol minimal de cubrimiento.

Definiciónsea B ⊆ N, y (u,v) ∈ A. Se dice que (u,v) toca B si (u ∈ B y v 6∈ B),o (u 6∈ B y v ∈ B).



I también será necesario el siguiente lema:

Lemasea G = 〈N,A〉 un grafo no dirigido, conexo, con pesos; B ⊂ N yT ⊆ A un conjunto promisorio de arcos tal que ninguno de susmiembros toca B. Luego si (u,v) es uno de los arcos minimales quetocan B, entonces T ∪{(u,v)} también es promisorio.

Prueba.Sea G′ el árbol minimal de cubrimiento que contiene a T . Si(u,v) ∈ G′, entonces T ∪{(u,v)} es promisorio. Si (u,v) 6∈ G′ ysuponemos por el absurdo que T ∪{(u,v)} no es promisorio,entonces existe G′′ arbol de cubrimiento tal quepeso(G′′) < peso(G′).



Algoritmo de Kruskal


I el Algoritmo de Kruskal es un algoritmo greedy que resuelve elproblema de encontrar un árbol minimal de cubrimiento.

I se caracteriza por seleccionar en cada iteración el menor de losarcos todavía no considerados.

I si el arco seleccionado junto con la solución parcial es viable,entonces se incluye en la solución parcial. En caso contrario, esdescartado.

I se puede demostrar que es correcto, ie que siempre encuentraun árbol minimal de cubrimiento para un grafo no dirigido, conexoy con pesos.




Paso Arco Componentes Conexos1 – {a}{b}{c}{d}{e}{f}{g}2 (a,b) {a,b}{c}{d}{e}{f}{g}3 (b,c) {a,b,c}{d}{e}{f}{g}4 (d,e) {a,b,c}{d ,e}{f}{g}5 (f,g) {a,b,c}{d ,e}{f ,g}6 (a,d) {a,b,c,d ,e}{f ,g}7 (b,e) rechazado8 (d,g) {a,b,c,d ,e, f ,g}




Implementación

I ordenar los arcos al principio para que la selección sea eficiente.

I usar conjuntos disjuntos para controlar si un nuevo arco conectacomponentes distintos.




ordenar A en Ln ::= |N|; a ::= |A|; T ::={}D.initiate(N)REPEAT

(u,v) ::= primer arco en Leliminar (u,v) de Lcompu ::= D.find(u)compv ::= D.find(v)

IF (compu != compv)D.merge(u,v)T ::= T + {(u,v)}

ENDIFUNTIL (|T|=n-1)RETURN T

costo vecesΘ(a loga) 1

b 1Θ(n) 1

c ac a× a× ac a× n−1c n−1

c a





I el tiempo de ejecución resulta:

T (G) = Θ(a loga) + Θ(a) + Θ(n) + O((2a + n−1) log∗ n)

= Θ(a logn) + O(a log∗ n)

∈ Θ(a logn)

I considerando que:I si G es conexo n−1≤ a≤ n(n−1)/2.I K llamadas a operaciones find() y merge() en una E.D. de

conjuntos disjuntos de n elementos lleva tiempo de O(K log∗ n)I log∗ n ∈ O(logn), pero logn 6∈ O(log∗ n).




Otra implementación:

(ejercicio)

I en lugar de ordenar los arcos al principio, se usa un heapinvertido para obtener el arco minimal en cada iteración.

I disminuye el tiempo de inicialización, pero aumenta el del cuerpodel ciclo.

I el orden exacto del tiempo de ejecución obtenido es el mismo,pero las constantes ocultas por la notación asintótica seríanmenores.




Correctitud

TeoremaEl algoritmo de Kruskal es correcto.

Prueba.Por inducción sobre i , se prueba que todo Ti es promisorio usando ellema 12, considerando como B al componente conexo de alguno delos extremos del (u,v) elegido en cada iteración. Luego el Ti final esuna solución optimal porque no puede tener más arcos.



Algoritmo de Prim

I en Kruskal la función de selección elige arcos sin considerar laconexión con los arcos precedentes.

I el algoritmo de Prim se caracteriza por hacer la selección enforma local, partiendo de un nodo seleccionado y construyendoel árbol en forma ordenada.

I dado que el arco es seleccionado de aquellos que parten delárbol ya construído, la viabilidad está asegurada.

I también se puede demostrar que el algoritmo de Prim escorrecto, es decir que devuelve un árbol minimal de cubrimientoen todos los casos.



Algoritmo de Prim

Esquema general de Prim

T ::= {}B ::= {un nodo de N}WHILE (B != N)

encontrar (u,v) tal que peso((u,v)) seamínimo con u en B y v en N-B

T ::= T+{(u,v)}B ::= B+{v}

ENDWHILERETURN T



Algoritmo de Prim

Paso Arco B1 – {a}2 (a,b) {a,b}3 (b,c) {a,b,c}4 (a,d) {a,b,c,d}5 (d,e) {a,b,c,d ,e}6 (d,g) {a,b,c,d ,e,g}7 (g,f) {a,b,c,d ,e, f ,g}



Algoritmo de Prim

Implementación

I suponer G representado por una matriz de adyacencia.

I usar un arreglo dist[] para conocer cuál es la distancia a B decada nodo

I usar un arreglo nodoMasCerca[] para conocer con cuál nodo deB se tiene esa distancia.



Algoritmo de Prim

// InicializaciónB ::= {1}; T ::= {}FOR i ::=2 TO n

dist[i] ::= G[1,i]nodoMasCerca[i] ::= 1

ENDFOR

costo veces

b 1b n−1b n−1b n−1



Algoritmo de Prim

// Ciclo greedyREPEAT

k ::= nodo con dist[k]>=0 yque minimice dist[k]

min ::= dist[k]T ::= T+{(k,nodoMasCerca[k])}B ::= B+{k}; dist[k] ::= -1FOR j ::= 2 TO n

IF G[j,k]<dist[j]dist[j] ::= G[j,k]nodoMasCerca[j] ::= k

ENDIFENDFOR

UNTIL |B|=n

costo veces

O(n) n−1

Θ(1) n−1Θ(1) n−1Θ(1) n−1

Θ(1) (n−1)(n−1)Θ(1) (n−1)(n−1)Θ(1) (n−1)(n−1)

Θ(1) n−1



Algoritmo de Prim

Comparación entre Kruskal y Prim

I el tiempo de ejecución de Prim resulta T (n) ∈Θ(n2).

I resultandoAlgoritmo de Kruskal Algoritmo de Prim

Θ(a logn) Θ(n2)

I como n−1≤ a≤ n(n−1)/2 vale:I si a≈ n conviene utilizar KruskalI si a≈ n2 conviene utilizar Prim



Algoritmo de Prim

Otra implementación

(ejercicio)

I se usa un heap invertido para obtener el arco minimal en cadaiteración.

I el orden del tiempo de ejecución en este caso es Θ(a logn).

I ¿cómo cambia el tiempo de ejecución si se representa al grafocon una lista de adyacencia?



Algoritmo de Prim

Correctitud

TeoremaEl algoritmo de Prim es correcto.

Prueba.Por inducción sobre i , se prueba que todo Ti es promisorio usando ellema 12, con el mismo B del algoritmo. Luego el Ti final es unasolución optimal porque no puede tener más arcos.



Definición del problema

I se tiene un servidor (que puede ser un procesador, un cajero enun banco, un surtidor de nafta, etc.) que tiene n clientes queservir.

I el tiempo de servicio requerido por cada cliente es conocidopreviamente: ti ,1≤ i ≤ n.

I Problema: SCHEDULING se quiere encontrar una secuencia deatención al cliente que minimice el tiempo total de espera de losclientes:

Tiempo de espera =n

∑i=1

(tiempo del cliente i en el sistema)



Ejemplo

I tres clientes numerados 1,2,3 con tiempos t1 = 5, t2 = 10, t3 = 3Scheduling Tiempo de espera123: 5+ (5+10) + (5+10+3) = 38132: 5+ (5+3) + (5+3+10) = 31213: 10+ (10+5) + (10+5+3) = 43231: 10+ (10+3) + (10+3+5) = 41312: 3+ (3+5) + (3+5+10) = 29 ← optimal321: 3+ (3+10) + (3+10+5) = 34



Algoritmo greedy

I el ejemplo anterior sugiere un algoritmo greedy en donde laselección se hace en base el menor tiempo de servicio restantesiempre devuelve un algoritmo optimal.

TeoremaEl algoritmo greedy para SCHEDULING es correcto.

Prueba.ejercicio Ayuda: se prueba por el absurdo, suponiendo que existe unasolución mejor a la resuelta por el algoritmo, y se llega a unacontradicción.



I Implementación:I se ordenan los procesos por orden creciente de tiempo de

servicio, y se implementa el ciclo greedy.I como el cuerpo del ciclo greedy es de Θ(1), y el ciclo no se repite

más de n veces, el tiempo del algoritmo en general estarádominado por el tiempo del ordenamiento: Θ(n logn).

(ejercicio)

I existen numerosas variantes de este problema (con más de unprocesos, con límites a la espera de los procesos, con gananciapor la ejecución del proceso antes del límite, etc.), la mayoría delas cuales tienen algoritmos greedy correctos.



Definición del problema

I se tienen n ciudadesy las distancias entrecada par de ellas,representadas enuna matriz.

I la ciudad de origenes 1.

I Problema: VIAJANTE se quiere partir de una de ellas y visitarexactamente una vez cada ciudad, regresando al punto departida al final, y recorriendo la menor distancia posible.



Algoritmo greedy

I un algoritmo greedy obvio consiste en, empezando del punto departida, elegir en cada paso la ciudad no visitada más próxima.

I su tiempo de ejecución sería de O(n2)

I pero no es un algoritmo correcto



Ejemplo

I matriz de distancias

Ciudades 1 2 3 4 5 61 – 3 10 11 7 252 – 8 12 9 263 – 9 4 204 – 5 155 – 18

I solución greedy: 1,2,3,5,4,6,1, con distancia 60.

I solución optimal: 1,2,3,6,4,5,1, con distancia 58.



I pero, ¿no será VIAJANTE como MOCHILA donde variasestrategias de selección no funcionan, pero existe una estrategiaque sí genera un un algoritmo correcto?

I se puede demostrar que ninguna estrategia de selección directagenera un algoritmo greedy correcto en todos los casos.

I es más, para cualquier estrategia se puede encontrar ejemplosde grafos cuya solución greedy es arbitrariamente muy mala.

Documents

Algoritmos y Complejidad - Algoritmos greedyprf/teaching/AyC14/downloads/Teoria/Algoritmos... · I se usan generalmente para resolver problemas deoptimización. I en general son algoritmos