algoritmos voraces

1Algoritmos voraces

1. Mtodo general.

2. Anlisis de tiempos de ejecucin.

3. Ejemplos.

3.1. Problema de la mochila.

3.2. Planificacin de tareas.

4. Tcnicas heursticas.

4.1. El problema del viajante.

4.2. Coloracin de grafos.

2Mtodo general

Los algoritmos voraces, vidos o de avance rpido(greedy) se utilizan normalmente en problemas de

optimizacin, donde una solucin est formada por un

conjunto de elementos entre un conjunto de candidatos

(con un orden determinado o no).

El algoritmo voraz funciona por pasos:

Partimos de una solucin vaca.

En cada paso se escoge el siguiente elemento para aadir a la solucin, entre los candidatos.

Una vez tomada esta decisin no se podr deshacer.

El algoritmo acabar cuando el conjunto de elementos seleccionados constituya una solucin.

3Mtodo general

Esquema general de un algoritmo voraz:

voraz (C: conjunto_candidatos; var S: conjunto_solucin);S = mientras (C ) y no solucin (S) hacer

x = seleccionar (C) C = C - {x}si factible (S {x}) entonces

S = S {x}finmientrassi no solucin (S) entonces

devolver No se puede encontrar una solucin

En cada paso tenemos los siguientes conjuntos: Candidatos seleccionados para la solucin S. Candidatos seleccionados pero rechazados luego. Candidatos pendientes de seleccionar C.

4Mtodo general

Funciones:

solucin (S). Comprueba si un conjunto de candidatos es una solucin (independientemente de que sea ptima o no).

seleccionar (C). Devuelve el elemento ms prometedor del conjunto de candidatos pendientes (no seleccionados ni rechazados).

factible (C). Indica si a partir del conjunto de candidatos C es posible construir una solucin (posiblemente aadiendo otros elementos).

Insertar un elemento en la solucin. Adems de la insercin, puede ser necesario hacer otras cosas.

Funcin objetivo (S). Dada una solucin devuelve el coste asociado a la misma (resultado del problema de optimizacin).

5Problema del cambio de monedas

Disponemos de monedas de distintos valores: de 1, 2, 5, 10, 20 y 50 cntimos de euro, y de 1 y 2 euros.

Supondremos una cantidad ilimitada de cada una.

Construir un algoritmo que dada una cantidad P devuelva esa cantidad con monedas de estos tipos, usando un nmero mnimo de monedas.

P. ej.: para devolver 3.89 : 1 monedas de 2, 1 moneda de 1, 1 moneda de 50 c, 1 moneda de 20 c, 3 monedas de 5 c y 2 monedas de 2 c.

Podemos aplicar la tcnica voraz: en cada paso aadir una moneda nueva a la solucin actual, hasta que el valor llegue a P.


Candidatos iniciales: todos los tipos de monedas disponibles. Solucin: conjunto de monedas que suman la cantidad P.

Una solucin ser de la forma (x1, x2, x3, x4, x5, x6, x7, x8), donde xi es el nmero de monedas de tipo i. Suponemos que la moneda i vale ci.

Funciones:

solucin. El valor actual ser solucin si xici = P

objetivo. La funcin a minimizar es xi, el nmero de monedas resultante.

seleccionar. Elegir en cada paso la moneda de valor ms alto posible, pero menor que el valor que queda por devolver.

factible. Valdr siempre verdad.

En lugar de seleccionar monedas de una en una, podemos usar la divisin entera y coger todas las monedas posibles de mayor valor.


Devolver-cambio (P: integer; C: array [1..N] of integer; var X: array [1..N] of integer);act = 0para i = 1,2,...,N

X[i] = 0mientras act P

j = el mayor elemento de C tal que C[j] (P - act)si j=0 then { Si no existe ese elemento }

devolver No existe solucin;X[j] = (P - act) div C[j]act = act + C[j]*X[j]


Para este sistema monetario encuentra siempre la solucin ptima.

Puede no encontrar la solucin ptima: supongamos que tenemos monedas de 100, 90 y 1. Queremos devolver

180.

Algoritmo voraz: 1 moneda de 100 y 80 monedas de 1: total 81 monedas.

