algoritmos voraces

12/07/2015

1

COMPANYLOGOTcnicas Algortmicas

Algoritmos Voraces

J. C. Carbajal L.

Paradigma algoritmo voraz1

Algunos algoritmos voraces2

Problema mochila 0-1 vs fraccional3

Problema actividad - seleccin4

D.A.I. A l g o r i t m i c a I I I

Cdigo HuffmanProblema5

COMPANYLOGOParadigma Algoritmo Voraz

Caractersticas de los algoritmos voraces: realizar una secuencia de elecciones

cada opcin es la que parece ser mejor hasta ahora, slo depende de lo que se ha hecho hasta ahora

la eleccin produce un problema ms pequeo para ser resuelto

Para la heurstica voraz resolver el problema, es que la solucin ptima para el problema grande contiene soluciones ptimas a subproblemas

J. C. Carbajal L.D.A.I. A l g o r i t m i c a I I I

COMPANYLOGOAlgoritmo Voraz: Descripcin

Normalmente usados en problemas de optimizacin.

Dado un conjunto de elementos de entrada se van seleccionando o desechando estos para formar un conjunto de elementos que cumplan con la restricciones.

Un algoritmo voraz no encuentra siempre una solucin ptima, pero muchas veces la logra.


COMPANYLOGOAlgoritmo Voraz: Forma general


COMPANYLOGOAlgoritmo Voraz: Descripcin


VENTAJAS

El algoritmo voraz arroja soluciones que estn muy cerca de las soluciones exactas.

Rapidez en hallar una solucin, cuando la encuentran.

Moderado costo computacional.

De implementacin sencilla.

DESVENTAJAS

El enfoque que aplican es muy corto y toma decisionesbasndose en la informacin que tienen disponible de modoinmediato, sin tener en cuenta los efectos que estas decisionespuedan tener en el futuro.

Se estancan en ptimos locales de las funciones que pretendenoptimizar y quiz no analizan vecindades ms all del criterio,por lo que pueden estar dejando de considerar al ptimo global.

COMPANYLOGODiseando un algoritmo Voraz

Repartir el problema para que hagamos una eleccin codiciosa (localmente ptima) y quedarnos con un subproblema

Demostrar que siempre hay una solucin ptima (globalmente) para el problema original que toma la decisin codiciosa

Demostrar que la eleccin junto con una solucin ptima al subproblema da una solucin ptima al problema original


12/07/2015

2

COMPANYLOGOAlgunos algoritmos Voraces

algoritmo mochila fraccional

cdigos de Huffman

MST algoritmo de Kruskal

Algoritmo MST de Prim

SSSP algoritmo de Dijkstra

...


COMPANYLOGOalgoritmo mochila fraccional

Hay n diversos artculos en una tienda

Artculo i:

pesa libras vale $ Un ladrn entra en la tienda

Puede transportar hasta W libras en su mochila

Qu debe tomar para maximizar el valor de su botn?


COMPANYLOGOMochila 0-1 vs Fraccional

Problema de la mochila 0-1: los artculos no se pueden dividir

el ladrn debe tomar elemento completo o dejarlo atrs

Problema de la mochila fraccional: el ladrn puede tomar los objetos parcialmente

por ejemplo, los artculos son lquidos o polvos

solucionable con un algoritmo voraz ...


COMPANYLOGOAlgoritmo voraz: mochila fraccional

Ordenar elementos en orden decreciente de valor por libra

Mientras exista espacio en la mochila (lmite de libras W) hacer considerar el siguiente elemento de la lista

ordenada

tomar tanto como sea posible (todo lo que hay o lo mucho que se ajuste a limite W)

O(n log n) tiempo de funcionamiento (para Ordenar)


COMPANYLOGOAlgoritmo voraz mochila 0-1?

Se tienen 3 artculos: artculo 1 pesa 10 libras, vale 60 ($ 6/lb)

artculo 2 pesa 20 libras, vale 100 ($ 5/lb)

artculo 3 pesa 30 libras, vale 120 ($ 4/lb)

La mochila puede contener 50 libras

estrategia voraz: tomar el artculo 1

tomar el artculo 2

no hay espacio para el artculo 3


COMPANYLOGOProblema de la mochila 0-1

Tomar el artculo 1 es un gran error globalmente, aunque se ve bien a nivel local

Utilice programacin dinmica para resolver esto en tiempo pseudo-polinomial


12/07/2015

3

COMPANYLOGOPlantilla algoritmo voraz

Voraz (entrada )

inicio

