estructuras de datos y...

Estructuras de Datos y AlgoritmosFacultad de Informatica

Universidad Politecnica de Valencia

Curso 2009/2010

Tema 5:

Algoritmos voraces

FI– UPV: Curso 2009/2010

EDA-5

TEMA 5. Algoritmos voraces

Objetivos

• Estudio de la tecnica de diseno de algoritmos voraces.• Estudio de algunos problemas clasicos. Otros ejemplos de algoritmos voraces se veran

en el tema 6.

Contenidos

1 Introduccion. Ambito de aplicacion. Ejemplos.2 El problema de la mochila con fraccionamiento.3 Codigo Huffman.

Bibliografıa

• Introduction to Algorithms, de Cormen, Leiserson y Rivest (seccion 17.2)• Fundamentos de Algoritmia, de Brassard y Bratley (capıtulo 6)• Computer algorithms, de Horowitz, Sahni y Rajasekaran (capıtulo 4)

FI– UPV: Curso 2009/2010 Pagina 5.1

EDA-5

1. INTRODUCCION

El esquema algorıtmico de resolucion voraz o avariciosa (greedy) se aplicanormalmente a problemas de optimizacion:

Busqueda del valor optimo (maximo o mınimo) de una ciertafuncion objetivo f : X → R en un dominio X determinado.

El esquema voraz consiste en tratar de obtener un optimo global tomandodecisiones localmente optimas. Es decir:

• Cada solucion x del dominio X puede descomponerse en un conjunto deelementos mas simples x = {x1, x2, . . . , xn}• La estrategia voraz selecciona el valor de cada xi de manera irreversible, sin

volver a replantearse la eleccion de los x1, . . . , xi−1.

• Para ello elige el xi que resulte mas “prometedor” de entre los que permitenseguir formando una solucion factible.

No siempre encuentra la solucion optima, pero en ocasiones permite encontraruna solucion aproximada con un coste computacional bajo.


EDA-5

1. INTRODUCCIONEjemplos

Cajero automatico: El desglose de una cantidad de dinero con el menor numeroposible de monedas y billetes.

La mochila con fraccionamiento: La carga de un contenedor con diferentes mate-riales fraccionables que reportan beneficios distintos de modo que maximicemosel beneficio total sin exceder la cantidad maxima de carga.

La asignacion de un recurso unico a una serie de actividades de las que se conoceel tiempo de inicio y finalizacion de modo que se atienda el mayor numero detareas.

Codigo Huffman: Diseno de la codificacion de un alfabeto de modo que seminimize la longitud esperada (en bits) de los mensajes.


EDA-5

1. INTRODUCCIONEjemplos

En el proximo tema veremos algunos algoritmos de grafos que utilizan una estrategiavoraz, entre ellos:

Los algoritmos de Kruskal y de Prim para el problema del recubrimiento mınimoen un grafo no dirigido, ponderado y conexo.

El algoritmo de Dijkstra para el problema del camino mas corto de un vertice aotro en un grafo ponderado.

Existen algunos problemas que admiten solucion aproximada aunque no optimacon una estrategia voraz, entre ellos:

El coloreado de un grafo.

El problema del viajante de comercio.


EDA-5

1. INTRODUCCIONUn ejemplo detallado

Cajero automatico: Suministrar la cantidad de billetes solicitada de forma que el no totalde billetes sea mınimo. Se supone que el cajero dispone de suficientes billetes de todas lascantidades consideradas.

Ejemplo: M = 110 euros. B = {10, 20, 50}.

11× 10 (11 billetes)

5× 20 + 1× 10 (6 billetes)

2× 50 + 1× 10 (3 billetes)

La estrategia voraz consiste en ir seleccionando el billete de mayor valor:

A veces no hay solucion; p.e. si M = 30 y no hay billetes de 10A veces no la encuentra; p.e. si M = 110 y no hay billetes de 10A veces encuentra una factible pero no optima; p.e. B = {100, 500, 1100, 50} y M = 1550.La solucion que se obtendrıa es: 1× 50 + 1× 1100 + 4× 100 (6 billetes) y la optima es:1× 50 + 3× 500 (4 billetes)


EDA-5

1. INTRODUCCIONEsquema general voraz