Solucin ptima: 2 monedas de 90: total 2 monedas.

Puede haber solucin y no encontrarla.

Puede no haber solucin y no lo detecta.

9Anlisis de tiempos de ejecucin

El orden de complejidad depende del nmero de candidatos, de las funciones bsicas a utilizar, del nmero de elementos de la solucin.

N: nmero de elementos de C. M: nmero de elementos de una solucin. Repetir, como mximo N veces y como mnimo M:

Comprobar si el valor actual es solucin: f(M). Normalmente O(1) O(M).

Seleccin de un elemento entre los candidatos: g(N). Entre O(1) y O(N).

La funcin factible es parecida a solucin, pero con una solucin parcial h(M).

La unin de un nuevo elemento a la solucin puede requerir otras operaciones de clculo, j(N, M).

Tiempo de ejecucin genrico: t(N,M)O(N*(f(M)+g(N)+h(M))+M*j(N, M))

En la prctica los algoritmos voraces suelen ser bastante rpidos, encontrndose dentro de rdenes de complejidad polinomiales.

10

Tenemos n objetos, cada uno con un peso (wi) y un beneficio (vi). Tambin tenemos una mochila en la que

podemos meter objetos, con una capacidad de peso

mximo M. (Supondremos todos los valores > 0)

El objetivo es llenar la mochila, maximizando el valor de los objetos transportados, y respetando la limitacin de

capacidad mxima M.

Supondremos que los objetos se pueden partir. De cada objeto i podremos coger un fraccin xi, entre 0 y 1.

Una solucin ser de la forma S = (x1, x2, ..., xn), cumpliendo:

Problema de la mochila

Restriccin Mwxn

i

ii 1

Funcin objetivo

n

i

ii vx1

11

Problema de la mochila Ejemplo: n = 3; M = 20

w = (18, 15, 10)

v = (25, 24, 15)

Solucin 1: S = (1, 2/15, 0), Valor total = 25 + 24*2/15 = 28.2

Solucin 2: S = (0, 2/3, 1), Valor total = 15 + 24*2/3 = 31

Diseo de la solucin. Podemos utilizar un algoritmo voraz para resolver el problema.

Candidatos: Cada uno de los n objetos de partida.

Funcin solucin: Tendremos una solucin si hemos introducido en la mochila el peso mximo M (o si se han acabado los objetos).

Funcin seleccionar: Escoger el objeto ms prometedor.

Funcin factible: Ser siempre cierta (podemos aadir trozos de objetos).

Aadir a la solucin: Aadir el objeto entero si cabe en la mochila, o en otro caso la proporcin del mismo que quede para completarla.

Funcin objetivo: Suma de los beneficios de cada candidato por la proporcin seleccionada del mismo.

12


Mochila (M: integer; V, W: array [1..N] of integer; var X: array [1..N] of integer);para i = 1,2,...,N

X[i] = 0peso_act = 0mientras peso_act < M

j = el mejor objeto restantesi peso_act + W[i] M

X[i] = 1peso_act = peso_act + W[i]

en otro casoX[i] = (M - peso_act)/W[i]peso_act = M

13


Criterios para seleccionar el mejor objeto de los restantes:

1. El objeto con ms beneficio vi.

2. El objeto menos pesado wi (para poder aadir

muchos objetos).

3. El objeto con mejor proporcin vi/wi (coste por unidad

de peso).

El criterio 3 obtiene siempre la solucin ptima.

14

Secuenciamiento de trabajos

Tenemos n tareas requieren un tiempo unitario en ejecutarse, y un nico procesador donde ejecutarlas.

En cualquier instante T = 1, 2, ... podemos ejecutar una nica tarea i. La ejecucin de esta tarea provocar un

beneficio gi.

Restriccin: una tarea i slo puede ejecutarse si se hace antes de un plazo di. Cada tarea tiene un plazo de

ejecucin y un beneficio dados.

En general puede que no sea posible ejecutar todas las tareas.

Objetivo: dar una planificacin de las tareas a ejecutar (i1, i2, ..., im) de forma que se maximice el beneficio obtenido:

m

