O que é programação dinâmica? [fechadas]

O que é programação dinâmica ?

Como é diferente de recursão, memorização, etc?

Eu li o artigo da Wikipedia , mas ainda não o entendo.

A programação dinâmica é quando você usa o conhecimento passado para facilitar a solução de um problema futuro.

Um bom exemplo é resolver a sequência de Fibonacci para n = 1.000.002.

Este será um processo muito longo, mas e se eu lhe der os resultados para n = 1.000.000 en = 1.000.001? De repente, o problema tornou-se mais gerenciável.

A programação dinâmica é muito usada em problemas de cadeia, como o problema de edição de cadeia. Você resolve um subconjunto (s) do problema e, em seguida, usa essas informações para resolver o problema original mais difícil.

Com a programação dinâmica, você armazena seus resultados em algum tipo de tabela em geral. Quando você precisar da resposta para um problema, consulte a tabela e veja se você já sabe o que é. Caso contrário, use os dados da sua tabela para dar a si mesmo um trampolim em direção à resposta.

O livro Algorithms de Cormen tem um ótimo capítulo sobre programação dinâmica. E é grátis no Google Livros! Confira aqui.

A programação dinâmica é uma técnica usada para evitar computar várias vezes o mesmo subproblema em um algoritmo recursivo.

Vamos pegar o exemplo simples dos números de Fibonacci: encontrar o ^enésimo número de Fibonacci definido por

F _n = F _n-1 + F _n-2 e F ₀ = 0, F ₁ = 1

Recursão

A maneira óbvia de fazer isso é recursiva:

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1

    return fibonacci(n - 1) + fibonacci(n - 2)

Programaçao dinamica

• Top Down - Memoização

A recursão faz muitos cálculos desnecessários porque um determinado número de Fibonacci será calculado várias vezes. Uma maneira fácil de melhorar isso é armazenar em cache os resultados:

cache = {}

def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fibonacci(n - 1) + fibonacci(n - 2)

    return cache[n]

• Debaixo para cima

Uma maneira melhor de fazer isso é se livrar da recursão, avaliando os resultados na ordem correta:

cache = {}

def fibonacci(n):
    cache[0] = 0
    cache[1] = 1

    for i in range(2, n + 1):
        cache[i] = cache[i - 1] +  cache[i - 2]

    return cache[n]

Podemos até usar espaço constante e armazenar apenas os resultados parciais necessários ao longo do caminho:

def fibonacci(n):
  fi_minus_2 = 0
  fi_minus_1 = 1

  for i in range(2, n + 1):
      fi = fi_minus_1 + fi_minus_2
      fi_minus_1, fi_minus_2 = fi, fi_minus_1

  return fi

• Como aplicar a programação dinâmica?

  1. Encontre a recursão no problema.
  2. De cima para baixo: armazene a resposta para cada subproblema em uma tabela para evitar a necessidade de recalculá-las.
  3. De baixo para cima: encontre a ordem certa para avaliar os resultados para que os resultados parciais estejam disponíveis quando necessário.

A programação dinâmica geralmente trabalha para problemas que têm uma ordem inerente da esquerda para a direita, como seqüências de caracteres, árvores ou seqüências inteiras. Se o algoritmo recursivo ingênuo não computar o mesmo subproblema várias vezes, a programação dinâmica não ajudará.

Fiz uma coleção de problemas para ajudar a entender a lógica: https://github.com/tristanguigue/dynamic-programing

Memoização é quando você armazena resultados anteriores de uma chamada de função (uma função real sempre retorna a mesma coisa, considerando as mesmas entradas). Não faz diferença para a complexidade algorítmica antes que os resultados sejam armazenados.

Recursão é o método de uma função que se chama, geralmente com um conjunto de dados menor. Como a maioria das funções recursivas pode ser convertida em funções iterativas semelhantes, isso também não faz diferença para a complexidade algorítmica.

A programação dinâmica é o processo de resolver sub-problemas mais fáceis de resolver e criar a resposta a partir disso. A maioria dos algoritmos de DP estará nos tempos de execução entre um algoritmo Greedy (se houver) e um algoritmo exponencial (enumere todas as possibilidades e encontre a melhor).

