A programação dinâmica é um conceito desenvolvido por Richard Bellman, um matemático e economista.
Na época, Bellman estava procurando uma maneira de resolver problemas complexos de otimização. Os problemas de otimização exigem que você escolha a melhor solução em um conjunto de opções.
Um exemplo de problema de otimização é o problema do caixeiro viajante. O objetivo é encontrar a rota mais curta que permita ao vendedor visitar cada cidade exatamente uma vez e retornar à cidade inicial.
A abordagem de Bellman para esses problemas era dividi-los em subproblemas menores e resolvê-los do menor para o maior. Ele então armazenou os resultados dos subproblemas e os reutilizou para resolver subproblemas maiores. Esta é a ideia principal por trás da programação dinâmica.
últimas postagens
O que é Programação Dinâmica?
A programação dinâmica resolve problemas de otimização dividindo-os em subproblemas menores, resolvendo cada subproblema uma vez e armazenando suas soluções para que possam ser reutilizadas e combinadas para resolver o problema maior. Os problemas são resolvidos do menor para o maior, permitindo o reaproveitamento de soluções.
Como funciona a programação dinâmica?
Resolver um problema usando programação dinâmica envolve as seguintes etapas:
Para ver isso em ação, calculamos o 6º número de Fibonacci, F(6), usando este processo.
Primeiro, defina os subproblemas que precisam ser resolvidos.
F(n) = F(n-1) + F(n-2) para n > 1
Portanto: F(6) = F(5) + F(4)
F(5) = F(4) + F(3)
F(4) = F(3) + F(2)
F(3) = F(2) + F(1)
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 0
A segunda etapa envolve a resolução de cada subproblema usando uma função recursiva ou um processo iterativo. Resolvemos os subproblemas do menor para o maior, reutilizando resultados de subproblemas menores. Isso nos dá o seguinte:
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
À medida que resolvemos cada um dos subproblemas, armazenamos as soluções em uma matriz ou tabela para que possam ser reutilizadas na resolução de subproblemas maiores, como:
Uma vez resolvidos todos os subproblemas, usamos as soluções para construir a solução do problema original.
Nesse caso, a solução do problema original é o 6º número de Fibonacci, que é obtido pela soma dos resultados de F(5) e F(4), subproblemas identificados a partir do problema maior. O resultado nos dá 8.
Onde e por que a programação dinâmica é usada?
A programação dinâmica é utilizada em áreas onde temos problemas que podem ser divididos em subproblemas menores, e suas soluções são utilizadas para resolver problemas maiores.
Essas áreas incluem ciência da computação, economia, matemática e engenharia. Na ciência da computação, é usado para resolver problemas envolvendo sequências, grafos e valores inteiros e em programação competitiva.
Na economia, é usado para resolver problemas de otimização em finanças, produção e alocação de recursos. Na matemática, a programação dinâmica é usada na teoria dos jogos, estatística e probabilidade, onde é usada para resolver problemas de otimização.
Na engenharia, é usado para resolver problemas de alocação de recursos, programação, fabricação, comunicação e sistemas de controle.
Existem várias vantagens em usar a programação dinâmica para resolver problemas de otimização:
Quando se trata de resolver problemas de otimização, a programação dinâmica é uma ferramenta muito útil para garantir eficiência nas soluções.
Abordagens usadas na programação dinâmica
Na programação dinâmica, duas abordagens são usadas para resolver problemas de otimização. Estas são a abordagem de cima para baixo e a abordagem de baixo para cima.
Abordagem de cima para baixo
Essa abordagem também é conhecida como memoização. A memorização é uma técnica de otimização usada principalmente para tornar os programas de computador mais rápidos, armazenando os resultados das chamadas de função no cache e retornando os resultados armazenados em cache na próxima vez em que forem necessários, em vez de computá-los novamente.
A abordagem de cima para baixo envolve recursão e cache. A recursão envolve uma função chamando a si mesma com versões mais simples do problema como seu argumento. A recursão é usada para dividir o problema em subproblemas menores e resolvê-los.
Depois que um subproblema é resolvido, seu resultado é armazenado em cache e reutilizado sempre que ocorrer um problema semelhante. O top-down é fácil de entender e implementar e só resolve um subproblema uma vez. Uma desvantagem, no entanto, é que ocupa muita memória por causa da recursão. Isso pode levar a um erro de estouro de pilha.
Abordagem de baixo para cima
A abordagem bottom-up, também conhecida como tabulação, elimina a recursão, substituindo-a pela iteração, evitando assim erros de estouro de pilha.
Nesta abordagem, um grande problema é dividido em subproblemas menores, e as soluções para os subproblemas são usadas para resolver o problema maior.
Subproblemas menores são primeiro resolvidos do maior para o menor, e seus resultados são armazenados em uma matriz, array ou tabela, daí o nome tabulação.
Os resultados armazenados resolvem problemas maiores que dependem dos subproblemas. O resultado do problema original é então encontrado resolvendo o maior subproblema usando valores previamente calculados.
Essa abordagem tem a vantagem de ser eficiente em termos de memória e tempo, eliminando a recursão.
Exemplos de problemas que podem ser resolvidos por programação dinâmica
A seguir estão alguns problemas de programação que podem ser resolvidos usando programação dinâmica:
#1. problema da mochila
Fonte: Wikipédia
Uma mochila é uma bolsa feita de lona, náilon ou couro normalmente amarrada nas costas e usada por soldados e caminhantes para carregar suprimentos.
No problema da mochila, você recebe uma mochila e, dada sua capacidade de carga, é solicitado que você escolha itens, cada um com seu valor. Sua seleção deve ser tal que você obtenha o valor total máximo dos itens escolhidos e o peso dos itens seja menor ou igual à capacidade da mochila.
Um exemplo do problema da mochila é dado a seguir:
Imagine que você vai fazer uma caminhada e tem uma mochila com capacidade para 15 quilos. Você tem uma lista de itens que pode trazer, juntamente com seus valores e pesos, conforme tabela abaixo:
ItemValorPesoTenda2003Saco de dormir1502Fogão501Comida1002Garrafa de água100,5Kit de primeiros socorros251
Escolha um subconjunto dos itens a serem trazidos de forma que o valor total dos itens seja maximizado enquanto o peso total for menor ou igual à capacidade da mochila, que é de 15 quilos.
As aplicações do mundo real do problema da mochila envolvem a seleção de títulos para adicionar a uma carteira para minimizar o risco e maximizar o lucro e encontrar as maneiras menos dispendiosas de cortar matérias-primas.
#2. Problema de Agendamento
Um problema de agendamento é um problema de otimização no qual o objetivo é atribuir tarefas de maneira otimizada a um conjunto de recursos. Os recursos podem ser máquinas, pessoal ou outros recursos usados para concluir as tarefas.
Um exemplo de problema de escalonamento é dado a seguir:
Imagine que você é um gerente de projeto responsável por agendar um conjunto de tarefas que precisam ser concluídas por uma equipe de funcionários. Cada tarefa tem uma hora de início, uma hora de término e uma lista de funcionários qualificados para concluí-la.
Aqui está uma tabela que descreve as tarefas e suas características:
TarefaHora de inícioHora de términoFuncionários qualificadosT1911A, B, CT21012A, CT31113B, CT41214A, B
Atribua cada tarefa a um funcionário para minimizar o tempo total de conclusão.
O problema de agendamento pode ser encontrado na indústria de manufatura ao tentar otimizar a alocação de recursos como máquinas, materiais, ferramentas e mão de obra.
Também pode ser encontrado na área da saúde ao otimizar o uso de leitos, pessoal e suprimentos médicos. Outros setores em que esse problema pode ocorrer são gerenciamento de projetos, gerenciamento da cadeia de suprimentos e educação.
#3. Problema do Caixeiro Viajante
Fonte: Wikipédia
Este é um dos problemas de otimização mais estudados que podem ser resolvidos usando programação dinâmica.
O problema do caixeiro viajante fornece uma lista de cidades e as distâncias entre cada par de cidades. Você deve encontrar a rota mais curta possível que visite cada cidade exatamente uma vez e retorne à cidade de origem.
Um exemplo de problema do caixeiro viajante é dado a seguir:
Imagine que você é um vendedor que precisa visitar um conjunto de cidades no menor tempo possível. Você tem uma lista das cidades que precisa visitar e as distâncias entre cada par de cidades, conforme tabela abaixo:
CidadeABCDEA010152030B100352515C153503020D202530010E301520100
O problema do caixeiro-viajante pode ser encontrado na indústria de lazer ao tentar planejar rotas para turistas, logística ao planejar o transporte de mercadorias, transporte ao planejar rotas de ônibus e na indústria de vendas, entre outros.
Claramente, a programação dinâmica tem muitas aplicações do mundo real, o que ajuda a aprender mais sobre ela.
Considere os seguintes recursos para expor seu conhecimento de programação dinâmica.
Recursos
Programação Dinâmica de Richard Bellman
Programação Dinâmica é um livro de Richard Bellman, que criou a programação dinâmica e a desenvolveu em seus estágios iniciais.
O livro é escrito de uma forma fácil de entender que requer apenas conhecimentos básicos de matemática e cálculo para entender o texto. No livro, Bellman apresenta a teoria matemática de um processo de decisão em vários estágios, que é fundamental na programação dinâmica.
O livro examina problemas de gargalo em processos de produção de vários estágios, teoremas de existência e exclusividade e a equação de estoque ideal.
A melhor coisa sobre o livro é que Bellman oferece exemplos de muitos problemas complexos em áreas como logística, teoria do agendamento, teoria da comunicação, economia matemática e processos de controle e mostra como a programação dinâmica pode resolver os problemas.
O livro está disponível nas versões Kindle, capa dura e brochura.
Curso de Mestrado em Algoritmos de Programação Dinâmica
Este Curso Master de Algoritmos de Programação Dinâmica da Udemy é oferecido por Apaar Kamal, engenheiro de software do Google, e Prateek Narang, que também trabalhou com o Google.
O curso é otimizado para ajudar os alunos a se destacarem na competição de programação, que apresenta muitos problemas que exigem programação dinâmica.
Além dos concorrentes de programação, o curso é ideal para programadores que buscam melhorar sua compreensão de algoritmos e pessoas que se preparam para entrevistas de programação e rodadas de codificação online.
O curso, com mais de 40 horas de duração, aborda a programação dinâmica em profundidade. O curso primeiro oferece uma atualização de conceitos como recursão e retrocesso.
Em seguida, cobre programação dinâmica em teoria de jogos, strings, árvores e gráficos, exponenciação de matrizes, bitmasks, combinatória e subsequências, problemas de partição e programação dinâmica multidimensional, entre muitos outros conceitos.
Conceitos Básicos de Programação Competitiva, Algoritmos Mestres
A Udemy oferece um Curso Básico de Programação Competitiva de Prateek Narang e Amal Kamaar que abrange programação dinâmica, matemática, teoria dos números e estruturas e algoritmos de dados avançados de uma maneira útil e relevante para programadores competitivos.
O curso oferece uma atualização sobre estruturas de dados e algoritmos antes de mergulhar em algoritmos e técnicas mais complexos que são úteis na programação competitiva.
O curso abrange programação dinâmica, matemática, teoria dos jogos, correspondência de padrões, Bitmasking e uma infinidade de algoritmos avançados usados e testados em competições de programação.
O curso da Udemy é dividido em 10 módulos e 42 seções e fornece muitas questões práticas após cada seção. Este curso best-seller é obrigatório para qualquer pessoa interessada em programação competitiva.
Palavras Finais
A programação dinâmica é uma habilidade benéfica para qualquer programador aprender a melhorar sua resolução de problemas do mundo real. Portanto, os programadores devem considerar os recursos sugeridos para adicionar essa ferramenta crucial à sua caixa de ferramentas.
A seguir, você pode conferir as linguagens de programação para usar na ciência de dados.