Algoritmos y Estructuras de Datos II - dis.um.esnmarin/transparencias-algoritmos-voraces-AED-II.pdf · Algoritmos y Estructuras ... Algoritmos voraces 4. Programación dinámica 5

A.E.D. II 1

Tema 3. Algoritmos voraces

Programa de teoría

Algoritmos y Estructuras de Datos II

1. Análisis de algoritmos

2. Divide y vencerás

3. Algoritmos voraces

4. Programación dinámica

5. Backtracking

6. Ramificación y poda

A.E.D. II 2


ALGORITMOS Y E. D. II


3.1. Método general

3.2. Análisis de tiempos de ejecución

3.3. Ejemplos de aplicación

3.3.1. Problema de la mochila

3.3.2. Planificación de tareas

3.4. Heurísticas voraces

3.4.1. El problema del viajante

3.4.2. Coloración de grafos

A.E.D. II 3



• Los algoritmos voraces, ávidos o de avance

rápido (en inglés greedy) se utilizan normalmente

en problemas de optimización.

– El problema se interpreta como: “tomar algunos

elementos de entre un conjunto de candidatos”.

– El orden el que se cogen puede ser importante o no.

• Un algoritmo voraz funciona por pasos:

– Inicialmente partimos de una solución vacía.

– En cada paso se escoge el siguiente elemento para

añadir a la solución, entre los candidatos.

– Una vez tomada esta decisión no se podrá deshacer.

– El algoritmo acabará cuando el conjunto de elementos

seleccionados constituya una solución.

A.E.D. II 4



• Ejemplo: “el viejo algoritmo de comprar patatas en el mercado”.

• Se puede generalizar el proceso intuitivo a un esquema algorítmico general.

• El esquema trabaja con los siguientes conjuntos de elementos:– C: Conjunto de elementos candidatos,

pendientes de seleccionar (inicialmente todos).– S: Candidatos seleccionados para la solución.– R: Candidatos seleccionados pero rechazados

después.

• ¿Cuál o cuáles son los candidatos? Depende de cada problema.

A.E.D. II 5



• Esquema general de un algoritmo voraz:

voraz (C: CjtoCandidatos; var S: CjtoSolución)

S:= Ø

mientras (C Ø) Y NO solución(S) hacer

x:= seleccionar(C)

C:= C - {x}

si factible(S, x) entonces

insertar(S, x)

finsi

finmientras

si NO solución(S) entonces

devolver “No se puede encontrar solución”

finsi

A.E.D. II 6



Funciones genéricas

• solución (S). Comprueba si un conjunto de candidatos es

una solución (independientemente de que sea óptima o no).

• seleccionar (C). Devuelve el elemento más “prometedor” del

conjunto de candidatos pendientes (no seleccionados ni

rechazados).

• factible (S, x). Indica si a partir del conjunto S y añadiendo

x, es posible construir una solución (posiblemente añadiendo

otros elementos).

• insertar (S, x). Añade el elemento x al conjunto solución.

Además, puede ser necesario hacer otras cosas.

• Función objetivo (S). Dada una solución devuelve el coste

asociado a la misma (resultado del problema de

optimización).

A.E.D. II 7



• Algunos algoritmos ya estudiados usan la técnica de avance rápido...

• Ejemplo 1. Algoritmo de Dijkstra:– Cjto. de candidatos: todos los nodos del grafo.

– Función de selección: escoger el nodo candidato con camino especial más corto.

– Función insertar: recalcular los caminos especiales.

– Solución: cuando se acaben los candidatos.

• Ejemplo 2. Algoritmo de Kruskal:– Cjto. de candidatos: el conjunto de aristas con sus pesos.

– Función de selección: escoger la arista con menor coste.

– Función factible: que no forme un ciclo en la solución actual.

– Solución: cuando hayamos seleccionado n-1 aristas.

• Ejemplo 3. Algoritmo de Prim: ¿?

A.E.D. II 8



• Problema del cambio de monedas.Construir un algoritmo que dada una cantidad P devuelva esa

cantidad usando el menor número posible de monedas.

Disponemos de monedas

con valores de 1, 2, 5, 10,

20 y 50 céntimos de euro,

1 y 2 euros (€).

SON 1,11 EUROS

AHÍ VAN 5 EUROS

TOMA EL CAMBIO,

3,89 EUROS

