Técnicas de Análise de Algoritmo

Algoritmos Gulosos

Alysson Milanez

Na aula passada...

2

Na aula passada...

Programação Dinâmica

​

3

Algoritmos Gulosos

4

Algoritmos Gulosos

Em geral, os algoritmos relacionados a problemas de otimização funcionam através de uma sequência de passos, com um conjunto de opções (escolhas) em cada passo.

5

Algoritmos Gulosos

Para muitos problemas de otimização, é um exagero utilizar a programação dinâmica para descobrir as melhores escolhas: algoritmos mais simples e eficientes farão a mesma coisa. Um algoritmo guloso sempre faz a escolha que parece ser a melhor no momento (escolha mais apetitosa).

​

​

6

Algoritmos Gulosos

Isto é, ele faz uma escolha ótima para as condições locais, na esperança de que essa escolha leve a uma solução ótima para a situação global.

7

Algoritmos Gulosos

Os algoritmos gulosos nem sempre produzem soluções ótimas, mas para muitos problemas eles são úteis.

​

O método guloso é bastante eficiente e funciona bem para uma ampla variedade de problemas.

8

Um problema de seleção de atividade

9

Um problema de seleção de atividade

Nosso primeiro exemplo é o problema de programar um recurso entre diversas atividades concorrentes. Descobriremos que um algoritmo guloso fornece um método simples para selecionar um conjunto de tamanho máximo de atividades mutuamente compatíveis.

10

Um problema de seleção de atividade

Vamos supor que temos um conjunto S = {a₁, a₂, ..., a_n} de n atividades propostas que desejam usar um recurso, como uma sala de conferências, o qual só pode ser utilizado por uma única atividade de cada vez.

11

Um problema de seleção de atividade

Cada atividade a_i tem um tempo de início s_i e um tempo de término f_i, onde 0 <= s_i < f_i < ∞. Se selecionada, a atividade a_i ocorre durante o intervalo de tempo meio aberto [s_i, f_i). As atividades a_i e a_j são compatíveis se os intervalos [s_i, f_i) e [s_j, f_j) não se superpõem (s_i >= f_j ou s_j >= f_i).

12

Um problema de seleção de atividade

O problema de seleção de atividade consiste em selecionar um subconjunto de tamanho máximo de atividades mutuamente compatíveis. Por exemplo, consideremos o seguinte conjunto S de atividades, que colocamos em ordem monotonicamente crescente de tempo de término:

13

Um problema de seleção de atividade

Para este exemplo, o subconjunto {a₃, a₉, a₁₁} consiste em atividades mutuamente compatíveis. Porém, ele não é um subconjunto máximo, pois o subconjunto {a₁, a₄, a₈, a₁₁} é maior. De fato, o conjunto {a₁, a₄, a₈, a₁₁} é um subconjunto maior de atividades mutuamente compatíveis; outro subconjunto maior é {a₂, a₄, a₉, a₁₁}.

14

Um problema de seleção de atividade

Resolveremos esse problema em várias etapas. Começamos formulando uma solução de programação dinâmica para esse problema, na qual combinamos soluções ótimas para dois subproblemas, a fim de formar uma solução ótima para o problema original. Consideraremos diversas escolhas ao determinar quais subproblemas usar em uma solução ótima.

​

​

15

Um problema de seleção de atividade

Então, observaremos que só precisamos considerar uma escolha - a escolha gulosa - e que, ao optarmos pela escolha gulosa, um dos subproblemas tem a garantia de ser vazio, de forma que só resta um subproblema não vazio. Com base nessas observações, desenvolveremos um algoritmo guloso recursivo para resolver o problema de tempo de atividades.

16

Um problema de seleção de atividade

Completaremos o processo de desenvolver uma solução gulosa convertendo o algoritmo recursivo em um iterativo. Embora as etapas que usaremos nesse exemplo sejam mais complexas que o comum para um algoritmo guloso, a ideia é ilustrar o relacionamento entre algoritmos gulosos e programação dinâmica.

17

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

Começaremos desenvolvendo uma solução de programação dinâmica para o problema. Nosso primeiro passo é encontrar a subestrutura ótima, e depois usá-la para construir uma solução ótima para o problema a partir de soluções ótimas para subproblemas.

18

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

Sabemos da necessidade de definir um espaço de subproblemas apropriado. Vamos começar definindo conjuntos

S_ij = {a_k ∈ S: f_i <= s_k < f_k <= s_j},

​

19

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

de forma que S_ij seja o subconjunto de atividades em S que podem começar após a atividade a_i terminar, e que terminam antes da atividade a_j começar.

20

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

De fato, S_ij consiste em todas as atividades compatíveis com a_i e a_j e que também são compatíveis com todas as atividades que não terminam depois de a_i terminar e com todas as atividades que não começam antes de a_j começar.

21

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

Para representar o problema inteiro, adicionamos atividades fictícias a₀ e a_n+1, e adotamos as convenções de que f₀ = 0 e s_n+1 = ∞. Então S = S_0,n+1, e os intervalos para i e j são dados por 0 <= i, j <= n+1.

22

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

Podemos restringir ainda mais os intervalos de i e j como a seguir. Vamos supor que as atividades estejam dispostas em ordem monotonicamente crescente de tempo de término:

f₀ <= f₁ <= f₂ <= ... <= f_n < f_n+1 (1)

23

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

S_ij = ∅ sempre que i >= j. Por quê?

​

Suponhamos que exista uma atividade a_k ∈ S_ij para algum i >= j, de forma que a_i segue a_j na sequência ordenada.

24

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

