Memoização sem matriz

Na Introdução aos algoritmos de Cormen et al. , Seção 15.3 Elementos da programação dinâmica explica a memorização da seguinte forma:

Um algoritmo recursivo memorizado mantém uma entrada em uma tabela para a solução para cada subproblema. Cada entrada da tabela contém inicialmente um valor especial para indicar que a entrada ainda não foi preenchida. Quando o subproblema é encontrado pela primeira vez à medida que o algoritmo recursivo se desenrola, sua solução é calculada e depois armazenada na tabela. Cada vez que encontramos esse subproblema subseqüente, simplesmente procuramos o valor armazenado na tabela e o retornamos.

E acrescenta, como nota de rodapé:

Essa abordagem pressupõe que conhecemos o conjunto de todos os parâmetros possíveis do subproblema e que estabelecemos a relação entre as posições da tabela e os subproblemas. Outra abordagem mais geral é memorizar usando hash com os parâmetros do subproblema como chaves.

Existe algum problema conhecido de DP que exija (ou facilite) o armazenamento de valores memorizados em um dicionário, e não em uma matriz (multidimensional)?

Antecedentes: se isso é de alguma utilidade, a razão para esta pergunta é que estou tentando motivar a noção de árvores de pesquisa binária (auto-equilibradas) para pessoas que acabaram de ver programação dinâmica.

Provavelmente existem exemplos melhores, mas aqui está um, em cima da minha cabeça:

$S,T$$\le d$$>d$

Eu gostaria de fornecer 2 exemplos.

0-1 Problema na mochila

No caso do problema 0-1 da mochila (onde W é uma capacidade da mochila e N é uma quantidade de itens), às vezes é melhor usar a programação dinâmica de cima para baixo com memorização, em vez da enumeração sistemática de baixo para cima de toda a matriz 2D de tamanho WxN (especialmente em um caso em que a capacidade da mochila W é grande, mas a cardinalidade do conjunto das combinações permitidas de pesos de itens é muito menor que W ).

Nesse caso, por uma questão de economia da memória, pode-se optar por usar o dicionário para memorização em vez da matriz 2D.

Algoritmo de análise de Earley

O algoritmo de análise Earley pode ser usado para a análise de instruções, que pertencem a uma gramática livre de contexto. Ao contrário do algoritmo CYK (que é baseado na abordagem DP de baixo para cima e usa a tabela 2D para memorização) - o analisador Earley usa a abordagem de cima para baixo em combinação com o gráfico de análise para memorização.

O gráfico de análise contém as produções gramaticais parcialmente analisadas (por exemplo: dada a produção X → AB e, após a correspondência bem-sucedida da parte A desta produção, armazenamos a produção parcialmente correspondente dentro do gráfico de análise: X → A • B , onde pontos de ponto para a parte já combinada).

A quantidade de colunas dentro do gráfico de análise igual à quantidade de tokens. No entanto, em geral, pode ser muito complicado estimar a quantidade de produções gramaticais parcialmente analisadas por coluna (depende da gramática e da sequência específica de tokens).

Portanto, é mais conveniente implementar o gráfico de análise com base na estrutura de dados do dicionário.

No domínio Processamento de linguagem natural, geralmente o analisador Earley é uma opção mais conveniente, porque não requer a forma normal de Chomsky para a gramática (e o CYK possui esse requisito).

Na minha experiência com programação competitiva, o uso de uma tabela de hash (Python dictou similar) geralmente é mais conveniente do que o uso de uma matriz, porque qualquer tipo de dados hashable pode ser usado como chave, como strings, sets ( frozensetem Python) ou tuplas como (string, int)etc. Se estiver usando uma matriz, você deve converter manualmente todas as chaves em números inteiros (começando em 0), o que exige trabalho extra e, como observa a fonte, pode não ser possível se você não conhecer o espaço das chaves com antecedência. Portanto, os dicionários são bem mais gerais do que matrizes.

Obviamente, se você pode se dar bem com o uso de matrizes, provavelmente é mais rápido, pois evita repetidamente os hashes de computação (por outro lado, é necessário inicializar toda a matriz primeiro, o que leva tempo e memória), mas pode levar mais tempo para escrever o código. porque você precisa fazer o trabalho extra de converter todas as chaves em números inteiros.