dynamic-programming - geeksforgeeks - how to solve dynamic programming problems




Qual é a diferença entre bottom-up e top-down? (5)

A abordagem bottom-up (para programação dinâmica) consiste em primeiro olhar para os subproblemas "menores" e depois resolver os subproblemas maiores usando a solução para os problemas menores.

O top-down consiste em resolver o problema de maneira "natural" e verificar se você calculou a solução para o subproblema antes.

Estou um pouco confuso. Qual é a diferença entre esses dois?


rev4: Um comentário muito eloquente do usuário Sammaron observou que, talvez, essa resposta tenha sido confundida de cima para baixo e de baixo para cima. Enquanto originalmente esta resposta (rev3) e outras respostas diziam que "bottom-up é memoization" ("assume os subproblemas"), pode ser o inverso (isto é, "top-down" pode ser "assumir os subproblemas" e " bottom-up "may be" compõe os subproblemas "). Anteriormente, eu li sobre memoização sendo um tipo diferente de programação dinâmica em oposição a um subtipo de programação dinâmica. Eu estava citando esse ponto de vista, apesar de não subscrevê-lo. Eu reescrevi esta resposta para ser agnóstico da terminologia até que referências apropriadas possam ser encontradas na literatura. Eu também converti essa resposta para um wiki da comunidade. Por favor, prefira fontes acadêmicas. Lista de referências: {Web: 1 , 2 } {Literatura: 5 }

Recapitular

A programação dinâmica tem tudo a ver com ordenar seus cálculos de uma maneira que evita recalcular o trabalho duplicado. Você tem um problema principal (a raiz da sua árvore de subproblemas) e subproblemas (subárvores). Os subproblemas normalmente se repetem e se sobrepõem .

Por exemplo, considere o seu exemplo favorito de Fibonnaci. Esta é a árvore completa dos subproblemas, se fizermos uma chamada recursiva ingênua:

TOP of the tree
fib(4)
 fib(3)...................... + fib(2)
  fib(2)......... + fib(1)       fib(1)........... + fib(0)
   fib(1) + fib(0)   fib(1)       fib(1)              fib(0)
    fib(1)   fib(0)
BOTTOM of the tree

(Em alguns outros problemas raros, esta árvore pode ser infinita em alguns ramos, representando não-terminação, e assim o fundo da árvore pode ser infinitamente grande. Além disso, em alguns problemas você pode não saber o que a árvore completa parece antes Assim, você pode precisar de uma estratégia / algoritmo para decidir quais subproblemas serão revelados.

Memoização, Tabulação

Existem pelo menos duas técnicas principais de programação dinâmica que não são mutuamente exclusivas:

  • Memoization - Essa é uma abordagem de laissez-faire: você supõe que já calculou todos os subproblemas e que não tem idéia de qual é a ordem de avaliação ideal. Normalmente, você executaria uma chamada recursiva (ou algum equivalente iterativo) da raiz e esperaria que chegasse perto da ordem de avaliação ideal ou obtivesse uma prova de que ajudaria a chegar à ordem de avaliação ideal. Você garantiria que a chamada recursiva nunca recomputa um subproblema porque você armazena em cache os resultados e, portanto, as subárvores duplicadas não são recalculadas.

    • exemplo: Se você está calculando a fibonacci seqüência fib(100) , você só chamaria isso, e chamaria fib(100)=fib(99)+fib(98) , que chamaria fib(99)=fib(98)+fib(97) , ... etc ..., que chamaria fib(2)=fib(1)+fib(0)=1+0=1 . Então ele finalmente resolveria fib(3)=fib(2)+fib(1) , mas não precisa recalcular fib(2) , porque nós o armazenamos em cache.
    • Isso começa no topo da árvore e avalia os subproblemas das folhas / subárvores de volta para a raiz.
  • Tabulação - Você também pode pensar em programação dinâmica como um algoritmo de "preenchimento de tabela" (embora geralmente multidimensional, esta "tabela" pode ter geometria não-euclidiana em casos muito raros *). Isso é como uma memoização, mas mais ativa, e envolve uma etapa adicional: você deve escolher, com antecedência, a ordem exata na qual fará seus cálculos. Isso não deve implicar que a ordem deve ser estática, mas que você tem muito mais flexibilidade do que a memoização.

    • exemplo: Se você está executando fibonacci, você pode escolher calcular os números nesta ordem: fib(2) , fib(3) , fib(4) ... armazenando em cache todos os valores para poder calcular os próximos com mais facilidade. Você também pode pensar nisso como preenchendo uma tabela (outra forma de armazenamento em cache).
    • Eu pessoalmente não ouço muito a palavra 'tabulação', mas é um termo muito decente. Algumas pessoas consideram essa "programação dinâmica".
    • Antes de executar o algoritmo, o programador considera a árvore inteira e, em seguida, grava um algoritmo para avaliar os subproblemas em uma determinada ordem em direção à raiz, geralmente preenchendo uma tabela.
    • * nota de rodapé: Às vezes, a 'tabela' não é uma tabela retangular com conectividade de grade, por si só. Em vez disso, pode ter uma estrutura mais complicada, como uma árvore, ou uma estrutura específica para o domínio do problema (por exemplo, cidades dentro de uma distância em um mapa) ou mesmo um diagrama de grade, que não tem uma estrutura de conectividade up-down-left-right, etc. Por exemplo, user3290797 vinculou um exemplo de programação dinâmica de encontrar o conjunto máximo independente em uma árvore , que corresponde ao preenchimento dos espaços em branco em uma árvore.

(No mais geral, em um paradigma de "programação dinâmica", eu diria que o programador considera a árvore inteira e, em seguida , grava um algoritmo que implementa uma estratégia para avaliar subproblemas que pode otimizar qualquer propriedade desejada (geralmente uma combinação de complexidade de tempo). e sua complexidade espacial) .Sua estratégia deve começar em algum lugar, com algum subproblema em particular, e talvez possa se adaptar com base nos resultados dessas avaliações.No sentido geral de "programação dinâmica", você pode tentar armazenar esses subproblemas em cache e mais geralmente, evite revisitar subproblemas com uma distinção sutil, talvez seja o caso de gráficos em várias estruturas de dados.Muitas vezes, essas estruturas de dados estão em seu núcleo, como matrizes ou tabelas.Soluções para subproblemas podem ser jogadas fora se não precisarmos delas não mais.)