Assim, teríamos f_i <= s_k < f_k <= s_j < f_j. Logo, f_i < f_j, o que contradiz a hipótese de que a_i segue a_j na sequência ordenada.

25

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

Concluímos que, se ordenarmos as atividades em ordem monotonicamente crescente de tempo de término, nosso espaço de subproblemas é selecionar um subconjunto de tamanho máximo de atividades mutuamente compatíveis de S_ij, para 0 <= i < j <= n+1, sabendo que todos os outros S_ij são vazios.

26

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

Agora, usamos nossa subestrutura ótima para mostrar que podemos construir uma solução ótima para o problema a partir de soluções ótimas para subproblemas. Qualquer solução para um subproblema não vazio S_ij inclui alguma atividade a_k e qualquer solução ótima contém dentro dela soluções ótimas para instâncias de subproblemas S_ik e S_kj.

27

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

Desse modo, podemos construir um subconjunto de tamanho máximo de atividades mutuamente compatíveis em S_ij dividindo o problema em dois subproblemas, encontrando subconjuntos de tamanho máximo A_ik e A_kj de atividades mutuamente compatíveis para esses subproblemas.

28

Um problema de seleção de atividade

A subestrutura ótima do problema de seleção de atividades

​

E formando nosso subconjunto de tamanho máximo A_ij de atividades mutuamente compatíveis como

A_ij = A_ik U {a_k} U A_kj (2)

​

Uma solução ótima para o problema inteiro é uma solução para S_0,n+1.

29

Um problema de seleção de atividade

Uma solução recursiva

​

O segundo passo é definir recursivamente o valor de uma solução ótima. Para esse problema, seja c[i,j] o número de atividades em um subconjunto de tamanho máximo de atividades mutuamente compatíveis em S_ij. Temos c[i,j] = 0 sempre que S_ij = ∅; em particular, c[i,j] = 0 para i >= j.

30

Um problema de seleção de atividade

Considerando S_ij não vazio: se a_k é usado em um subconjunto de tamanho máximo de atividades compatíveis de S_ij, também usamos subconjuntos de tamanho máximo de atividades compatíveis para os subproblemas S_ik e S_kj. Usando a equação (2), temos

c[i,j] = c[i,k] + c[k,j] + 1.

31

Um problema de seleção de atividade

Essa equação recursiva pressupõe que conhecemos o valor de k, o que não ocorre. Há j-i-1 valores possíveis para k: k = i+1, ..., j-1. Tendo em vista que o subconjunto de tamanho máximo de S_ij deve usar um desses valores de k, checamos todos eles para achar o melhor. Assim, a definição recursiva completa de c[i,j] se torna

(3)

32

Um problema de seleção de atividade

Convertendo uma solução de programação dinâmica em uma solução gulosa

Agora seria o momento de escrevermos um algoritmo de PD bottom-up, baseado na equação (3). No entanto, existem duas observações importantes que nos permitem simplificar a solução.

33

Um problema de seleção de atividade

Teorema 1

Considere qualquer subproblema não vazio S_ij, e seja a_m a atividade em S_ij com o tempo de término mais antigo:

f_m = min{f_k: a_k ∈ S_ij}.

​

34

Um problema de seleção de atividade

Então,

1. A atividade a_m é usada em algum subconjunto de tamanho máximo de atividades compatíveis de S_ij.

2. O subproblema S_im é vazio, de forma que a escolha de a_m deixa o subproblema S_mj como o único que pode ser não vazio.

35

Um problema de seleção de atividade

Por que o Teorema 1 é valioso?

36

Um problema de seleção de atividade

Vimos que a subestrutura ótima varia na quantidade de subproblemas usados em uma solução ótima para o problema original e em quantas escolhas temos na determinação de quais subproblemas usar. Em nossa solução de PD, dois subproblemas são usados em uma solução ótima, e existem j-i-1 escolhas ao se resolver o subproblema S_ij.

37

Um problema de seleção de atividade

O Teorema 1 reduz ambas quantidades de forma significativa: apenas um subproblema é usado em uma solução ótima e, quando resolvemos o subproblema S_ij, só precisamos considerar uma escolha: a que tem o tempo de término mais antigo em S_ij. Felizmente, podemos determinar com facilidade que atividade é essa.

38

Um problema de seleção de atividade

Além de reduzir o número de subproblemas e o número de escolhas, o Teorema 1 produz outro benefício: podemos resolver cada subproblema de cima para baixo, em vez de usar a solução de baixo para cima de PD.

39

Um problema de seleção de atividade

Para resolver o subproblema S_ij, escolhemos a atividade a_m de S_ij com o tempo de término mais antigo e adicionamos a essa solução o conjunto de atividades usadas em uma solução ótima para o subproblema S_mj. Como sabemos que, tendo escolhido a_m, certamente usaremos uma solução para S_mj em nossa solução ótima para S_ij, não precisamos resolver S_mj antes de resolver S_ij.

40

Um problema de seleção de atividade

Para resolver S_ij, podemos primeiro escolher a_m como a atividade em S_ij com o tempo de término mais antigo, e depois resolver S_mj.

41

Um problema de seleção de atividade

Observe também que existe um padrão para os subproblemas que resolvemos. Nosso problema original é S = S_0,n+1. Suponha que escolhemos a_m1 como a atividade em S_0,n+1 com o tempo de término mais antigo. Nosso próximo subproblema é S_m1,n+1.

42

Um problema de seleção de atividade

Agora, suponha que escolhemos a_m2 como a atividade em S_m1,n+1 com o tempo de término mais antigo. Nosso próximo subproblema é S_m2,n+1. Continuando, vemos que cada subproblema terá a forma S_mi,n+1 para algum número de atividade m_i. Cada subproblema consiste nas últimas atividades a terminar, e o número de tais atividades varia de um subproblema para outro.

