Uma distinção entre casos em programação dinâmica: exemplo necessário!

19

Trabalho com programação dinâmica há algum tempo. A maneira canônica de avaliar uma recursão de programação dinâmica é criando uma tabela de todos os valores necessários e preenchendo-a linha por linha. Veja, por exemplo , Cormen, Leiserson et al: "Introdução aos algoritmos" para uma introdução.

Focalizo o esquema de computação baseado em tabela em duas dimensões (preenchimento linha a linha) e investigo a estrutura das dependências de células, ou seja, quais células precisam ser executadas antes que outras possam ser computadas. Nós denotar com Γ(i) o conjunto de índices de células a célula i depende. Observe que Γ precisa estar livre de ciclos.

Eu abstraio da função real que é calculada e concentro-me em sua estrutura recursiva. Formalmente, eu considero um recurrrence d ser programação dinâmica se ele tem a forma

d(i)=f(i,Γ~d(i))

com i[0m]×[0n] , Γ~d(i)={(j,d(j))jΓd(i)} e f alguma função (calculável) que não faz use d diferente de via Γ~d .

Ao restringir a granularidade de a áreas ásperas (à esquerda, superior esquerda, superior, superior direita, ... da célula atual), observa-se que existem essencialmente três casos (até simetrias e rotação) válidos recursões de programação dinâmica que informam como a tabela pode ser preenchida:Γd

Três casos de dependências de célula de programação dinâmica

As áreas vermelhas denotam (aproximações demais de) . Os casos um e dois admitem subconjuntos, o caso três é o pior caso (até a transformação do índice). Observe que não é estritamente necessário que todas as áreas vermelhas sejam cobertas por Γ ; algumas células em cada parte vermelha da tabela são suficientes para pintar de vermelho. É explicitamente necessário que as áreas brancas não contenham nenhuma célula necessária.ΓΓ

Exemplos para o caso um são a distância de edição e a subsequência comum mais longa , o caso dois se aplica a Bellman & Ford e CYK . Exemplos menos óbvios incluem aqueles que trabalham nas diagonais, em vez de linhas (ou colunas), pois podem ser rotacionados para se ajustarem aos casos propostos; veja a resposta de Joe para um exemplo.

Não tenho exemplo (natural) para o caso três! Então, minha pergunta é: Quais são os exemplos para o caso de três recursões / problemas de programação dinâmica?

Rafael
fonte
2
O caso 3 inclui os casos 1 e 2.
JeffE 12/12/12
Não, apesar das aparências. Por exemplo, uma instância do caso 1 não pode ter uma célula necessária na área superior esquerda, enquanto uma instância do caso 3 precisa ter uma célula necessária na área superior esquerda. Eu editei a explicação para esclarecer.
Raphael

Respostas:

15

Existem muitos outros exemplos de algoritmos de programação dinâmica que não se encaixam no seu padrão.

  • O maior problema de subsequência crescente requer apenas uma tabela unidimensional.

  • Existem vários algoritmos de programação dinâmica natural cujas tabelas requerem três ou até mais dimensões. Por exemplo: Encontre o retângulo branco da área máxima em um bitmap. O algoritmo de programação dinâmica natural usa uma tabela tridimensional.

  • Mas o mais importante é que a programação dinâmica não é sobre tabelas ; trata-se de desenrolar recursão. Existem muitos algoritmos de programação dinâmica natural em que a estrutura de dados usada para armazenar resultados intermediários não é uma matriz, porque a recorrência que está sendo desenrolada não está acima de um intervalo de números inteiros. Dois exemplos fáceis são encontrar o maior conjunto independente de vértices em uma árvore e encontrar a maior subárvore comum de duas árvores. Um exemplo mais complexo é o algoritmo de aproximação para o problema dos vendedores ambulantes euclidianos de Arora e Mitchell.(1+ϵ)

