Algoritmos Voraces

Curso 2003/2004
Daniel García
José Moya
José A. Gallud

Algoritmos Voraces 1
1. Introducción
• Conjunto de algoritmos que toman decisiones basándose
en la información disponible inmediatamente
– Sin tener en cuenta los efectos de las decisiones
– Fáciles de diseñar, implementar y, en muchos casos, eficientes
• Se utilizan para resolver problemas de optimización
• Ejemplo: devolver el cambio
– Devolver una cantidad a un cliente utilizando el menor número de
monedas
– Monedas posibles: 500, 200, 100, 25, 10, 5 y 1
• Para devolver 289: 1 de 200, 3 de 25, 1 de 5 y 4 de 1: total 9 monedas
– Algoritmo voraz: escoger cada vez una moneda del mayor valor
sin que la suma supere la cantidad total a devolver

Algoritmos Voraces 2
– Algoritmo:
funcion devolver(n):conjunto de monedas
const c={500,200,100,25,10,5,1}
S=0 //conjunto solución
s=0 //suma de los elementos de S
mientras s<>n hacer
x=mayor elemento de C tal que s+xn
si no existe x, devolver “No hay solución”
S=SU{una moneda de valor x}
s=s+x
devolver S
– Características del algoritmo:
• Este algoritmo, teniendo monedas suficientes, produce una solución
óptima
• Es voraz: en cada paso selecciona la mayor de las monedas, sin
pensar en las consecuencias posteriores
• Nunca modifica la decisión una vez ha escogido una moneda

Algoritmos Voraces 3
• Características generales de los algoritmos voraces:
– Elementos característicos:
• Conjunto de candidatos: dará lugar a seleccionados y rechazados
• Función de solución: comprueba si el conjunto de seleccionados es ya
una solución
• Función de factabilidad: comprueba si el conjunto de candidatos
seleccionados es factible (si es posible completar la solución)
• Función de selección: candidato más prometedor de los no
seleccionados
• Función objetivo: devuelve la solución al problema
– Características generales
• Búsqueda de un conjunto de candidatos que sean solución óptima
• Avanzan paso a paso: inicialmente el conjunto de candidatos está
vacío
• Si con el nuevo candidato no es factible, se rechaza, en otro caso se
escoge
• Cada vez que se añade un candidato, se comprueba si es solución
• Si funciona bien, la primera solución es la óptima

Algoritmos Voraces 4
– Notas importantes:
• La función de selección suele estar relacionada con la función
objetivo
– Si se quiere maximizar beneficios  escoger el candidato con mayor
valor individual
– Si se quiere minimizar costes  selección del candidato más barato
• Pueden definirse varias funciones de selección, se escoge la más
adecuada en función de los objetivos
– Caso general:
funcion voraz(C:conjunto):conjunto
S=0 //S solucion y C conjunto de candidatos
mientras C<>0 y no solucion(S) hacer
x=seleccionar c que minimice la f. de selección
C = C -{x}
si factible(SU{x}) entonces S=SU{x}
si solucion(S) entonces devolver S
sino devolver “No hay solución”

Algoritmos Voraces 5
– Aplicación al ejemplo Devolver Cambio:
• Candidatos: conjunto de monedas {500,200,100,25,10,5,1}
• Función solución: comprueba si el valor de las monedas
seleccionadas es el valor que hay que devolver
• Conjunto de monedas será factible si su valor total no sobrepasa la
cantidad a pagar
• Función de selección: toma la moneda con valor más alto que quede
en el conjunto de candidatos
• Función objetivo: cuenta el número de monedas de las solución

Algoritmos Voraces 6
• Grafos: árboles de recubrimiento mínimo
– G=<N,A>
G: grafo conexo no dirigido
N: conjunto de nodos
A: conjunto de aristas. Cada arista tiene un costo
– Problema 1: Hallar un subconjunto T de las aristas de G tal que las
aristas de T conecten a todos los nodos y la suma de las longitudes
de las aristas de T sea tan pequeño como sea posible.
• Como G es conexo  al menos existe una solución
• Si existen aristas de longitud 0  varias soluciones con la misma
longitud
– Escoger la que tenga un menor número de aristas
– Problema 2: Hallar un subconjunto T de las aristas de G cuyo
coste total sea mínimo
• Igual que el anterior: coste=longitud
• G’=<N,T> donde N es el conjunto de nodos y T el de aristas del grafo
solución