43

Um problema de seleção de atividade

Também há um padrão nas atividades que escolhemos. Como sempre escolhemos a atividade com o tempo de término mais antigo em S_mi,n+1, os tempos de término das atividades escolhidas sobre todos os subproblemas serão estritamente crescentes ao longo do tempo. Além disso, podemos considerar cada atividade apenas uma vez de modo geral, na ordem monotonicamente crescente de tempos de término.

​

44

Um problema de seleção de atividade

A atividade a_m que escolhemos ao resolver um subproblema é sempre aquela com o tempo de término mais antigo que pode ser programado legalmente. A atividade escolhida é portanto uma escolha "gulosa" no sentido de que, intuitivamente, ela deixa tanta oportunidade quanto possível para que as atividades restantes sejam programadas. Isto é, a escolha gulosa é a que maximiza a quantidade de tempo restante não programado.

45

Um algoritmo recursivo

46

Um algoritmo guloso recursivo

Nossa solução recursiva direta: RECURSIVE-ACTIVITY-SELECTOR. Ele toma os tempos de início e término das atividades, representados como arranjos s e f, bem como os índices iniciais i e j do subproblema S_i,j que ele deve resolver. O procedimento retorna um conjunto de tamanho máximo de atividades mutuamente compatíveis em S_i,j.

47

Um algoritmo guloso recursivo

Supomos que as n atividades de entrada estão ordenados por tempo de término monotonicamente crescente, de acordo com a equação (1). Se não, podemos ordená-las nessa ordem no tempo O(n log n), dividindo os intervalos arbitrariamente. A chamada inicial é RECURSIVE-ACTIVITY-SELECTOR(s,f,0,n+1).

48

Um algoritmo guloso recursivo

RECURSIVE-ACTIVITY-SELECTOR(s,f,i,j)

m = i+1

while m < j and s_m < f_i do // Encontrar a 1a atividade em S_ij.

m = m+1

if m < j then

return {a_m} <- RECURSIVE-ACTIVITY-SELECTOR(s,f,m,j)

else return {}

49

Um algoritmo guloso recursivo

Em uma dada chamada recursiva RECURSIVE-ACTIVITY-SELECTOR(s,f,i,j), o laço while procura pela primeira atividade em S_ij. O laço examina a_i+1, a_i+2, ..., a_j-1, até encontrar a primeira atividade a_m que seja compatível com a_i; tal atividade tem s_m >= f_i.

RECURSIVE-ACTIVITY-SELECTOR(s,f,i,j)

m = i+1

while m < j and s_m < f_i do // Encontrar a 1a atividade em S_ij.

m = m+1

50

Um algoritmo guloso recursivo

Se o laço terminar porque encontra tal atividade, o procedimento retorna a união de {a_m} com o subconjunto de tamanho máximo de S_mj retornado pela chamada recursiva RECURSIVE-ACTIVITY-SELECTOR(s,f,m,j).

RECURSIVE-ACTIVITY-SELECTOR(s,f,i,j)

...

if m < j then

return {a_m} <- RECURSIVE-ACTIVITY-SELECTOR(s,f,m,j)

​

51

Um algoritmo guloso recursivo

Como outra alternativa, o laço pode terminar porque m >= j, e nesse caso examinamos todas as atividades cujos tempos de término são anteriores a de a_j sem encontrar uma que seja compatível com a_i. Nesse caso, S_ij = {}, e então o procedimento retorna {}.

RECURSIVE-ACTIVITY-SELECTOR(s,f,i,j)

...

else return {}

52

Um algoritmo guloso recursivo

Supondo que as atividades já foram ordenadas por tempo de término, o tempo de execução da chamada RECURSIVE-ACTIVITY-SELECTOR(s, f, 0, n+1) é Θ(n). Em todas as chamadas recursivas, cada atividade é examinada exatamente uma vez no teste do laço while. Em particular, a atividade a_k é examinada na última chamada feita em que i < k.

53

Um algoritmo iterativo

54

Um algoritmo guloso iterativo

Podemos converter facilmente nosso procedimento recursivo em um iterativo. O procedimento RECURSIVE-ACTIVITY-SELECTOR termina com uma chamada recursiva a ele próprio (recursivo de final), seguida de uma operação de união.

55

Um algoritmo guloso iterativo

Em geral, é uma tarefa direta transformar um procedimento recursivo de final para uma forma iterativa; de fato, alguns compiladores de certas linguagens de programação executam essa tarefa automaticamente. RECURSIVE-ACTIVITY-SELECTOR funciona para qualquer subproblema S_ij, mas vimos que só é preciso considerar subproblemas para os quais j = n+1, isto é, subproblemas que consistem nas últimas atividades a terminar.

56

Um algoritmo guloso iterativo

O procedimento GREEDY-ACTIVITY-SELECTOR é uma versão iterativa do procedimento RECURSIVE-ACTIVITY-SELECTOR. Ele também pressupõe que as atividades de entrada estão ordenadas por tempo de término monotonicamente crescente. Ele reúne atividades selecionadas em um conjunto A e retorna esse conjunto quando termina.

57

Um algoritmo guloso iterativo

GREEDY-ACTIVITY-SELECTOR(s,f)

n = comprimento[s]

A = {1}

i = 1

for m = 2 to n do

if s_m >= f_i then

A = A ∪ {a_m}

i = m

return A

58

Um algoritmo guloso iterativo