k kig

1

15


Ejemplo: n = 4

g = (100, 10, 15, 27)

d = ( 2, 1, 2, 1)

Soluciones:

(1) GTOTAL = 100 (2, 1) GTOTAL = 110

(4, 3) GTOTAL = 42 (4, 1) GTOTAL = 127

Comprobar todas las posibilidades tendra una complejidad n!

Con un algoritmo voraz construimos la solucin paso a paso.

Una solucin estar formada por un conjunto de candidatos, junto con un orden de ejecucin de los mismos, S = (i1, i2, ..., im).

Funcin solucin: Tendremos la solucin cuando hayamos tratado todos los candidatos.

Funcin de seleccin: de los candidatos restantes elegir el que tenga mayor valor de beneficio.

Solucin (1,3) no ptima.

16


Funcin factible: Dada una planificacin (i1, i2, ..., ik) en un paso del algoritmo y un nuevo candidato j,

Cundo ser factible la solucin parcial que incluye a j?

Dnde debera ser colocado j dentro de la planificacin?

Solucin: buscar si existe alguna ordenacin de {i1, i2, ..., ik, j} que respete los plazos de ejecucin di. Problema: complejidad (k+1)!

Parece lgico no comprobar todas las posibles ordenaciones, sino hacer una ordenacin de forma que las tareas con plazos dims tempranos se ejecuten antes, y dejar para despus las que tengan plazos mayores.

Lema: Sea J un conjunto de k tareas, entonces existe una ordenacin factible de J (es decir que respeta los plazos) s y slo s la ordenacin S = (s1, s2, ..., sk), con ds1 ds2 ... dskes factible.

Es decir, slo es necesario probar la planificacin en orden creciente de plazo de ejecucin.

17


Estructura del algoritmo voraz:

Empezar con una secuencia vaca, con todos las tareas como candidatas.

Ordenar los candidatos segn el valor de gi.

En cada paso, hasta que se acaben los candidatos, repetir:

Elegir entre los candidatos restantes el que tenga mayor beneficio.

Comprobar si es posible aadir la tarea elegida a la solucin actual. Para ello introducir la nueva tarea en la

posicin adecuada, segn el valor de plazo d.

Si el nuevo orden (s1, s2, ..., sk) es tal que dsi i, para todo i entre 1 y k, entonces el nuevo candidato es factible. Sino

rechazar el candidato.

18

Secuenciamiento de trabajosTrabajos(in d:array[1..n] of real; out s:array[0..n] of 0..n)

d[0] = 0 ; s[0] = 0 ; k = 1 ; s[1] = 1

para i = 2,3,..,n

r = k

mientras d[s[r]]>d[i] y d[s[r]]r

r = r-1

finmientras

si d[s[r]]d[i] y d[i]>r

para l = k,k-1,..,r+1

s[l+1] = s[l]

finpara

s[r+1] = i

k = k+1

finsi

finpara

19


Orden de complejidad del algoritmo, suponiendo ntareas:

Primero, ordenar las tareas por orden creciente de plazo: O(nlog n)

Repetir para i desde 1 hasta n:

Elegir el prximo candidato: O(1).

Comprobar si la nueva planificacin es factible, y aadirlo a la solucin en caso afirmativo: O(i) en el peor caso.

En total, el algoritmo es de O(n2).

En promedio es una ordenacin por insercin: (n2).

20

Tcnicas heursticas

Existen muchos problemas para los cuales no se conocen algoritmos que puedan encontrar la solucin de forma eficiente:

problemas NP-completos.

La solucin exacta puede requerir un orden factorial o exponencial: el problema de la explosin combinatoria.

Se hace necesario utilizar algoritmos heursticos:

Un algoritmo heurstico (o simplemente heurstica) puede

producir una buena solucin (puede que la ptima) pero

tambin puede que no produzca ninguna solucin o dar una

solucin no muy buena. Normalmente, se basa en un

conocimiento intuitivo del programador sobre un determinado

problema.

La estructura de algoritmo voraz se puede utilizar para construir procedimientos heursticos: hablamos de heursticas voraces.

Objetivo: obtener buenas soluciones en un tiempo de ejecucin corto.

