MO417 - Ata da Aula

Algoritmos Gulosos I

1. Introdução
2. Algoritmos Gulosos
2.1. Visão Geral
2.2. Seleção de Atividades
2.3. Teorema 16.1
2.4. Algoritmo guloso interativo
2.5. Elementos da estratégia gulosa
2.5.1. Escolha gulosa
2.5.2. Subestrutura ótima
2.5.3. Estratégia gulosa versus programação dinâmica
2.6. Mochila 0-1 versus mochila fracionária.
3. Conclusões
4. Referências bibliográficas

Resumo

Os algoritmos gulosos são usados em alguns problemas onde podemos também utilizar programação dinâmica, porém com um custo de execução menor. Esses algoritmos utilizam alguma heurística para encontrar a solução ótima. Normalmente se faz uma escolha que parece ser ótima em determinado passo, e em uma análise top-down, vai se resolvendo os subproblemas até que (como esperado) se cheque na solução ótima global do problema. Por este motivo, nem todos os algoritmos onde a programação dinâmica é aplicada, por compartilhar essa propriedade de subestrutura ótima, uma estratégia gulosa pode ser utilizada. De fato, só poderemos utilizar uma estratégia gulosa quando a partir de uma escolha ótima local que fizermos, subdividirmos nosso problema em apenas um subproblema a ser solucionado, não dependendo de outras escolhas ou da solução de outros subproblemas. Além disso, deve existir um modo de fazer esta escolha local que funcione.




1. Introdução

Uma breve descrição dos tópicos do capítulo 16 do livro do Cormen (2002) será apresentada nesta ata. Todos os tópicos aqui apresentados foram abordados durante a aula da disciplina Complexidade de Algoritmos ministrada no 1º semestre letivo de 2003 pelo professor João Meidanis, na data do dia 09 de abril de 2003, das 08:00 às 10:00.



2. Algoritmos Gulosos

2.1. Visão Geral

          Os algoritmos para problemas de otimização geralmente seguem uma sequência de passos, com um conjunto de escolhas a cada passo. Os algoritmos gulosos sempre fazem uma escolha que parece melhor em um determinado momento, o que significa dizer que esses algoritmos fazem uma escolha local ótima na esperança dessa escolha tender a uma solução global ótima. Discutiremos a seguir alguns problemas de otimização que são resolvidos utilizando algoritmos gulosos, e como determinar quanto podemos aplicar esta estratégia para encontrar uma solução para um determinado problema de otimização.



2.2. Seleção de Atividades

          O problema de Seleção de atividades consiste agendar a utilização de um determinado recurso por um conjunto de atividades. Suponha que você tenha um conjunto S = {a₁, a₂,..,a_n} de n atividades propostas que desejam utilizar um mesmo recurso, tal como uma sala de conferências, que pode ser utilizada por apenas uma atividade por um determinado período de tempo. Cada atividade a_i tem um tempo de início s_i e um tempo de término f_i, onde s_i < f_i. Duas 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 sobrepõem, i.e., se s_i >= f_j ou se s_j >= f_i. O problema de Seleção de Atividades consiste em encontrar o subconjunto de tamanho máximo de atividades mutuamente compatíveis.


          Discussão em aula a respeito desse tópico:
• Prof. seleciona o colega Alexandro para enunciar o problema de seleção de atividades (enunciado bem completo). Colega Alexandro: Você tem um conjunto de atividades que possuem um tempo de início e um tempo de término. Por exemplo, você tem em um conjunto {a₁, a₂, ... a_n}. Cada atividade a_i dessas tem um tempo de início e de término.
  Interrupção do prof. para um comentário: Por exemplo, começar as quatro horas da tarde (16:00) e terminar as cinco e meia (17:30). Os tempos são fixos.
  Alexando continua: O que você tem que fazer? Você tem que encontrar um subconjunto dessas atividades, tal que cada elemento desse subconjunto não seja superposto a outro, i.e., o tempo de início de um elemento não seja menor que o tempo de término de um outro. A idéia é você pegar um subconjunto que tenha essa propriedade, e este subconjunto seja o maior, o maior subconjunto possível. Para que isso seria interessante? Você poderia ter um recurso que seria utilizado por este conjunto, e você queira utilizar o máximo de atividades para maximizar a utilização deste recurso.
