PDF de programación - Algoritmos: Algoritmos voraces

Algoritmos:

Algoritmos voraces

Alberto Valderruten

LFCIA - Departamento de Computación

Facultad de Informática

Universidad de A Coruña, España

www.lfcia.org/alg

www.fi.udc.es

Contenido

Características
Devolver el cambio

Problema de la mochila

Ordenación topológica

Arbol expandido mínimo
Kruskal, Prim

Caminos mínimos
Dijkstra

Algoritmos - Algoritmos voraces - 2

Devolver el cambio

Sistema monetario M : monedas de valor 1, 2, 5, 10, 20, 50, 100, 200

Problema: pagar exactamente n unidades de valor
con un mínimo de monedas.
→ Función Devolver cambio:

función Devolver cambio (n) : conjunto de monedas

const M = {1, 2, 5, 10, 20, 50, 100, 200}; {denominaciones de las monedas}
{la solución se construye en S}
S := conjunto vacío;
ss := 0;
{suma de las monedas de S}
{bucle voraz:}
mientras ss <> n hacer

x := mayor elemento de M : ss + x <= n;
si no existe tal elemento entonces devolver "no hay soluciones";
S := S U {una moneda de valor x};
ss := ss + x;

devolver S

fin función

Intuitivamente, sabemos que se obtiene siempre una solución óptima

Algoritmos - Algoritmos voraces - 3

Devolver el cambio: caracterización

¿Por qué funciona?

⇒ M adecuado y número suficiente de monedas.

No funciona con cualquier M :

Ejemplo: M = {1, 4, 6}, n = 8 → {6, 1, 1} en vez de {4, 4} (óptimo)
Este problema se resolverá con Programación Dinámica

La función Devolver cambio es voraz (algoritmos ávidos, greedy )

¿Por qué voraz?

• Selecciona el mejor candidato que puede en cada iteración,
• Una vez seleccionado un candidato, decide definitivamente:

sin valorar consecuencias.

- aceptarlo, o
- rechazarlo

sin evaluación en profundidad de alternativas, sin retroceso...

→ Algoritmos sencillos: tanto en diseño como en implementación.

Cuando la técnica funciona, se obtienen algoritmos eficientes.

Algoritmos - Algoritmos voraces - 4

Características de los algoritmos voraces

Resuelven problemas de optimización:

En cada fase, toman una decisión (selección),
satisfaciendo un óptimo local según la información disponible,
esperando así, en conjunto, satisfacer un óptimo global.

Manejan un conjunto de candidatos C:

En cada fase, retiran el candidato seleccionado de C,
y si es aceptado se incluye en S:
Conjunto donde se construye la solución ≡ candidatos aceptados.

Utilizan 4 funciones (explícitamente o no):

¿S es Solución?
¿S es Factible? ≡ ¿Puede completarse para obtener una solución?

1.
2.
3. Selección: determina el mejor candidato
4. Objetivo: valora S (relacionada con Selección)
→ Encontrar S: Solución y optimiza Objetivo (max/min)

Algoritmos - Algoritmos voraces - 5

Esquema de los algoritmos voraces

Función Voraz (esquema):

función Voraz (C:conjunto): conjunto

S := conjunto vacío;
{bucle voraz:}
mientras C <> conjunto vacío y no solución(S) hacer

{la solución se construye en S}

x := seleccionar(C);
C := C\{x};
si factible (SU{x}) entonces S := SU{x}

si solución (S) entonces devolver S
sino devolver "no hay soluciones"

fin función

Ejemplo: Devolver cambio
→ tenemos que:

- adaptar el esquema al problema
- introducir mejoras (ejemplo: añadir div)

Problema: Asegurarse/demostrar que la técnica funciona.

No siempre funciona: “tomar calle principal”

Algoritmos - Algoritmos voraces - 6

El problema de la mochila I (1)

peso wi > 0

valor vi > 0

n objetos: i = 1..n

Problema: cargar una mochila de capacidad W ,
maximizando el valor de su carga.
Versión I: los objetos se pueden fraccionar ≡ fracción xi, 0 ≤ xi ≤ 1
⇒ el objeto i contribuye

en xiwi al peso de la carga, limitado por W ,
en xivi al valor de la carga, que se quiere maximizar.

