87
An´ alise de Algoritmos Método Guloso – p. 1/50

Análise de Algoritmos - Método Guloso

Embed Size (px)

Citation preview

Page 1: Análise de Algoritmos - Método Guloso

Analise de Algoritmos

Método Guloso

–p. 1/50

Page 2: Análise de Algoritmos - Método Guloso

Método Guloso

Algumas características:

Aplicado a problemas de otimização, em quequeremos computar a melhor solução

– p. 2/50

Page 3: Análise de Algoritmos - Método Guloso

Método Guloso

Algumas características:

Aplicado a problemas de otimização, em quequeremos computar a melhor solução

Em cada passo, o algoritmo sempre escolhe amelhor opção local viável, sem se preocuparcom as consequências futuras

– p. 2/50

Page 4: Análise de Algoritmos - Método Guloso

Método Guloso

Algumas características:

Aplicado a problemas de otimização, em quequeremos computar a melhor solução

Em cada passo, o algoritmo sempre escolhe amelhor opção local viável, sem se preocuparcom as consequências futuras

Nem sempre produz a solução ótima, masmuitas vezes sim.

– p. 2/50

Page 5: Análise de Algoritmos - Método Guloso

Metodo Guloso

Árvore geradora de custo mínimo

–p. 3/50

Page 6: Análise de Algoritmos - Método Guloso

Árvore geradora de custo mínimo

Dado um grafo G = (V,E) com pesos nas arestas,determinar um subgrafo gerador conexo de customínimo, ou seja, uma árvore geradora de customínimo.

– p. 4/50

Page 7: Análise de Algoritmos - Método Guloso

Árvore geradora de custo mínimo

Dado um grafo G = (V,E) com pesos nas arestas,determinar um subgrafo gerador conexo de customínimo, ou seja, uma árvore geradora de customínimo. O algoritmo que vamos estudar pararesolver este problema é de autoria de Kruskal(1956).

– p. 4/50

Page 8: Análise de Algoritmos - Método Guloso

Árvore geradora de custo mínimo

Dado um grafo G = (V,E) com pesos nas arestas,determinar um subgrafo gerador conexo de customínimo, ou seja, uma árvore geradora de customínimo. O algoritmo que vamos estudar pararesolver este problema é de autoria de Kruskal(1956).

Idéia do algoritmo:

Em cada passo, selecione a aresta de menorcusto e que não forma circuito.

– p. 4/50

Page 9: Análise de Algoritmos - Método Guloso

Algoritmo de Kruskal

1. Dado um grafo G = (V,E), considere o grafoT = (V (G), !)

2. S " E(G)

– p. 5/50

Page 10: Análise de Algoritmos - Método Guloso

Algoritmo de Kruskal

1. Dado um grafo G = (V,E), considere o grafoT = (V (G), !)

2. S " E(G)

3. Enquanto |T | < |V |# 1 façaremova uma aresta e de peso mínimo de S

(Aqui está o guloso!!!)Se e liga duas componentes distintas de T

então adicione e à T ; Senão descarte e

– p. 5/50

Page 11: Análise de Algoritmos - Método Guloso

Algoritmo de Kruskal

Qual é o tempo gasto por este algoritmo?

–p. 6/50

Page 12: Análise de Algoritmos - Método Guloso

Algoritmo de Kruskal

Qual é o tempo gasto por este algoritmo?Resp: O(m log n), onde

m é o número de arestas, e

n é o número de vértices do grafo.

– p. 6/50

Page 13: Análise de Algoritmos - Método Guloso

Algoritmo de Kruskal

Qual é o tempo gasto por este algoritmo?Resp: O(m log n), onde

m é o número de arestas, e

n é o número de vértices do grafo.

Sugestão de implementação: utilize heap e uniãode conjuntos disjuntos.

– p. 6/50

Page 14: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Teorema: O algoritmo de Kruskal determinacorretamente uma árvore geradora K de customínimo em um grafo conexo com custos reaisassociados às arestas.

– p. 7/50

Page 15: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Teorema: O algoritmo de Kruskal determinacorretamente uma árvore geradora K de customínimo em um grafo conexo com custos reaisassociados às arestas.