• Os algoritmos de DP podem ser implementados com recursão, mas não precisam.
• Os algoritmos de DP não podem ser acelerados pela memorização, pois cada subproblema é resolvido apenas (ou a função "resolver" é chamada) uma vez.

É uma otimização do seu algoritmo que reduz o tempo de execução.

Enquanto um algoritmo ganancioso é geralmente chamado ingênuo , porque pode ser executado várias vezes no mesmo conjunto de dados, a Programação Dinâmica evita essa armadilha por meio de um entendimento mais profundo dos resultados parciais que devem ser armazenados para ajudar a construir a solução final.

Um exemplo simples é percorrer uma árvore ou um gráfico apenas através dos nós que contribuiriam com a solução ou colocar em uma tabela as soluções que você encontrou até agora para evitar percorrer os mesmos nós repetidamente.

Aqui está um exemplo de um problema adequado para programação dinâmica, do juiz on-line da UVA: Edit Steps Ladder.

Vou fazer um resumo rápido da parte importante da análise desse problema, extraída do livro Desafios de Programação, sugiro que você verifique.

Dê uma boa olhada nesse problema, se definirmos uma função de custo nos dizendo qual a distância entre duas cadeias, temos duas que consideram os três tipos naturais de mudanças:

Substituição - altere um único caractere do padrão "s" para um caractere diferente no texto "t", como alterar "tiro" para "ponto".

Inserção - insira um único caractere no padrão "s" para ajudá-lo a corresponder ao texto "t", como alterar "atrás" para "novamente".

Exclusão - exclua um único caractere do padrão "s" para ajudá-lo a corresponder ao texto "t", como alterar "hora" para "nosso".

Quando definimos cada uma dessas operações para custar uma etapa, definimos a distância de edição entre duas seqüências. Então, como calculamos isso?

Podemos definir um algoritmo recursivo usando a observação de que o último caractere na string deve ser correspondido, substituído, inserido ou excluído. Cortar os caracteres na última operação de edição deixa uma operação de par deixa um par de seqüências menores. Seja i e j o último caractere do prefixo relevante de et, respectivamente. existem três pares de cadeias mais curtas após a última operação, correspondentes à cadeia após uma correspondência / substituição, inserção ou exclusão. Se soubéssemos o custo de editar os três pares de cadeias menores, poderíamos decidir qual opção leva à melhor solução e escolher essa opção de acordo. Podemos aprender esse custo, através da coisa incrível que é a recursão:

#define MATCH 0 /* enumerated type symbol for match */
#define INSERT 1 /* enumerated type symbol for insert */
#define DELETE 2 /* enumerated type symbol for delete */


int string_compare(char *s, char *t, int i, int j)

{

    int k; /* counter */
    int opt[3]; /* cost of the three options */
    int lowest_cost; /* lowest cost */
    if (i == 0) return(j * indel(’ ’));
    if (j == 0) return(i * indel(’ ’));
    opt[MATCH] = string_compare(s,t,i-1,j-1) +
      match(s[i],t[j]);
    opt[INSERT] = string_compare(s,t,i,j-1) +
      indel(t[j]);
    opt[DELETE] = string_compare(s,t,i-1,j) +
      indel(s[i]);
    lowest_cost = opt[MATCH];
    for (k=INSERT; k<=DELETE; k++)
    if (opt[k] < lowest_cost) lowest_cost = opt[k];
    return( lowest_cost );

}

Este algoritmo está correto, mas também é impossivelmente lento.

Rodando em nosso computador, leva alguns segundos para comparar duas seqüências de 11 caracteres, e o cálculo desaparece em uma área nunca-nunca, por mais tempo.

Por que o algoritmo é tão lento? Leva um tempo exponencial porque recalcula os valores novamente e novamente. Em todas as posições da cadeia, a recursão se ramifica de três maneiras, o que significa que cresce a uma taxa de pelo menos 3 ^ n - de fato, ainda mais rápido, pois a maioria das chamadas reduz apenas um dos dois índices, não os dois.

Então, como podemos tornar o algoritmo prático? A observação importante é que a maioria dessas chamadas recursivas está computando coisas que já foram computadas antes. Como nós sabemos? Bem, só pode haver | s | T | possíveis chamadas recursivas exclusivas, uma vez que existem apenas muitos pares distintos (i, j) para servir como parâmetros de chamadas recursivas.

