O que é programação dinâmica?

Programação dinâmica, ao se referir ao campo da ciência da computação, descreve um grupo de algoritmos de computador semelhantes destinados a resolver problemas complexos, dividindo o problema em conjuntos de problemas menores. Criado pela primeira vez por Richard Bellman na década de 1950, a programação dinâmica trabalha com problemas que são subproblemas sobrepostos ou subestruturas ideais. Para entender como a programação dinâmica funciona, é melhor entender o conceito por trás desses dois termos.

Subproblemas sobrepostos descrevem equações complicadas que, quando divididas em conjuntos menores de equações, reutilize partes das equações menores mais de uma vez para obter uma resposta. Por exemplo, uma equação matemática instruída a calcular todos os resultados possíveis usando um conjunto de números pode calcular o mesmo resultado várias vezes enquanto calcula outros resultados apenas uma vez. A programação dinâmica diria a esse problema que, depois de calcular o resultado, na primeira vez que ele deve salvar esse resultado e conectar a resposta aoequação mais tarde, em vez de calculá -la novamente. Ao lidar com processos e equações complexas longas, isso economiza tempo e cria uma solução mais rápida usando muito menos etapas.

As subestruturas ideais criam uma solução encontrando a melhor resposta para todos os subproblemas e criando a melhor resposta geral. Depois de dividir um problema complexo em problemas menores, o computador usa um sistema matemático para determinar qual é a melhor resposta para cada problema. Ele calcula a resposta para o problema original das respostas menores. As falhas existem com esse processo. Embora dê a solução que funcione melhor matematicamente, pode ou não ser a melhor solução na vida real, dependendo do tipo de problema e de como ela se relaciona com o mundo real.

Durante qualquer uma dessas operações, o algoritmo de programação dinâmico tenta encontrar o caminho mais curto para a solução. Pode levar um deduas abordagens para fazer isso. A abordagem de cima para baixo divide a equação em equações menores e reutiliza as respostas para essas equações quando necessário. A abordagem de baixo para cima tenta resolver o menor valor matemático depois de quebrar a equação e depois subir em direção ao maior a partir daí. Ambas as abordagens economizam tempo, mas a programação dinâmica só funciona quando o problema original pode dividir em equações menores que em algum momento são reutilizadas para resolver a equação.