Sobre o que é a programação dinâmica?

33

Desculpe antecipadamente se esta pergunta parece idiota ...

Tanto quanto eu sei, a construção de um algoritmo usando programação dinâmica funciona da seguinte maneira:

  1. expressar o problema como uma relação de recorrência;
  2. implementar a relação de recorrência por meio de memorização ou por uma abordagem de baixo para cima.

Até onde eu sei, eu disse tudo sobre programação dinâmica. Quero dizer: a programação dinâmica não fornece ferramentas / regras / métodos / teoremas para expressar relações de recorrência, nem para transformá-las em código.

Então, o que há de especial na programação dinâmica? O que isso lhe dá, além de um método vago para abordar um certo tipo de problemas?

ei ei
fonte
11
Factídico histórico (esse comentário não irá ajudá-lo, mas Bellman é realmente um bom líder, se você quiser aprofundar a teoria sobre programação dinâmica): quando Bellman criou o que hoje é conhecido como programação dinâmica, ele chamou a idéia de "programação dinâmica". "porque o trabalho puramente teórico não voava com seu empregador naquela época, ele precisava de algo mais exagerado que não pudesse ser usado de maneira pejorativa .
G. Bach
3
Até onde eu sei, são exatamente esses dois pontos que você menciona. Torna-se especial quando evita explosão exponencial por causa de subproblemas sobrepostos. Isso é tudo. Ah, a propósito, meu professor prefere "paradigma algorítmico" a "método vago".
Hendrik Jan
"Programação dinâmica" parece ser principalmente um chavão (que perdeu o chavão). Isso não significa que não é útil, é claro.
user253751
3
Não é digno de resposta, mas para mim a programação dinâmica é definitivamente "aquela coisa que você usa quando tenta resolver um problema de forma recursiva, mas acaba perdendo tempo revisando os mesmos subproblemas repetidamente".
Hbbs #
@ Hobbs: Exatamente, mas a habilidade está em encontrar essa maneira inicial de perder tempo;)
j_random_hacker

Respostas:

27

A programação dinâmica oferece uma maneira de pensar sobre o design de algoritmos. Isso geralmente é muito útil.

Os métodos de memorização e de baixo para cima fornecem uma regra / método para transformar relações de recorrência em código. Memoização é uma idéia relativamente simples, mas as melhores idéias geralmente são!

A programação dinâmica oferece uma maneira estruturada de pensar sobre o tempo de execução do seu algoritmo. O tempo de execução é basicamente determinado por dois números: o número de subproblemas que você precisa resolver e o tempo necessário para resolver cada subproblema. Isso fornece uma maneira fácil e conveniente de pensar sobre o problema de design do algoritmo. Quando você tem uma relação de recorrência de candidato, pode examiná-la e ter uma noção rápida de qual será o tempo de execução (por exemplo, é possível dizer com muita rapidez quantos subproblemas haverá, o que é um limite inferior no tempo de execução; se houver exponencialmente muitos subproblemas a serem resolvidos, a recorrência provavelmente não será uma boa abordagem). Isso também ajuda a descartar decomposições de subproblemas de candidatos. Por exemplo, se tivermos uma sequênciaS [ 1 .. i ]S[1..n], definindo um subproblema por um prefixo ou sufixo S [ j . . n ] ou substring S [ i . . j ] pode ser razoável (o número de subproblemas é polinomial em n ), mas definir um subproblema por uma subsequência de S provavelmente não será uma boa abordagem (o número de subproblemas é exponencial em n ). Isso permite remover o "espaço de pesquisa" de possíveis recorrências.S[1..i]S[j..n]S[i..j]nSn