A.E.D. II 9



• Caso 1. Devolver 3,89 Euros.1 moneda de 2€, 1 moneda de 1€, 1 moneda de 50 c€, 1

moneda de 20 c€, 1 moneda de 10 c€ , 1 moneda de 5 c€ y

2 monedas de 2 c€. Total: 8 monedas.

• El método intuitivo se puede entender como un

algoritmo voraz: en cada paso añadir una moneda

nueva a la solución actual, hasta llegar a P.

A.E.D. II 10



Problema del cambio de monedas

• Conjunto de candidatos: todos los tipos de monedas

disponibles. Supondremos una cantidad ilimitada de

cada tipo.

• Solución: conjunto de monedas que sumen P.

• Función objetivo: minimizar el número de monedas.

Representación de la solución:

• (x1, x2, x3, x4, x5, x6, x7, x8), donde xi es el número de

monedas usadas de tipo i.

• Suponemos que la moneda i vale ci.

• Formulación: minimizar xi, sujeto a xi·ci = P, xi≥0i=1..8 i=1..8

A.E.D. II 11



Funciones del esquema:• inicialización. Inicialmente xi= 0, para todo i= 1..8

• solución. El valor actual es solución si xi·ci = P• seleccionar. ¿Qué moneda se elige en cada paso

de entre los candidatos?• Respuesta: elegir en cada paso la moneda de

valor más alto posible, pero sin sobrepasar la

cantidad que queda por devolver.

• factible. Valdrá siempre verdad.

• En lugar de seleccionar monedas de una en una,

usamos la división entera y cogemos todas las

monedas posibles de mayor valor.

A.E.D. II 12



• Implementación. Usamos una variable local act para acumular la cantidad devuelta hasta este punto.

• Suponemos que las monedas están ordenadas de menor a mayor valor.

DevolverCambio (P: entero; C: array [1..n] de entero;var X: array [1..n] de entero)

act:= 0j:= npara i:= 1,...,n hacer

X[i]:= 0mientras act P hacer

mientras (C[j] > (P - act)) AND (j>0) hacer j:= j - 1si j==0 entonces devolver “No existe solución”X[j]:= (P - act) / C[j]act:= act + C[j]*X[j]

finmientras

inicialización

no solución(X)seleccionar(C,P,X)

no factible(j)

insertar(X,j)

A.E.D. II 13



• ¿Cuál es el orden de complejidad del algoritmo?

• ¿Garantiza siempre la solución óptima?

• Para este sistema monetario sí. Pero no siempre...

• Ejemplo. 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.

– Solución óptima. 2 monedas de 90: total 2

monedas.

A.E.D. II 14



• El orden de complejidad depende de:

– El número de candidatos existentes.

– Los tiempos de las funciones básicas utilizadas.

– El número de elementos de la solución.

– ...

• Ejemplo. n: número de elementos de C. m: número de

elementos de una solución.

• Repetir, como máximo n veces y como mínimo m:– Función solución: f(m). Normalmente O(1) u O(m).

– Función de selección: g(n). Entre O(1) y O(n).

– Función factible (parecida a solución, pero con una

solución parcial): h(m).

– Inserción de un elemento: j(n, m).

A.E.D. II 15



• Tiempo de ejecución genérico:

t(n,m) O(n*(f(m)+g(n)+h(m)) + m*j(n, m))

• Ejemplos:– Algoritmos de Prim y Dijkstra: n candidatos, la función

de selección e inserción son O(n): O(n2).

– Devolución de monedas: podemos encontrar el

siguiente elemento en un tiempo constante (ordenando

las monedas): O(n).

• El análisis depende de cada algoritmo concreto.

• En la práctica los algoritmos voraces suelen ser

bastante rápidos, encontrándose dentro de

órdenes de complejidad polinomiales.

A.E.D. II 16


3.3. Ejemplos de aplicación

• Tenemos:

– n objetos, cada uno con un peso (pi) y un beneficio (bi)

– Una mochila en la que podemos meter objetos, con una

capacidad de peso máximo M.

• Objetivo: llenar la mochila, maximizando el beneficio de los

objetos transportados, y respetando la limitación de

capacidad máxima M.

• Los objetos se pueden partir en trozos.

3.3.1. Problema de la mochila no 0/1

20 Kg.

A.E.D. II 17


Datos del problema:• n: número de objetos disponibles.

• M: capacidad de la mochila.

• p = (p1, p2, ..., pn) pesos de los objetos.

• b = (b1, b2, ..., bn) beneficios de los objetos.


Representación de la solución:• Una solución será de la forma S = (x1, x2, ..., xn), con 0 ≤ xi ≤ 1,

siendo cada xi la fracción escogida del objeto i.

Formulación matemática:

• Maximizar xi bi, sujeto a la restricción xi pi ≤ M, y 0 ≤ xi ≤ 1i=1..n i=1..n

A.E.D. II 18


3.3.1. Problema de la mochila no 0/1• Ejemplo: n = 3; M = 20

p = (18, 15, 10)

b = (25, 24, 15)

• Solución 1: S = (1, 2/15, 0)

Beneficio total = 25 + 24*2/15 = 28,2

• Solución 2: S = (0, 2/3, 1)

Beneficio total = 15 + 24*2/3 = 31

20 Kg.18 kg

15 kg10 kg

PVP 25 PVP 24 PVP 15

18 kg2 kg

PVP 25 PVP 24

10 kg10 kg

PVP 24 PVP 15

A.E.D. II 19


3.3.1. Problema de la mochila no 0/1• El problema se ajusta bien a la idea de algoritmo voraz.

• Diseño de la solución:

– Candidatos: cada uno de los n objetos de partida.

– Función solución: tendremos una solución si hemos

introducido en la mochila el peso máximo M, o si se han

acabado los objetos.

– Función seleccionar: escoger el objeto más prometedor.

– Función factible: será siempre cierta (podemos añadir trozos

de objetos).

– Añadir a la solución: añadir el objeto entero si cabe, o en otro

caso la proporción del mismo que quede para completarla.

– Función objetivo: suma de los beneficios de cada candidato

por la proporción seleccionada del mismo.

• Queda por definir la función de selección. ¿Qué criterio

podemos usar para seleccionar el objeto más prometedor?

A.E.D. II 20



Mochila (M: entero; b, p: array [1..n] de entero;var X: array [1..n] de entero)

para i:= 1, ..., n hacerX[i]:= 0

pesoAct:= 0mientras pesoAct < M hacer

i:= el mejor objeto restantesi pesoAct + p[i] M entonces

X[i]:= 1pesoAct:= pesoAct + p[i]

sinoX[i]:= (M - pesoAct)/p[i]pesoAct:= M

finsifinmientras

A.E.D. II 21



• Posibles criterios para seleccionar el mejor objeto de

los restantes:

1. El objeto con más beneficio bi: argmax bii= 1, ..., n

2. El objeto menos pesado pi (para poder añadir

muchos objetos): argmin pii= 1, ..., n

3. El objeto con mejor proporción bi/pi (coste por unidad

de peso): argmax bi/pii= 1, ..., n

• ¿Cuál es el mejor criterio de selección?

• ¿Garantiza la solución óptima?

A.E.D. II 22



• Ejemplo 1: n = 4; M = 10p = (10, 3, 3, 4)

b = (10, 9, 9, 9)

– Criterio 1: S = (1, 0, 0, 0). Beneficio total = 10

– Criterio 2 y 3: S = (0, 1, 1, 1). Beneficio total = 27

• Ejemplo 2: n = 4; M = 10p = (10, 3, 3, 4)

b = (10, 1, 1, 1)

– Criterio 1 y 3: S = (1, 0, 0, 0). Beneficio total = 10

– Criterio 2: S = (0, 1, 1, 1). Beneficio total = 3

• Los criterios 1 y 2 pueden dar soluciones no muy buenas.

• El criterio 3 garantiza siempre una solución óptima.

A.E.D. II 23


3.3.1. Problema de la mochila no 0/1• Demostración (por reducción al absurdo):

Supongamos que tenemos una solución óptima x=(x1, x2, ..., xn), que incluye un objeto i, pero no incluye (o incluye con menor proporción) otro objeto j con mejor proporción:(xi > xj) y (bi/pi < bj/pj).

• Si quitamos un trozo de peso de i y lo metemos de jentonces obtendríamos más beneficio. Por ejemplo, si quitamos un peso r, con 0 < r xi·pi , r (1-xj)·pj:

bnuevo = bantiguo - r*bi/pi + r*bj/pj =

