O que é "dinâmico" na programação dinâmica?

9

Um dos meus idosos teve uma entrevista de emprego e ele foi perguntado por que é chamado de dinâmico. Ele não conseguiu responder e, depois de desistir, o entrevistador disse que não havia nada de dinâmico nisso, é chamado assim. Isso é difícil de acreditar.

Refere-se ao fato de que os subproblemas são resolvidos durante o tempo de execução e usados ​​para atingir a meta final? Como a alocação dinâmica de memória que acontece durante o tempo de execução?

[RESPONDA]

Eu deveria ter lido este artigo da wiki antes de fazer a pergunta, desculpe.

kintoki
fonte
2
Resposta curta, é apenas um nome. Não precisa ter um significado literal.
Yuval Filmus
4
Indiscutivelmente, implementações típicas de DP (preenchimento de tabela) são tão estáticas quanto um algoritmo pode obter.
Raphael

Respostas:

1

Sempre intuí que isso significava que algoritmos usando programação dinâmica pareciam editar o espaço do problema " dinamicamente " até que o problema pudesse ser resolvido com um algoritmo ganancioso.

Por exemplo, com o problema do tabuleiro de damas , o algoritmo de programação dinâmica edita toda a placa à medida que passa por ela e, finalmente, um algoritmo ganancioso pode ser usado (da mesma forma, com o algoritmo de caminho mais curto de Dijkstra, etc.).

Não tenho certeza se isso generaliza para todos os problemas de programação dinâmica.

Realz Slaw
fonte
9

Na verdade, não há nada de especial no nome "programação dinâmica"; a técnica em si é apenas sobre recursão inteligente desenrolando. Veja esta pergunta e veja a resposta @Jeffe, na qual é relatado que Belman escolhe esse nome para distrair intencionalmente.

Massimo Cafaro
fonte
3
Embora isso possa teoricamente responder à pergunta, seria preferível incluir aqui as partes essenciais da resposta e fornecer o link para referência.
John Dvorak
Alguém na Wikipedia parece discordar, acabei de achar isso: é dinâmico, porque os valores na tabela são preenchidos pelo algoritmo com base em outros valores da tabela, e está programando no sentido de definir as coisas em uma tabela, como a televisão programação está preocupado com quando a transmissão que mostra - em Wikibooks
Kintoki
@akki: há exemplos de programação dinâmica em que uma tabela não é necessária em todos os ...
Massimo Cafaro
11
O(1 1)mnO(mEun(m,n))mn
2
@akki: é exatamente a isso que eu me refiro quando digo que o DP trata de desenrolar a recursão com inteligência! Mas o nome em si era inútil e permanece inútil.
Massimo Cafaro
6

Há uma história interessante aqui. Bellman foi pioneiro nesse paradigma. Mas, na verdade, essa era uma pesquisa matemática. Naquela época, o então secretário de Defesa era paranóico das palavras Pesquisa e Matemática (cara louco, né!). Bellman estava com medo de que a arte secreta ficasse furiosa com seu trabalho e, eventualmente, o colocasse em problemas. Então, para confundir um pouco as coisas, ele chamou de Programação Dinâmica , mas não há nada de 'dinâmico' nisso ..

Subhayan
fonte
11
Fonte para isso? Parece uma história realmente interessante.
jmite
Apenas como uma observação lateral: parece incerto quem planejou a Programação Dinâmica pela primeira vez. Bellman deve ser creditado por provar que qualquer implementação de Programação Dinâmica, quando ideal, obedece às chamadas equações de Bellman-Ford. Infelizmente, parece que muitas pessoas acreditam facilmente que isso faz de Bellman o principal pesquisador por trás da ideia original.
Carlos Linares López
@jmite eu li isso em algum lugar (provavelmente algum blog) .. i vai tentar fornecer a fonte ...
Subhayan
@jmite Você pode encontrar a história na nota de aula de Jeff da Aula 5: Programação Dinâmica e também no wiki: programação dinâmica .
Hengxin
3

Richard Bellman chamou de Programação Dinâmica nas palavras em Bellman insira a descrição da imagem aqui

Passei o trimestre de outono (de 1950) na RAND. Minha primeira tarefa foi encontrar um nome para processos de decisão em vários estágios.

Uma pergunta interessante é: de onde veio o nome, programação dinâmica? 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, de vários estágios, variando no tempo. Eu 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. Ele também possui uma propriedade muito interessante como adjetivo e é impossível usar a palavra dinâmica 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.

Fonte: Olho do furacão, Richard Bellman (autobiografia)

Anuj Gupta
fonte