JeffE
fonte
Obrigado pela sua resposta, mas restrinjai explicitamente a pergunta a problemas bidimensionais e ao esquema de computação canônico baseado em tabela (editado para tornar esse ponto ainda mais claro). Estou ciente da estrutura mais geral, mas não estou interessada nela neste momento.
Raphael
9
Ok, mas eu realmente acho que você está perdendo o objetivo.
Jeffe
Como existem muitos votos positivos, achei que deveria deixar isso claro: este post não responde à pergunta e, de fato, nem tenta.
Raphael
2
@Raphael está correto. Minha "resposta" não é uma resposta, mas uma crítica à pergunta, mas foi muito tempo para um comentário.
30412 JeffE
3

A função Ackermann de computação está nesse espírito. Para calcular você precisa conhecer A ( m , n - 1 ) e A ( m - 1 , k ) para alguns k grandes . A segunda coordenada diminui ou a primeira diminui e a segunda potencialmente aumenta.UMA(m,n)UMA(m,n-1)UMA(m-1,k)k

Isso não se encaixa idealmente nos requisitos, já que o número de colunas é infinito e o cálculo geralmente é feito de cima para baixo com memorização, mas acho que vale a pena mencionar.

sdcvvc
fonte
1
Não, o aninhamento como em UMA(m-1,UMA(m,n-1)) não se presta realmente à programação dinâmica. Hehe, isso é tão estranho que vou ter que verificar se minhas definições excluem esses casos de alguma forma. DP não primitivo-recursivo, oh meu ...
Raphael
1
Não sei por que essa resposta foi reduzida, pois é uma boa resposta. A função Ackermann se presta extremamente bem à programação dinâmica. Em geral, qualquer função definida recursivamente que é computada repetidamente para os mesmos argumentos se presta à programação dinâmica. Para vê-lo, basta implementá-lo e comparar os tempos de execução. O que leva anos para calcular com a função Ackermann comum pode levar segundos com a função de programação dinâmica.
Jules
@Jules: O problema do esquema de tabelas canônicas é que você não conhece um limite (recursivo primitivo) no tamanho da tabela a priori. É claro que você pode fazer memórias, mas não da maneira usual. Portanto, sim, pode ser viável para o DP, mas não se encaixa na classe de problemas com os quais minha pergunta está relacionada.
Raphael
1
Eu não acho que é um requisito para o DP ter um limite a priori no tamanho da tabela? De fato, como JeffE menciona, o cache não precisa ser uma tabela. Pode ser qualquer estrutura de dados associativa. DP é realmente uma idéia muito, muito simples: você deseja calcular uma função definida recursivamente, mas essa função é chamada repetidamente nos mesmos argumentos. O DP é a otimização em que você introduz um cache para calcular cada caso apenas uma vez. Existem muitas funções que não se encaixam em nenhum dos seus casos, mesmo que sejam funções de dois números inteiros limitados.
Jules
2

Isso não se encaixa exatamente no caso 3, mas não sei se algum dos seus casos captura um problema muito comum usado para ensinar programação dinâmica: Multiplicação em Cadeia de Matrizes . Para resolver esse problema (e muitos outros, esse é apenas o canônico), preenchemos a matriz diagonal por diagonal, em vez de linha por linha.

Portanto, a regra é algo como isto:

diagMatrix

Joe
fonte
1
Escrito assim, de fato não se encaixa em nenhum caso. No entanto, se você girar 45 graus no sentido horário, obtém o caso 2 (e todas as propriedades implícitas). Isso vale para outros exemplos que também trabalham da diagonal para os cantos. Mas obrigado por mencionar!
Raphael
@ Rafael, não é imediatamente óbvio que estes são equivalentes, você pode mencionar isso na sua pergunta.
3111 Joe
0

Eu sei que é um exemplo bobo, mas acho que um problema iterativo simples como

Encontre a soma dos números em uma matriz quadrada

pode se qualificar. O tradicional "para cada linha para cada coluna" parece com o seu caso 3.

hugomg
fonte
-1

Este não é exatamente o espaço de pesquisa que você está procurando, mas tenho uma ideia do topo da minha cabeça que pode ser útil.

Problema:

n×nMxM

Responda

Isso pode ser resolvido da seguinte maneira recursiva:

k=1+n2xmk,kx<mk,kmEu,jkEunkjn1/4x>mk,k1/434n2x(34)3n2

0x0
fonte
1
Esta não é uma instância de programação dinâmica, não é?
Raphael