[Anteriormente, essa resposta fez uma declaração sobre a terminologia top-down x bottom-up; há claramente duas abordagens principais chamadas Memoização e Tabulação que podem estar em bijeção com esses termos (embora não inteiramente). O termo geral usado pela maioria das pessoas ainda é "Programação Dinâmica" e algumas pessoas dizem "Memoização" para se referir a esse subtipo específico de "Programação Dinâmica". Essa resposta se nega a dizer de cima para baixo e de baixo para cima até que a comunidade possa encontrar referências adequadas em artigos acadêmicos. Em última análise, é importante entender a distinção e não a terminologia.]

Prós e contras

Facilidade de codificação

A memorização é muito fácil de codificar (geralmente você pode * escrever uma anotação "memoizer" ou função de wrapper que faz isso automaticamente para você), e deve ser sua primeira linha de abordagem. A desvantagem da tabulação é que você precisa fazer um pedido.

* (isto é realmente fácil se você está escrevendo a função você mesmo, e / ou codificando em uma linguagem de programação impura / não funcional ... por exemplo, se alguém já escreveu uma função fib pré-compilada, necessariamente faz chamadas recursivas para si mesma, e você não pode magicamente memorizar a função sem garantir que as chamadas recursivas chamem sua nova função de memo (e não a função original sem memória))

Recursividade

Observe que tanto de cima para baixo quanto de baixo para cima podem ser implementados com recursão ou preenchimento de tabela iterativo, embora possa não ser natural.

Preocupações práticas

Com a memoização, se a árvore for muito profunda (por exemplo, fib(10^6) ), você ficará sem espaço na pilha, porque cada cálculo atrasado deve ser colocado na pilha e você terá 10 ^ 6 deles.

Otimalidade

Qualquer uma das abordagens pode não ser ideal se a ordem em que você acontece (ou tentar) visitar subproblemas não é a ideal, especificamente se há mais de uma maneira de calcular um subproblema (normalmente, o cache resolveria isso, mas é teoricamente possível que o cache não em alguns casos exóticos). A memorização normalmente adiciona complexidade de tempo à sua complexidade de espaço (por exemplo, com tabulação você tem mais liberdade para jogar fora os cálculos, como usar tabulação com Fib permite usar O (1) espaço, mas memoização com Fib usa O (N) espaço de pilha).

Otimizações avançadas

Se você também está fazendo um problema extremamente complicado, você pode não ter outra escolha senão fazer uma tabulação (ou pelo menos assumir um papel mais ativo na direção da memória onde você quer que ela vá). Além disso, se você estiver em uma situação onde a otimização é absolutamente crítica e você deve otimizar, a tabulação permitirá que você faça otimizações que a memorização não permitiria que você fizesse de uma maneira sã. Na minha humilde opinião, na engenharia de software normal, nenhum desses dois casos surgiu, então eu usaria apenas o memoization ("uma função que armazena suas respostas") a menos que algo (como o espaço da pilha) torne a tabulação necessária ... embora tecnicamente para evitar um estouro de pilha você pode 1) aumentar o limite de tamanho de pilha em linguagens que o permitem, ou 2) comer um fator de trabalho extra para virtualizar seu stack (ick), ou 3) programar em estilo de continuação, que de fato também virtualiza sua pilha (não tem certeza da complexidade disso, mas basicamente você efetivamente pega a cadeia de chamadas adiada da pilha de tamanho N e de fato a cola em N funções de thunk sucessivamente aninhadas ... embora em alguns idiomas sem otimização de chamada de cauda, ​​você pode ter que trampolim coisas para evitar uma explosão de pilha).

