Eu diria que programação dinâmica é programação dinâmica. Esse é um conceito separado dos algoritmos. Se você perguntasse "aplicações algorítmicas da programação dinâmica", isso faria mais sentido para mim.
Yoshio Okamoto 24/03
1
É claro que dp é dp, mas programação e dinâmica significam algo diferente hoje; portanto, quando ensino programação dinâmica, desejo que ele tenha um nome diferente.
25411 Jack
4
Desculpe, eu não estava claro o suficiente. Você está interessado em programação dinâmica em geral, incluindo o uso em controle e planejamento de políticas, etc., e até em programação dinâmica estocástica, ou apenas em programação dinâmica como método para o design de algoritmos? O público principal aqui conheceria apenas o último, mas sua pergunta é bastante geral, incluindo o primeiro.
Yoshio Okamoto 25/03
1
Yoshio, acho que você deveria apenas explicar o conceito mais geral e as diferenças em uma resposta, pois isso poderia esclarecer muitos de nós.
24511 Raphael
2
Outra idéia não-inteiro-tongue-in-cheek: "a coisa que você recebe empregos no Google" - com base na experiência meus alunos tiveram :)
Os anos 50 não foram bons anos para a pesquisa matemática. Tínhamos um cavalheiro muito interessante em Washington chamado Wilson. Ele era secretário de Defesa e, na verdade, tinha um medo e ódio patológico da palavra "pesquisa". Não estou usando o termo de ânimo leve; Estou usando com precisão. Seu rosto seria difuso, ele ficaria vermelho e ficaria violento se as pessoas usassem o termo "pesquisa" em sua presença. Você pode imaginar como ele se sentiu, então, sobre o termo "matemático". A RAND Corporation era empregada pela Força Aérea, e a Força Aérea tinha Wilson como chefe, essencialmente. Por isso, senti que tinha que fazer algo para proteger Wilson e a Força Aérea do fato de que estava realmente fazendo matemática dentro da RAND Corporation.
Qual título, qual nome, eu poderia escolher? Em primeiro lugar, eu estava interessado em planejar, em tomar decisões, em pensar. Mas planejar, não é uma boa palavra por várias razões. Decidi, portanto, usar a palavra 'programação'. Eu queria passar a ideia de que isso era dinâmico, multiestágio, variava no tempo - pensei: vamos matar dois coelhos com uma cajadada só. Vamos usar uma palavra que tenha um significado absolutamente preciso, ou seja, 'dinâmico', no sentido físico clássico. Também possui uma propriedade muito interessante como adjetivo, e é impossível usar a palavra "dinâmico" em um sentido pejorativo. Tente pensar em alguma combinação que possivelmente lhe dê um significado pejorativo. É impossível. Assim, pensei que “programação dinâmica” era um bom nome. Era algo que nem mesmo um congressista poderia se opor.
(Como Russell e Norvig apontam em seu livro de IA, no entanto, essa história deve ser um embelezamento criativo da verdade. Bellman usou a frase "programação dinâmica" em 1952 e Charles Erwin Wilson não se tornou secretário de Defesa até 1953. )
De qualquer forma, a motivação original de Bellman sugere planejamento em vários estágios , mas pelo menos para fins algorítmicos, prefiro algo como recursão frugal de baixo para cima , apenas com menos sílabas.
Claro, o que eu realmente gostaria de fazer é renomear "Equação de Bellman", ou como os cientistas da computação a chamam, "qualquer recorrência qualquer".
Existem dois aspectos importantes do DP: (1) definir os subproblemas (ou seja, configurar uma "tabela", que pode ser uma matriz multidimensional indexada talvez por números inteiros, vértices, subconjuntos de vértices etc.) e (2) resolver recursivamente subproblemas. Proponho "recursão tabular / tabulada" como um nome que se refere a ambos os aspectos.
Exatamente. Memoização é programação dinâmica por acidente.
Jeffε
@professor erickson - muito bem dito. não consigo parar de rir.
precisa
7
Ainda assim, se escolhermos um novo nome para DP, o uso de memoização seria adequado para ele. Por exemplo, "a distância de edição pode ser calculada em poli-tempo usando a memorização".
Noam
A programação dinâmica é um caso especial de memorização, além de direcionar explicitamente o fluxo de controle, em vez de seguir a ordem de avaliação do aplicativo natural. É uma pena que geralmente seja ensinado do jeito que é, pois coloca muita ênfase no preenchimento de uma tabela, em vez da especificação recursiva. Parece mágico.
Neil Toronto
8
Para dividir e conquistar , eu diria que emendar e combinar.
Eu costumo usar as duas palavras, unir e combinar ao ensinar / explicar DP; mas não usado emendar e combinar explicitamente. Às vezes, usei sobreposição, divisão e conquista para contrastar os dois paradigmas.
Após minha recente palestra sobre programação dinâmica em design de algoritmos, pedi aos alunos que sugerissem um novo nome para esta técnica. Enquanto eu me divertia com "Programação difícil", queria algo que pudesse tornar a técnica mais memorável. Após a discussão aqui, proponho dois nomes, um para cima e para baixo e outro para baixo:
Multiway-Divide e Memoized-Conquer (também conhecido como Divide ^ M & Conquer ^ M) e
Mesclar todos os subproblemas (também conhecido como Merge_all)
Não acho que seja uma boa idéia criar uma forte associação com a divisão e conquista usuais (como no Mergesort). Lá, os subproblemas são resolvidos independentemente e apenas dois resultados são mesclados. No DP, os subproblemas verificados não são independentes e todas as combinações são verificadas. (ambos em termos aproximados). Portanto, acho que um nome deve destacar a diferença, em vez de criar um senso de semelhança.
24511 Raphael
@Raphael, compartilho a preocupação com os perigos de criar uma associação forte, mas discordo de sua declaração das diferenças. No DP, é crucial que os subproblemas sejam "resolvidos independentemente", mesmo que as soluções para os subproblemas sejam compartilhadas. Costumo apontar que se algum oráculo lhe dissesse a divisão correta, seria dividir e conquistar, mas como não falo grego (ao contrário do meu orientador de doutorado), tenho que tentar todas as divisões possíveis.
26411 Jack
2
Sim, os subproblemas são conceitualmente independentes. No entanto, eu estava me relacionando com eles usando os mesmos resultados parciais, como você aponta. Isso separa DP de D&C, pois é possível, por exemplo, paralelizar o último sem computar subproblemas várias vezes (ou comunicar os resultados) em oposição ao anterior. Sua analogia é boa, mas não garante o nome nesse caso, pois encontrar as divisões corretas é uma parte essencial do problema. Suponho que você possa dizer que DP é uma generalização de D&C com base nesse raciocínio.
24511 Rafael
@ Rafael, desculpe ser pedante, mas como essa é uma pergunta sobre o ensino, quero que a noção de independência dos subproblemas seja clara, e apenas dizer "conceitualmente independente" não é preciso. Quando você tenta uma divisão, os subproblemas que você produz podem não ter dependências. Seus outros comentários se concentram nas etapas dos algoritmos de DP; Prefiro me concentrar primeiro na definição precisa do problema a ser resolvido. Meus exemplos favoritos: peso min triangulação e min convexo decomposição de polígonos simples ( cs.unc.edu/~snoeyink/demos/convdecomp/MWTDemo.html )
Jack
Não há problema em ser pendente. Mas considere a importância didática da escolha das palavras: você diz aos alunos que os subproblemas são independentes e, em seguida, fornece a eles um algoritmo que não separa sua computação, mas, na verdade, depende muito da computação "intercalada". Eu acho que isso pode ser muito confuso. Portanto, você realmente precisa separar independência conceitual / matemática / otimização / ... e independência computacional em algum momento.
Isso soa como algo que você faz em um call center terceirizado;)
Suresh Venkat
2
Eu sugeriria o nome de Programação Indutiva - como uma espécie de ponte, desde nossos tempos até os bons tempos de Euler, Kepler et al. Ou talvez até Programação Indutiva Reversa . E sim, para mim, o DP está fortemente associado à indução, no antigo bom senso da noção. Memorização, cache, tabelas etc. são apenas elementos da técnica, não o núcleo da abordagem para quebrar as coisas.
Bah. A programação dinâmica não é sobre tabelas ; é sobre recursão inteligente.
Jeffε
3
Acho melhor separar dois aspectos: "Extrair uma estrutura recursiva do problema e escrever como recorrência" (modelagem) e "Resolver a recorrência obtida de maneira ascendente" (algoritmos). Sinto-me programação dinâmica (em algoritmos) refere-se a ambos, e este é também o caso para a programação linear, programação inteira, programação semidefinido, etc
Yoshio Okamoto
1
Às vezes, as tabelas são usadas. A programação dinâmica sobre árvores (por exemplo: conjunto independente máximo) normalmente não usa uma tabela [= array] para memorizar a recorrência; usa uma árvore ou, em alguns casos, uma árvore de arranjos, ou um arranjo de árvores, ou, em alguns casos, um produto cartesiano de árvores. Da mesma forma, para programação dinâmica sobre dags ou programação dinâmica sobre decomposições em árvore para gráficos de largura de árvore limitada.
Jeffε
1
JeffE, um nome para uma técnica quase nunca abrange todas as aplicações. Veja "diagonalização", por exemplo; em aplicativos avançados, não há diagonais à vista (ou pelo menos não a área de ação exclusiva). Mas não estou muito apaixonada pelo "preenchimento da mesa", apesar de achar que poderia ser um nome razoável para iniciantes.
Raphael
3
Meus 2 centavos neste tópico. A programação dinâmica tem dois aspectos distintos para projetar algoritmos. Primeiro, é entender a mecânica do dp como em: recursão inteligente mais memoização, levando a um algoritmo mais rápido. O segundo aspecto é como reconhecer que um problema pode admitir uma recursão inteligente e apresentá-la. Ambos são importantes para ensinar. Para este último, um caso comum é dividir e conquistar com interação limitada e, a meu ver, vale a pena destacar explicitamente.
Respostas:
A autobiografia de Richard Bellman sugere que ele escolheu o termo “programação dinâmica” para ser uma distração intencional.
(Como Russell e Norvig apontam em seu livro de IA, no entanto, essa história deve ser um embelezamento criativo da verdade. Bellman usou a frase "programação dinâmica" em 1952 e Charles Erwin Wilson não se tornou secretário de Defesa até 1953. )
De qualquer forma, a motivação original de Bellman sugere planejamento em vários estágios , mas pelo menos para fins algorítmicos, prefiro algo como recursão frugal de baixo para cima , apenas com menos sílabas.
fonte
Existem dois aspectos importantes do DP: (1) definir os subproblemas (ou seja, configurar uma "tabela", que pode ser uma matriz multidimensional indexada talvez por números inteiros, vértices, subconjuntos de vértices etc.) e (2) resolver recursivamente subproblemas. Proponho "recursão tabular / tabulada" como um nome que se refere a ambos os aspectos.
fonte
Memoização é uma variante bastante comum.
fonte
Para dividir e conquistar , eu diria que emendar e combinar.
Eu costumo usar as duas palavras, unir e combinar ao ensinar / explicar DP; mas não usado emendar e combinar explicitamente. Às vezes, usei sobreposição, divisão e conquista para contrastar os dois paradigmas.
fonte
Após minha recente palestra sobre programação dinâmica em design de algoritmos, pedi aos alunos que sugerissem um novo nome para esta técnica. Enquanto eu me divertia com "Programação difícil", queria algo que pudesse tornar a técnica mais memorável. Após a discussão aqui, proponho dois nomes, um para cima e para baixo e outro para baixo:
Multiway-Divide e Memoized-Conquer (também conhecido como Divide ^ M & Conquer ^ M) e
Mesclar todos os subproblemas (também conhecido como Merge_all)
fonte
Este documento ( paywalled doi ) chama problemas que podem ser atacados usando o DP "decompostos".
fonte
Discuti isso recentemente com alguns colegas e, após uma discussão acalorada, criamos o cache de chamadas tabulares .
fonte
Eu sugeriria o nome de Programação Indutiva - como uma espécie de ponte, desde nossos tempos até os bons tempos de Euler, Kepler et al. Ou talvez até Programação Indutiva Reversa . E sim, para mim, o DP está fortemente associado à indução, no antigo bom senso da noção. Memorização, cache, tabelas etc. são apenas elementos da técnica, não o núcleo da abordagem para quebrar as coisas.
fonte
Provavelmente algo que inclui as palavras tabela e preenchimento , pois é isso que acontece.
fonte
Vista recursiva ou horizonte recursivo
fonte
Eu o chamaria de "Recursão direta com memorização".
fonte