i=1 xivi con la restricciónPn

i=1 xiwi ≤ W

⇒ maxPn
+ Hipótesis:Pn
⇒ en óptimo,Pn

i=1 wi > W , sino la solución es trivial.
i=1 xiwi = W

Algoritmos - Algoritmos voraces - 7

El problema de la mochila I (2)

función Mochila 1 ( w[1..n], v[1..n], W): objetos[1..n]

para i := 1 hasta n hacer

x[i] := 0;

{la solución se construye en x}

peso := 0;
{bucle voraz:}
mientras peso < W hacer

i := el mejor objeto restante; {1}
si peso+w[i] <= W entonces

x[i] := 1;
peso := peso+w[i]

sino

x[i] := (W-peso)/w[i];
peso := W;

devolver x

fin función

Algoritmos - Algoritmos voraces - 8

El problema de la mochila I (3)

¿Mejor objeto restante? → Ejemplar de problema: n = 5, W = 100

1
20
10

2
30
20

3
66
30

4
40
40

5
60
50

vi
wi

(Pn

i=1 wi > W )

Selección:

1.
2.
3.

¿Objeto más valioso? ↔ vi max
¿Objeto más ligero? ↔ wi min
¿Objeto más rentable? ↔ vi/wi max
4
40
40
1,0
0,5
1
0

xi (vi max)
xi (wi min)

3
66
30
2,2
1
1
1

1
20
10
2,0
0
1
1

2
30
20
1,5
0
1
1

vi
wi

vi/wi

xi (vi/wi max)

5
60
50

1,2 Objetivo (Pn

1
0
0,8

146
156
164

i=1 xivi)

Algoritmos - Algoritmos voraces - 9

El problema de la mochila I (4)

Teorema: Si los objetos se seleccionan por orden decreciente de vi/wi,
el algoritmo Mochila 1 encuentra la solución óptima.
Demostración por absurdo.

Análisis:
inicialización: O(n);
bucle voraz: O(1) ∗ n (peor caso) → O(n)
+ ordenación: O(nlogn)

Mejora: con un montículo
inicialización: +O(n) (Crear montículo);
bucle voraz: O(logn) ∗ n (peor caso) → O(nlogn)
→ pero mejores T (n)

Algoritmos - Algoritmos voraces - 10

Ordenación topológica (1)

Definición: Ordenación de los nodos de un grafo dirigido acíclico:
∃ camino vi, ..., vj

vj aparece después de vi.

⇒

Aplicación: sistema de prerrequisitos (llaves) en una titulación.
(u, v) ≡ u debe aprobarse antes de acceder a v
→ grafo acíclico, sino la ordenación no tiene sentido.

Observación: la ordenación no es única.

Definición: Grado de entrada de v: número de aristas (u, v).

Algoritmo: buscar nodo de grado 0, enviarlo a la salida y eliminarlo
junto a las aristas que partan de él.
Hipótesis: el grafo ya está en memoria, listas de adyacencia.

Algoritmos - Algoritmos voraces - 11

Ordenación topológica (2)

procedimiento Ordenación topológica 1 (G:grafo)
{Precondición: Grado Entrada [1..|N|] previamente calculado}

contador := 1;
error := falso;
mientras contador <= |N| y no error hacer

v := Buscar nodo de grado 0 (...); {*}
si v=0 entonces

error:=cierto;
error "el grafo tiene un ciclo"

sino

Número Topológico [v] := contador ;
para cada w adyacente a v hacer

Grado Entrada [w] := Grado Entrada [w]-1;

incrementar contador

fin procedimiento

{*} recorre Grado Entrada buscando 0 ∧ sin Número Topológico asignado.

|N| = n ⇒ O(n) para cada llamada (acceso secuencial)
n llamadas ⇒ O(n2) para el algoritmo.

Algoritmos - Algoritmos voraces - 12

Ordenación topológica (3)

Mejora: estructura para nodos cuyo grado de entrada sea 0.

- {*} puede devolver cualquiera de ellos;
- al decrementar un grado, decidir si se incluye el nodo en la estructura.

→ pila o cola.

Ejemplo: evolución de Grado Entrada

nodo

0
1
1
2
2
3
3
4
1
5
3
6
2
7
Ins
1
Elim 1

