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

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 $\Gamma(\mathbf{i})$ o conjunto de índices de células a célula $\mathbf{i}$ depende. Observe que $\Gamma$ 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

$\qquad d(\mathbf{i}) = f(\mathbf{i}, \widetilde{\Gamma}_d(\mathbf{i}))$

com $\mathbf{i} \in [0\dots m] \times [0\dots n]$ , $\widetilde{\Gamma}_d(\mathbf{i}) = \{(\mathbf{j},d(\mathbf{j})) \mid \mathbf{j} \in \Gamma_d(\mathbf{i}) \}$ e $f$ alguma função (calculável) que não faz use $d$ diferente de via $\widetilde{\Gamma}_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:$\Gamma_d$

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.$\Gamma$$\Gamma$

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?

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+\epsilon)$

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.$A(m,n)$$A(m,n-1)$$A(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.

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:

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.

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 × n$$M$$x$$M$

Responda

Isso pode ser resolvido da seguinte maneira recursiva:

$k = \lceil{\frac{1+n}{2}}\rceil$$x$$m_{k,k}$$x<m_{k,k}$$m_{i,j}$$k\leq i\leq n$$k\leq j\leq n$$1/4$$x>m_{k,k}$$1/4$$\frac{3}{4} n^2$$x$$\left(\frac{3}{4}\right)^3 n^2$