Armazenando os valores para cada um desses pares (i, j) em uma tabela, podemos evitar recalculá-los e procurá-los conforme necessário.

A tabela é uma matriz bidimensional m onde cada um dos | s | · | t | células contém o custo da solução ideal desse subproblema, além de um ponteiro pai explicando como chegamos a esse local:

typedef struct {
int cost; /* cost of reaching this cell */
int parent; /* parent cell */
} cell;

cell m[MAXLEN+1][MAXLEN+1]; /* dynamic programming table */

A versão de programação dinâmica possui três diferenças em relação à versão recursiva.

Primeiro, ele obtém seus valores intermediários usando a pesquisa de tabela em vez de chamadas recursivas.

** Segundo, ** ele atualiza o campo pai de cada célula, o que nos permitirá reconstruir a sequência de edição posteriormente.

** Terceiro, ** Terceiro, ele é instrumentado usando uma cell()função de objetivo mais geral , em vez de apenas retornar m [| s |] [| t |] .cost. Isso nos permitirá aplicar essa rotina a uma classe mais ampla de problemas.

Aqui, uma análise muito particular do que é necessário para obter os melhores resultados parciais é o que torna a solução "dinâmica".

Aqui está uma solução alternativa completa para o mesmo problema. Também é "dinâmico", embora sua execução seja diferente. Sugiro que você verifique a eficiência da solução enviando-a ao juiz on-line da UVA. Acho incrível como um problema tão pesado foi tratado com tanta eficiência.

Os principais bits da programação dinâmica são "subproblemas sobrepostos" e "subestrutura ideal". Essas propriedades de um problema significam que uma solução ótima é composta pelas soluções ótimas para seus subproblemas. Por exemplo, os problemas de caminho mais curto exibem a subestrutura ideal. O caminho mais curto de A a C é o caminho mais curto de A para algum nó B, seguido pelo caminho mais curto desse nó B para C.

Mais detalhadamente, para resolver um problema de caminho mais curto, você irá:

• encontre as distâncias do nó inicial a todos os nós que o tocam (digamos de A a B e C)
• encontre as distâncias desses nós para os nós que os tocam (de B para D e E e de C para E e F)
• agora conhecemos o caminho mais curto de A a E: é a soma mais curta de Ax e xE para algum nó x que visitamos (B ou C)
• repita esse processo até chegarmos ao nó de destino final

Como estamos trabalhando de baixo para cima, já temos soluções para os subproblemas na hora de usá-los, memorizando-os.

Lembre-se de que problemas de programação dinâmica devem ter subproblemas sobrepostos e subestrutura ideal. Gerar a sequência de Fibonacci não é um problema de programação dinâmica; utiliza memoização porque possui subproblemas sobrepostos, mas não possui subestrutura ideal (porque não há nenhum problema de otimização envolvido).

Programaçao dinamica

Definição

A programação dinâmica (DP) é uma técnica geral de design de algoritmo para resolver problemas com subproblemas sobrepostos. Esta técnica foi inventada pelo matemático americano "Richard Bellman" na década de 1950.

Ideia-chave

A idéia principal é salvar respostas de subproblemas menores sobrepostos para evitar a recomputação.

Propriedades de programação dinâmica

• Uma instância é resolvida usando as soluções para instâncias menores.
• As soluções para uma instância menor podem ser necessárias várias vezes, portanto, armazene seus resultados em uma tabela.
• Assim, cada instância menor é resolvida apenas uma vez.
• Espaço adicional é usado para economizar tempo.

Eu também sou muito novo na Programação Dinâmica (um algoritmo poderoso para tipos específicos de problemas)

Em palavras mais simples, pense na programação dinâmica como uma abordagem recursiva ao usar o conhecimento anterior

Conhecimento prévio é o que mais importa aqui. Acompanhe a solução dos sub-problemas que você já possui.

Considere isso, exemplo mais básico para dp da Wikipedia

Encontrando a sequência de fibonacci

function fib(n)   // naive implementation
    if n <=1 return n
    return fib(n − 1) + fib(n − 2)

Vamos quebrar a chamada de função com digamos n = 5