mientras que (la solucin no es completa) hacer

Seleccionar el mejor elemento x en la entrada restante ;

Ponga x en la siguiente salida;

Retire x de la entrada restante;

end mientras

fin


COMPANYLOGOEjemplo 1: Problema mochila 1

2 posibles estrategias voraces

Primera estrategia

seleccione el elemento ms valioso en cada paso que todava cabe en la mochila: la capacidad de la mochila: 15


Objeto Tamao Valor

g1g2g3g4

3

4

6

7

3

5

8

9

elegir: g4; Valor: 9; capacidad restante: 8

elegir: g4; Valor: 9; capacidad restante: 1

y no es ptima

COMPANYLOGOEjemplo 2: Problema mochila 2

Segunda estrategia

seleccione el elemento relativamente ms valioso (max (()

()))

Esto conducir a la solucin ptima en el caso descrito anteriormente. Sin embargo, esto no siempre es el caso!Capacidad de la mochila: 50


La estrategia escoger g1(valor 90)Sin embargo, el ptimo sera g3 (valor 110)

Objeto Tamao Valor

g1g2g3

30

40

50

90

100

110

3

2,5

2,2

Los algoritmos voraces no siempre proporcionan la solucin ptima. A cambio, ellos son mucho menos caros que la programacin dinmica.

La complejidad de la mochila-voraces: ()

COMPANYLOGOproblema de optimizacin

Problema con una funcin objetivo a cualquiera: Maximizar algn beneficio Minimizar algn costo

Problemas de optimizacin aparecen en tantas aplicaciones Maximizar el nmero de puestos de trabajo mediante

un recurso [Problema Actividad-Seleccin] Codificar los datos en un archivo para reducir al

mnimo su tamao [Problema Codificacin de Huffman] Recoger el mximo valor de los bienes que se ajustan

en un cubo dado [Problema de la mochila] Seleccione el peso ms pequeo de las aristas para

conectar todos los nodos en un grafo [MinimumSpanning Tree]


COMPANYLOGOAlgoritmo voraz


2 tcnicas para resolver problemas de optimizacin:

1. Programacin dinmica

2. Algoritmo voraz (Estrategia Voraz)

El enfoque voraz puede

resolver estos problemas:

Para los problemas de optimizacin:

La programacin dinmica

puede resolver estos problemas

Para algunos problemas de optimizacin, La programacin Dinmica es "excesiva" La estrategia voraz es ms simple y ms eficiente.



Concepto principal Divida el problema en varios pasos (sub-problemas)

Para cada paso tomar la mejor opcin en el momento actual (ptimo local) (eleccin voraz)

Un algoritmo voraz siempre hace la eleccin que se ve mejor en este momento

La esperanza: Una eleccin localmente ptima conducir a una solucin ptima a nivel global Para algunos problemas, funciona. Para otros, no es as

12/07/2015

4

COMPANYLOGOMochila 0-1


Los elementos no pueden ser divididos

Lo tomas o lo dejas

hallar xi tal que para todo xi = {0, 1},

i = 1, 2, .., n

wixi W y

xivi es mximo

If Xi = 1, then item i se tomar

If Xi = 0, then item i se omitir

COMPANYLOGO

Mochila 0-1 La estrategia voraz no funciona


50

Ejm 1:

1020

30

50

Item 1

Item 2

Item 3

$60 $100 $120

10

20

$60

$100

+

$160

50

20 $100

$120

+

$220

30

$6/libra $5/libra $4/libra

W

Eleccin voraz:

Calcula el beneficio por libra

Ordena los items basado en estos valores

No ptimo

COMPANYLOGOMochila 0-1 Fraccional


Los items pueden ser divididos

Puede tomar parte de ella, segn sea necesario

hallar xi tal que para todo 0

12/07/2015

5

COMPANYLOGOEjemplo de actividades compatibles


Conjunto de actividades A = {A1, A2, ., An}

Cada Ai = (Si, Ei)

A1

A2

A3

A4

A5

A6

A7

A8

Dimensin Tiempo

Ejemplos de actividades compatibles:

{A1, A3, A8}

{A1, A4, A5, A7}

{A2, A5, A8}

.



Seleccione la actividad que termina primero (el ms pequeo tiempo final) Intuicin: deja el mayor espacio vaco posible

para ms actividades

Una vez seleccionada una actividad Eliminar todas las actividades no compatibles Ellos no se pueden seleccionar

Repita el algoritmo para el resto de actividades Ya sea utilizando iteraciones o recursin



