Marathoncode: Algoritmos Gulosos

Geralmente, os algoritmos gulosos são utilizados em problemas de otimização. Um problema de otimização consiste em encontrar a partir de um conjunto S um subconjunto E de S que deva possuir o menor ou maior custo que satisfazem certa propriedade. Durante o algoritmo guloso, fazemos uma escolha ótima para condições locais esperando que essa escolha ótima local (escolha gulosa) seja também uma escolha ótima global.

Problema do Troco

Suponha que tenhamos disponíveis moedas com valores de 100, 25, 10, 5 e 1. O problema é criar um algoritmo que para conseguir obter um determinado valor com o menor número de moedas possível (problema do troco).

Troco(n)

1. C ← { 100 , 50 , 10 , 5 , 1}

2. S ← Ø //Conjunto de moedas escolhida

3. soma ← 0 //Soma obtida

4. i ← 0

5. enquanto soma ≠ n faça

6. //Faça a escolha gulosa

7. x ← é o maior item em C tal que x + s ≤ n

8. se não existe tal item então

9. retorne “solução não encontrada”

10. fim-se

11. //Dependendo dos valores escolhidos

12. //alguns valores poderiam não ser construídos

13. S = S ∪ { valor da moeda x}

14. soma = soma + x

15. fim-enquanto

Simplificando ficaria:

Troco(n)

1. C ← { 100 , 50 , 10 , 5 , 1}

2. S ← Ø //Conjunto de moedas escolhida

3. soma ← 0 //Soma obtida

4. i ← 1

5. enquanto i <= 5 e soma ≠ n faça

6. se s + C[i] <= n então

16. S = S ∪ {i}

7. soma = soma + C[i]

8. Senão

9. i=i+1

Entretanto, ressalta-se que para diferentes valores de moedas, ou então quando se tem uma quantidade limitada de cada uma, o algoritmo guloso pode vir a não chegar em uma solução ótima, ou até mesmo não chegar a solução nenhuma (mesmo esta existindo). Suponha que os valores disponíveis seja C = {10,7,2,1} e precisamos dar o troco de 14 centavos. A solução dada pelo algoritmo guloso é 3 moedas: 1 de valor 10 e 2 de valor 2. Porém, o menor número de moedas é 2 moedas: 2 de valor 7.

Teorema O algoritmo guloso produz a solução com o menor número de moedas possível.

Suponha por absurdo que existe uma solução ótima S' que utiliza menos moedas que a solução encontrada pelo algoritmo S. Seja q' o número de moedas de 100 utilizada na solução S' e q o número de moedas 100 encontrada pelo algoritmo guloso. Como a solução S' é melhor que S temos que q' <= q. Se q' <= q então a solução S' utiliza um menos de moedas de 100 do que o permitido. Logo, a solução S' utiliza moedas de 50,10,5,1 para obter cada moeda de 100. Podemos encontrar uma solução S' + { um moeda de 100} - {x+y+z+w | 50x+10y + 5z + w = 100 }. Essa solução é melhor do que a solução ótima S'. Absurdo!

GulosoGeral(P)

1. S ← Ø

2. enquanto S não for uma solução de P faça

3. x ← é um elemento selecionado

4. se S ∪ {x} é viável para P sentão

5. S = S ∪ {x}

6. fim-se

7. fim-enquanto

Merge Ótimo

Dado n listas ordenadas de tamanhos diferentes. Quer-se determinar a ordem do merge, visando minimizar o número de operações. Dados duas listas l1 e l2, de tamanho t1 e t2, respectivamente, o número de operações para se fazer a intercalação (merge) das mesmas é igual a t1 + t2. Cada operação de merge gera uma nova lista ordenada. Depois do merge, temos o mesmo problema novamente com um tamanho menor.

Lista	A	B	C	D	E
Tamanho	300	500	150	400	200

Para minimizar o número de operações, temos que escolher as duas menores listas e fazer o merge das duas listas. O merge das duas listas gera uma nova lista ordenada.

MergeÓtimo(n,t1,..,tn){

custo = 0

enquanto n > 1 faça

Seja a e b os dois menores tamanhos da lista

Retire a e b da lista de tamanho

Insira a + b na lista de tamanho

Custo = custo + a + b

fim-enquanto

retorne custo

}

A complexidade do algoritmo vai depende quão rápido você consegue fazer a operação de escolhe os dois menores da lista e retira da lista. Vamos utilizar para realizar essa operação uma estrutura de dado chamada fila de prioridade. A fila de prioridade tem as seguintes propriedades:

Operação	Complexidade
Consultar o menor	O(1)
Inserir um elemento	O(log n)
Retirar um elemento	O(log n)

Exemplo extraído do livro Algoritmos do Professor Paulo Eustáquio Duarte Pinto