Algoritmos Voraces 7
– Conceptos básicos para obtener el grafo solución:
• Un grafo conexo con n nodos tiene al menos n-1 aristas
• Un grafo conexo con n nodos y n-1 aristas tiene al menos un ciclo
• Si G’ es conexo y T tiene más de n-1 aristas 
– Se puede eliminar al menos una arista sin desconectar G’
– Esa arista debe formar parte de un ciclo, con lo que la eliminación:
» Puede disminuir la longitud de las aristas de T o no (si es 0)
» Disminuye nº aristas en T
» Disminuye la suma de longitudes, si la arista tiene long<>0
• Para la solución: T debe tener exactamente n-1 aristas, como G’ es
conexo  es un árbol (grafo acíclico, conexo y no dirigido)
• G’ es el Árbol de Recubrimiento Mínimo de G
– Aplicaciones de este problema:
» Tendido de líneas eléctricas entre ciudades G’ la red más barata

Algoritmos Voraces 8
– Algoritmo voraz para resolver este problema:
• Táctica A: Comenzar con T vacío, y en cada etapa seleccionar la
arista más corta que no se haya seleccionado o rechazado,
independientemente de donde se encuentre  Kruskal
• Táctica B: Seleccionar un nodo y construir un árbol a partir de él,
seleccionando en cada etapa la arista más corta posible hasta otro
nodo, extendiendo el árbol Prim
– Correspondencia de este problema con los elementos de los
algoritmos voraces:
• Conjunto de candidatos: aristas de G, es decir A.
• Función solución: Un conjunto de aristas es solución si constituye un
árbol de recubrimiento para los nodos de N
• Función de factabilidad: Un conjunto de aristas es factible si no
contiene ciclos
• Función de selección: varía según el algoritmo
• Función objetivo: Minimizar la longitud total de las aristas de la
solución

Algoritmos Voraces 9
• Algoritmo de Kruskal
– Inicialmente:
• T=conjunto de aristas solución, vacío
– Cada nodo de G forma una componente conexa distinta
• Los nodos de una componente conexa en T forman un árbol de
recubrimiento mínimo para los nodos de esa componente
• Al final solo habrá una componente conexa en T, luego T es un
árbol de recubrimiento mínimo para todos los nodos de G
– Proceso del algoritmo:
1. Ordenar las aristas de G por orden creciente de longitud
2. Tomar la arista de longitud menor que no se haya seleccionado o
rechazado
3. Si una arista une a dos nodos de componentes conexas distintas, la
arista se añade a T, uniendo las componentes en una sola
4. En caso contrario, se rechaza la arista (si se añadiera  ciclo)
5. Volver al paso 2 hasta que sólo quede una componente conexa en T

Algoritmos Voraces 10
– Teorema: el algoritmo de Kruskal halla un árbol de recubrimiento
mínimo
– Implementación:
• Operaciones básicas sobre conjuntos
– Buscar(x): indica la componente conexa a la que  el nodo x
– Fusionar(A,B): une las componentes conexas A y B
– Representación del grafo: vector de aristas con sus longitudes asociadas
Funcion Kruskal(G=<N,A>:grafo,longitud AR+):cjto de aristas
Ordenar A por longitudes crecientes
N=nº de nodos en N
T=0
Iniciar n conjuntos, cada uno es un elemento de N
Repetir
e = {u,v}
comp_u = buscar{u}
comp_v = buscar{v}
si comp_u  comp_v entonces fusionar(comp_u,comp_v); T=T{e}
Hasta que T contenga n-1 aristas
Devolver T

Algoritmos Voraces 11
– Tiempo de ejecución del algoritmo de Kruskal:
• n: número de nodos y a: nº de aristas
• Ordenación de aristas (alog a) y como n-1an(n-1)/2 
Ordenación de aristas (a log n)
• Iniciar los n conjuntos disjuntos (n)
• Nº de operaciones buscar es 2a como máximo
• Nº de operaciones fusionar es n-1 como máximo
• Resto de operaciones (a) en el peor de los casos
 luego Kruskal (alog n)

La complejidad es:
si el grafo es disperso: (nlog n)
si el grafo es denso: (n2log n)

Tanto Kruskal como Prim se pueden utilizar para obtener el árbol de