Seleccione la actividad que termina primero (el ms pequeo tiempo final) Intuicin: deja el mayor espacio vaco

posible para ms actividades

Una vez seleccionada una actividad Eliminar todas las actividades no

compatibles Ellos no se pueden seleccionar

Repita el algoritmo para el resto de actividades Ya sea utilizando iteraciones o

recursin

Esperemos que cuando fusionamos el ptimo local + la solucin al sub-problema ptimo obtenemos un ptimo global

Seleccin voraz:

Selecciona la prxima

mejor actividad

(ptimo Local)

Sub-problema: Creamos

un sub-problema para

resolver

(Encuentra el plan ptimo

despus de la actividad

seleccionada)

COMPANYLOGOEjemplo


El algoritmo voras seleccionar:

{A1, A4, A6, A7}

A1

A2

A3

A4

A5

A6

A7

A8

Time dimension

A: i 1 2 3 4 5 6 7 8

Si 1 2 7 5 10 16 21 23

Ei 4 9 15 8 18 17 27 30

Eso es una

respuesta ptima ??

Podemos encontrar

un conjunto ms

amplio?

COMPANYLOGOSolucin ptima


El Algoritmo voraz conduce a la solucin ptima

Cmo probarlo Podemos convertir cualquier otra solucin ptima