0
1
2
1
3
2
2
2

1
1
0
3
2
5
5

1
0

3
1
4
4

0

2
0
3,7
3

1

-
7

0

6
6

Algoritmos - Algoritmos voraces - 13

Ordenación topológica (4)

procedimiento Ordenación topológica 2 (G:grafo)

Crear Cola (C);
contador := 1 ;
para cada nodo v hacer

si Grado Entrada [v] = 0 entonces Insertar Cola (v, C);

mientras no Cola Vacía (C) hacer

v := Eliminar Cola (C);
Número Topológico [v] := contador;
incrementar contador;
para cada w adyacente a v hacer

Grado Entrada [w] := Grado Entrada [w]-1;
si Grado Entrada [w] = 0 entonces Insertar Cola (w, C);

si contador <= |N| entonces error "el grafo tiene un ciclo"

fin procedimiento

→ O(|A| + |N|) con listas de adyacencia.
Peor caso: grafo denso y visita todas las aristas.

Algoritmos - Algoritmos voraces - 14

Arbol expandido mínimo (1)

a. e. m., árbol de expansión, árbol de recubrimiento
Sea G = (N, A) conexo, no dirigido, pesado (costes ≥ 0 en las aristas):
Problema: T subconjunto de A tal que G0 = (N, T ) conexo,

P costes mínimo y |T| mínimo.

|N| = n ⇒ |T| ≥ n − 1;
pero, si |T| > n − 1 ⇒ ∃ ciclo
→ podemos quitar una arista del ciclo
⇒ |T| = n − 1 ∧ G0 conexo ⇒ árbol (e. m.)
Aplicación: instalación de cableado → ¿solución más económica?

Técnica voraz:
- Candidatos: aristas → S: conjunto de aristas
- Solución? : S = T ?
- Factible?: (N, S) sin ciclos (ej: S vacío)

Algoritmos - Algoritmos voraces - 15

Arbol expandido mínimo (2)

Definición: una arista parte de un conjunto de nodos
⇔ uno de sus extremos está en el conjunto.
(no parte ⇔ sus 2 extremos están dentro/fuera del conjunto)

Lema: sean G = (N, A) un grafo conexo, no dirigido, pesado;

B un subconjunto (estricto) de N ;
T un subconjunto (estricto) de A, Factible,

sin aristas que partan de B;

(u, v): la arista más corta que parte de B

⇒ T U{(u, v)} es Factible
→ Algoritmos de Kruskal y Prim

Algoritmos - Algoritmos voraces - 16

Algoritmo de Kruskal (1)

Inicialmente: T vacío

Invariante:
(N, T ) define un conjunto de componentes conexas (subgrafos): árboles

Final: sólo una componente conexa: el a. e. m.
Selección: lema → arista más corta...

Factible?:

...que una componentes conexas distintas

Estructuras de datos:
- “grafo”: aristas ordenadas
- componentes conexas: Conjuntos Disjuntos (buscar(x), fusionar(A, B))

Algoritmos - Algoritmos voraces - 17

Algoritmo de Kruskal (2)

Ejemplo:

arista
peso

(1,2)

(2,3)

(4,5)

(6,7)

(1,4)

(2,5)

(4,7)

(3,5)

...

1

2

3

3

4

4

4

5

paso

ini

1

2

3

4

5

6

7

selección

componentes conexas

-

(1,2)

(2,3)

(4,5)

(6,7)

(1,4)

(2,5) rechazada

(4,7)

1

2

3

4

5

6

7

1,2

3

4

5

6

7

1,2,3

4

5

6

7

1,2,3

4,5

6

7

1,2,3

4,5

6,7

1,2,3,4,5

1,2,3,4,5

6,7

6,7

1,2,3,4,5,6,7

Algoritmos - Algoritmos voraces - 18

Algoritmo de Kruskal (3)

función Kruskal ( G =(N,A) ) : árbol

Ordenar A según longitudes crecientes;
n := |N|;
T := conjunto vacío;
inicializar n conjuntos, cada uno con un nodo de N;
{bucle voraz:}
repetir

a := (u,v) : arista más corta de A aún sin considerar;
Conjunto U := Buscar (u);
Conjunto V := Buscar (v);
si