Algoritmos Voraces 12
Procedure Kruskal(var grafo:array[1..n2]of aristas);
Var
Padre:array[1..n] of integer;
soluc:arary[1..n,1..2] of integer;
CostArbMin:real;
RaizOr,RaizEx,k,i:integer;
Begin
{ordenar grafo según la clave Valor de menor a mayor}
For i:=1 to n do Padre[i]:=-1;
k:=0; i:=0; CostArbMin:=0;
While (kxn-1) and (grafo[i+1].valor<) do
begin
i:=i+1
with grafo[i] do
begin
BuscaArbol(Or,RaizOr);
buscaArbol(Ex,RaizEx);
if RaizOr<>RaizEx then
begin
k:=k+1;
CostArbMin:=CostArbMin + Valor;
Soluc[k,1]:=Or;
Soluc[k,2]:=Ex;
UnirArbol(RaizOr, RaizEx);
end; end; end; end;
Algoritmos Voraces 13
Procedure BuscaArbol(Nodo:integer; var Procedure UnirArbol(RaizArbol1,RaizArbol2:integer);
RaizArbol:integer); Var
Var Sum:integer;
j:integer; Begin
Begin Sum:=Padre[RaizArbol1]+Padre[RaizArbol2];
while Padre[j]>0 do j:=Padre[j]; if Padre[RaizArbol1] > Padre[RaizArbol2] then
RaizArbol:=j; begin
while Nodo<>RaizArbol do Padre[RaizArbol1]:=RaizArbol2;
begin Padre[RaizArbol2]:=Sum;
j:=Padre[Nodo]; end
Padre[Nodo]:=RaizArbol; else
Nodo:=j; begin
end; Padre[RaizArbol2]:=RaizArbol1;
end; Padre[RaizArbol1]:=Sum;
end
end;

Algoritmos Voraces 14
– Para el algoritmo de Kruskal:
type Aristas=record
valor:real;
Or,Ex:integer;
end;
• el array Soluc de tamaño n·2 irá conteniendo la solución:
Soluc[1..n][1..2] (Soluc[i][1]: nodo OR, Soluc[i][2]:nodo Ex)
• El array Padre[1..n]:
- Padre[i]=nodo antecesor del nodo i
- Si Padre[i]<0 i es la raiz y contiene el nº de nodos de ese
árbol o componente conexa
• Const n2=n·n
- (...)

Algoritmos Voraces 15
– Complejidad:
• Ordenar grafo: ordenar un array de tamaño 1..a (a=n·n)
• Como queremos ordenar todas las aristas del grafo según su valor, el
orden de complejidad de esta ordenación es:
O(alog a)  n-1<a<n(n-1)/2  O(n2log n2)  O(n2log n)
• Inicializar  O(n)
• While:
• Interior:
- UnirArbol O(1)
- BuscaArbol  O(n)
- Resto  O(1)
• Nº de vueltas: depende de lo equilibrado que estén los subárboles que
se van generando:
- caso peor: n vueltas (totalmente extendido)
- Caso mejor: log n vueltas (árbol equilibrado)
 O(n·n)  O(n2) en el caso peor
 O(n·log n) en el caso mejor
La complejidad se puede obtener en función de las aristas (a) o de los nodos (n)
como tamaño del problema, sabiendo que a=n 2

Algoritmos Voraces 16
• Algoritmo de Prim
– El árbol crece desde una raíz arbitraria, en cada fase se añade una
rama al árbol
G=<N,A>
B:conjunto de nodos, inicialmente con un único nodo
T:conjunto de aristas solución. Inicialmente vacío
Funcion PRIM(G=<N,A>:grafo;longitud AR+):conjunto de aristas
T=; B={nodo arbitrario de N}
Mientras BN
buscar {u,v} de longitud mínima tal que uB y v N\B
T = T  {u,v}
B = B  {v}
Devolver T
– Ejemplo: (...)
– Partiendo de cualquier nodo se obtendrán las mismas aristas
– Teorema: el algoritmo de Prim halla un árbol de recubrimiento mínimo
– Identificar los elementos característicos de los algoritmos voraces:
• Candidatos función de factabilidad función objetivo
• Función solución función de selección

Algoritmos Voraces 17
– Implementación de Prim
N={1,2,...,n}
L: matriz que da la longitud de todas las aristas de modo que
Matriz mas_proximo[i] : indica el nodo de B más próximo a i
Matriz distmin[i]: distancia desde i hasta el nodo más próximo calculado en mas_proximo
distmin[i]=-1  iB, sirve para indicar si un nodo está o no en B
Funcion Prim(L[1..n,1..n]):conjunto de aristas
T=;
Para i=2 hasta n
mas_proximo[i]=1; distmin[i]=L[i,1];
Repetir n-1 veces
min=;
para j=2 hasta n
si 0distmin[j]<min entonces min=distmin[j]; k=j;
T=TU{mas_proximo[k],k}; distmin[k]=-1
para j=2 hasta n
si L[j,k]<distmin[j]
distmin[j]=L[j,k]
mas_proximo[j]=k
devolver T
• Prim (n2)
– Kruskal: si el grafo es denso (a=n·n)  (n2lg n), si es disperso (a=n)  (n2lg n)