A programação dinâmica oferece uma abordagem estruturada para procurar relações de recorrência de candidatos. Empiricamente, essa abordagem geralmente é eficaz. Em particular, existem algumas heurísticas / padrões comuns que você pode reconhecer por maneiras comuns de definir subproblemas, dependendo do tipo de entrada. Por exemplo:

  • Se a entrada for um número inteiro positivo , uma maneira candidata de definir um subproblema é substituindo n por um número inteiro menor n (st 0 n n ).nnn0nn

  • Se a entrada for uma string , algumas maneiras candidatas de definir um subproblema incluem: substitua S [ 1 .. n ] pelo prefixo S [ 1 .. i ] ; substitua S [ 1 .. n ] por um sufixo S [ j . . n ] ; substitua S [ 1 .. n ] por uma substring S [ i . . j ]S[1..n]S[1..n]S[1..i]S[1..n]S[j..n]S[1..n]S[i..j]. (Aqui o subproblema é determinado pela escolha de .)i,j

  • Se a entrada for uma lista , faça o mesmo que faria para uma sequência.

  • Se a entrada for uma árvore , uma maneira candidata de definir um subproblema é substituir T por qualquer subárvore de T (ou seja, escolha um nó x e substitua T pela subárvore com raiz em x ; o subproblema é determinado pela escolha de x )TTTxTxx

  • Se a entrada for um par , observe recursivamente o tipo de xe o tipo de y para identificar uma maneira de escolher um subproblema para cada um. Em outras palavras, uma maneira candidata de definir um subproblema é substituir ( x , y ) por ( x , y ) onde x é um subproblema para x e y ' é um subproblema para y . (Você também pode considerar subproblemas do formulário ( x , y(x,y)xy(x,y)(x,y)xxyy Ou ( x , y ) .)(x,y)(x,y)

E assim por diante. Isso fornece uma heurística muito útil: apenas observando a assinatura de tipo do método, você pode criar uma lista de maneiras candidatas para definir subproblemas. Em outras palavras, apenas olhando para a declaração do problema - olhando apenas para os tipos de entradas - você pode encontrar várias maneiras candidatas para definir um subproblema.