fib(5)
fib(4) + fib(3)
(fib(3) + fib(2)) + (fib(2) + fib(1))
((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
(((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Em particular, a fib (2) foi calculada três vezes a partir do zero. Em exemplos maiores, muitos outros valores de fib, ou subproblemas, são recalculados, levando a um algoritmo de tempo exponencial.

Agora, vamos tentar armazenando o valor que já descobrimos em uma estrutura de dados, como um Mapa

var m := map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

Aqui estamos salvando a solução de subproblemas no mapa, se ainda não a tivermos. Essa técnica de salvar valores que já calculamos é denominada Memoização.

Por fim, para um problema, primeiro tente encontrar os estados (possíveis subproblemas e tente pensar na melhor abordagem de recursão para poder usar a solução do subproblema anterior em outros).

A programação dinâmica é uma técnica para resolver problemas com subproblemas sobrepostos. Um algoritmo de programação dinâmica resolve todos os subproblemas apenas uma vez e salva sua resposta em uma tabela (matriz). Evitando o trabalho de recalcular a resposta sempre que o subproblema for encontrado. A idéia subjacente da programação dinâmica é: Evite calcular o mesmo material duas vezes, geralmente mantendo uma tabela de resultados conhecidos de subproblemas.

As sete etapas no desenvolvimento de um algoritmo de programação dinâmica são as seguintes:

1. Estabeleça uma propriedade recursiva que dê a solução para uma instância do problema.
2. Desenvolver um algoritmo recursivo conforme a propriedade recursiva
3. Veja se a mesma instância do problema está sendo resolvida novamente e novamente em chamadas recursivas
4. Desenvolver um algoritmo recursivo memorizado
5. Veja o padrão em armazenar os dados na memória
6. Converta o algoritmo recursivo memorizado em algoritmo iterativo
7. Otimize o algoritmo iterativo usando o armazenamento conforme necessário (otimização de armazenamento)

em suma, a diferença entre memorização de recursão e programação dinâmica

A programação dinâmica, como o nome sugere, está usando o valor calculado anterior para construir dinamicamente a próxima nova solução

Onde aplicar a programação dinâmica: Se a sua solução for baseada na subestrutura ideal e no subproblema sobreposto, nesse caso, usar o valor calculado anteriormente será útil para que você não precise recalculá-lo. É uma abordagem de baixo para cima. Suponha que você precise calcular fib (n) nesse caso, tudo o que você precisa fazer é adicionar o valor calculado anterior de fib (n-1) e fib (n-2)

Recursão: basicamente subdividindo o problema em uma parte menor para resolvê-lo com facilidade, mas lembre-se de que isso não evita o re-cálculo se tivermos o mesmo valor calculado anteriormente em outra chamada de recursão.

Memorização: Basicamente, o armazenamento do antigo valor de recursão calculado na tabela é conhecido como memorização, o que evitará o recálculo se já tiver sido calculado por alguma chamada anterior, para que qualquer valor seja calculado uma vez. Portanto, antes de calcular, verificamos se esse valor já foi calculado ou não, se já calculado, retornamos o mesmo da tabela em vez de recalcular. Também é abordagem de cima para baixo

Aqui está um exemplo simples de código python de Recursive, Top-down, Bottom-upabordagem para a série de Fibonacci:

Recursiva: O (2 ⁿ )

def fib_recursive(n):
    if n == 1 or n == 2:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)


print(fib_recursive(40))

De cima para baixo: O (n) Eficiente para entrada maior

def fib_memoize_or_top_down(n, mem):
    if mem[n] is not 0:
        return mem[n]
    else:
        mem[n] = fib_memoize_or_top_down(n-1, mem) + fib_memoize_or_top_down(n-2, mem)
        return mem[n]


n = 40
mem = [0] * (n+1)
mem[1] = 1
mem[2] = 1
print(fib_memoize_or_top_down(n, mem))

Bottom-up: O (n) Para simplicidade e tamanhos de entrada pequenos

def fib_bottom_up(n):
    mem = [0] * (n+1)
    mem[1] = 1
    mem[2] = 1
    if n == 1 or n == 2:
        return 1

    for i in range(3, n+1):
        mem[i] = mem[i-1] + mem[i-2]

    return mem[n]


print(fib_bottom_up(40))