bantiguo + r*(bj/pj - bi/pi) > bantiguo

• ¿Cuánto es el orden de complejidad del algoritmo?

• ¿Cómo calcular el beneficio total?

• ¿Qué ocurre si no se pueden partir los objetos?

A.E.D. II 24



Problema de secuenciamiento de trabajos con plazos:

• Tenemos un procesador y n tareas disponibles.

• Todas las tareas requieren 1 unidad de tiempo para

ejecutarse y tienen:– bi: beneficio obtenido si se ejecuta la tarea i.

– di: plazo máximo de ejecución de la tarea i.

• Significado: la tarea i sólo puede ejecutarse si se hace

en un instante igual o anterior a di. En ese caso se

obtiene un beneficio bi.

• En general puede que no sea posible ejecutar todas las

tareas.

A.E.D. II 25



• Objetivo: dar una planificación de las tareas a ejecutar

(s1, s2, ..., sm) de forma que se maximice el beneficio

total obtenido.

btotal = bsii=1..m

T 1 2 3 4

S s1 s2 s3 s4

• Problemas a resolver:

1) ¿Qué tareas ejecutar?

2) ¿En qué orden ejecutarlas?

A.E.D. II 26



• Ejemplo: n = 4

b = (100, 10, 15, 27)

d = ( 2, 1, 2, 1)

• Posibles soluciones:

T 1 2

S 1 3

b 100 15

d 2 2

btotal= 115

T 1 2

S 4 3

b 27 15

d 1 2

btotal= 42

T 1 2

S 1 4

b 100 27

d 2 1

No factible

T 1 2

S 4 1

b 27 100

d 1 2

btotal = 127

• Algoritmo sencillo: comprobar todos los posibles órdenes

de las tareas y quedarse con el mejor (y que sea factible).

• Tendría una complejidad de Ω(n!) ...

A.E.D. II 27



• Aplicamos avance rápido: empezamos con una

planificación sin tareas y vamos añadiéndolas paso a

paso.

• Una solución estará formada por un conjunto de

candidatos, junto con un orden de ejecución de los

mismos.

• Representación de la solución: S = (s1, s2, ..., sm),

donde si es la tarea ejecutada en el instante i.

• Función de selección: de los candidatos restantes

elegir el que tenga mayor valor de beneficio: argmax bi.

• ¿Cómo es la función factible (S, x)?

A.E.D. II 28



• ¿Dónde debería ser colocada x dentro de la planificación?

• ¿Es factible la solución parcial que incluye a x?

• Idea 1: Probar todas las posibles colocaciones. MAL

• Idea 2: Ordenar las tareas por orden de plazo dx. Que las tareas con plazos más tempranos se ejecuten antes. BIEN

T 1 2 3 4

S s1 s2 s3 s4

b bs1 bs2 bs3 bs4

d ds1 ds2 ds3 ds4

x

bx

dx

Planifi-

cación

actual

A.E.D. II 29



• Lema: sea J un conjunto de k tareas. Existe una

ordenación factible de J (es decir que respeta los plazos)

si y sólo si la ordenación S = (s1, s2, ..., sk), con ds1 ds2

... dsk es factible.

• Es decir, sólo es necesario probar la planificación en orden

creciente de plazo de ejecución, comprobando que cada

dsi i (la tarea ejecutada en la i-ésima posición tiene un

plazo de i o más).

T 1 2 ... k

S s1 s2 ... sk

b bs1 bs2 ... bsk

d ds1 ds2 ... dsk≤ ≤ ≤

A.E.D. II 30


3.3.2. Planificación de tareas• Demostración del lema:

) Si el orden S (antes definido) es factible entonces

existe una ordenación factible de J: trivial.

) Si existe alguna ordenación factible de J, S es factible.

– Supongamos (por reducción al absurdo) que existe esa

ordenación factible pero que S no es factible.

– Entonces debe existir una tarea sr tal que dsr < r.

– Puesto que las r-1 tareas anteriores tienen dsi dsr < r, habrán

r tareas cuyo plazo es menor que r.

– En conclusión, no puede existir ningún orden de las tareas J,

de forma que se ejecuten dentro de su plazo Contradicción.

T 1 2 r ...

S s1 s2 sr ...

d ds1 ds2 dsr ...≤ ≤ ≤

A.E.D. II 31



