Algoritmo guloso
Algoritmo guloso, algoritmo ganancioso é a denominação dada para a técnica de projeto de algoritmos que tenta resolver o problema fazendo a escolha localmente ótima em cada fase com a esperança de encontrar uma correspondência global ótima.
Componentes
Em geral o algoritmo guloso tem cinco componentes:
Desempenho
A avaliação de qualidade da solução obtida por um algoritmo é feita através da comparação com um limite inferior para a solução do problema, o que pode ser expresso pela seguinte fórmula:
Árvore de extensão mínima
O primeiro algoritmo a encontrar uma árvore de extensão mínima foi desenvolvido pelo cientista checo Otakar Borůvka em 1926 (veja algoritmo de Boruvka). Seu propósito era fornecer uma cobertura elétrica eficiente na área rural da cidade de Morávia do Sul. Existem hoje dois algoritmos comummente usados, o algoritmo de Prim e o algoritmo de Kruskal. Todos são algoritmos gulosos exatos que rodam em tempo polinomial, então o problema de encontrar tais árvores pertence a classe de complexidade P.
Problema do empacotamento
No problema de bin packing (ou problema do empacotamento), objetos de diferentes volumes devem ser embalados em um número finito de bandejas ou recipientes de volume V de uma forma que minimize o número de recipientes utilizados. Na teoria da complexidade computacional, este é um problema de combinatória NP-difícil. Podem ser utilizadas heurísticas gulosas para obtenção de uma solução aproximada, tais como: algoritmo first fit, algoritmo best fit, dentre outros.
Problema de programação de tarefas independentes
Dado um conjunto de n tarefas independentes com duração t1, t2, ..., tn e m processadores idênticos que funcionam em paralelo, inicialmente ociosos. Distribuir as n tarefas pelos m processadores minimizando o tempo de término da última tarefa é um problema NP-difícil param ≥ 2. Alocar as tarefa aleatoriamente aos processadores, sempre que ficarem ociosos. Neste caso a solução terá performance: Sempre que um processador ficar ocioso aloca-se a tarefa de maior duração ainda não processada (empates são resolvidos arbitrariamente). Neste caso a solução terá performance: Observa-se que a heurística 2 é superior à heurística 1.
