Programação dinâmica: o que é, como funciona e recursos de aprendizagem

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.

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:

1. Definir os subproblemas: Um grande problema é dividido em pequenos subproblemas.
2. Resolver os subproblemas: envolve resolver o subproblema identificado, o que pode ser feito usando recursão ou iteração.
3. Armazene as soluções : As soluções para subproblemas são armazenadas para que possam ser reutilizadas.
4. Construa a solução para o problema original : A solução para o grande problema é construída a partir dos subproblemas que já foram calculados.

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:

1. Eficiência : A programação dinâmica pode ser mais eficiente do que outros algoritmos de otimização, pois evita o recálculo de problemas semelhantes várias vezes.
2. Resolvendo Grandes Problemas : A programação dinâmica é ideal para grandes problemas de otimização que seriam inviáveis ​​de resolver usando outros métodos. Isso ocorre porque ele divide o problema em problemas menores, reduzindo sua complexidade.
3. Soluções ótimas : algoritmos de programação dinâmica podem encontrar a solução ótima para um problema se os subproblemas e objetivos forem definidos corretamente.
4. Simplicidade: Algoritmos de programação dinâmica são simples de implementar e entender, especialmente se o problema puder ser definido em uma ordem específica.
5. Extensibilidade: os algoritmos de programação dinâmica podem ser facilmente estendidos para resolver problemas mais complexos adicionando subproblemas adicionais e modificando os objetivos do problema.

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

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:

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:

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

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:

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.

Visualização	produtos	Avaliação	Preço
	Programação Dinâmica (Dover Books on Computer Science)	Ainda não há avaliações	$ 17,29	Compre na Amazon

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.