Estructura del algoritmo voraz:

• Inicialización: empezar con una secuencia vacía, con todas

las tareas como candidatas.

• Ordenar las tareas según el valor de bi.

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

– Selección: elegir entre los candidatos restantes el que

tenga mayor beneficio.

– Factible: introducir la nueva tarea en la posición

adecuada, según los valores 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. Añadirlo a la solución.

• En otro caso, rechazar el candidato.

A.E.D. II 32



• Ejemplo: n=6

b = (20, 15, 10, 7, 5, 3)

d = ( 3, 1, 1, 3, 1, 3)

• Es posible demostrar que este algoritmo obtiene la

solución óptima.

• Idea: suponer una solución óptima y comprobar

que tiene el mismo beneficio que la calculada por

el algoritmo.

T 1 2 4

S 2 4 1

b 15 7 20

d 1 3 3

A.E.D. II 33



• Orden de complejidad del algoritmo, suponiendo

n tareas:– Primero, ordenar las tareas por orden creciente de plazo:

O(n·log n)

– Repetir para i desde 1 hasta n:

• Elegir el próximo candidato: O(1)

• Comprobar si la nueva planificación es factible, y

añadirla a la solución en caso afirmativo: O(i) en el

peor caso.

– En total, el algoritmo es un O(n2)

• Ejercicio: en lugar de desplazar tareas, planificar cada

tarea lo más tarde posible según su plazo y la

ordenación actual.

A.E.D. II 34



• Problemas NP-completos: la solución exacta puede requerir órdenes factoriales o exponenciales (el problema de la explosión combinatoria).

• Objetivo: obtener “buenas” soluciones en un tiempo de ejecución corto (razonable).

• Algoritmos de aproximación: garantizan una solución más o menos buena (o una cierta aproximación respecto al óptimo).

• Un tipo son los algoritmos heurísticos1: algoritmo basado en el conocimiento “intuitivo” o “experto” del programador sobre determinado problema.

1DRAE. Heurística: arte de inventar.

A.E.D. II 35



• La estructura de algoritmos voraces se puede utilizar

para construir procedimientos heurísticos: hablamos

de heurísticas voraces.

• La clave: diseñar buenas funciones de selección.

PROBLEMA COMPLEJO

Algoritmo

exactoBacktracking

Fuerza bruta

Ram. y Poda

Algoritmo

heurístico 1Heur. voraz

Alg. genético

Alg. probabilista

Algoritmo

heurístico 2Solución

inmediata o

fija

+ tiempo - tiempo

+ preciso - preciso

A.E.D. II 36


• Problema: dado un grafo no dirigido, completo y con pesos G = (V, A), encontrar un ciclo de coste mínimo que pase por todos los nodos.

• Es un problema NP-completo, pero necesitamos una

solución eficiente.

• Problema de optimización, la solución está formada por

un conjunto de elementos en cierto orden: podemos

aplicar el esquema voraz.


1 2

35

4

30

10

A.E.D. II 37


• Primera cuestión: ¿cuáles son los candidatos?

• Dos posibilidades:

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

cualquiera. En cada paso, moverse al nodo no visitado

más próximo al último nodo seleccionado.

2) Las aristas son los candidatos. Hacer igual que en el

algoritmo de Kruskal, pero garantizando que se forme un

ciclo.


1 2

35

4

30

10

A.E.D. II 38



• Heurística voraz 1) Candidatos = V

– Una solución será un cierto orden en el conjunto de

nodos.

– Representación de la solución: s = (c1, c2, ..., cn),

donde ci es el nodo visitado en el lugar i-ésimo.

– Inicialización: empezar en un nodo cualquiera.

– Función de selección: de los nodos candidatos

seleccionar el más próximo al último (o al primero) de la

secuencia actual (c1, c2, ..., ca).

– Acabamos cuando tengamos n nodos.

A.E.D. II 39



• Ejemplo 1. Empezando en el nodo 1.

1 2

35

4

30

10

Solución: (1, 2, 3, 4, 5)

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

A.E.D. II 40



• Ejemplo 2. Empezando en el nodo 5.

1

30

10

Solución: (5, 3, 4, 2, 1)

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

• Conclusión: el algoritmo no es óptimo.

35

2

4

A.E.D. II 41



• Heurística voraz 2) Candidatos = A

– Una solución será un conjunto de aristas (a1, a2, ..., an)

