A principal diferença entre o Método Greedy e a Programação Dinâmica é que a decisão (escolha) feita pelo método Greedy depende das decisões (escolhas) feitas até o momento e não depende de escolhas futuras ou de todas as soluções para os subproblemas. Por outro lado, a programação dinâmica toma decisões com base em todas as decisões tomadas na etapa anterior para resolver o problema.

Um algoritmo é uma sequência sistemática de etapas para resolver um problema. Método ganancioso e programação dinâmica são dois algoritmos. Ambos são usados ​​para resolver problemas de otimização.

Método ganancioso, programação dinâmica

O que é o método ganancioso

O método ganancioso envolve encontrar a melhor opção entre vários valores presentes. Nesse método, consideramos o primeiro estágio e decidimos a saída sem considerar as saídas futuras. Em outras palavras, o algoritmo Greedy resolve o problema considerando a melhor opção naquele momento específico.

O algoritmo guloso funciona se o problema contém duas propriedades como propriedade de escolha gulosa e subestrutura ótima. É possível encontrar uma solução idealmente global, criando uma solução ideal localmente. Em outras palavras, criar escolhas ambiciosas ajuda a encontrar a solução ideal. Conseqüentemente, essa propriedade é chamada de propriedade de escolha gananciosa. Além disso, as soluções ótimas contêm sub-soluções ótimas. Assim, essa propriedade é chamada de subestrutura ótima.

O que é programação dinâmica

A programação dinâmica envolve a divisão do problema principal em pequenos subproblemas. O método armazena os resultados dos subproblemas e os aplica a subproblemas semelhantes. Aqui, armazenar as respostas dos subproblemas é chamado de memorização. Ele verifica as respostas dos subproblemas e, finalmente, chega a uma conclusão para encontrar a solução ótima ou a melhor. Como a programação dinâmica verifica as respostas anteriores e evita computar a mesma resposta várias vezes, é mais eficiente.

Na programação dinâmica, a solução ótima para o problema principal está dentro da solução ótima de seus subproblemas. Além disso, quando há situações de enfrentamento dos mesmos subproblemas, repetidamente, isso é chamado de subproblemas sobrepostos.

Diferença entre método ganancioso e programação dinâmica

Definição

O método Greedy é um algoritmo que segue a heurística de resolução de problemas de fazer a escolha ideal localmente em cada loja com a intenção de encontrar um ótimo global. A Programação Dinâmica, por outro lado, é um algoritmo que ajuda a resolver com eficiência uma classe de problemas que possuem subproblemas sobrepostos e propriedade de subestrutura ótima. Essas definições explicam a principal diferença entre o Método Greedy e a Programação Dinâmica.

Eficiência

Além disso, a principal diferença entre o Método Greedy e a Programação Dinâmica é sua eficiência. O método Greedy é menos eficiente, enquanto a programação dinâmica é mais eficiente.

Processo

Tomando uma decisão

O método de tomada de decisão é outra diferença entre o Método Greedy e a Programação Dinâmica. O método Greedy toma decisões considerando o primeiro estágio, enquanto a programação dinâmica toma decisões em cada estágio.

Conclusão

A decisão (escolha) feita pelo método Greedy depende das decisões (escolhas) feitas até o momento e não depende de escolhas futuras ou de todas as soluções para os subproblemas. No entanto, a programação dinâmica toma decisões com base em todas as decisões tomadas no estágio anterior para resolver o problema. Essa é a principal diferença entre o Método Greedy e a Programação Dinâmica.

Referência:

1. “Introdução à Programação Dinâmica - Javatpoint.” Www.javatpoint.com, disponível aqui.2. Programação dinâmica | Steps to Design & Applications |, Education 4u, 2 de abril de 2018, disponível aqui.3. “Greedy Algorithms Introduction - Javatpoint.” Www.javatpoint.com, disponível aqui.4. “Algoritmo ganancioso.” Wikipedia, Wikimedia Foundation, 9 de outubro de 2018, disponível aqui.

Cortesia de imagem:

1. “Greedy-search-path-example” Por Swfung8 - Trabalho próprio (CC BY-SA 3.0) via Commons Wikimedia2. “Fibonacci dynamic programming” Por en: Usuário: Dcoatzee, rastreado por Usuário: Stannered - en: Imagem: Fibonacci dynamic programming.png (Domini público) via Commons Wikimedia