O procedimento funciona da seguinte maneira: a variável i indexa a adição mais recente a A, correspondendo à atividade a_i na versão recursiva. Como as atividades são consideradas em ordem de tempo monotonicamente crescente, f_i é sempre o tempo de término máximo de qualquer atividade em A. Isto é,

f_i = max{f_k : a_k ∈ A}. (4)

59

Um algoritmo guloso iterativo

GREEDY-ACTIVITY-SELECTOR(s,f)

n = comprimento[s]

A = {1}

i = 1

for m = 2 to n do

if s_m >= f_i then

A = A ∪ {a_m}

i = m

return A

60

Um algoritmo guloso iterativo

As linhas 2 e 3 selecionam a atividade a₁, inicializam A para conter apenas essa atividade e inicializam i para indexar essa atividade.

​

GREEDY-ACTIVITY-SELECTOR(s,f)

n = comprimento[s]

A = {1}

i = 1

61

Um algoritmo guloso iterativo

O laço for encontra a atividade mais antiga a terminar em S_i,n+1. O laço considera cada atividade a_m por sua vez e adiciona a_m a A se ela é compatível com todas as atividades selecionadas anteriormente; tal atividade é a mais antiga a terminar em S_i,n+1.

62

Um algoritmo guloso iterativo

Para ver se a atividade a_m é compatível com cada atividade presente no momento em A, é suficiente pela equação (4) verificar se seu tempo de início s_m não é anterior ao tempo de término de f_i da atividade mais recentemente adicionada a A. Se a atividade é compatível, ela é adicionada a A e i é definido como m.

63

Um algoritmo guloso iterativo

GREEDY-ACTIVITY-SELECTOR(s,f)

n = comprimento[s]

A = {1}

i = 1

for m = 2 to n do

if s_m >= f_i then

A = A ∪ {a_m}

i = m

return A

64

Um algoritmo guloso iterativo

O conjunto A retornado pela chamada GREEDY-ACTIVITY-SELECTOR(s,f) é justamente o conjunto retornado pela chamada RECURSIVE-ACTIVITY-SELECTOR(s,f,0,n+1).

65

Um algoritmo guloso iterativo

Como a versão recursiva, o procedimento GREEDY-ACTIVITY-SELECTOR programa um conjunto de n atividades no tempo Θ(n), supondo-se que as atividades já tenham sido ordenadas inicialmente por seus tempos de término.

66

Elementos da estratégia gulosa

67

Elementos da estratégia gulosa

Um algoritmo guloso obtém uma solução ótima para um problema fazendo uma sequência de escolhas.

​

Para cada ponto de decisão do algoritmo, a opção que parece melhor no momento é escolhida.

​

​

68

Elementos da estratégia gulosa

Essa estratégia de heurística nem sempre produz uma solução ótima mas, algumas vezes ela funciona (conforme para o problema de seleção de atividades). Discutiremos agora algumas propriedades gerais de métodos gulosos.

69

Elementos da estratégia gulosa

O processo que seguimos no exemplo de seleção de atividades para desenvolver um algoritmo guloso foi um pouco mais complicado que o normal.

​

​

​

70

Elementos da estratégia gulosa

Seguimos estas etapas:

1. Determinar a subestrutura ótima do problema.

2. Desenvolver uma solução recursiva.

3. Verificar que, em qualquer fase da recursão, uma das escolhas ótimas é a escolha gulosa.

​

71

Elementos da estratégia gulosa

4. Mostrar que todos os subproblemas induzidos por ter sido feita a escolha gulosa, exceto um, são vazios.

5. Desenvolver um algoritmo recursivo que implemente a estratégia gulosa.

6. Converter o algoritmo recursivo em um algoritmo iterativo.

72

Elementos da estratégia gulosa

Seguindo estas etapas, vimos em detalhes as características de PD de um algoritmo guloso.

​

Contudo, na prática, normalmente simplificamos as etapas anteriores durante o projeto de um algoritmo guloso. Desenvolvemos nossa subestrutura com uma intenção de fazer uma escolha gulosa que deixe apenas um subproblema para resolver de forma ótima.

73

Elementos da estratégia gulosa

Por exemplo, no problema de seleção de atividades, primeiro definimos os subproblemas S_ij, onde tanto i quanto j variavam. Em seguida, descobrimos que, se sempre fizéssemos a escolha gulosa, poderíamos restringir os subproblemas à forma S_i,n+1.

74

Elementos da estratégia gulosa

Alternativamente, poderíamos ter adaptado a subestrutura ótima com uma escolha gulosa em mente. Isto é, poderíamos ter descartado o segundo subscrito e definido subproblemas da forma S_i = {a_k ∈ S: f_i <= s_k}. Então, poderíamos ter provado que uma escolha gulosa (a primeira atividade a terminar em S_i), combinada com uma solução ótima para o conjunto restante S_m de atividades compatíveis, produz uma solução ótima para S_i.

75

Elementos da estratégia gulosa

De modo mais geral, projetamos algoritmos gulosos de acordo com a seguinte sequência de etapas:

1. Moldar o problema de otimização como um problema no qual fazemos uma escolha e ficamos com um único subproblema para resolver.

​

​

76

Elementos da estratégia gulosa

2. Provar que sempre existe uma solução ótima para o problema original que faz a escolha gulosa, de modo que a escolha gulosa é sempre segura.

​

77

Elementos da estratégia gulosa

3. Demonstrar que, tendo feito a escolha gulosa, o que resta é um subproblema com a propriedade de que, se combinarmos uma solução ótima para o subproblema com a escolha gulosa que fizemos, chegamos a uma solução ótima para o problema original.

78

Elementos da estratégia gulosa

Apesar disso, embaixo de todo algoritmo guloso, quase sempre há uma solução de programação dinâmica (PD) mais incômoda.

​

Então surge a pergunta:

Como saber se um algoritmo guloso resolverá um determinado problema de otimização?

​

79

Elementos da estratégia gulosa

Em geral, não há como saber, mas existem dois ingredientes que são exibidos pela maioria dos problemas que se prestam a uma estratégia gulosa: a propriedade de escolha gulosa e a subestrutura ótima.

80

Elementos da estratégia gulosa

Se pudermos demonstrar que o problema tem essas propriedades, estaremos no bom caminho para desenvolver um algoritmo guloso para ele.

81

Propriedade de escolha gulosa

82

Propriedade de escolha gulosa

A primeira propriedade chave é a propriedade de escolha gulosa: uma solução globalmente ótima pode ser alcançada fazendo-se uma escolha localmente ótima (gulosa).

​

Em outras palavras, quando estamos considerando que escolha fazer, efetuamos a escolha que parece melhor no problema atual, sem considerar resultados de subproblemas.

83

Propriedade de escolha gulosa

É nesse ponto que os algoritmos gulosos diferem da programação dinâmica.

​

Na programação dinâmica, fazemos uma escolha em cada passo, mas a escolha pode depender das soluções para subproblemas. Consequentemente, resolvemos problemas de PD de baixo para cima, progredindo de subproblemas menores para subproblemas maiores.

84

Propriedade de escolha gulosa

Em um algoritmo guloso, fazemos qualquer escolha que pareça melhor no momento e depois resolvemos o subproblema que surge após a escolha ser feita.

85

Propriedade de escolha gulosa

A escolha pode depender das escolhas até o momento, mas não pode depender de nenhuma escolha futura ou das soluções para subproblemas. Desse modo, diferente da PD, que resolve os subproblemas de baixo para cima, uma estratégia gulosa em geral progride de cima para baixo, fazendo uma escolha gulosa após outra, reduzindo de modo iterativo cada instância do problema dado a um problema menor.

86

Propriedade de escolha gulosa

Devemos provar que uma escolha gulosa em cada passo produz uma solução globalmente ótima, e é nesse ponto que pode ser necessária alguma inteligência. Normalmente, como no caso do Teorema 1, a prova examina uma solução globalmente ótima para algum subproblema.

87

Propriedade de escolha gulosa

Em seguida, ela mostra que a solução pode ser modificada para usar a escolha gulosa, resultando em um subproblema similar, embora menor.

88

Propriedade de escolha gulosa

A propriedade de escolha gulosa frequentemente nos oferece alguma eficiência ao fazermos nossa escolha em um subproblema.

​

Por exemplo, no problema de seleção de atividades, supondo que já ordenamos as atividades em ordem monotonicamente crescente de tempos de término, precisamos examinar cada atividade apenas uma vez.

89

Propriedade de escolha gulosa

Com frequência, pelo pré-processamento da entrada ou usando uma estrutura de dados apropriada (muitas vezes, uma fila de prioridades), podemos fazer escolhas gulosas rapidamente, produzindo desse modo um algoritmo eficiente.

90

Subestrutura ótima

91

Subestrutura ótima

Um problema exibe subestrutura ótima se uma solução ótima para o problema contém dentro dela soluções ótimas para subproblemas.

​

Essa propriedade é crucial para avaliação do uso de PD, como também de algoritmos gulosos.

92

Subestrutura ótima

Como exemplo de subestrutura ótima, vimos que se uma solução ótima para o subproblema S_ij inclui uma atividade a_k, então ela também deve conter soluções ótimas para os subproblemas S_ik e S_kj.

93

Subestrutura ótima

Dada essa subestrutura ótima, demonstramos que, se soubéssemos que atividade usar como a_k, poderíamos construir uma solução ótima para S_ij selecionando a_k juntamente com todas as atividades em soluções ótimas para os subproblemas S_ik e S_kj.

​

​

94

Subestrutura ótima

Com base nisso, pudemos escrever a recorrência que descreveu o valor de uma solução ótima.

95

Subestrutura ótima

Normalmente usamos uma abordagem mais direta relativa à subestrutura ótima quando a aplicamos a algoritmos gulosos. Conforme já dito, nos demos o luxo de pressupor que chegamos a um subproblema tendo feito a escolha gulosa no problema original.

96

Subestrutura ótima

Na realidade, tudo que precisamos fazer é demonstrar que uma solução ótima para o subproblema, combinada com a escolha gulosa já feita, produz uma solução ótima para o problema original. Esse esquema utiliza implicitamente a indução sobre os subproblemas para provar que fazer a escolha gulosa em cada etapa produz uma solução ótima.

97

Estratégia Gulosa

vs

Programação Dinâmica

98

Estratégia Gulosa vs Programação Dinâmica

Pelo fato da propriedade de subestrutura ótima ser explorada tanto por estratégias gulosas quanto por estratégias de programação dinâmica, alguém poderia ser tentado a gerar uma solução de programação dinâmica para um problema quando uma solução gulosa fosse suficiente, ou alguém poderia pensar erroneamente que uma solução gulosa funcionaria, quando de fato fosse necessária uma solução de programação dinâmica.

99

Estratégia Gulosa vs Programação Dinâmica

Para ilustrar as sutilezas entre as duas técnicas, vamos investigar duas variantes de um problema clássico de otimização.

100

Estratégia Gulosa vs Programação Dinâmica

O problema da mochila 0-1 é apresentado como a seguir.

Um ladrão que rouba uma loja encontra n itens: o i-ésimo item vale v_i reais e pesa w_i quilos, onde v_i e w_i são inteiros. Ele deseja levar uma carga tão valiosa quanto possível, mas pode carregar no máximo W quilos em sua mochila, para algum inteiro W.

101

Estratégia Gulosa vs Programação Dinâmica

Que itens ele deve levar? (Isso se chama problema da mochila 0-1 porque cada item deve ser levado ou deixado para trás; o ladrão não pode levar uma quantidade fracionária de um item ou levar um item mais de uma vez.)

102

Estratégia Gulosa vs Programação Dinâmica

No problema da mochila fracionária, a configuração é a mesma, mas o ladrão pode levar frações de itens, em vez de ter de fazer uma escolha binária (0-1) para cada item. Você pode imaginar um item no problema da mochila 0-1 como sendo algo semelhante a um lingote de ouro, enquanto um item no problema da mochila fracionária é semelhante ao ouro em pó.

103

Estratégia Gulosa vs Programação Dinâmica

Ambos os problemas de mochilas exibem a propriedade de subestrutura ótima.

​

No caso do problema 0-1, considere a carga mais valiosa que pesa no máximo W quilos. Se removermos o item j dessa carga, a carga restante deve ser a carga mais valiosa que pese no máximo W - w_j que o ladrão pode levar dos n-1 itens originais, excluindo j.

104

Estratégia Gulosa vs Programação Dinâmica

No caso do problema fracionário comparável, considere que, se removermos um peso w de um item j da carga ótima, a carga restante deve ser a carga mais valiosa que pese no máximo W - w que o ladrão pode levar dos n-1 itens originais, mais w_j - w do item j.

105

Estratégia Gulosa vs Programação Dinâmica

Embora os problemas sejam semelhantes, o problema da mochila fracionária pode ser resolvido por uma estratégia gulosa, enquanto o problema 0-1 não pode. Para resolver o problema fracionário, primeiro calculamos o valor por quilo v_i/w_i para cada item.

106

Estratégia Gulosa vs Programação Dinâmica

Obedecendo a uma estratégia gulosa, o ladrão começa levando o máximo possível do item com o maior valor por quilo. Se o suprimento desse item se esgotar e ele ainda puder levar mais, o ladrão levará tanto quanto possível do item com o próximo maior valor por quilo e assim por diante até não poder levar mais nada.

107

Estratégia Gulosa vs Programação Dinâmica

Desse modo, ordenando os itens pelo valor por quilo, o algoritmo guloso é executado no tempo O(n log n).

108

Estratégia Gulosa vs Programação Dinâmica

Para ver que essa estratégia gulosa não funciona no caso do problema da mochila 0-1, consideremos a instância do problema ilustrada a seguir.

109

(a) (b) (c)

Estratégia Gulosa vs Programação Dinâmica

Existem 3 itens, e a mochila pode conter 50 quilos. O item 1 pesa 10 quilos e vale R$ 60. O item 2 pesa 20 quilos e vale R$ 100. O item 3 pesa 30 quilos e vale R$ 120. Desse modo, o valor por quilo do item 1 é R$ 6 por quilo, que é maior que o valor por quilo do item 2 (R$ 5/kg) ou do item 3 (R$ 4/kg).

​

​

110

Estratégia Gulosa vs Programação Dinâmica

Assim, a estratégia gulosa levaria o item 1 primeiro. Porém, como podemos ver na análise de caso da figura (b), a solução ótima leva os itens 2 e 3, deixando o item 1 de fora.

111

(b)

Estratégia Gulosa vs Programação Dinâmica

As duas soluções possíveis que envolvem o item 1 não são ótimas.

112

(b)

Estratégia Gulosa vs Programação Dinâmica

Contudo, para o problema fracionário comparável, a estratégia gulosa, que leva o item 1 primeiro, produz uma solução ótima, conforme a figura (c).

113

(c)

Estratégia Gulosa vs Programação Dinâmica

Levar o item 1 não funciona no problema 0-1, porque o ladrão é incapaz de preencher plenamente sua mochila, e o espaço vazio diminui o valor efetivo por quilo de sua carga.

114

Estratégia Gulosa vs Programação Dinâmica

No problema 0-1, quando consideramos um item para inclusão na mochila, devemos comparar a solução para o subproblema no qual o item é incluído com a solução para o subproblema no qual o item é excluído, antes de podermos fazer a escolha.

115

Estratégia Gulosa vs Programação Dinâmica

O problema formulado desse modo ocasiona muitos subproblemas superpostos - um caso legítimo de programação dinâmica e, de fato, a programação dinâmica pode ser usada para resolver o problema 0-1.

116

Códigos de Huffman

117

Códigos de Huffman

Os códigos de Huffman constituem uma técnica amplamente utilizada e muito eficiente para comprimir dados, guardando a relação típica de 20 a 90%, dependendo das características dos dados que estão sendo comprimidos.

118

Códigos de Huffman

O algoritmo guloso de Huffman utiliza uma tabela das frequências de ocorrência dos caracteres para elaborar um modo ótimo de representar cada caractere como uma cadeia binária.

119

Códigos de Huffman

Vamos supor que temos um arquivo de dados de 100.000 caracteres que desejamos armazenar em forma compacta. Observamos que os caracteres no arquivo ocorrem com frequências dadas na figura a seguir.

120

Códigos de Huffman

Isto é, aparecem somente seis caracteres diferentes, e o caractere a ocorre 45.000 vezes.

​

Há muitas maneiras de representar um arquivo de informações como esse. Consideramos o problema de projetar um código de caracteres binários (ou código) no qual cada caractere é representado por uma cadeia binária única.

121

Códigos de Huffman