que formen un ciclo hamiltoniano, sin importar el orden.

– Representación de la solución: s = (a1, a2, ..., an),

donde cada ai es una arista, de la forma ai = (vi, wi).

– Inicialización: empezar con un grafo sin aristas.

– Selección: seleccionar la arista candidata de menor

coste.

– Factible: una arista se puede añadir a la solución actual

si no se forma un ciclo (excepto para la última arista

añadida) y si los nodos unidos no tienen grado mayor

que 2.

A.E.D. II 42



• Ejemplo 3.

Solución: ((1, 2), (4, 3), (2, 3), (1, 5), (4, 5))

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

1

30

10

35

2

4

A.E.D. II 43



Conclusiones:

• Ninguno de los dos algoritmos garantiza la

solución óptima.

• Sin embargo, “normalmente” ambos dan

soluciones buenas, próximas a la óptima.

• Posibles mejoras:

– Buscar heurísticas mejores, más complejas.

– Repetir la heurística 1 con varios orígenes.

– A partir de la solución del algoritmo intentar hacer

modificaciones locales para mejorar esa

solución.

A.E.D. II 44



• Coloración de un grafo: asignación de un color a cada

nodo, de forma que dos nodos unidos con un arco tengan

siempre distinto color.

• Problema de coloración: dado un grafo no dirigido, realizar

una coloración utilizando el número mínimo de colores.

1 2

5

4

3

• También es un problema NP-completo.

• ¿Cómo interpretar el problema? ¿Cómo representar una

solución?

A.E.D. II 45



• Representación de la solución: una solución tiene la

forma (c1, c2, ..., cn), donde ci es el color asignado al

nodo i.

• La solución es válida si para toda arista (v, w) A, se

cumple que cv cw.

1 2

5

4

3

• S = (1, 2, 2, 1, 1), Total: 2 colores

A.E.D. II 46



• Podemos usar una heurística voraz para obtener una

solución:

– Inicialmente ningún nodo tiene color asignado.

– Tomamos un color colorActual:= 1.

– Para cada uno de los nodos sin colorear:

• Comprobar si es posible asignarle el color actual.

• Si se puede, se asigna. En otro caso, se deja sin

colorear.

– Si quedan nodos sin colorear, escoger otro color

(colorActual:= colorActual + 1) y volver al paso anterior.

A.E.D. II 47



• La estructura básica del esquema voraz se repite

varias veces, una por cada color, hasta que todos los

nodos estén coloreados.

• Función de selección: cualquier candidato restante.

• Factible(x): se puede asignar un color a x si ninguno

de sus adyacentes tiene ese mismo color.

para todo nodo y adyacente a x hacer

si cy == colorActual entonces

devolver false

finpara

devolver true

• ¿Garantiza el algoritmo la solución óptima?

A.E.D. II 48



• Ejemplo.

• Resultado: se necesitan 3 colores. Recordar que el óptimo

es 2 colores.

• Conclusión: el algoritmo no es óptimo.

• ¿Cuál será el tiempo de ejecución en el peor caso?

1 2

5

4

3

c1 c2 c3 c4 c5

1 1 2 3 3

A.E.D. II 49



Conclusiones:

• Avance rápido se basa en una idea intuitiva:

– Empezamos con una solución “vacía”, y la

construimos paso a paso.

– En cada paso se selecciona un candidato (el más

prometedor) y se decide si se mete o no (función

factible).

– Una vez tomada una decisión, no se vuelve a

deshacer.

– Acabamos cuando tenemos una solución o cuando

no queden candidatos.

A.E.D. II 50



Conclusiones:

• Primera cuestión: ¿cuáles son los candidatos?,

¿cómo se representa una solución al problema?

• Cuestión clave: diseñar una función de selección

adecuada.

– Algunas pueden garantizar la solución óptima.

– Otras pueden ser más heurísticas...

• Función factible: garantizar las restricciones del

problema.

• En general los algoritmos voraces son la solución rápida

a muchos problemas (a veces óptimas, otras no).

• ¿Y si podemos deshacer decisiones...?

Documents

Algoritmos y Estructuras de Datos II - dis.um.esnmarin/transparencias-algoritmos-voraces-AED-II.pdf · Algoritmos y Estructuras ... Algoritmos voraces 4. Programación dinámica 5