Prova: Observe que uma árvore geradora de customínimo pode não ser única.

SejaM uma árvore geradora de custo mínimomais próxima possível de K. Vamos mostrar queM = K.

– p. 7/50

Page 16: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Seja e1, e2, . . . , en#1 a sequência das arestasincluídas em K.

– p. 8/50

Page 17: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Seja e1, e2, . . . , en#1 a sequência das arestasincluídas em K.

Suponha queM $= K. Seja i o menor índice talque {e1, e2, . . . , ei} % E(M) e ei+1 /& E(M).

– p. 8/50

Page 18: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Seja e1, e2, . . . , en#1 a sequência das arestasincluídas em K.

Suponha queM $= K. Seja i o menor índice talque {e1, e2, . . . , ei} % E(M) e ei+1 /& E(M).

A inclusão de ei+1 emM forma um único circuito.Este circuito deve conter uma aresta x /& E(K),senão teríamos um circuito em K.

– p. 8/50

Page 19: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Como x, e1, e2, . . . , ei pertencem àM (que nãocontém circuito), e como a algoritmo de Kruskalconsulta as arestas por ordem de custo,concluímos que peso(x) ' peso(ei+1), senão x teriasido escolhido no lugar de ei+1. Consideremos aárvore geradoraM ( = (M # {x}) ) {ei+1}.

– p. 9/50