Isso geralmente é muito útil. Ele não informa qual é a relação de recorrência, mas quando você tem uma opção específica de como definir o subproblema, geralmente não é muito difícil descobrir uma relação de recorrência correspondente. Portanto, muitas vezes transforma o design de um algoritmo de programação dinâmica em uma experiência estruturada. Você escreve em um pedaço de papel uma lista de maneiras candidatas para definir subproblemas (usando a heurística acima). Em seguida, para cada candidato, você tenta anotar uma relação de recorrência e avaliar seu tempo de execução contando o número de subproblemas e o tempo gasto por subproblema. Depois de experimentar cada candidato, você mantém o melhor que conseguiu encontrar. Fornecer alguma estrutura para o processo de design de algoritmos é uma grande ajuda, pois, caso contrário, o design de algoritmos pode ser intimidador (há '

DW
fonte
Portanto, você confirma que a programação dinâmica não fornece "procedimentos" concretos a serem seguidos. É apenas "uma maneira de pensar", como você disse. Note que não estou argumentando que o DP é inútil (pelo contrário!), Estou apenas tentando entender se há algo que me falta ou se devo praticar mais.
ei ei
@heyhey, bem, sim ... e não. Veja minha resposta revisada para mais elaboração. Não é uma bala de prata, mas fornece alguns procedimentos semi-concretos que geralmente são úteis (não garantidos que funcionem, mas muitas vezes são úteis).
DW
Muito Obrigado! Ao praticar, estou me familiarizando cada vez mais com alguns desses "procedimentos semi-concretos" que você está descrevendo.
ei ei
"se houver exponencialmente muitos subproblemas a serem resolvidos, a recorrência provavelmente não será uma boa abordagem". Para muitos problemas, não existe um algoritmo de tempo polinomial conhecido. Por que esse deveria ser um critério para usar o DP?
Chiel ten Brinke
@ Chiel, não é um critério para usar o DP. Se você tiver um problema em que ficaria satisfeito com os algoritmos de tempo exponencial, poderá ignorar essa observação entre parênteses. É apenas um exemplo para tentar ilustrar o argumento geral que eu estava argumentando - não algo que você deve levar muito a sério ou interpretar como uma regra rígida.
DW
9

Seu entendimento da programação dinâmica está correto ( afaik ) e sua pergunta é justificada.

Eu acho que o espaço de design adicional que obtemos do tipo de recorrência que chamamos de "programação dinâmica" pode ser melhor visto em comparação com outros esquemas de abordagens recursivas.

Vamos fingir que nossas entradas são as matrizes com o objetivo de destacar os conceitos.A[1..n]

  1. Abordagem Indutiva

    Aqui, a idéia é diminuir o problema, resolver a versão menor e obter uma solução para a original. Esquematicamente,

    f(A)=g(f(A[1..nc]),A)

    com a função / algoritmo que traduz a solução.g

    Exemplo: Localizando Estrelas em Tempo Linear

  2. Dividir e conquistar

    Particione a entrada em várias partes menores, resolva o problema para cada uma e combine. Esquematicamente (por duas partes),

    .f(A)=g(f(A[1..c]),f(A[c+1..n]),A)

    Exemplos: Mesclagem / Quicksort, menor distância pareada no plano

  3. Programaçao dinamica

    Considere todas as maneiras de particionar o problema em problemas menores e escolha o melhor. Esquematicamente (por duas partes),

    .f(A)=best{g(f(A[1..c]),f(A[c+1..n]))|1cn1}

    Exemplos: distância de edição, problema de mudança

    Nota lateral importante: programação dinâmica não é força bruta ! A aplicação do em cada etapa reduz consideravelmente o espaço de pesquisa.best

Em certo sentido, você sabe cada vez menos estaticamente de cima para baixo e precisa tomar mais e mais decisões dinamicamente.

A lição de aprender sobre programação dinâmica é que não há problema em tentar todos os particionamentos possíveis (bem, é necessário para correção), porque ainda pode ser eficiente usando a memorização.

Rafael
fonte
A "Programação dinâmica podada" (quando aplicável) prova que tentar todas as possibilidades NÃO é necessário para a correção.
Ben Voigt
@BenVoigt Claro. Permaneci deliberadamente vago sobre o que significa "todos os modos de dividir"; você quer descartar o maior número possível, é claro! (No entanto, mesmo que você tente todas as formas de particionamento, não obtém força bruta, pois você sempre investiga combinações de soluções ótimas para subproblemas, enquanto a força bruta investiga todas as combinações de todas as soluções.)
Raphael
5

A Programação Dinâmica permite trocar memória pelo tempo de computação. Considere o exemplo clássico, Fibonacci.

Fibonacci é definido pela recorrência . Se você resolver usar essa recursão, acabará fazendochamadas O ( 2 n ) para F i b ( ) , pois a árvore de recursão é uma árvore binária com altura n .Fib(n)=Fib(n1)+Fib(n2)O(2n)Fib()n

Em vez disso, você deseja calcular e use-o para encontrar FFib(2) , use-o para encontrar F i b ( 4 ) , etc. Isso leva apenas tempo O ( n ) .Fib(3)Fib(4)O(n)

O DP também nos fornece técnicas básicas para converter uma relação de recorrência em uma solução ascendente, mas são relativamente diretas (e geralmente envolvem o uso de uma matriz dimensional , ou uma fronteira dessa matriz, em que m é o número de parâmetros em a relação de recorrência). Isso está bem explicado em qualquer texto sobre DP.mm

Kittsil
fonte
1
Você fala apenas da parte da memorização, que perde o objetivo da pergunta.
Raphael
1
"A programação dinâmica permite que você troque memória por tempo de computação" não é algo que ouvi ao fazer graduação, e é uma ótima maneira de abordar esse assunto. Esta é uma resposta intuitiva com um exemplo sucinto.
trueshot 16/09/2015
@trueshot: Exceto que algumas vezes a programação dinâmica (e particularmente a "Programação dinâmica podada") é capaz de reduzir os requisitos de tempo e espaço.
Ben Voigt
@ Ben Eu não disse que era um comércio de um para um. Você também pode podar uma árvore de recorrência. Eu afirmo que respondi à pergunta, que era "O que o DP nos leva?" Isso nos torna algoritmos mais rápidos, trocando espaço por tempo. Concordo que a resposta aceita é mais completa, mas isso também é válido.
Kittsil 17/09/2015
2

Aqui está outra maneira ligeiramente diferente de expressar o que a programação dinâmica oferece. A programação dinâmica recolhe um número exponencial de soluções candidatas em um número polinomial de classes de equivalência, de modo que as soluções candidatas em cada classe sejam indistinguíveis em algum sentido.

Deixe-me tomar como exemplo o problema de encontrar o número de subsequentes crescentes de comprimento em uma matriz A de comprimento n . É útil particionar o conjunto de todas as subsequências em classes de equivalência, de modo que duas subsequências pertençam à mesma classe se e somente se tiverem o mesmo comprimento e terminarem no mesmo índice. Todas as 2 n subsequências possíveis pertencem exatamente a um dos O ( n 2kAn2nO(n2)f(i,)i

f(i,)=j<i such thatA[j]<A[i]f(j,1)
f(i,1)=1 for all i=1n

O(n2k)

jnalanko
fonte