dynamic programming programacao Qual é a diferença entre memorização e programação dinâmica?




programação dinâmica artigos (5)

Programação Dinâmica é freqüentemente chamada de Memoização!

  1. A memorização é a técnica de cima para baixo (comece a resolver o problema determinado dividindo-a) e a programação dinâmica é uma técnica de baixo para cima (começar a resolver desde o sub-problema trivial, até o problema dado)

  2. DP encontra a solução iniciando do (s) caso (s) base (s) e segue seu caminho para cima. O DP resolve todos os sub-problemas, porque ele faz isso de baixo para cima

    Ao contrário do Memoization, que resolve apenas os sub-problemas necessários

  3. O DP tem o potencial de transformar soluções de força bruta em tempo exponencial em algoritmos de tempo polinomial.

  4. O DP pode ser muito mais eficiente porque o seu iterativo

    Pelo contrário, a Memoização deve pagar pela sobrecarga (geralmente significativa) devido à recursão.

Para ser mais simples, o Memoization usa a abordagem de cima para baixo para resolver o problema, isto é, ele começa com o problema principal (principal) e então o divide em sub-problemas e resolve esses sub-problemas de maneira similar. Nesta abordagem, o mesmo subproblema pode ocorrer várias vezes e consumir mais ciclo de CPU, aumentando assim a complexidade do tempo. Enquanto na programação dinâmica, o mesmo sub-problema não será resolvido várias vezes, mas o resultado anterior será usado para otimizar a solução.

Qual é a diferença entre memorização e programação dinâmica? Eu acho que a programação dinâmica é um subconjunto da memoização. Está certo?


Tanto o Memoization como o Dynamic Programming resolvem o subproblema individual apenas uma vez.

A memorização usa recursão e funciona de cima para baixo, enquanto a programação dinâmica se move na direção oposta, resolvendo o problema de baixo para cima.

Abaixo está uma analogia interessante -

De cima para baixo - Primeiro você diz que eu vou dominar o mundo. Como você vai fazer isso? Você diz que eu vou dominar a Ásia primeiro. Como você vai fazer isso? Eu assumirei a Índia primeiro. Eu me tornarei o ministro-chefe de Delhi, etc. etc.

Bottom-up - Você diz que eu vou me tornar o CM de Delhi. Em seguida, assumirá a Índia, depois todos os outros países da Ásia e, finalmente, conquistarei o mundo.


Qual é a diferença entre memorização e programação dinâmica?

Memoization é um termo que descreve uma técnica de otimização em que você armazena em cache os resultados calculados anteriormente e retorna o resultado em cache quando o mesmo cálculo é necessário novamente.

A programação dinâmica é uma técnica para resolver problemas de natureza recursiva, iterativamente e é aplicável quando os cálculos dos subproblemas se sobrepõem.

A programação dinâmica é tipicamente implementada usando tabulação, mas também pode ser implementada usando memoização. Então, como você pode ver, nenhum deles é um "subconjunto" do outro.

Uma questão de acompanhamento razoável é: Qual é a diferença entre a tabulação (a técnica de programação dinâmica típica) e a memorização?

Quando você resolve um problema de programação dinâmica usando a tabulação, você resolve o problema "de baixo para cima ", isto é, resolvendo primeiro todos os subproblemas relacionados, tipicamente preenchendo uma tabela n- dimensional. Com base nos resultados da tabela, a solução para o problema "top" / original é então calculada.

Se você usar o memoization para resolver o problema, faça isso mantendo um mapa dos sub-problemas já solucionados. Você faz isso "de cima para baixo ", no sentido de que resolve primeiro o problema "top" (que normalmente recorre para resolver os sub-problemas).

Um bom slide here (link agora está morto, slide ainda é bom embora):

  • Se todos os subproblemas tiverem que ser resolvidos pelo menos uma vez, um algoritmo de programação dinâmica bottom-up geralmente supera um algoritmo de memo de cima para baixo por um fator constante
    • Nenhuma sobrecarga para recursão e menos sobrecarga para manter a mesa
    • Existem alguns problemas para os quais o padrão regular de acessos de tabela no algoritmo de programação dinâmica pode ser explorado para reduzir ainda mais os requisitos de tempo ou espaço.
  • Se alguns subproblemas no espaço do subproblema não precisarem ser resolvidos, a solução de memo tem a vantagem de resolver apenas os subproblemas que são definitivamente necessários

Recursos adicionais:

Isto foi reescrito como um artigo aqui .


Da wikipedia:

Memorando

Na computação, a memoização é uma técnica de otimização usada principalmente para acelerar os programas de computador, pois as chamadas de função evitam repetir o cálculo dos resultados das entradas processadas anteriormente.

Programaçao dinamica

Em matemática e ciência da computação, a programação dinâmica é um método para resolver problemas complexos dividindo-os em subproblemas mais simples.

Ao dividir um problema em subproblemas menores / mais simples, muitas vezes encontramos o mesmo subproblema mais de uma vez - por isso, usamos a Memoização para salvar os resultados de cálculos anteriores, para que não seja necessário repeti-los.

A programação dinâmica geralmente encontra situações em que faz sentido usar o memoization, mas você pode usar uma das técnicas sem necessariamente usar a outra.


Programação dinâmica é um paradigma algorítmico que resolve um determinado problema complexo, dividindo-o em subproblemas e armazena os resultados de subproblemas para evitar o mesmo resultado de computação.

http://www.geeksforgeeks.org/dynamic-programming-set-1/

A memorização é um método fácil de rastrear soluções previamente resolvidas (geralmente implementadas como um par de valores de chave hash, em oposição à tabulação que é frequentemente baseada em matrizes) para que não sejam recalculadas quando forem encontradas novamente. Pode ser usado nos métodos bottom up ou top down.

Veja esta discussão sobre a memorização vs tabulação.

Portanto, a programação dinâmica é um método para resolver certas classes de problemas resolvendo relações de recorrência / recursão e armazenando soluções encontradas anteriormente por meio de tabulação ou memoização. Memoização é um método para rastrear soluções para problemas previamente resolvidos e pode ser usado com qualquer função que tenha soluções determinísticas únicas para um dado conjunto de entradas.