Tema 5 Algoritmos Voraces

1

Departamento de Lenguajes y Sistemas Informáticos

UNIVERSIDAD DE ALICANTE

TEMA 5ALGORITMOS VORACES

2

Algoritmos voraces (greedy)EJEMPLO INTRODUCTORIO (1)

El Problema de la Mochila (continuo). Sean n objetos con valores vi y pesos pi y una mochila con capacidad máxima de transporte de un peso P. Seleccionar un conjunto de objetos de forma que:

no sobrepase el peso P (restricción)el valor transportado sea máximo (función objetivo)

El problema se reduce a:Seleccionar un subconjunto de los objetos disponiblesQue cumpla las restriccionesMaximice la función objetivo

¿Cómo resolverlo?Selección de objetos a introducir en la mochila (secuencia de decisión)Se necesita un criterio que decida qué objeto seleccionar en cada momento (criterio de selección)

2

3

Algoritmos voraces EJEMPLO INTRODUCTORIO (2)

¿Qué criterio seguimos?

Supongamos el siguiente ejemplo:

Criterios posibles:

CRITERIO SOLUCIÓN PESO VALOR

El de mayor valor (1, 1, 1/2) 12 99

12

(6,5,2)3

(49, 40,20)

P

pn

v

=⎧⎪⎨ =⎧

=⎪ ⎨ =⎩⎩

4




Criterios posibles:



El de menor peso (5/6, 1, 1) 12 100,8

12

(6,5,2)3

(49, 40,20)

P

pn

v

=⎧⎪⎨ =⎧

=⎪ ⎨ =⎩⎩

3

5




Criterios posibles:



El de menor peso (5/6, 1, 1) 12 100,8

El de mayor valor por unidad de peso (vi/pi)

(1, 4/5, 1) 12 101

12

(6,5,2)3

(49, 40,20)

P

pn

v

=⎧⎪⎨ =⎧

=⎪ ⎨ =⎩⎩

vi/pi = ( 8’16 , 8 , 10 )

6


Tipificación del problema:

Solución = secuencia de decisionesSe expresa la solución mediante una tupla donde xi representa la decisión tomada con respecto al elemento i.

Función objetivo: (valor transportado)

Restricciones:

1

n

i ii

x p P=

≤∑

1 2, , , n iX x x x x=< … > ∈

1

Max( )n

i ii

x v=∑

[ ]0,1ix ∈0 no se selecciona el objeto 1 se selecciona el objeto completo

0 1 fracción seleccionada del objeto

i

i

i

x ix i

x i

=⎧⎪ =⎨⎪ < <⎩

1 2, , , nx x x< … >

4

7

Algoritmos voraces EJEMPLO INTRODUCTORIO (4)función MOCHILA_C (E:vector[λ];v,p:vector[R];n,P:R):vector[0,1]x

vector[λ]var P_acumulado: N

x: vector[0,1]

comienzopara i=1 hasta n hacer xi=0 fpara (1)P_acumulado=0ORDENA_ELEMENTOS_DECRECIENTE_V/P (E,v,p) (2)i=1mientras (i ≤ n) ∧ (P_acumulado < P) hacer (3)

si P_acumulado+p[i] ≤ P entoncesP_acumulado += p[i]x[i]=1

si_nox[i]=(P – P_acumulado) / p[i]P_acumulado=P

fsii=i+1

fmientrasdevuelve(x,E)

fin

n+nlogn+n→Ο(nlogn)

8


¿Conduce siempre este criterio a la obtención de la solución óptima?Teorema: Si se seleccionan los objetos por orden decreciente de v/p entonces este algoritmo encuentra la solución óptimaDemostración:

Supongamos los elementos ordenados (decreciente v/p)Sea la solución obtenida por el algoritmo

Si la solución es óptima En caso contrario:

Supongamos que j es el índice tal que

Entonces xi=1 cuando i<j ; xi=0 cuando i>jSea cualquier solución factible

Tenemos que: y y por tanto:

Por otra parte

Y dado que siempre se cumple que

Podemos concluir que :

1

ni ii

x p P=

=∑

1 : (1 )ix i i n= ∀ ≤ ≤1 2, , , nX x x x=< … >

1 1 1 1( ) ( ) ( ) ( )n n n n i

i i i i i i i i i ii i i ii

vV X V Y x v y v x y v x y pp= = = =

− = − = − = −∑ ∑ ∑ ∑

1jx <

