Algoritmos gulosos

Algoritmos gulosos: definicoes e aplicacoes
¸˜
¸˜
Anderson Rocha [e-mail] Leyza Baldo Dorini [e-mail] Campinas, 29 de abril de 2004

Introducao
¸˜
De forma geral, os algoritmos relacionados com otimizacao lidam com uma seq¨ encia de passos,
¸˜
uˆ 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 uˆ aa de empregar procedimentos elaborados 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 apresentada uma formalizacao e 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˜ o