1 // C Conjunto de elementos o candidatos2 // S Conjunto de elementos de la solucion en curso3 // solucion(S) Determina si S es solucion4 // factible(S) Determina si S completable o factible5 // seleccion(C) Selecciona un candidato6 // f Funcion objetivo7 voraz(C) {8 S = cjt_vacio;9 while (!solucion(S) && (C != cjt_vacio)) {

10 x = selecciona(C);11 C = C - {x};12 if (factible(unir(S,{x})))13 S = unir(S,{x});14 }15 if (solucion(S))16 cout << "La solucion es " << S;17 else18 cout << "No hay solucion\n";19 }


EDA-5

2. LA MOCHILA CON FRACCIONAMIENTO

Tenemos una mochila de capacidad M y N objetos para incluir en ella. Cada objeto tiene unpeso pi y un beneficio bi, 1 ≤ i ≤ N . Los objetos se pueden fraccionar.

¿Como llenar la mochila de forma que el beneficio total de loselementos que contenga sea maximo?

Planteamiento del problema

Datos del problema: capacidad M y N objetos de peso 〈p1, . . . , pN〉 y beneficio 〈b1, . . . , bN〉

Resultado: 〈x1, . . . , xN〉, donde 0 ≤ xi ≤ 1, 1 ≤ i ≤ N

Maximizar el beneficio∑N

i=1 bixi con la restriccion de que los objetos quepan en la mochila∑Ni=1 pixi ≤M


EDA-5


Criterio de seleccion de los objetos:Objeto de mayor beneficio bi

p = 〈30, 18, 15, 10〉, b = 〈25, 13, 12, 10〉 y M = 50

Step M C solucion

50 {1, 2, 3, 4} 0 0 0 0

1 20 {2, 3, 4} 1 0 0 0

2 2 {3, 4} 1 1 0 0

3 0 {4} 1 1 2/15 0

Beneficio = 25 + 13 + 2/15 · 12 = 39,6


EDA-5


Criterio de seleccion de los objetos:Objeto de menor peso pi

p = 〈30, 18, 15, 10〉, b = 〈25, 13, 12, 10〉 y M = 50

Step M C solucion

50 {1, 2, 3, 4} 0 0 0 0

1 40 {1, 2, 3} 0 0 0 1

2 25 {1, 2} 0 0 1 1

3 7 {1} 0 1 1 1

4 0 ∅ 7/30 1 1 1

Beneficio = 7/30 · 25 + 13 + 12 + 10 = 40,83


EDA-5


Criterio de seleccion de los objetos:Objeto con mayor beneficio unitario bi/pi

p = 〈30, 18, 15, 10〉, b = 〈25, 13, 12, 10〉 y M = 50

Step M C solucion

50 {1, 2, 3, 4} 0 0 0 0

1 40 {1, 2, 3} 0 0 0 1

2 10 {2, 3} 1 0 0 1

3 0 {2} 1 0 10/15 1

Beneficio = 25 + 10/15 · 12 + 10 = 42,99


EDA-5


1 using namespace std;2 #include <iostream>3 #include <queue> // cola de prioridad4 class objeto {5 public:6 string nombre;7 float peso, beneficio, bu; // bu = beneficio unitario8 objeto() {}; // constructor9 objeto(string nombre, float peso, float beneficio); // constructor

10 // al comparar dos objetos se comparan por beneficio unitario:11 bool operator < (const objeto& b) const {return bu < b.bu;}12 bool operator > (const objeto& b) const {return bu > b.bu;}13 bool operator <= (const objeto& b) const {return bu <= b.bu;}14 bool operator >= (const objeto& b) const {return bu >= b.bu;}15 bool operator == (const objeto& b) const {return bu == b.bu;}16 };17 objeto::objeto(string nombre, float peso, float beneficio) {18 this->nombre = nombre; this->peso = peso;19 this->beneficio = beneficio; bu = beneficio/peso;20 }


EDA-5