Se usarmos um código de comprimento fixo, precisaremos de 3 bits para representar seis caracteres: a = 000, b = 001, ..., f = 101. Esse método exige 300.000 bits para codificar o arquivo inteiro.

​

Podemos fazer algo melhor?

122

Códigos de Huffman

Um código de comprimento variável pode funcionar consideravelmente melhor que um código de comprimento fixo, fornecendo palavras de código curtas a caracteres frequentes e palavras de código longas a caracteres pouco frequentes.

123

Códigos de Huffman

A figura mostra um código desse tipo; aqui, a cadeia de 1 bit 0 representa a, e a cadeia de 4 bits 1100 representa f.

124

Códigos de Huffman

Esse código exige

​

(45*1 + 13*3 + 12*3 + 16*3 + 9*4 + 5*4)*1.000 = 224.000 bits

​

para representar o arquivo, uma economia de aproximadamente 25%. De fato, esse é um código de caracteres ótimo para esse arquivo.

125

Códigos de Huffman - códigos de prefixo

Consideramos aqui apenas códigos nos quais nenhuma palavra de código é também um prefixo de alguma outra palavra de código. Tais códigos são chamados códigos de prefixo.

126

Códigos de Huffman - códigos de prefixo

É possível mostrar que a compressão de dados ótima que se pode obter por meio de um código de caracteres sempre pode ser alcançada com um código de prefixo, e assim não há perda de generalidade em restringirmos nossa atenção a códigos de prefixo.

127

Códigos de Huffman - códigos de prefixo

A codificação é sempre simples para qualquer código de caracteres binários; simplesmente concatenamos as palavras de código que representam cada caractere do arquivo. Por exemplo, com o código de prefixo de comprimento variável da figura, codificamos o arquivo de 3 caracteres abc como 0.101.100 = 10101100, onde usamos "." para denotar a concatenação.

128

Códigos de Huffman - códigos de prefixo

Os códigos de prefixo são desejáveis porque simplificam a decodificação. Como nenhuma palavra de código é um prefixo de qualquer outra, a palavra de código que inicia um arquivo codificado não é ambígua.

​

​

129

Códigos de Huffman - códigos de prefixo

Podemos simplesmente identificar a palavra de código inicial, traduzi-la de volta para o caractere original, removê-la do arquivo codificado e repetir o processo de decodificação no restante do arquivo codificado.

130

Códigos de Huffman - códigos de prefixo

O processo de decodificação precisa de uma representação conveniente para o código de prefixo, de forma que a palavra de código inicial possa ser extraída com facilidade. Uma árvore binária cujas folhas são os caracteres dados fornece tal representação.

131

Códigos de Huffman - códigos de prefixo

Interpretamos a palavra de código binária para um caractere como o caminho desde a raiz até esse caractere, onde 0 significa "vá para o filho da esquerda" e 1 significa "vá para o filho da direita".

132

Códigos de Huffman - códigos de prefixo

Um código ótimo para um arquivo é sempre representado por uma árvore binária cheia, na qual cada nó que não é uma folha tem dois filhos.

​

​

133

Códigos de Huffman - códigos de prefixo

Tendo em vista que podemos restringir nossa atenção a árvores binárias completas, dizemos que, se C é o alfabeto do qual os caracteres são obtidos e todas as frequências de caracteres são positivas, então a árvore para um código de prefixo ótimo tem exatamente |C| folhas, uma para cada letra do alfabeto, e |C| - 1 nós internos.

134

A construção de um código de Huffman

Huffman criou um algoritmo guloso que produz um código de prefixo ótimo chamado código de Huffman.

​

No pseudocódigo a seguir, supomos que C é um conjunto de n caracteres e que cada caractere c ∊ C é um objeto com uma frequência definida f[c].

​

135

A construção de um código de Huffman

O algoritmo constrói de baixo para cima a árvore T correspondente ao código ótimo. Ele começa com um conjunto de |C| folhas e executa uma sequência de |C|-1 operações de "intercalação" para criar a árvore final. Uma fila de prioridade mínima Q, tendo f como chave, é usada para identificar os dois objetos menos frequentes a serem intercalados.

136

A construção de um código de Huffman

O resultado da intercalação de dois objetos é um novo objeto cuja frequência é a soma das frequências dos dois objetos que foram intercalados.

​

137

A construção de um código de Huffman

HUFFMAN(C)

n = |C|

Q = C

for i = 1 to n-1 do

alocar um novo nó z

esquerda[z] = x = EXTRACT-MIN(Q)

direita[z] = y = EXTRACT-MIN(Q)

f[z] = f[x] + f[y]

INSERT(Q, z)

return EXTRACT-MIN(Q) // retornar a raiz da árvore

138

A construção de um código de Huffman

Em nosso exemplo, o algoritmo de Huffman procede do seguinte modo.

139

A construção de um código de Huffman

Tendo em vista que existem 6 letras no alfabeto, o tamanho da fila inicial é n = 6, e 5 passos de intercalação são exigidos para construir a árvore. A árvore final representa o código de prefixo ótimo. A palavra de código para uma letra é a sequência de etiquetas de arestas no caminho da raiz até a letra.

140

A construção de um código de Huffman

A linha 2 inicializa a fila de prioridades Q com os caracteres em C.

HUFFMAN(C)

n = |C|

Q = C

141

A construção de um código de Huffman

O laço for extrai repetidamente os dois nós x e y de frequência mais baixa da fila e os substitui na fila por um novo nó z representando sua intercalação. A frequência de z é calculada como a soma das frequências de x e y.

for i = 1 to n-1 do

alocar um novo nó z

esquerda[z] = x = EXTRACT-MIN(Q)