(S') a la solucin algoritmo voraz (S)

Idea: Comparacin de las actividades en S'y S de izquierda

a derecha Si coinciden en la actividad seleccionada saltar Si no coinciden

Podemos sustituir la actividad en S'por aquel en S debido a que el que est en S termina primero

COMPANYLOGOEjemplo


Solucin voraz S = {A1, A4, A6, A7}

Otra solucin S = {A1, A4, A5, A8}

A5 en S puede ser reemplazado por A6 de S (termina antes)

A8 en S puede ser reemplazado por A7 de S (termina antes)

A1

A2

A3

A4

A5

A6

A7

A8

Time dimension

A: i 1 2 3 4 5 6 7 8

Si 1 2 7 5 10 16 21 23

Ei 4 9 15 8 18 17 27 30

Por estos reemplazos, ahorramos tiempo. As, la solucin voraz debe ser al menos tan buena como cualquier otra solucin ptima

12/07/2015

6

COMPANYLOGOSolucin recursiva


Actividad-Seleccion-Recursiva(S, E, k, n)

m = k +1

While (m

12/07/2015

7

COMPANYLOGOCdigo Huffman


01

a:45 b:13 c:12 d:16 e:9 f:5

0

0

0

0

0

1

1

1 1

Los esquemas de codificacin pueden ser

representados por rboles:

Frecuencia Longitud-Fija

(en miles) cdigo word

a 45 000b 13 001c 12 010d 16 011e 9 100f 5 101

100

86 14

1401

58 28

a:45 b:13 c:12 d:16 e:9 f:5

0

0

0

0

0

1

1

1 1

Frecuencia Longitud-Variable

(en miles) cdigoword

a 45 0b 13 101c 12 100d 16 111e 9 1101f 5 1100

100

55

0125 30

0

0

0

1

1

1

a:45

14

e:9 f:5

0 1d:16b:13 c:12

01

a:45 b:13 c:12 d:16 e:9 f:5

0

0

0

0

0

1

1

1 114

0158 28

a:45 b:13 c:12 d:16 e:9 f:5

0

0

0

0

0

1

1

1 1

86 14

1401

58 28

a:45 b:13 c:12 d:16 e:9 f:5

0

0

0

0

0

1

1

1 1

No es un

rbol binario

completo

A. B. completocada nodo no hoja

tiene dos hijos

Un archivo de

100,000 caracteres.



Frecuencia Codeword

a 45000 0b 13000 101c 12000 100d 16000 111e 9000 1101f 5000 1100

100

55

0125 30

0

0

0

1

1

1

a:45

14

e:9 f:5

0 1d:16b:13 c:12

Para encontrar un cdigo ptimo para un archivo:

1. La codificacin debe ser inequvoca.

Considerar los cdigos en los que no es Codeword

tambin un prefijo de otro Codeword. => Cdigos de

prefijo

Cdigos prefijos son inequvocos.

Una vez que los Codeword son decididos, es fcil de

comprimir (codificar) y descomprimir (recepcin).

2. Tamao del archivo debe ser ms pequeo.

=> Puede ser representado por un A.B. completo.

=> Por lo general, los caracteres menos frecuentes

estn en el fondo

Sea C el alfabeto (ej. C = {'a', 'b', 'c', 'd', 'e', 'f'})

Para cada carcter c, nro. de bits para codificar todas

las ocurrencias de c = freqc*depthcTamao Archivo B(T) = cCfreqc*depthcEjm. abc es codificado

como 0101100



Cdigo Huffman (1952) fue inventado para resolverlo.

Por un enfoque Greedy.

Q: Una cola min-prioridad f:5 e:9 c:12 b:13 d:16 a:45

100

55

25 30

a:45

14

e:9 f:5

d:16b:13 c:12

c:12 b:13 d:16 a:4514

f:5 e:9

d:16

a:45

14

25

c:12 b:13

30

f:5 e:9

a:45

d:1614

25

c:12 b:13

30

55

f:5 e:9

d:16 a:4514 25

c:12 b:13f:5 e:9

Cmo encontramos el cdigo ptimo prefijo?



HUFFMAN(C)

1 Construir Q desde C

2 For i = 1 to |C|-1

3 Asignar un nuevo nodo de z

4 z.left = x = EXTRACT_MIN(Q)

5 z.right = y = EXTRACT_MIN(Q)

6 z.freq = x.freq + y.freq

7 Inserte z en Q en la posicin correcta.

8 Return EXTRACT_MIN(Q)

Q: Una cola min-prioridad f:5 e:9 c:12 b:13 d:16 a:45

c:12 b:13 d:16 a:4514

f:5 e:9

d:16 a:4514 25

c:12 b:13f:5 e:9

.Si Q se implementa como un min-

heap binario,

"Construir Q de C" es O (n)

"EXTRACT_MIN(Q)" es O(log n)

"Insertar z en Q" es O (log n)

Huffman (C) es O (n log n)

Cmo es "voraz"?

COMPANYLOGOEncontrar el cdigo ptimo

entrada: archivo de datos de caracteres y

nmero de ocurrencias de cada caracter

salida: una codificacin binaria de cada carcter de

manera que el archivo de datos puede ser representado tan eficientemente como sea posible

"cdigo ptimo"



Idea: usar cdigos cortos para los caracteres ms frecuentes y cdigos largos para menos frecuente


12/07/2015

8

COMPANYLOGOVoraz

Con el cdigo de longitud fija, fcil:

dividirse en 3, por ejemplo,

Para el cdigo de longitud variable, asegrese de que el nro del cdigo del carcter es el prefijo de otro

ninguna ambigedad


101111110100b d e a a

COMPANYLOGORepresentacin rbol binario


0 1

0 1 0

0 1 0 1 0 1

a b c d e f

Cdigo de longitud fija

costo de cdigo es la suma, sobre todos los caracteres c, de nmero de ocurrencias de c veces la profundidad de c en el rbol

COMPANYLOGORepresentacin rbol binario


0 1

f e

10

01

0 1 0 1

a

bc d

Cdigo de longitud variable

costo de cdigo es la suma, sobre todos los caracteres c, de nmero de ocurrencias de c veces la profundidad de c en el rbol

COMPANYLOGO

Algoritmo para construir el rbol de Representacin del Cdigo Huffman

Dado el conjunto C de n caracteres, c ocurre f[c] veces

inserte cada c en la cola de prioridad Q utilizando f[c] como clave

para i: = 1 hasta n-1 hacer x: = extract-min (Q) y: = extract-min (Q) hacer un nuevo nodo w/ hijo izquierdo de

(borde etiqueta 0), hijo derecho (borde etiqueta 1), y [] = [] + []

inserte en Q


COMPANYLOGOEjemplo

Char Fr eq. Char Fr eq. Char Fr eq. E 1 y 1 k 1 e 8 s 2 . 1 r 2 n 2 i 1 a 2 space 4 l 1

E

1

i

1

y

1

l

1

k

1

.

1

r

2

s

2

n

2

a

2

4

e

8

Cada char. tiene

un nodo hoja con

su frecuencia


COMPANYLOGO

Encuentra las dos frecuencias ms pequeas ... Reemplcelas con su padre

E

1

i

1

y

1

l

1

k

1

.

1

r

2

s

2

n

2

a

2

4

e

8

E 1

i 1

2


12/07/2015

9

COMPANYLOGO

E 1

i 1

y 1

l 1

k

1

.

1

r

2

s

2

n

2

a

2

4

e

8

2

y 1 l 1

2



COMPANYLOGO

E 1

i 1

k

1

.

1

r

2

s

2

n

2

a

2

4

e

8

2

y 1

l 1

2

k 1

. 1

2



COMPANYLOGO

E 1

i 1

r

2

s

2

n

2

a

2

4

e

8

2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4



COMPANYLOGO

E 1

i 1

n

2

a

2

4

e

8

2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4

n 2

a 2

4



COMPANYLOGO

E 1

i 1

4

e

8

2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4

n 2

a 2

4

E 1

i 1

2

y 1

l 1

2

4



COMPANYLOGO

E 1

i 1

4

e

8 2

y 1

l 1

2 k 1

. 1

2

r 2

s 2

4

n 2

a 2

4 4

4

k 1

. 1

2

6



12/07/2015

10

COMPANYLOGO

E 1

i 1

4

e

8 2

y 1

l 1

2

k 1

. 1

2 r 2

s 2

4

n 2

a 2

4 4 6

r 2

s 2

4

n 2

a 2

4

8



COMPANYLOGO

E 1

i 1

4

e

8 2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4

n 2

a 2

4

4 6 8

E 1

i 1

4

2

y 1

l 1

2

k 1

. 1

2

4 6

10



COMPANYLOGO

E 1

i 1

4

e

8

2

y 1

l 1

2

k 1

. 1

2 r 2

s 2

4

n 2

a 2

4 4 6

8 10

e 8

r 2

s 2

4

n 2

a 2

4

8

16



COMPANYLOGO

E 1

i 1

4

e 8 2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4

n 2

a 2

4

4 6

8

10 16



COMPANYLOGO

E 1

i 1

4

e 8

2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4

n 2

a 2

4

4 6

8

10 16

26


Ahora tenemos una sola raz ... Este es el rbol de Huffman

COMPANYLOGOVamos a analizar Huffman rbol

E 1

i 1

4

e 8

2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4

n 2

a 2

4

4 6

8

10 16

26

Todos los caracteres estn en los nodos hoja

El nmero en la raz = # de los caracteres en el archivo

Caracteres de alta frecuencia (por ejemplo, la "e") estn cerca de la raz

Caracteres de baja frecuencia estn lejos de la raz


12/07/2015

11

COMPANYLOGOVamos a asignar cdigos

Atravesar el rbol A toda arista izquierda aadir etiqueta 0

A toda arista derecha aadir etiqueta 1

El cdigo de cada carcter es su secuencia de etiqueta-raz a hojas

E 1

i 1

4

e 8

2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4

n 2

a 2

4

4 6

8

10 16

26


COMPANYLOGO

E 1

i 1

4

e 8

2

y 1

l 1

2

k 1

. 1

2

r 2

s 2

4

n 2

a 2

4

4 6

8

10 16

26

01

0

0

0

0

0

0 0

1

1

11

1

1

1

10

001 1





Vamos a asignar cdigos

COMPANYLOGO

Char Code

E 0000

i 0001

y 0010

l 0011

k 0100

. 0101

space 011

e 10

r 1100

s 1101

n 1110

a 1111

Tabla de codificacin





Vamos a asignar cdigosCOMPANY

LOGOAlgoritmo Huffman

Paso 1: Obtener Frecuencias Analiza el archivo a comprimir y contar la aparicin de cada

caracter Clasificar los caracteres en funcin de su frecuencia

Paso 2: Elaborar cdigos de rboles y Asignar Elaborar un rbol Huffman-cdigo (rbol binario) Recorrer el rbol para asignar cdigos

Paso 3: Codificar (Comprimir) Analiza el archivo de nuevo y vuelva a colocar cada

carcter por su cdigo

Paso 4: Decodificar (Descomprimir) rbol de Huffman es la clave para descomprimir el

archivo


COMPANYLOGOPaso 3: Codificar (Comprimir)


Generar el archivo

codificado

Eerie eyes seen near lake.

Archivo entrada:

Char Code

E 0000

i 0001

y 0010

l 0011

k 0100

. 0101

space 011

e 10

r 1100

s 1101

n 1110

a 1111

Tabla de codificacin

+

000010 1100 000110 .

Note que el cdigo no es prefijo de cualquier otro

cdigo Asegura que la decodificacin ser nica

COMPANYLOGOPaso 4: Decodificar (Descomprimir)


Debe tener el archivo codificado + el rbol de codificacin

Analiza el archivo codificado Para cada 0 mover hacia la izquierda en el rbol Por cada 1 mover hacia la derecha Hasta llegar a un nodo hoja Emitir ese carcter y volver a la raz

000010 1100 000110 .

+

Eerie

Generar el

archivo original

Documents

algoritmos voraces