Algoritmo Guloso

Algoritimo guloso, ou ganancioso é uma técnica de algoritimos para resolver problemas de otimização, sempre realização a escolha que parece ser a melhor no momento, fazendo uma escolha ótima local, na esperança de que está escolha leve até a solução ótima global. para resolver um problema, um algoritmo guloso escolhe, em cada iteração, o objeto mais "promissor" que vê pela frente. (A definição de "apetitoso" é establecida a priori.) O objeto escolhido passa a fazer parte da solução que o algoritmo constrói.Um algoritmo guloso é "míope": ele toma decisões com base nas informações disponíveis na iteração corrente, sem olhar as consequências que essas decisões terão no futuro. Um algoritmo guloso jamais se arrepende ou volta atrás: as escolhas que faz em cada iteração são definitivas. mbora algoritmos gulosos pareçam óbviamente corretos, a prova de sua correção é, em geral, muito sutil. Para compensar, algoritmos gulosos são muito rápidos e eficientes.

Suponha que S é uma coleção de subconjuntos de inteiros. Um elemento X de S é máximo se não existe Y em S tal que |Y| > |X| , ou seja, se nenhum elemento de S é maior que X. Um elemento X de S é maximo se não existir Y em S tal que Y < X , ou seja, se nenhum elemento de S é superconjunto próprio de X. Todo máximo é maximal, mas nem todo o máximal é máximo.

Procurar por um elemento máximo de S é, em geral, uma tarefa computacionalmente pesada (pois exige que todos os elementos de S sejam examinados). Já encontrar um elemento maximal de S é muito fácil. Basta aplicar um algoritmo guloso, que seleciona o primeiro Y aceitável que vê pela frente.

...