Algoritmos Voraces 18
• Grafos: caminos mínimos
– G=<N,A> donde N es el conjunto de nodos y A el de aristas
• G es un grafo dirigido
– Encontrar el camino mínimo (menor longitud, menor coste)
– Algoritmo voraz: algoritmo de Dijkstra:
• S:conjunto con los nodos seleccionados. Se conoce la distancia mínima a estos
nodos
• C:conjunto con el resto de nodos
• N=SUC
• En cada paso selecciona el nodo de C cuya distancia desde el origen sea
mínima
• Camino especial: desde el origen a un nodo, cuando todos los nodos
intermedios pertenecen a S
• Hay una matriz D con la longitud del camino especial más corto que va a cada
nodo
• En cada fase se añade un nuevo nodo v a S, de forma que el camino especial
más corto hasta v es también el más corto de los caminos hasta v
• Todos los caminos desde el origen hasta algún otro nodo son especiales
• Los valores de D dan la solución del problema de caminos mínimos
• La matriz L contiene las longitudes de todas las aristas dirigidas
– L[i,j]0 si la arista (i,j)A, L[i,j]= en caso de no haber arista

Algoritmos Voraces 19
– Función Dijkstra:
Funcion Dijkstra(L[1..n,1..n]:matriz[2..n]
C=2,3,...,n {S=N-C}
Para i=2 hasta n
D[i]=L[1,i]
Repetir n-2 veces
v=algún elemento de C que minimice D[v]
C = C – {v} {S = S U {v}}
para cada wC
D[w] = min(D[w], D[v]+L[v,w])
Devolver D
– Para poder determinar los caminos mínimos y por dónde pasa: se define
P[2..n] tal que P[v] indica el nº de nodos que preceden a v en el camino
más corto.
• Modificar el algoritmo (contenido del para):
Si D[w]>D[v]+L[v,w] entonces
D[w] = D[v] + L[v,w]
P[w] = v
– Teorema: el algoritmo de Dijkstra halla los caminos más cortos desde un
único origen hasta los demás nodos

Algoritmos Voraces 20
– Análisis del algoritmo de Dijkstra:
• Inicialización  O(n)
• Repeat (n2)
– Para interno: O(n)
• Por tanto es (n2)
– Elementos de los algoritmos voraces:
• Candidatos: nodo origen y el resto de nodos
• F. Factabilidad: el nuevo candidato es siempre factible si
D[candidato] es la mínima
• F. objetivo: caminos mínimos con las distancias mínimas del origen a
cada nodo
• F. Solución: no se realiza
• F. Selección: selecciona el nodo con mínima distancia conocida al
origen
– Dijkstra no obtiene la solución óptima si se permiten valores
negativos en las distancias
– No obtiene soluciones óptimas para caminos máximos

Algoritmos Voraces 21
• El problema de la mochila
– Tenemos 1 mochila y n objetos i=1,2,...,n
• El objeto i tiene un peso positivo wi y un valor vi
– Objetivo: llenar la mochila maximizando el valor de los objetos
transportados en ella
• La mochila soporta un peso máximo W
– Se pueden descomponer los objetos en trozos más pequeños
• Fracción xi del objeto i, 0xi  1 para 1  i  n
– Problema: maximizar xivi de modo que xiwi  W
• De modo que vi>0 wi>0 y 0xi  1 para 1  i  n
– Elementos:
• Candidatos: objetos
• F. Solución: vector(x1,...,xn) indicando la fracción de cada objeto que
se incluye
• F. Factabilidad: es factible si se respetan las restricciones
• F. Objetivo: valor total de los objetos en la mochila
• F. Selección: seleccionar el objeto con mayor valor, tomando la mayor
fracción posible del objeto

Algoritmos Voraces 22
– Función mochila
Funcion mochila(w[1..n],v[1..n]):x[1..n]
Para i=1 hasta n hacer
x[i]=0
Mientras peso<W hacer
i=el mejor objeto no seleccionado
si peso+w[i]<=W entonces
x[i]=1
peso=peso+w[i]
sino
x[i]=(W-peso)/w[i]
peso=W
Devolver x
• Funciones de selección posibles
– Objeto más valioso: incrementa el valor de la carga rápidamente
– Objeto con peso más pequeño: la capacidad se agota lentamente
– Objeto cuyo valor por unidad de peso sea el mayor posible
 Ejemplo (...)
• Teorema: si seleccionamos los objetos por orden decreciente de v i/wi, el
algoritmo de la mochila encuentra una solución óptima
• Coste:
• Si están ordenados: O(n)
• Coste total incluyendo ordenación: O(nlg n)

Algoritmos Voraces 23