1 2, , , nY y y y=< … >

( )( ) ( )( )i i i i i i j jx y v p x y v p− ≥ −

1

ni ii

y p P=

≤∑ 1( ) 0n

i i iix y p

=− ≥∑

5

9

Algoritmos voraces DEFINICION

Sea C un conjunto de elementosProblema de selección / optimización: aquel cuya resolución consiste en obtener un subconjunto de C (que será la solución al problema) tal que:

Satisfaga unas restricciones Optimice una cierta función objetivo

Solución factible: Aquella que cumple las restricciones del problemaSolución óptima: Solución factible que optimiza (maximiza o minimiza) la función objetivo del problema.

Los algoritmos voraces implementan una estrategia de resolución de este tipo de problemas

10

Algoritmos voraces DEFINICION

Los algoritmos voraces implementan una estrategia concreta para obtener la solución óptima al problemaPasos:

Construirá la solución por etapasEn cada etapa:

Se elige un elemento i del conjunto C para incluirlo en el subconjunto solución.

El elemento i será aquel que produce un óptimo local para esta etapa (según estado actual de la solución y sin considerar decisiones futuras)

Se comprueba si la solución sigue siendo factible al añadir i a la solución. Si lo es, el candidato i se incluye en la solución. Si no lo es, se descarta para siempre.

La decisión es irreversible. El elemento i ya nunca se vuelve a reconsiderar.Terminará el proceso cuando hayamos encontrado la solución buscada o nos quedemos sin elementos que considerar

6

11

Algoritmos voraces ESQUEMA

VORAZ (x:conjunto(λ);DP:T):conjunto(λ)var y: conjunto(λ)

decisión: λsolución: conjunto(λ)

comienzoy=xsolución=∅mientras (y ≠ ∅) ∧ (¬ES_SOLUCION(solución)) hacer

decisión=SELECCIONAR(y)si FACTIBLE(decisión,solución) entonces

solución=solución ∪ {decisión}fsiy = y – {decisión}

fmientrasdevuelve solución

fin

λ → Elemento del problemaDP → Datos del problema----------------------------ES_SOLUCION: conjunto(λ) → boolSELECCIONAR: conjunto(λ) → λFACTIBLE: λ x conjunto(λ) → bool

12

Algoritmos voraces CARACTERÍSTICAS Y ÁMBITO DE APLICACIÓN

Se obtiene algoritmos eficientes y fáciles de implementarCostes normalmente polinómicos y a menudo O(nlgn)

¿Porqué no se emplea siempre?No todos los problemas admiten esta estrategiaLa búsqueda de óptimos locales no conduce siempre a óptimos globales.Para aplicarlo con garantías a un problema ha de encontrarse un criterio de selección que encuentre siempre la solución óptima al problema. Es decir, hemos de demostrar formalmente que la función escogida consigue encontrar óptimos globales para cualquier entrada del algoritmo.

7

13

Algoritmos voraces CARACTERÍSTICAS Y ÁMBITO DE APLICACIÓN

Se aplica mucho aunque se sepa que no necesariamente encuentran la solución óptima

Cuando es preferible una solución aproximada a tiempo a una óptima demasiado tardeEquilibrio entre eficiencia (reducida complejidad) y eficacia (solución aproximada que depende del criterio de selección)

Pero ¡¡CUIDADO!!. En estos casos:Podemos obtener una solución no óptima a un problema que la tiene o incluso podemos no encontrar ninguna soluciónPara cada problema particular, hay que indagar si se pueden dar estas circunstancias y sobre todo, valorar cómo afectarán a la toma de decisiones derivada del uso del algoritmo

14

Algoritmos voraces EJEMPLOS DE APLICACIÓN

Problema de la mochila discreta (sin fraccionamiento)Problema del cambio

8

15

Algoritmos voraces PROBLEMA DE LA MOCHILA DISCRETA (sin fraccionamiento)

Sean n objetos con valores vi y pesos pi y una mochila con capacidad máxima de transporte de un peso P. Seleccionar un conjunto de objetos de forma que:

no sobrepase el peso Pel valor transportado sea máximo

Tipificación del problema:Expresaremos la solución mediante una tupla donde xi representa la decisión tomada con respecto al elemento i.

Función objetivo: (valor transportado)Restricciones:

1

n

i ii

x p P=

≤∑

1 2, , , nx x x< … >

1

Max( )n

i ii

x v=∑