• Prof. complementa: Por exemplo, uma sala de conferência ou uma sala de reuniões. Vários grupos querem usar a sala e cada um tem uma necessidade.
  Alexandro interrompe para comentar: Ou seja, você está privilegiando a quantidade.
  Prof. continua: Você está privilegiando a quantidade! Eu vou alocar, alguns vão ficar sem, mas eu vou alocar o máximo possível. (Reforça)Você está privilegiando a quantidade!



2.3. Teorema 16.1

           Considere um subproblema não vazio S_i,j, e seja a_m uma atividade com o menor tempo de término:
f_m = min{f_k: a_k Pertence S_i,j}.
Então:
1. A atividade a_m está presente em um subconjunto S_i,j de tamanho máximo de atividades mutuamente compatíveis
2. O subproblema S_i,m é vazio, de tal maneira que a_m deixa o subproblema S_m,j como o único que pode ser não vazio

A prova para este teorema está no livro texto.


          Discussão em aula a respeito desse tópico:
• Prof. seleciona o colega Carlos e pergunta sobre o Teorema 16.1: Talvez a gente precise de uns pré-requisitos pra falar sobre este teorema. Carlos: Acho que precisa falar sobre a subestrutura ótima! Prof. comenta: Então tudo bem, fale-nos sobre a subestrutura ótima. Carlos: A subestrutura ótima é você ter um intervalo, ou melhor, um intervalo onde o tempo de iníncio e término dela não sobreponha as atividades anterior e posterior, pra você poder fazer recursivamente a união desses intervalos para ter a solução ótima.
  Prof. comenta: Vamos por parte. Eu achei que o teorema cita uma coisa chamada S_i,j. Nós não sabemos o que é esse S_i,j.
  Carlos: S_i,j é o subconjunto das atividades lógicas. A sequência ocupa o recurso.
  Prof. pergunta: Que subconjunto?
  Carlos: Subconjunto das atividades desse intervalo
  Prof. pergunta: Que intervalo?
  Carlos: Intervalo de i até j, que vai da atividade a_i até a atividade a_j.
  Prof. comenta: Não sei se é bem isso. A atividade a_i está, por exemplo, no conjunto S_{i j}?
  Carlos: É o subconjunto das atividade a_i até a atividade a_j que estão em sequência.
  Alexandro comenta: Ou seja, depois que a_i terminou.
  Prof. comenta: Tem mais um problema aqui. Se nós comparamos números, eu entendo que você fale as palavras esse é menor que aquele e todos que estão entre esse e aquele. Porém, quando nós estamos falando de intervalos, nem sempre você pode falar que este esta antes daquele ou todos entre este e aquele. Intervalos não são comparáveis, porque cada intervalo tem um ponto de início e ponto de fim. O que você quer dizer quando você fala este antes daquele?
  Carlos: O ponto final de um está antes do ponto inicial do seguinte, eles nunca se sobrepõem.
  Prof. comenta: Mas na entrada, as atividades se sobrepõem.
  Carlos: Mas este conjunto S_i,j será um de tal forma que elas não se sobrepõem entre a_i e a_j.
  Prof. comenta: Eu discordo de você. S_i,j pode conter atividades que se sobrepõem sim.
  Alexandro comenta novamente Só está limitando os extremos.
  Prof. comenta: Só está limitando os extremos!
  Augusto. comenta: As atividades são compativies com a_j mas que podem não ser compatíveis com todas as atividades.
  André. comenta: As atividades que começam depois ou igual ao fim de a_i, e terminam antes ou igual ao início de a_j.
  Prof. solicita ao Carlos para ler a definição na página 297. Solicita que ele resuma em uma frase com menos de 10 palavras.
  Carlos: Pelo que eu consigo entender aqui é que as atividades não estão se sobrepondo, elas são independentes.
  Prof. comenta: Então vamos ter que fazer um desenho (levanta e vai até a lousa pra desenhar):
  
  

  Fig. 1: Exemplo para seleção de atividades, Teorema 16.1.

  Prof. define: Todas as atividades totalmente contidas no intervalo de s_i a f_j.
