30

O que é um Algoritmo Guloso ?

  • Quais suas características ?
  • Quais suas vantagens e desvantagens ?
3
  • Qual o motivo do negativo?
    – Ricardo
    Commented 14/12/2015 às 11:13
  • 6
    eu respondo: "Bem-vindo ao stackoverlow em português" Commented 14/12/2015 às 11:29
  • Não fui eu. +1, também quero saber o que é o algorítimo guloso. Commented 14/12/2015 às 11:30

1 Resposta 1

26

Algoritmo Guloso é uma solução comum para problemas de otimização onde:

  • Realiza a escolha que parece ser a melhor no momento na esperança de que a mesma acarrete em uma solução ou prevenção de futuros problemas a nível global.
  • É simples e de fácil implementação;
  • É míope: ele toma decisões com base nas informações disponíveis na iteração corrente.

Características

  • Jamais se arrepende de uma decisão, as escolhas realizadas são definitivas;
  • Não leva em consideração as consequências de suas decisões;
  • Podem fazer cálculos repetitivos;
  • Nem sempre produz a melhor solução (depende da quantidade de informação fornecida);
  • Quanto mais informações, maior a chance de produzir uma solução melhor.

Algoritmos Gulosos vs Programação Dinâmica

  • Em um algoritmo de programação dinâmica a escolha pode depender da solução dos subproblemas, enquanto um algoritmo guloso vai tentar escolher a melhor solução naquele momento.
  • A solução dos problemas na programação dinâmica parte de baixo para cima, enquanto um algoritmo guloso vai de cima para baixo, ou seja, na programação dinâmica, as soluções para todos os subproblemas são calculadas partindo dos menores subproblemas para os maiores.
  • Os resultados dos subproblemas na programação dinâmica são salvos, facilitando a prova de correção.

Pontos a favor

  • Simples e de fácil implementação;
  • Algoritmos de rápida execução;
  • Podem fornecer a melhor solução (estado ideal).

Pontos Contra

  • Dependentes de informações;
  • Correm o risco de entrarem em loops infinitos;
  • Situacionais, só resolvem tipos específicos de problemas;
  • Decisões tomadas são irrevogáveis;

Código de exemplo (neste caso uma implementação simples de uma devolução de troco gulosa)

import java.text.DecimalFormat;

public class Troco {

    public String calculaTroco(double conta, double pago) {
        DecimalFormat formatador = new DecimalFormat("###,##0.00");
        if (pago < conta)
            return ("\nPagamento insuficiente, faltam R$" + formatador.format(conta - pago) + "\n");
        else {

            String resultado;
            double troco;

            troco = pago - conta;
            resultado = "\nTroco = R$" + formatador.format(troco) + "\n\n";

            resultado = this.calculaNotas(troco, resultado);
            resultado = this.calculaMoedas(troco, resultado);

            resultado = resultado + "\n";

            return (resultado);
        }
    }

    private String calculaNotas(final double troco, String resultado) {

        int nota[] = { 100, 50, 20, 10, 5, 2, 1 };

        int valor;
        int ct;

        int contadorNota = 0;

        valor = (int) troco;
        while (valor != 0) {
            ct = valor / nota[contadorNota]; // calculando a qtde de notas
            if (ct != 0) {
                resultado = resultado + (ct + " nota(s) de R$" + nota[contadorNota] + "\n");
                valor = valor % nota[contadorNota]; // sobra
            }
            contadorNota++; // próxima nota
        }
        return resultado;
    }

    private String calculaMoedas(final double troco, String resultado) {

        int centavos[] = { 50, 25, 10, 5, 1 };

        int contadorMoeda = 0;
        int valor;
        int ct;

        valor = (int) Math.round((troco - (int) troco) * 100);
        while (valor != 0) {
            ct = valor / centavos[contadorMoeda]; // calculando a qtde de moedas
            if (ct != 0) {
                resultado = resultado + (ct + " moeda(s) de" + centavos[contadorMoeda] + "centavo(s)\n");
                valor = valor % centavos[contadorMoeda]; // sobra
            }
            contadorMoeda++; // próximo centavo
        }
        return resultado;
    }

}
1
  • 1
    Só para aprofundar, a solução do troco gulosa para este caso é ótima. Quando duas "moedas consecutivas" m[i] e m_[i+1] sempre satisfazem 2*m_[i] <= m_[i+1] então a solução gulosa sempre será ótima Commented 25/02/2018 às 21:49

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .