Algoritmos gulosos

Disponível somente no TrabalhosFeitos
  • Páginas : 66 (16403 palavras )
  • Download(s) : 0
  • Publicado : 3 de junho de 2012
Ler documento completo
Amostra do texto
Algoritmos gulosos: definicoes e aplicacoes
¸˜
¸˜
Anderson Rocha
anderson.rocha@ic.unicamp.br
Leyza Baldo Dorini
leyza.dorini@ic.unicamp.br
Campinas, 29 de abril de 2004

Introducao
¸˜
De forma geral, os algoritmos relacionados com otimizacao lidam com uma seq¨ encia de passos,
¸˜

sendo que em cada passo h´ um conjunto de escolhas/opcoes. Uma estrat´ gia para resolver problea
¸˜e
mas de otimizacao s˜ o os algoritmos gulosos, os quais escolhem a opcao que parece ser a melhor no
¸˜ a
¸˜
´
momento (escolha otima), e esperam que desta forma consiga-se chegar a uma solucao otima global.
¸˜ ´
Embora nem sempre seja poss´vel chegar a uma solucao otima a partir da utilizacao de algoritmos
ı
¸˜ ´
¸˜
gulosos, eles s˜ o eficientes em uma ampla variedade de problemas,conforme poderemos ver neste
a
trabalho.
Os algoritmos gulosos tomam decis˜ es com base apenas na informacao dispon´vel, sem se
o
¸˜
ı
´
preocupar com os efeitos futuros de tais decis˜ es, isto e, eles nunca reconsideram as decis˜ es tomadas,
o
o
independentemente das conseq¨ encias. N˜ o h´ , portanto, necessidade de avaliar as alternativas nem

aa
de empregar procedimentoselaborados permitindo que decis˜ es anteriores sejam desfeitas. Devido
o
a tais caracter´sticas, de forma geral eles s˜ o f´ ceis de se “inventar” e implementar, e s˜ o eficientes
ı
aa
a
quando funcionam [3], [2].
O Cap´tulo 1 apresenta uma nocao introdut´ ria do assunto, envolvendo as caracter´sticas geı
¸˜
o
ı
rais dos algoritmos gulosos, elementos da estrat´ gia gulosa. Tamb´ m e apresentadauma formalizacao
e

¸˜
dos algoritmos gulosos segundo a teoria dos matr´ ides.
o
O Cap´tulo 2 apresenta o relacionamento dos algoritmos gulosos com a programacao
ı
¸˜
dinˆ mica. Julgou-se pertinente realizar tal abordagem devido aos dois temas possu´rem alguns pontos
a
ı
em comum. Al´ m disso, outro semin´ rio tratou deste assunto, o que possibilitou que neste trabalho
e
a
n˜ ofosse preciso fazer um levantamento te´ rico sobre programacao dinˆ mica. Ainda neste cap´tulo
a
o
¸˜
a
ı
foram apresentados dois problemas: o problema de selecao de atividade e o problema da mochila.
¸˜
No Cap´tulo 3 ser˜ o apresentados mais dois exemplos. O primeiro deles foi o C´ digo de
ı
a
o
Huffman, relacionado com a compress˜ o de dados. O outro busca organizar tarefas de talforma que o
a
´
tempo m´ dio que cada tarefa fica no sistema e minimizado (a definicao de “tarefas” e “sistema” pode
e
¸˜
variar de um caso para outro, conforme veremos).
Os algoritmos gulosos em grafos est˜ o no Cap´tulo 4. Ser˜ o abordados dois algoritmos para
a
ı
a
´
descobrir a arvore geradora m´nima em um grafo conexo e ponderado, e um algoritmo para se comı
´
putar o caminho m´nimoem um grafo. O quinto e ultimo cap´tulo apresenta um exemplo de como os
ı
ı
algoritmos gulosos podem ser utilizados como heur´stica.
ı
Al´ m disso, o Anexo 1 apresenta conceitos sobre grafos, os quais s˜ o importantes em algumas
e
a
partes do trabalho, especialmente no Cap´tulo 4.
ı

1

Cap´tulo 1
ı

Algoritmos Gulosos
Para possibilitar uma “nocao geral” de como trabalham osalgoritmos gulosos, vamos abordar um
¸˜
exemplo. Suponha que tenhamos dispon´veis moedas com valores de 100, 25, 10, 5 e 1. O problema
ı
´
e criar um algoritmo que para conseguir obter um determinado valor com o menor n´ mero de moedas
u
poss´vel (problema do troco).
ı
´
´
Suponha que e preciso “dar um troco” de $2.89. A melhor solucao, isto e, o menor n´ mero de
¸˜
u
moedas poss´vel paraobter o valor, consiste em 10 moedas: 2 de valor 100, 3 de valor 25, 1 de valor 10
ı
e 4 de valor 1. De forma geral, agimos tal como um algoritmo guloso: em cada est´ gio adicionamos
a
a moeda de maior valor poss´vel, de forma a n˜ o passar da quantia necess´ ria.
ı
a
a
´
Embora seja uma afirmacao dif´cil de provar, e verdade que com os valores dados das moedas,
¸˜
ı
e tendo-se...
tracking img