Exemplos mais complicados

Aqui listamos exemplos de interesse particular, que não são apenas problemas gerais de DP, mas que, curiosamente, distinguem a memorização e a tabulação. Por exemplo, uma formulação pode ser muito mais fácil que a outra, ou pode haver uma otimização que basicamente requer tabulação:

  • o algoritmo para calcular edit-distance [ 4 ], interessante como um exemplo não-trivial de um algoritmo de preenchimento de tabela bidimensional

A seguir, a solução baseada em DP para o problema Edit Distance, que é de cima para baixo. Espero que também ajude a entender o mundo da programação dinâmica:

public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
         int m = word2.length();
            int n = word1.length();


     if(m == 0) // Cannot miss the corner cases !
                return n;
        if(n == 0)
            return m;
        int[][] DP = new int[n + 1][m + 1];

        for(int j =1 ; j <= m; j++) {
            DP[0][j] = j;
        }
        for(int i =1 ; i <= n; i++) {
            DP[i][0] = i;
        }

        for(int i =1 ; i <= n; i++) {
            for(int j =1 ; j <= m; j++) {
                if(word1.charAt(i - 1) == word2.charAt(j - 1))
                    DP[i][j] = DP[i-1][j-1];
                else
                DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
            }
        }

        return DP[n][m];
}

Você pode pensar em sua implementação recursiva em sua casa. É muito bom e desafiador se você não resolveu algo assim antes.


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

1.Memoização é a técnica de cima para baixo (comece a resolver o problema dado 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 a partir 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

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

  2. 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.


Simplesmente falando de cima para baixo, usa a recursão para chamar problemas Sub repetidamente
Onde a abordagem bottom up usa o single sem chamar ninguém e, portanto, é mais eficiente.


Vamos pegar a série de fibonacci como um exemplo

1,1,2,3,5,8,13,21....

first number: 1
Second number: 1
Third Number: 2

Outra maneira de colocar isso,

Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21

No caso dos primeiros cinco números de fibonacci

Bottom(first) number :1
Top (fifth) number: 5 

Agora vamos dar uma olhada no algoritmo recursivo da série Fibonacci como um exemplo

public int rcursive(int n) {
    if ((n == 1) || (n == 2)) {
        return 1;
    } else {
        return rcursive(n - 1) + rcursive(n - 2);
    }
}

Agora, se nós executarmos este programa com os seguintes comandos

rcursive(5);

Se olharmos atentamente para o algoritmo, para gerar o quinto número, ele requer o terceiro e o quarto números. Então minha recursão realmente começa do topo (5) e vai até os números inferiores / inferiores. Essa abordagem é, na verdade, uma abordagem de cima para baixo.

Para evitar fazer o mesmo cálculo várias vezes, usamos técnicas de programação dinâmica. Armazenamos o valor previamente computado e o reutilizamos. Essa técnica é chamada de memorização. Há mais na programação dinâmica, além da memorização, que não é necessária para discutir o problema atual.

Careca

Vamos reescrever nosso algoritmo original e adicionar técnicas de memorização.

public int memoized(int n, int[] memo) {
    if (n <= 2) {
        return 1;
    } else if (memo[n] != -1) {
        return memo[n];
    } else {
        memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
    }
    return memo[n];
}

E nós executamos este método como seguindo

   int n = 5;
    int[] memo = new int[n + 1];
    Arrays.fill(memo, -1);
    memoized(n, memo);

Esta solução é ainda de cima para baixo quando o algoritmo começa do valor superior e vai para o fundo de cada passo para obter o nosso valor máximo.

Debaixo para cima

Mas, a questão é: podemos começar de baixo, como do primeiro número de fibonacci, e depois caminhar para cima. Vamos reescrevê-lo usando essas técnicas,

public int dp(int n) {
    int[] output = new int[n + 1];
    output[1] = 1;
    output[2] = 1;
    for (int i = 3; i <= n; i++) {
        output[i] = output[i - 1] + output[i - 2];
    }
    return output[n];
}

Agora, se olharmos para este algoritmo, ele realmente começa a partir de valores mais baixos e depois vai para o topo. Se eu precisar do 5º número de fibonacci, eu estou realmente calculando o 1º, depois o segundo e o terceiro até o quinto número. Essas técnicas realmente chamavam técnicas de baixo para cima.

Os dois últimos algoritmos preenchem os requisitos de programação dinâmica. Mas um é de cima para baixo e outro é de baixo para cima. Ambos os algoritmos possuem complexidade espacial e temporal similar.