direita[z] = y = EXTRACT-MIN(Q)

f[z] = f[x] + f[y]

142

A construção de um código de Huffman

O nó z tem x como seu filho da esquerda e y como seu filho da direita. Depois de n-1 intercalações, o único nó da esquerda na fila - a raiz da árvore de código - é retornado.

​

return EXTRACT-MIN(Q) // retornar a raiz da árvore

​

143

A construção de um código de Huffman

A análise do tempo de execução do algoritmo de Huffman supõe que Q é implementada como um heap binário. Para um conjunto C de n caracteres, a inicialização de Q na linha 2 pode ser executada em tempo O(n) usando-se o procedimento BUILD-MIN-HEAP.

​

144

A construção de um código de Huffman

O laço for é executado exatamente n-1 vezes e, como cada operação de heap exige o tempo O(log n), o laço contribui com O(n log n) para o tempo de execução.

​

Desse modo, o tempo de execução total de HUFFMAN em um conjunto de n caracteres é O(n log n).

​

145

Fundamentos teóricos de métodos gulosos

146

Fundamentos teóricos de métodos gulosos

A teoria sobre algoritmos gulosos é útil para determinarmos quando o método produz uma solução ótima. Ela envolve estruturas combinatórias conhecidas como "matróides".

​

​

​

147

Fundamentos teóricos de métodos gulosos

Embora essa teoria não cubra todos os casos aos quais um método guloso se aplica, ela envolve muitos casos de interesse prático. Além disso, essa teoria está sendo rapidamente desenvolvida e estendida para cobrir muitas outras aplicações.

148

Matróides

Um matróide é um par ordenado M = (S, l) que satisfaz às condições a seguir:

​

1. S é um conjunto finito não vazio.

​

​

149

Matróides

2. l é uma família não vazia de subconjuntos de S, chamados subconjuntos independentes de S, tais que, se B ∊ l e A ⊆ B, então A ∊ l. Dizemos que l é hereditário se ele satisfaz a essa propriedade. Observe que o conjunto vazio ∅ é necessariamente um membro de l.

​

150

Matróides

3. Se A ∊ l, B ∊ l e |A| < |B|, então existe algum elemento x ∊ B - A tal que A U {x} ∊ l. Dizemos que M satisfaz à propriedade de troca.

151

Matróides

O termo matróide se deve a Hassler Whitney. Ele estava estudando matróides de matrícula, nos quais os elementos de S são as linhas de uma dada matriz, e um conjunto de linhas é independente se elas são linearmente independentes no sentido usual.

​

​

​

152

Matróides

Como outro exemplo de matróides, considere o matróide gráfico M_G = (S_G, l_G), definido em termos de um grafo não orientado G = (V, E):

- O conjunto S_G é definido como E, o conjunto de arestas de G.

- Se A é um subconjunto de E, então A ∊ l_G se e somente se A é acíclico.

153

Matróides

O matróide gráfico está relacionado com o problema da árvore de amplitude mínima.

​

Teorema: Se G é um grafo não orientado, então M_G = (S_G, l_G) é um matróide.

154

Matróides

Teorema: Todos os subconjuntos independentes máximos em um matróide têm o mesmo tamanho.

​

​

155

Algoritmos gulosos em um matróide ponderado

Muitos problemas para os quais uma abordagem gulosa fornece soluções ótimas podem ser formulados em termos de encontrar um subconjunto independente de peso máximo em um matróide ponderado.

​

156

Algoritmos gulosos em um matróide ponderado

Isto é, temos um matróide ponderado M = (S, l) e desejamos encontrar um conjunto independente A ∊ l tal que w(A) seja maximizado. Chamamos tal subconjunto de subconjunto ótimo do matróide.

157

Resumindo...

158

Algoritmos Gulosos

Como os algoritmos de programação dinâmica, os algoritmos gulosos em geral se aplicam a problemas de otimização em que diversas escolhas devem ser feitas, a fim de se chegar a uma solução ótima. A ideia de um algoritmo guloso é fazer cada escolha de uma maneira ótima para as condições locais (a escolha mais apetitosa).

159

Algoritmos Gulosos

Um exemplo é a troca de moedas: para minimizar o número de moedas necessárias para trocar uma quantia dada, basta selecionar repetidamente a moeda de maior valor de face que não seja maior que a quantia ainda devida.

160

Algoritmos Gulosos

Existem muitos problemas desse tipo para os quais uma abordagem gulosa fornece uma solução ótima muito mais depressa que uma abordagem de programação dinâmica. Contudo, nem sempre é fácil determinar se uma abordagem gulosa será efetiva.

161

Referências

162

Referências

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Algoritmos - Teoria e Prática (tradução da 2ª Ed. Americana), Ed. Campus (2002).

Capítulo 16

163

Referências

E. Horowitz, S. Sahni, S. Rajasekaran. Computer Algorithms.

Capítulo 4

​

M. Soltys. An Introduction to the Analysis of Algorithms. 2nd edition.

Capítulo 2

164

Outros materiais

165

Links interessantes

Links interessantes acerca de algoritmos gulosos:

http://www.cs.mun.ca/~kol/courses/3719-w12/scheduling.pdf

​

http://www.cs.sfu.ca/~kabanets/307/sched307.pdf

166

Links interessantes

Vídeos ilustrando alguns problemas

​

Map Coloring: https://www.youtube.com/watch?v=vGjsi8NIpSE

​

Job Scheduling Problem: https://www.youtube.com/watch?v=Hq4VrKqAb88

167

Técnicas de Análise de Algoritmo

Algoritmos Gulosos

Alysson Milanez