Page 20: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Se peso(x) > peso(ei+1),M ( é uma árvoregeradora de custo menor do queM , o que éuma contradição.

– p. 10/50

Page 21: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Se peso(x) > peso(ei+1),M ( é uma árvoregeradora de custo menor do queM , o que éuma contradição.

Se peso(x) = peso(ei+1),M ( é uma árvoregeradora de custo mínimo, masM ( contém asarestas e1, e2, . . . , ei, ei+1, contradizendo aescolha deM .

– p. 10/50

Page 22: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Kruskal

Se peso(x) > peso(ei+1),M ( é uma árvoregeradora de custo menor do queM , o que éuma contradição.

Se peso(x) = peso(ei+1),M ( é uma árvoregeradora de custo mínimo, masM ( contém asarestas e1, e2, . . . , ei, ei+1, contradizendo aescolha deM .

Conclusão: M = K.

– p. 10/50

Page 23: Análise de Algoritmos - Método Guloso

Exercícios

1. Estude e descreva o algoritmo de Prim. Façauma análise da complexidade e compare com oalgoritmo de Kruskal. (tem no Cormen!!!)

2. Para completar a prova da corretude doalgoritmo de Kruskal, mostre que se T é umaárvore geradora de um grafo G então a inclusãode uma nova aresta de G em T produz umúnico circuito em T .

– p. 11/50

Page 24: Análise de Algoritmos - Método Guloso

Metodo Guloso

Códigos de Huffman

–p. 12/50

Page 25: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Suponha que temos um grande arquivo texto queprecisa ser compactado e transmitido para umoutro local. As hipóteses são:

– p. 13/50

Page 26: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Suponha que temos um grande arquivo texto queprecisa ser compactado e transmitido para umoutro local. As hipóteses são:

Sabemos a frequência de cada caracter, ouseja, o números de vezes que cada caracteraparece no texto;

– p. 13/50

Page 27: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Suponha que temos um grande arquivo texto queprecisa ser compactado e transmitido para umoutro local. As hipóteses são:

Sabemos a frequência de cada caracter, ouseja, o números de vezes que cada caracteraparece no texto;

No processo de compactação, queremosatribuir um código binário para cada caracter.

– p. 13/50

Page 28: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Problema: Como atribuir códigos aos caracteresde tal forma que o texto compactado seja o menorpossível?

– p. 14/50

Page 29: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Problema: Como atribuir códigos aos caracteresde tal forma que o texto compactado seja o menorpossível?

Atencao: Para não ocorrer ambiguidade nadescompactação, é necessário que nenhumcódigo seja prefixo de outro.

– p. 14/50

Page 30: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Subproblema: Como atribuir códigos livres deprefixos?

– p. 15/50

Page 31: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Subproblema: Como atribuir códigos livres deprefixos? Sugestao: Utilizando uma árvore binária.

– p. 15/50

Page 32: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Subproblema: Como atribuir códigos livres deprefixos? Sugestao: Utilizando uma árvore binária.

Exemplo: Se os caracteres são a, b, c, d, e, f ,podemos atribuir códigos da seguinte forma.

fa b

c d

e

0

00

0

0 11

1 11

– p. 15/50

Page 33: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Mas como atribuir códigos de forma que o textocompactado seja o menor possível?

– p. 16/50

Page 34: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Mas como atribuir códigos de forma que o textocompactado seja o menor possível?

Huffman propôs um algoritmo guloso paraatribuição dos códigos. Ilustraremos este algoritmoatravés de um exemplo.

– p. 16/50

Page 35: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Vamos supor que as frequências dos caracteressejam: a = 2, b = 3, c = 4, d = 7, e = 8, f = 10.

– p. 17/50

Page 36: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Vamos supor que as frequências dos caracteressejam: a = 2, b = 3, c = 4, d = 7, e = 8, f = 10.

O passo geral do algoritmo é:

Escolha um par de valores mínimos f e f ( doconjunto de frequências; (Aqui está o guloso!!!)

Substitua f e f ( por f + f ( no conjunto;

Repita este processo até que um únicoelemento reste no conjunto.

– p. 17/50

Page 37: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Podemos ilustrar a execução deste algoritmo poruma árvore binária da seguinte forma:

– p. 18/50

Page 38: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Podemos ilustrar a execução deste algoritmo poruma árvore binária da seguinte forma:

101 2 3 4 7 8

– p. 18/50

Page 39: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Podemos ilustrar a execução deste algoritmo poruma árvore binária da seguinte forma:

101 2 3 4 7 8

52 4 7 8 10

2 3

– p. 18/50

Page 40: Análise de Algoritmos - Método Guloso

Códigos de Huffman

93 7 8 10

2 3

54

– p. 19/50

Page 41: Análise de Algoritmos - Método Guloso

Códigos de Huffman

154 10

2 3

54

9

7 8

– p. 20/50

Page 42: Análise de Algoritmos - Método Guloso

Códigos de Huffman

10

2 3

54

9

5

7 8

1519

– p. 21/50

Page 43: Análise de Algoritmos - Método Guloso

Códigos de Huffman

6

7 8

1519

10

2 3

54

9

34

– p. 22/50

Page 44: Análise de Algoritmos - Método Guloso

Códigos de Huffman

1

7 8

1519

10

2 3

54

9

34

a b

c

d ef

0

0

0

0

0

1

11

1

– p. 23/50

Page 45: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Qual o tempo gasto pelo algoritmo de Huffman?

–p. 24/50

Page 46: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Qual o tempo gasto pelo algoritmo de Huffman?

Lembre-se: O passo geral do algoritmo é:

Escolha um par de valores mínimos f e f ( doconjunto de frequências;

Substitua f e f ( por f + f ( no conjunto;

Repita este processo até que um únicoelemento reste no conjunto.

– p. 24/50

Page 47: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Qual o tempo gasto pelo algoritmo de Huffman?

Lembre-se: O passo geral do algoritmo é:

Escolha um par de valores mínimos f e f ( doconjunto de frequências;

Substitua f e f ( por f + f ( no conjunto;

Repita este processo até que um únicoelemento reste no conjunto.

O tempo gasto é O(n. log n) utilizando um heap.– p. 24/50

Page 48: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Huffman

Teorema: O algoritmo de Huffman atribui códigosbinários aos caracteres de forma ótima, ou seja, talque o texto compactado seja o menor possível.

– p. 25/50

Page 49: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Huffman

Teorema: O algoritmo de Huffman atribui códigosbinários aos caracteres de forma ótima, ou seja, talque o texto compactado seja o menor possível.

Ideia da prova: Observe primeiramente que todaatribuição de códigos binários pode serrepresentada por uma árvore binária.

– p. 25/50

Page 50: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Huffman

Considere então uma atribuição binária ótima paraum dado texto e seja T a árvore binária que arepresenta.

– p. 26/50

Page 51: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Huffman

Considere então uma atribuição binária ótima paraum dado texto e seja T a árvore binária que arepresenta.

Vamos mostrar que T pode ser transformada naárvore de Huffman sem aumento do tamanho dotexto compactado.

– p. 26/50

Page 52: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Para isso, vamos considerar:

a e b dois caracteres “irmãos” de profundidademáxima em T ; (Vamos supor s.p.g. quef(a) * f(b))

x e y dois caracteres do texto que possuem asmenores frequências; (Vamos supor s.p.g. quef(x) * f(y))

– p. 27/50

Page 53: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Para isso, vamos considerar:

a e b dois caracteres “irmãos” de profundidademáxima em T ; (Vamos supor s.p.g. quef(a) * f(b))

x e y dois caracteres do texto que possuem asmenores frequências; (Vamos supor s.p.g. quef(x) * f(y))

Então f(x) * f(a) e f(y) * f(b).

– p. 27/50

Page 54: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Então f(x) * f(a) e f(y) * f(b).

T T ( T ((

xx

x

y

yy

aa

a

b

bb

– p. 28/50

Page 55: Análise de Algoritmos - Método Guloso

Códigos de Huffman

Então f(x) * f(a) e f(y) * f(b).

T T ( T ((

xx

x

y

yy

aa

a

b

bb

Conclusão: uma prova por indução no número decaracteres pode ser escrita.

– p. 28/50

Page 56: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Huffman

A diferença no tamanho do texto compactado entreT e T ( é:

C(T )# C(T () =!

f(c).pT (c)#!

f(c).pT !(c)

= f(x)pT (x) + f(a).pT (a)

#f(x).pT !(x)# f(a).pT !(a)

= f(x)pT (x) + f(a).pT (a)

#f(x).pT (a)# f(a).pT (x)

= (f(a)# f(x)).(pT (a)# pT (x))

' 0– p. 29/50

Page 57: Análise de Algoritmos - Método Guloso

Exercícios1. Determine os códigos de Huffman para um texto com

os seguintes caracteres e frequências:(a) a = 7, b = 5, c = 10, d = 21, e = 90, f = 11, g = 7 e

h = 2;(b) a = 1, b = 1, c = 2, d = 3, e = 5, f = 8, g = 13 e

h = 21.2. Descreva a árvore de Huffman quando as frequências

são os primeiros n números de Fibonacci.3. Qual é um pior caso para o algoritmo de Huffman, ou

seja, um caso em que o texto compactado não é menordo que o original?

4. Generalize o algoritmo de Huffman para códigosternários (isto é, códigos usando simbolos 0, 1 e 2).

– p. 30/50

Page 58: Análise de Algoritmos - Método Guloso

Exercícios5. Suponha que temos n listas ordenadas, com valores

inteiros, que precisam ser intercaladas 2 a 2 (como noalgoritmo mergesort) para produzir uma única listaordenada contendo os elementos de todas as listas.Sabendo o número de elementos de cada lista, qual éa sequência ótima de intercalação?

– p. 31/50

Page 59: Análise de Algoritmos - Método Guloso

Metodo Guloso

O problema do caminho mínimo

–p. 32/50

Page 60: Análise de Algoritmos - Método Guloso

O problema do caminho mínimo

Seja G um grafo simples tal que a cada aresta e

associamos um custo c(e) ' 0. O problema docaminho mínimo consiste em encontar umcaminho de menor custo entre dois vértices dados,digamos u e v.

– p. 33/50

Page 61: Análise de Algoritmos - Método Guloso

O problema do caminho mínimo

1

1 2

2

4

7

17

5

1

2

1

6

3

4

2

8

6

9

3

9 9

u v

– p. 34/50

Page 62: Análise de Algoritmos - Método Guloso

O problema do caminho mínimo

Para resolver este problema, vamos estudar oalgoritmo de Dijkstra (1959). Como veremos, estealgoritmo não só encontra o caminho mínimo de u

a v, mas de u a qualquer outro vértice do grafo.

– p. 35/50

Page 63: Análise de Algoritmos - Método Guloso

O problema do caminho mínimo

Para resolver este problema, vamos estudar oalgoritmo de Dijkstra (1959). Como veremos, estealgoritmo não só encontra o caminho mínimo de u

a v, mas de u a qualquer outro vértice do grafo.

O algoritmo de Dijkstra pode ser visto como umageneralização da busca em largura.

Vamos assumir que c(x, y) = + se (x, y) /& E(G).

– p. 35/50

Page 64: Análise de Algoritmos - Método Guloso

Algoritmo de Dijkstra

1. d(u) " 0; S " {u};

2. Para cada v & (V (G)# {u}) faça d(v) " c(u, v)

– p. 36/50

Page 65: Análise de Algoritmos - Método Guloso

Algoritmo de Dijkstra

1. d(u) " 0; S " {u};

2. Para cada v & (V (G)# {u}) faça d(v) " c(u, v)

3. Enquanto S $= V (G) façaEscolha v & V (G)# S tal que d(v) sejamínimoS " S ) {v}Para cada w & V (G)# S façad(w) " min{d(w), d(v) + c(v, w)}

– p. 36/50

Page 66: Análise de Algoritmos - Método Guloso

Algoritmo de Dijkstra

Qual é o tempo gasto por este algoritmo?

–p. 37/50

Page 67: Análise de Algoritmos - Método Guloso

Algoritmo de Dijkstra

Qual é o tempo gasto por este algoritmo?

Resposta: O(n2)

– p. 37/50

Page 68: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Dijkstra

Teorema: O algoritmo de Dijkstra determinacorretamente as distâncias de u a cada vértice deV (G).

– p. 38/50

Page 69: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Dijkstra

Teorema: O algoritmo de Dijkstra determinacorretamente as distâncias de u a cada vértice deV (G).

Prova: Suponha o contrário, ou seja, que existe umvértice v tal que o valor d(v) calculado peloalgoritmo não é a distância mínima de u a v.Consideremos o primeiro vértice v nessa condiçãodurante a execução do algoritmo (ou seja, aprimeira vez que o algoritmo erra).

– p. 38/50

Page 70: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Dijkstra

Então a distância de u a v é menor do que d(v), epara todo vértice w & S a distância de u a w estácorreta, ou seja, é d(w).

– p. 39/50

Page 71: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Dijkstra

Então a distância de u a v é menor do que d(v), epara todo vértice w & S a distância de u a w estácorreta, ou seja, é d(w).

Considere um caminho P de u a v cujo custo émenor do que d(v).

– p. 39/50

Page 72: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Dijkstra

Então a distância de u a v é menor do que d(v), epara todo vértice w & S a distância de u a w estácorreta, ou seja, é d(w).

Considere um caminho P de u a v cujo custo émenor do que d(v). Então P contém um vérticeinterno w fora de S (senão o algoritmo teriaescolhido P ).

– p. 39/50

Page 73: Análise de Algoritmos - Método Guloso

Corretude do algoritmo de Dijkstra

Logo, a distância de u a w é menor do que adistância de u a v, pois os custos são todos nãonegativos. Mas isto contradiz a escolha de v peloalgoritmo (w deveria ter sido escolhido nestaiteração). Portanto, o algoritmo está correto.

– p. 40/50

Page 74: Análise de Algoritmos - Método Guloso

Exercícios

1. Determine o caminho mínimo entre os vértices ue v.

1

1 2

2

4

7

17

5

1

2

1

6

3

4

2

8

6

9

3

9 9

u v

– p. 41/50

Page 75: Análise de Algoritmos - Método Guloso

Exercícios

2. Determine o caminho mínimo entre os vértices ue v.

3

5 5

5

9 2 9

1 6

9 2

3 41

5

26

u v

– p. 42/50

Page 76: Análise de Algoritmos - Método Guloso

Exercícios

3. Determine o caminho mínimo entre os vértices ue v.

9

7

1

5

4

8

2

6

7

2

6

4 1

2

8

10

6

1 3

5 5

8

3

2

4u v

– p. 43/50

Page 77: Análise de Algoritmos - Método Guloso

Exercícios

4. O algoritmo de Dijkstra funciona corretamentese as arestas tiverem custos negativos?

– p. 44/50

Page 78: Análise de Algoritmos - Método Guloso

Metodo Guloso

Problema da Seleção de Atividades

(para estudar)

– p. 45/50

Page 79: Análise de Algoritmos - Método Guloso

Seleção de atividades

Dada uma coleção de atividadesS = {a1, a2, . . . , an} para ser executada, onde cadaatividade ai tem um horário de início si e umhorário de término fi, determinar um subconjuntosem sobreposição de horário (compatível) máximode atividades de S.

– p. 46/50

Page 80: Análise de Algoritmos - Método Guloso

Exemplo

Conjunto de atividades S:i 1 2 3 4 5 6 7 8 9 10 11

s[i] 1 3 0 5 3 5 6 8 8 2 12

f [i] 4 5 6 7 8 9 10 11 12 13 14

2 3 410 5 6 7 8 9 10 11 12 13 14

– p. 47/50

Page 81: Análise de Algoritmos - Método Guloso

Exemplo

Conjunto de atividades S:i 1 2 3 4 5 6 7 8 9 10 11

s[i] 1 3 0 5 3 5 6 8 8 2 12

f [i] 4 5 6 7 8 9 10 11 12 13 14

2 3 410 5 6 7 8 9 10 11 12 13 14

Um subconjunto compatível máximo de S: {a1, a4, a8, a11}

– p. 47/50

Page 82: Análise de Algoritmos - Método Guloso

Seleção de atividades

O que pode ser uma estratégia gulosa para este problema?

– p. 48/50

Page 83: Análise de Algoritmos - Método Guloso

Seleção de atividades

O que pode ser uma estratégia gulosa para este problema?

Ordene as atividades por ordem crescente de término;A cada iteração, escolha uma atividade compatível eque acaba mais cedo.

– p. 48/50

Page 84: Análise de Algoritmos - Método Guloso

Seleção de atividades

O que pode ser uma estratégia gulosa para este problema?

Ordene as atividades por ordem crescente de término;A cada iteração, escolha uma atividade compatível eque acaba mais cedo.

Mais precisamente:A " {a1}; i " 1;Para j " 2 até n faça

Se sj ' fi então {A " A ) {aj}; i " j}

– p. 48/50

Page 85: Análise de Algoritmos - Método Guloso

Seleção de atividades

O que pode ser uma estratégia gulosa para este problema?

Ordene as atividades por ordem crescente de término;A cada iteração, escolha uma atividade compatível eque acaba mais cedo.

Mais precisamente:A " {a1}; i " 1;Para j " 2 até n faça

Se sj ' fi então {A " A ) {aj}; i " j}

Qual o tempo gasto por este algoritmo?

– p. 48/50

Page 86: Análise de Algoritmos - Método Guloso

Exercícios1. Aplique o algoritmo acima para o conjunto de

atividades especificadas pelos seguintes pares dehorários inicial e final: S ={(1, 2), (1, 3), (1, 4), (2, 5), (3, 7), (4, 9), (5, 6), (6, 8), (7, 9)}.

2. Argumente que este algoritmo realmente determina umsubconjunto compatível máximo de atividades.

3. Considere a seguinte estratégia para o problema daseleção de atividades: A cada iteração, escolha umaatividade compatível e que começa mais tarde. Seráque esta estratégia também produz uma soluçãoótima?

4. O que voce acha da seguinte estratégia: A cadaiteração, escolha a atividade de menor duração.

– p. 49/50

Page 87: Análise de Algoritmos - Método Guloso

Mais exercícios1. Considere o problema de efetuar troco usando um

número mínimo de moedas.(a) Descreva um algoritmo guloso para efetuar o troco

utilizando moedas de 1, 5, 10 e 25 centavos;(b) Seu algoritmo produz a solução ótima?(c) Seu algoritmo funciona corretamente para qualquer

conjunto de moedas?2. Problema da mochila fracionaria: Dados n objetos com

valor e peso associado a cada um deles, e umamochila que suporta peso máximo W , determinar umsubconjunto do conjunto de objetos de valor máximo ecujo peso não excede W . Considere que é permitidoselecionar frações de quaisquer elementos.

– p. 50/50