21

Problema: Dado un grafo no dirigido y con pesos G = (V, A), encontrar un ciclo simple de costo mnimo que pase por todos los nodos.

El problema del viajante

Es un problema NP, pero necesitamos una solucin eficiente.

Problema de optimizacin, donde la solucin est formada por un grupo de elementos en cierto orden: podemos aplicar el esquema voraz.

Posibilidades:

1) Los nodos son los candidatos. Empezar en un nodo cualquiera. En

cada paso moverse al nodo no visitado ms prximo al ltimo nodo

seleccionado.

2) Las aristas son los candidatos, pero garantizando que se forme un

ciclo.

15

30

20

25

50

45

10

35

40 55

5

4

3

1

2

22

El problema del viajante Heurstica voraz 1)

Una solucin ser un cierto orden en el conjunto de nodos (c1, c2, ..., cn): el orden de visita de los nodos.

Inicializacin: seleccionar un nodo cualquiera.

Funcin de seleccin: de los nodos candidatos seleccionar el ms prximo al ltimo (o al primero) de la secuencia actual (c1, c2, ..., ca).

Acabamos cuando tengamos n nodos.

Ejemplo.

Empezando en el nodo 1.

Solucin: (1, 4, 5, 3, 2)

Coste: 30+15+25+10+45=125

Empezando en el nodo 3.

Solucin: (5, 4, 3, 2, 1)

Coste: 15+20+10+45+50=140

2 3

41

5 15

30 25

45

10

2 3

41

5 15

20

50

45

10

23

El problema del viajante Heurstica voraz 2)

Una solucin ser un conjunto de aristas (a1, a2, ..., an-1) que formen un ciclo hamiltoniano, sin importar el orden.

Empezar con un grafo sin aristas.

Seleccin: seleccionar la arista candidata de menor coste.

Factible: una arista se puede aadir a la solucin actual si no se forma un ciclo (excepto para la ltima arista aadida) y si los nodos unidos no tienen grado mayor que 2.

Ejemplo.

Solucin: ((2, 3), (4, 5), (3, 4), (1, 2), (1, 5))

Coste = 10+15+20+45+50 = 140

Conclusiones:

Ninguno de las dos funciones de seleccin garantiza una solucin ptima. Sin embargo, normalmente ambos dan soluciones buenas, prximas a la ptima.

Posibles mejoras: buscar heursticas mejores; repetir la heurstica 1 con varios orgenes; o bien, a partir de la solucin del algoritmo intentar hacer modificaciones locales para mejorar esa solucin: bsqueda local.

2 3

41

5 15

20

50

45

10

24

Coloracin de grafos Problema: dado un grafo no dirigido, realizar una coloracin

utilizando el nmero mnimo de colores.

Coloracin: asignacin de un color a cada nodo, de forma que dos nodos unidos con un arco tengan siempre distinto color.

1 2

5

4

3

Una solucin ser un conjunto de pares de la forma (nodo, color) cumpliendo que para todo (ni, ci) y (nj, cj), si (ni, nj) es una arista del

grafo, entonces ci cj.

Podemos usar una heurstica voraz para obtener una solucin:

Empezar con un color c1, y todos los nodos sin colorear.

Para cada uno de los nodos que no tienen asignado un color, comprobar si es posible asignarles el color actual. Repetir hasta

comprobar todos los candidatos.

Si quedan nodos sin colorear, escoger otro color y volver al paso anterior.

25

Coloracin de grafos

Ejemplo.

Solucin: ((1, 1), (2, 1), (3, 2), (4, 3), (5, 3))

Nmero de colores = 3

1 2

5

4

3

La estructura bsica del esquema voraz se repite varias veces, una por cada color, hasta que todos los nodos estn coloreados.

Funcin de seleccin: seleccionar cualquier candidato restante.

Funcin factible: se puede asignar un color al candidato actual si ninguno de sus adyacentes tiene ese mismo color.

El algoritmo no garantiza la solucin ptima (en el ejemplo 2 colores).

Cul ser el tiempo de ejecucin en el peor caso?

1 2

5

4

3

algoritmos voraces

Documents