{ }0,1ix ∈0 no se selecciona el objeto 1 se selecciona el objeto

i

i

x ix i=⎧

⎨ =⎩

16

Algoritmos voraces PROBLEMA DE LA MOCHILA DISCRETA (sin fraccionamiento)

Cuando no se permiten fraccionar objetos, el método voraz no resuelve el problema.No hay ningún criterio voraz (conocido) de selección que conduzca a la solución óptima.Ejemplo:

Este contraejemplo nos sirve para demostrar que el criterio óptimo para la mochila con fraccionamiento, no es óptimo en este caso .

óptima

(60,60, 20)3

(300,300,200)120

/ (5,5,10)solución: 0,1,1 beneficio 500

1,1,0 beneficio 600

pn

vPv p

X

=⎧= ⎨ =⎩==

< > → == < > → =

9

17

Algoritmos voraces PROBLEMA DEL CAMBIO

Formar una cantidad M con el menor número de monedas tomadas de un conjunto C.

La solución es una secuencia de decisiones (monedas):

•

Función objetivo

• Min |S|, Min n

Restricciones

•

Obtención de la solución: Dado que se trata de minimizar el número de monedas, se deberá tomar la de mayor valor posible (siempre que se satisfagan las restricciones).

1

( )n

ii

valor s M=

=∑

1 2, , , : n iS s s s s C=< … > ∈

18

Algoritmos voraces PROBLEMA DEL CAMBIO

Formar una cantidad M con el menor número de monedas tomadas de un conjunto C.

{ }1,5,25,50 65C M= =

50,5,5,5 4 Solución óptimaS n=< > =

{ }1,5,7, 25,50 65C M= =

{ }1,5,11,25,50 65C M= =

50,11,1,1,1,1 6 Solución factible pero no óptimaS n=< > =

{ }5,11,25,50 65C M= =

50,11,? 2 NO encuentra soluciónS n=< > =

50,5,5,5 4 No es solución vorazS n=< > =

50,7,7,1 4 Solución óptimaS n=< > =

10

19

Algoritmos voraces EJERCICIOS OBLIGATORIOS

1.- Calculo del árbol de recubrimiento de coste mínimo(Algoritmos de Prim y Kruskal)2.- El fontanero diligente3.- La asignación de tareas

20

Algoritmos voracesEJERCICIOS

1.- ARBOL DE RECUBRIMIENTO DE COSTE MINIMOPartimos de un grafo conexo, ponderado y no dirigido g = (V,A) de arcos no negativos, y deseamos encontrar el árbol de recubrimiento de g de coste mínimo. Por árbol de recubrimiento de un grafo g entendemos un subgrafo sin ciclos que contenga a todos sus vértices. En caso de haber varios árboles de coste mínimo, nos quedaremos de entre ellos con el que posea menos arcos.Existen al menos dos algoritmos muy conocidos que resuelven este problema, como son el de Prim y el de Kruskal. En ambos se va construyendo el árbol por etapas, y en cada una se añade un arco. La forma en la que se realiza esa elección es la que distingue a ambos algoritmos.

11

21


2.- EL FONTANERO DILIGENTEUn fontanero necesita hacer n reparaciones urgentes, y sabe deantemano el tiempo que le va a llevar cada una de ellas: en la tarea i-ésima tardará ti minutos. Como en su empresa le pagan dependiendode la satisfacción del cliente, necesita decidir el orden en el queatenderá los avisos para minimizar el tiempo medio de espera de losclientes.En otras palabras, si llamamos Ei a lo que espera el cliente i-ésimohasta ver reparada su avería por completo, necesita minimizar laexpresión:

1

( )n

ii

E n E=

= ∑

22


3.- LA ASIGNACION DE TAREASSupongamos que disponemos de n trabajadores y n tareas. Sea bij>0el coste de asignarle el trabajo j al trabajador i. Una asignación detareas puede ser expresada como una asignación de los valores 0 ó1 a las variables xij, donde xij = 0 significa que al trabajador i no lehan asignado la tarea j, y xij = 1 indica que sí. Una asignación válidaes aquella en la que a cada trabajador sólo le corresponde una tareay cada tarea está asignada a un trabajador.Dada una asignación válida, definimos el coste de dicha asignacióncomo:

Diremos que una asignación es óptima si es de mínimo coste.

1 1

n n

i j i ji j

x b= =∑ ∑

Documents

Tema 5 Algoritmos Voraces