• Prof. seleciona o colega Ivan e pergunta: Sabemos o que é o problema e sabemos o que é S_i,j, que é um subproblema. Pelo jeito, este problema goza da propriedade da subestrutura ótima, para este tipo de subproblema. Ou seja, se eu tenho uma solução para S, esta solução contém uma solução para S_i,j para todo i e j? Diga-nos o que diz o teorema 16.1.
  Ivan: Ele vai considerar uma atividade a_m tal que ela tenha o tempo de término mais antigo, i.e., ela termina primeiro dentro do subconjunto S_i,j. Sobre esta condição podemos afirmar 2 fatos:
  
  1º: Essa atividade vai estar no subconjunto S_i,j;
  2º: S_m,j != Ø.
  
  Prof. Comenta: A atividade a_m é aquela que tem o final maior, é a primeira que termina. Então ela vai estar em alguma solução. E outra, qualquer subproblema da forma [i,m) é vazio.
  André interrompe para comentar: Intuitivamente essa segunda dá pra entender, mas a prova dele eu não consegui entender mesmo tendo lido cerca de 3 vezes. Inclusive acho que tem um erro e até discordo de algumas coisas.
  Prof. Comenta: Entendi o que ele quer fazer. Suponha que você tenha uma solução ótima. Ele quer tirar o primeiro cara dessa solução e colocar a_m no lugar. Ele deveria então ter definido A'_i,j da forma:
  A'_i,j = (A_i,j \ A_k) U {a_m}
  Deveria ser assim na minha opinião. Então o teorema fala o seguinte: Em qualquer subproblema não vazio da forma S_i,j, você pega o cara que termina primeiro. Esse cara você pode tirar ele porque alguma solução ótima vai contê-lo. Isso imediatamente nos dá uma divisão do problema em 2 subproblemas. Quando escolho um cara e digo que ele vai estar na solução ótima, eu na verdade divido em 2 subproblemas: o que acontece antes dele e o que acontece depois dele. Neste caso, o que acontece antes dele não acontece nada. Isso nos dá uma idéia de como funciona o algoritmo guloso.
  



2.4. Algoritmo guloso interativo

           A seguir descrevemos um algoritmo guloso interativo para solucionar o problema de seleção de atividades. No entanto, é assumido que o conjunto de atividades fornecido como entrada esteja ordenado pelo tempo de término das atividades, i.e., da atividade mais antiga (a que termina primeiro) para a mais nova (última a terminar).
Caso contrário, poderíamos então ordenar o conjunto de atividades pelo seu tempo de término, mas isso levaria O(n lg n).

      Greed-Activity-Selector(S)
      1  n <- length(S)
      2  A <- {Ai}
      3  j <- 1
      4  for i <- 2 to n
      5      do if si >= fj
      6            then A <- A U {Ai}
      7                 j <- i
      8  return A
      

Observe que o conjunto A é a coleção de atividades selecionadas. A variável j especifica o último elemento adicionado a A.



          Discussão em aula a respeito desse tópico:
• Prof. seleciona o colega Fábio para explicar como é o algoritmo guloso.
  Fábio: O algoritmo seleciona o elemento com menor tempo de término, e depois ele pega o próximo que começa depois dele, pois os elementos estão em ordenados crescentemente pelo tempo de término, e assim em diante.
  Prof. pede para o Fábio fazer utilizando o desenho que ilustrou o teorema 16.1.
  Fábio: Ficaria assim (com X os que ele selecionou, da esquerda para a direita, após algumas discussões paralelas sobre a forma como Fábio encontrou a solução):
  
  

  Fig. 2: Exemplo do algoritmo guloso interativo.

  Então uma solução possível seriam as atividades 1,3,5 e 8. O maior tamanho vai ser sempre 4.
  Prof. comenta: Você desafia então alguém a encontrar mais que quatro! Outra solução com 4 elementos é possível, mas maior que 4 não dá.
  Prof. Comenta: No caso de um algoritmo errôneo, ele pode pensar em pegar o primeiro cara que der sopa pela frente, o que começa primeiro. Com isso o resultado seria errado.
  André comenta: Na versão em português, tem uma "setinha" na linha 5 do algoritmo recursivo, que na versão em inglês é uma união.
  




2.5. Elementos da estratégia gulosa

           Um algoritmo guloso consegue uma solução ótima para um problema fazendo uma sequência de escolhas, para as quais, ele considera a melhor naquele momento. Essa heurística nem sempre resulta em uma solução ótima, mas algumas vezes isso é verificado. Discutiremos quais as propriedades que os métodos gulosos devem ter.


2.5.1. Propriedade da escolha gulosa

Uma solução ótima global pode ser obtida a partir de uma escolha gulosa local. Isso representa uma das diferenças entre algoritmos gulosos e a programação dinâmica. Na programação dinâmica, nós fazemos uma escolha para cada passo, porém, cada escolha pode depender da solução dos subproblemas. Nos algoritmos gulosos, fazemos uma escolha que parece melhor naquele instante, independente da solução dos subproblemas e de nenhuma outra escolha futura. Enquanto que na programação dinâmica o problema é resolvida por bottom up, a estratégia gulosa resolve o problema resolve por top-down, fazendo uma escolha gulosa atrás de outra, reduzindo interativamente cada instância dada do problema em outra menor.

2.5.2. Subestrutura Ótima

Um problema possui a propriedade de subestrutura ótima se uma solução ótima para o problema é composta por soluções ótimas para subproblemas. Observe essa propriedade na prova do teorema 16.1.

2.5.3. Estratégia gulosa versus programação dinâmica

O fato de possuir subestrutura ótima pode induzir à utilização de algoritmos gulosos para resolver problemas que deveriam ser resolvidos por programação dinâmica. Nem todo problema que pode ser resolvido por programação dinâmica também pode ser resolvido utilizando alguma estratégia gulosa. É preciso também que a estratégia gulosa deixe apenas um subproblema para ser resolvido, para que a escolha a ser feita não dependa de escolhas futuras nem da solução de subproblemas.


          Discussão em aula a respeito desse tópico:
• Prof. seleciona o colega Augusto para falar sobre estratégia gulosa. Augusto: Para um dado problema de otimização, você escolhe uma estratégia gulosa e usa esta estratégia para solucionar cada subproblema.
  Eric comenta: Ele espera que a cada passo, pegando a solução ótima, no final vai ser um resultado ótimo do problema.
  Prof. comenta: o teorema 16.1 garante isso. Primeiro ele mostra que se você escolher a_m você nunca vai estar errado. Você pode ter outras soluções, mas uma delas pelo menos vai ter a_m.
  Alexandro comenta: Aqui ele diz que só sobra um subproblema para resolver. O outro é vazio.
  Prof. comenta: Se sobrar mais de um, você vai ter que pegar a programação dinâmica e tentar resolver. Talvez nem com a programação dinâmica é resolvido.
  




2.6. Mochila 0-1 versus mochila fracionária

           Considere o seguinte problema: um ladrão assalta uma loja e encontra n itens, onde cada item i tem peso w_i e valor v_i. Ele quer levar o maior valor possível, porém o peso máximo que ele pode carregar é W.

Mochila 0-1

Neste caso, o ladrão não poderá levar itens fracionários. Ele simplesmente deve escolher quais itens levar a fim de maximizar o valor a ser carregado na mochila, e que o peso não ultrapasse o peso máximo W.

Mochila fracionária