21 typedef priority_queue<objeto> cola_prioridad_objetos;22 int main(int argc, char **argv) { // programa principal23 cola_prioridad_objetos Q;24 string nombre;25 float capacidad_max,capacidad,beneficio,peso,gano,r;26 objeto obj;27 cin >> capacidad_max; // leemos los datos28 while (cin >> nombre >> peso >> beneficio)29 if (peso > 0) Q.push(objeto(nombre,peso,beneficio));30 gano = 0; capacidad = 0;31 while ((capacidad < capacidad_max) && (Q.size() > 0)) {32 obj = Q.top(); Q.pop(); // extraemos el de mayor b.u.33 r = (capacidad_max - capacidad)/obj.peso;34 if (r>1) r = 1; // como mucho el objeto entero35 capacidad += r*obj.peso;36 gano += r*obj.beneficio;37 cout << "Meto " << r << " de " << obj.nombre << endl;38 }39 cout << "Ganancia = " << gano << endl;40 }


EDA-5

3. CODIGO HUFFMAN

Es un codigo binario de longitud variable.

El objetivo consiste en representar los datos mas frecuentes con el menor numerode bits posibles.

Se utiliza para compresion de informacion.

Se trata de un algoritmo voraz

Entrada: una tabla de frecuencias de aparicion de los sımbolos del alfabeto Σ.

Salida: Un codigo binario prefijo.

Un codigo binario es prefijo si ningun sımbolo del alfabeto Σ esta codificado con unasecuencia de bits que es un prefijo de la secuencia de bits que codifica cualquier otrosımboloEl conjunto de soluciones factibles es el conjunto de arboles binarios con |Σ| hojas,cada una de las cuales corresponde a un sımbolo distinto del alfabeto. De entre todosellos nos interesa el que hace mınimo el valor de f(T ) =

∑a∈Σ dT (a) · freq(a) donde

dT (a) representa la profundidad del sımbolo a en el arbol T y freq(a) es la frecuenciadel sımbolo a.


EDA-5

3. CODIGO HUFFMAN

Supongamos que tenemos un fichero con 100.000 caracteres.

Caracter a b c d eFrecuencia (en miles) 30 25 15 20 10Codigo de longitud fija 000 001 010 011 100Codigo de longitud variable 11 10 011 00 010

Numero de bits utilizando el codigo de longitud fija: 300.000 bitsNumero de bits utilizando el codigo de longitud varible: 225.000 bits

Codigo de longitud fija:

Codificacion aace → 000000010100Descodificacion 000000010100 → 000 000 010 100 → aace

Codigo de longitud variable:

Codificacion aace → 1111011010Descodificacion 1111011010 → ?


EDA-5

3. CODIGO HUFFMAN

Descodificacion con codigo de longitud variable

d

0

0

0

0

1

1 1

1

e c

b a

A

B

C

D

1111011010 → A 1 D 1 a A 1 D 1 a A 0 B 1 C 1 c A 0 B 1 C 0 e


EDA-5

3. CODIGO HUFFMAN

TRAZA EJEMPLO

30a

25b

15c

20d

10e


EDA-5

3. CODIGO HUFFMAN

TRAZA EJEMPLO

10e

15c

20d

25b

30a


EDA-5

3. CODIGO HUFFMAN

TRAZA EJEMPLO

25b

30a

20d

10e

15c

250 1


EDA-5

3. CODIGO HUFFMAN

TRAZA EJEMPLO

10e

15c

25b

30a

20d 25

450 1

10


EDA-5

3. CODIGO HUFFMAN

TRAZA EJEMPLO

20d

25b

30a

10e

15c

45

25

55

0 1

0 1

0 1


EDA-5

3. CODIGO HUFFMAN

TRAZA EJEMPLO

25b

30a

10e

15c

100

45 55

20d 25

0

0

0

0

1

1 1

1


EDA-5

3. CODIGO HUFFMAN

1 // Huffman, pseudocodigo2 Crear un heap con n nodos (caracter, frecuencia);3

4 for (i = 1; i < n; i++) {5 Crear un nuevo nodo A;6 Asignar el minimo del heap como hijo izquierda de A;7 Eliminar el minimo del heap;8 Asignar el minimo del heap como hijo derecha de A;9 Eliminar el minimo del heap;

10 La clave de A es la suma de las claves de los hijos;11 Insertar el nodo en el heap;12 }13 return unico elemento del heap;

El coste computacional es O(n log n)


EDA-5

3. CODIGO HUFFMAN

73 dic_cadena_cadena* huffman(dic_cadena_entero& entrada) {74 dic_cadena_cadena *salida = new dic_cadena_cadena;75 if (entrada.size() == 0) return salida;76 cola_prioridad_nodos Q; pnodo uno,dos,tres,raiz; int iteracion = 1;77 cout << "Metemos los simbolos en una cola de prioridad:\n";78 dic_cadena_entero::iterator i;79 for (i = entrada.begin(); i != entrada.end(); i++) {80 uno = pnodo(new nodo(i->first, i->second));81 Q.push(uno); cout << "Inserto " << uno << endl;82 }83 while (Q.size() > 1) {84 cout<<"\nIteracion "<<iteracion<< "\n-------------\n";iteracion++;85 uno = Q.top(); Q.pop(); cout << "Extraigo " << uno << endl;86 dos = Q.top(); Q.pop(); cout << "Extraigo " << dos << endl;87 tres=pnodo(new nodo(uno,dos));88 Q.push(tres);cout<<"Inserto "<<tres<<endl;89 }90 raiz = Q.top(); raiz.n->recorrido_extraccion(string(""),salida);91 raiz.n->recorrido_liberar(); delete raiz.n;92 return salida;93 }


EDA-5

3. CODIGO HUFFMAN

13 typedef map<string,string> dic_cadena_cadena;14 typedef map<string,int> dic_cadena_entero;15 class nodo {16 public:17 string simbolo;18 int freq;19 nodo *h_izq, *h_der;20 nodo(string simbolo, int freq); // constructor para una hoja21 nodo(nodo *x, nodo *y); // constructor que junta 2 nodos22 void recorrido_extraccion(string prefijo, dic_cadena_cadena* dic);23 void recorrido_liberar(); // para liberar la memoria al final24 void recorrido_imprimir(ostream &s); // para una traza del algoritmo25 };26 nodo::nodo(string simbolo, int freq) { // constructor para una hoja27 this->simbolo = simbolo; this->freq = freq; h_izq = h_der = 0;28 }29 nodo::nodo(nodo *x, nodo *y) { // constructor que junta 2 nodos30 simbolo = string(""); // no hace falta, no se utiliza31 freq = x->freq + y->freq; h_izq = x; h_der = y;32 }


EDA-5

3. CODIGO HUFFMAN

33 void nodo::recorrido_extraccion(string prefijo, dic_cadena_cadena* dic) {34 if (h_izq == 0) // es una hoja, caso base35 (*dic)[simbolo] = prefijo;36 else { // necesariamente tiene los 2 hijos37 h_izq->recorrido_extraccion(prefijo+"0",dic);38 h_der->recorrido_extraccion(prefijo+"1",dic);39 }40 }41 void nodo::recorrido_liberar() {42 if (h_izq != 0) {43 h_izq->recorrido_liberar(); delete h_izq;44 h_der->recorrido_liberar(); delete h_der;45 }46 }47 void nodo::recorrido_imprimir(ostream &s) {48 if (h_izq != 0) {49 s << "[" << freq << "](";50 h_izq->recorrido_imprimir(s); s << ",";51 h_der->recorrido_imprimir(s); s << ")";52 } else s << "[" << freq << "]" << simbolo;53 }


EDA-5

3. CODIGO HUFFMAN

54 class pnodo { // basicamente es un puntero a nodo...55 public:56 nodo *n; // <-- unico atributo de la clase57 pnodo() {}; // un contructor58 pnodo(nodo *n) { this->n = n; } // otro constructor59 operator nodo*() { return n; } // conversion automatica a nodo*60 int freq() const { return n->freq; }61 // sobrecargamos comparaciones OJO!!! es mayor el de menor freq62 bool operator < (const pnodo& b) const {return freq() > b.freq();}63 bool operator > (const pnodo& b) const {return freq() < b.freq();}64 bool operator <= (const pnodo& b) const {return freq() >= b.freq();}65 bool operator >= (const pnodo& b) const {return freq() <= b.freq();}66 bool operator == (const pnodo& b) const {return freq() == b.freq();}67 };68 ostream& operator<< (ostream& s, pnodo& p) {69 p.n->recorrido_imprimir(s);70 return s;71 }72 typedef priority_queue<pnodo> cola_prioridad_nodos;


EDA-5

3. CODIGO HUFFMAN

94 int main(int argc, char **argv) { // programa principal95 dic_cadena_entero entrada;96 string simbolo;97 int freq;98 while (cin >> simbolo >> freq)99 entrada[simbolo] = freq;

100 dic_cadena_cadena *salida = huffman(entrada);101 dic_cadena_cadena::iterator iter;102 cout << "\nLa codificacion Huffman obtenida es:\n";103 for (iter = salida->begin(); iter != salida->end(); iter++)104 cout<<setw(5)<<left<<iter->first<<" --> "<< iter->second<<endl;105 }


estructuras de datos y...

Documents