algoritmo

Algoritmos gulosos: definic¸o˜ es e aplicac¸o˜ es
Anderson Rocha [e-mail] Leyza Baldo Dorini [e-mail] Campinas, 29 de abril de 2004

Introduc¸a˜ o
De forma geral, os algoritmos relacionados com otimizac¸a˜ o lidam com uma seq¨ueˆ ncia de passos, sendo que em cada passo h´a um conjunto de escolhas/opc¸o˜ es. Uma estrat´egia para resolver problemas de otimizac¸a˜ o s˜ao os algoritmos gulosos, os quais escolhem a opc¸a˜ o que parece ser a melhor no momento (escolha o´ tima), e esperam que desta forma consiga-se chegar a uma soluc¸a˜ o o´ tima global.
Embora nem sempre seja poss´ıvel chegar a uma soluc¸a˜ o o´ tima a partir da utilizac¸a˜ o de algoritmos gulosos, eles s˜ao eficientes em uma ampla variedade de problemas, conforme poderemos ver neste trabalho. Os algoritmos gulosos tomam decis˜oes com base apenas na informac¸a˜ o dispon´ıvel, sem se preocupar com os efeitos futuros de tais decis˜oes, isto e´ , eles nunca reconsideram as decis˜oes tomadas, independentemente das conseq¨ueˆ ncias. N˜ao h´a, portanto, necessidade de avaliar as alternativas nem de empregar procedimentos elaborados permitindo que decis˜oes anteriores sejam desfeitas. Devido a tais caracter´ısticas, de forma geral eles s˜ao f´aceis de se “inventar” e implementar, e s˜ao eficientes quando funcionam [3], [2].
O Cap´ıtulo 1 apresenta uma noc¸a˜ o introdut´oria do assunto, envolvendo as caracter´ısticas gerais dos algoritmos gulosos, elementos da estrat´egia gulosa. Tamb´em e´ apresentada uma formalizac¸a˜ o dos algoritmos gulosos segundo a teoria dos matr´oides.
O Cap´ıtulo 2 apresenta o relacionamento dos algoritmos gulosos com a programac¸a˜ o dinˆamica. Julgou-se pertinente realizar tal abordagem devido aos dois temas possu´ırem alguns pontos em comum. Al´em disso, outro semin´ario tratou deste assunto, o que possibilitou que neste trabalho n˜ao fosse preciso fazer um levantamento te´orico sobre programac¸a˜ o dinˆamica. Ainda