Já neste caso, o ladrão poderá escolher o quanto ele quer carregar de cada item, a fim de maximizar o valor total a ser carregado, podendo inclusive carregar partes fracionárias de um determinado item.

Embora semelhantes, somente o problema da mochila fracionária pode ser resolvido utilizando uma estratégia gulosa. Para isso, nós calculamos o valor por unidade de peso de cada item e ordenamos os itens segundo esse critério. Como ele quer levar o maior valor possível, a estratégia gulosa então é preencher a mochila com o quanto couber do item com maior valor e, quando acabar, continuar a preencher com o seguinte, até que a mochila fique completamente cheia. Observe que para resolver este problema o algoritmo guloso leva tempo O(n lg n).
A prova de que a busca gulosa não funciona para o problema da mochila 0-1 pode ser observada no exemplo ilustrado pela figura 3. Seja uma mochila de 50 kg e 3 itens, pesando 10, 20 e 30 Kg. Os valores dos itens são $60, $100 e $120, respectivamente. Observe que a estratégia gulosa nos daria como solução os itens de 10 e 20 Kg,e o valor máximo seria $160. Porém, a solução ótima seria os itens de 20 e 30 Kg, com o valor máximo de $220.



Fig. 3: Problema da mochila 0-1 e fracionária: em a) temos os itens e o peso máximo
que a mochila suporta. b) mochila 0-1. A melhor solução seria a primeira, obtida
utilizando a programação dinâmica. Das outras 2 possibilidades, a terceira seria a
escolhida pela estratégia gulosa. c) mochila fracionária. Este resultado seria possível
tanto pela estratégia gulosa quanto pela programação dinâmica.



          Discussão em aula a respeito desse tópico:
• Prof. seleciona o colega José Augusto para nos falar sobre as mochilas
  José Augusto Nos dois casos você tem um ladrão e uma loja assaltada, e uma mochila com um determinado peso máximo. A diferença é que no 0-1 ou o ladrão pega um determinado item valioso ou deixa ele por outro de maior valor. E a outra, o ladrão pode colocar partes fracionárias dos itens que desejar. A idéia é você encher a mochila para levar o maior valor possível.
  Prof. comenta: Cada coisa tem um peso e um valor. O peso é usado para ver o quanto cabe na mochila, e o valor é usado para você maximizar o que vai levar. Na mochila 0-1 cada coisa você pega ou não pega, e na fracionária você pode pegar uma fração e com isso vai ter uma fração do peso e do valor. E qual a diferença no ponto de vista de complexidade disso?
  José Augusto responde: O que ele fala é que no fracionário você pode usar um algoritmo guloso na boa que funciona e a solução é ótima, e no 0-1 você não pode usar.
  Prof. comenta Na verdade, vamos ver no final do curso que a mochila 0-1 é um problema N-P Completo. (um celular toca e descontrai a turma).
  No exercício 16.2-2 ele fala em resolver o problema da mochila 0-1 por programação dinâmica, mas qual a complexidade que dá? O(nW), e como W é um número, fornecido como entrada, então pela primeira vez temos um número fixo em notação decimal. Então o tamanho da entrada é log₁₀ W . Então, se nós definirmos m = log ₁₀ W, então a programação dinâmica vai levar O(n 10^m), o que dá exponencial.

3. Conclusões

Todos os tópicos previstos para a aula foram amplamente discutidos e comentados. Houve uma intensa participação dos alunos, principalmente no que se refere ao entendimento do teorema 16.1, considerado a peça chave para o entendimento dos algoritmos gulosos. Também ficou bem claro a diferença entre onde se pode utilizar uma estratégia gulosa e onde se deve utilizar programação dinâmica. As ilustrações foram muito úteis para o entendimento geral.

4. Referências bibliográficas

(Cormen, 2002) Cormen, T.H.;Leiserson, C.E.; Rivest, R.L.; Stein, C.; Algoritmos. Tradução da 2ª edição americana Teoria e Prática. 2002.