#include <vector>
#include <queue>
#include <iostream>
#include <stdlib.h>
#define forn(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
  int n,x,i,a,b,custo;
  priority_queue <int, vector<int>, greater<int> > q;
  cin >> n;  
  forn(i,n){
  cin >> x;
  q.push(x);
  }
 
  custo = 0;
  forn(i,n-1){
  a = q.top();
  q.pop();
  b = q.top();
  q.pop();
  cout << i+1 << "Merge com custo :" << a+b << endl; 
  custo += a+b;
  q.push(a+b);
 }
     cout << custo;
     system("PAUSE");
 return 0;
}

Problema de seleção de Tarefas

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 = {a1, a2, .., an} 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 ai tem um tempo de início si e um tempo de término fi, onde si < fi. Duas atividades ai e aj são compatíveis se os intervalos [si, fi) e [sj , fj) não se sobrepõem, i.e., se si >= fj ou se sj >= fi. O problema de Seleção de Atividades consiste em encontrar o subconjunto de tamanho máximo de atividades mutuamente compatíveis.

Banda U2

A banda U2 vai começar um show daqui a 17 minutos. Os quatros integrantes estão na margem esquerda de um rio e precisam cruzar uma ponte para chegar ao palco na margem direita. É noite. Há somente uma lanterna. Só podem passar uma ou duas pessoas juntas pela ponte, e sempre com a lanterna. A lanterna não pode ser jogada, etc . Cada integrante possui um tempo diferente para atravessar a ponte: O Bono leva 1 minuto, o Edge 2 minutos, o Adam 5 minutos e o Larry 10 minutos. Quando os dois atravessam juntos, eles vão pelo tempo do mais lento. Você precisa ajudá-los a atravessar com o menor tempo possível.

a) Encontra a solução para esse problema para qualquer tempo de travessia.

b) Encontre a solução para o problema que há n pessoas do mesmo lado da pontes com diversos tempos de travessia(não necessariamente distintos) e uma lanterna.

Mochila Fracionária

Dado um conjunto de n objetos {o₁,o₂,..,o_n}. Cada objeto o_i tem um peso w_i e um valor v_i. Você pode pegar partes fracionárias de cada objeto. Dado uma mochila com peso W, qual é o valor máximo que pode ser levado na mochila.

Problema do Leite

A empresa Betânia precisa comprar N litros de leite por dia. A Betânia tem M possíveis fornecedores. Cada fornecedor tem um limite de produção de leite c_i e preçoo por litro p_i, 1 ≤ i ≤ M. Queremos comprar N litros com o menor custo possível.

A demanda da empresa Betânia é 100 litros de leite. O número de fornecedores é 5. A lista de fornecedores segue abaixo com o preçoo por litro e a sua produção:

5 20

9 40

3 10

8 80

6 30

Saída

630

Problema Consertando o Celeiro

Temos uma longa lista de M estábulos ocupados que devem ser vedados com placas. Você pode usar até N placas, uma placa pode cobrir qualquer número de cocheiras consecutivas depende apenas do seu comprimento . Você escolhe o comprimento da placa, mas a placa não pode ser cortada. O custo da placa é igual ao comprimento da placa. Cubra todas as cocheiras ocupadas, com o menor custo possível. Como resolver o problema?

O número de placas que podem ser encomendadas são 4. O número máximo de celeiros é 50. O número de estabulos ocupados é 18. O seguintes celeiros estão ocupados:

3 4 6 8 14 15 16 17 21 25 26 27 30 31 40 41 42 43

O custo mínimo possível é 25. Uma placa cobrindo os estábulos 3-8 com custo 6. Uma placa cobrindo os estábulos 14-17 com custo 4. Uma placa cobrindo os estábulos 21-31 com custo 11. Uma placa cobrindo os estábulos 40-43 com custo 4.

Problema de programação de tarefas

O problema de programação de tarefas de tempo unitário com prazos finais e penalidades para um único processador tem as seguintes entradas:

• Um conjunto de tarefas S = { a1, . . . , an} de n tarefas de tempo unitário.

• Um conjunto de n prazos finais inteiros d1, . . . , dn, e a tarefa i deve terminar no tempo di.

• Um conjunto de n pesos não negativos ou penalidades w1, . . . ,wn, tal que uma penalidade wi ocorre se a tarefa i não é terminada no tempo di e nenhuma penalidade ocorre se uma tarefa termina até prazo final.

a_i	1	2	3	4	5	6	7
d_i	4	2	4	3	1	4	6
w_i	70	60	50	40	30	20	10

Arvore Geradora Mínima

Considere um grafo, conectado e associado a cada arco uma distância (custo,tempo, etc) não-negativa. O objetivo é encontrar uma subgrafo que é uma árvore com custo mínimo.