Programacao Dinamica - Conceitos e Recursões Progressivas e Regressivas

8º Aula PROGRAMAÇÃO DINÂMICA Objetivos de aprendizagem Ao término desta aula vocês serão capazes de entender o conceito da programação dinâmica entender as recursões progressivas entender as recursões regressivas Prezadosas alunosas Nesta última aula estudaremos programação dinâmica que é a mais conceitual de nossa jornada de aprendizado de PO A programação dinâmica PD é considerada mais conceitual por ser diferente da PL que existem regras e formas para resolução dos problemas Dessa forma se limita a uma forma genérica e que necessita de grande engenhosidade para uso dessa ferramenta Bons estudos 64 Pesquisa Operacional 1 Seções de estudo Programação Dinâmica 2 Recursões Progressiva e Regressiva 1 Programação Dinâmica De acordo com Taha 2008 Programação Dinâmica PD é uma técnica matemática útil para tomar uma sequência de decisões interrelacionadas Ela fornece um procedimento sistemático para determinar a combinação de decisões ótimas Ao contrário da programação linear não existe uma formulação matemática padrão do problema de programação dinâmica Em vez disso a programação dinâmica é um tipo genérico de metodologia para resolução de problemas e as equações particulares utilizadas têm de ser desenvolvidas para cada situação Portanto é necessário certo grau de engenhosidade e de insight na estrutura geral dos problemas de programação dinâmica para reconhecer quando e como um problema pode ser resolvido pelos procedimentos dessa mesma programação Essas habilidades podem ser mais bem desenvolvidas pela exposição a ampla gama de aplicações de programação dinâmica e um estudo das características que são comuns a todas essas situações TAHA 2008 Os cálculos em PD são feitos recursivamente de modo que a solução ótima de um subproblema é usada como dado de entrada para o subproblema seguinte Quando o último subproblema é resolvido a solução ótima para o problema inteiro está à mão O modo como os cálculos recursivos são executados depende de como decompomos o problema original Em particular os subproblemas normalmente estão ligados por restrições em comum À medida que passamos de um subproblema para o seguinte a viabilidade dessas restrições em comum deve ser mantida 11 Exemplo de Progeamação Dinâmica Para esse exemplo vamos nos basear nos estudos de Taha 2008 Sendo assim suponha que você queira selecionar a rota mais curta entre duas cidades A rede da Figura 1 apresenta as possíveis rotas entre a cidade inicial no nó 1 e a cidade de destino no nó 7 As rotas passam por cidades intermediárias designadas pelos nós 2 a 6 Figura 1 Rede de rotas para o Exemplo Fonte Taha 2008 Podemos resolver esse problema enumerando exaustivamente todas as rotas entre os nós 1 e 7 há cinco delas Contudo em uma rede grande a enumeração exaustiva pode não ser praticável em termos de cálculo Para resolver o problema por PD primeiro o decompomos em estágios como mostram as linhas verticais tracejadas na Figura 2 Em seguida executamos os cálculos para cada estágio separadamente Figura 2 Decomposição do problema do caminho mais curto em estágios Fonte Taha 2008 A ideia geral para determinar a rota mais curta é calcular as distâncias mais curtas cumulativas até todos os nós terminais de um estágio e depois usar essas distâncias como dados de entrada para o estágio imediatamente subsequente Começando no nó 1 o estágio 1 inclui três nós finais 2 3 e 4 e seus cálculos são simples Estágio 1 Resumo Distância mais curta do nó 1 ao nó 2 7 milhas a partir do nó 1 Distância mais curta do nó 1 ao nó 3 8 milhas a partir do nó 1 Distância mais curta do nó 1 ao nó 4 5 milhas a partir do nó 1 Em seguida o estágio 2 tem dois nós finais 5 e 6 Considerando o nó 5 em primeiro lugar vemos pela Figura 102 que o nó 5 pode ser alcançado com base em três nós 2 3 e 4 por três rotas diferentes 2 5 3 5 e 4 5 Essa informação junto com as distâncias mais curtas até os nós 2 3 e 4 determina a distância mais curta cumulativa até o nó 5 por O nó 6 só pode ser alcançado a partir dos nós 3 e 4 assim 65 Estágio 2 Resumo Distância mais curta do nó 1 ao nó 5 12 milhas a partir do nó 4 Distância mais curta do nó 1 ao nó 6 17 milhas a partir do nó 3 A última etapa é considerar o estágio 3 O nó de destino 7 pode ser alcançado partindo dos nós 5 ou 6 Usando os resultados do resumo do estágio 2 e as distâncias dos nós 5 e 6 ao nó 7 obtemos Estágio 3 Resumo Distância mais curta do nó 1 ao nó 7 21 milhas a partir do nó 5 O resumo do estágio 3 mostra que a distância mais curta entre os nós 1 e 7 é 21 milhas Para determinar a rota ótima o resumo do estágio 3 liga o nó 7 ao nó 5 o resumo do estágio 2 liga o nó 4 ao nó 5 e o resumo do estágio 1 liga o nó 4 ao nó 1 Assim a rota mais curta é 1 4 5 7 O exemplo revela as propriedades básicas dos cálculos em PD 1 Os cálculos em cada estágio são uma função das rotas viáveis desse estágio e somente dele 2 O estágio atual está ligado somente ao estágio imediatamente precedente sem levar em consideração estágios anteriores A ligação está na forma do resumo de distância mais curta que representa o resultado do estágio imediatamente precedente 2 Recursões Progressiva e Regressiva Ainda de acordo com Taha 2008 no exemplo citado anteriormente usaseS recursão progressiva na qual os cálculos prosseguem do estágio 1 ao estágio 3 O mesmo exemplo pode ser resolvido por recursão regressiva começando no estágio 3 e terminando no estágio 1 Ambas as recu rsões progressiva e regressiva dão a mesma solução Embora o procedimento progressivo pareça mais lógico a literatura de PD invariavelmente usa recursão regressiva A razão para essa preferência é que em geral a recursão regressiva pode ser mais eficiente em termos de cálculo Demonstraremos a utilização da recursão regressiva aplicandoa ao mesmo exemplo A demonstração também dará a oportunidade de apresentar os cálculos de PD em uma forma tabular compacta Estágio 3 Como o nó 7 x4 7 está conectado aos nós 5 e 6 x3 5 e 6 com exatamente uma rota cada não há nenhuma alternativa a escolher e os resultados do estágio 3 podem ser resumidos como demonstrado na Tabela 1 Tabela 1 Decisão no estágio 3 Fonte Taha 2008 Estágio 2 A rota 2 6 está bloqueada porque não existe Dado f3 x3 do estágio 3 podemos comparar as alternativas viáveis como mostrado na Tabela 2 Tabela 2 Decisão no estágio 2 Fonte Taha 2008 A solução ótima do estágio 2 é lida da seguinte maneira se você estiver nas cidades 2 ou 4 a rota mais curta passa pela cidade 5 e se você estiver na cidade 3 a rota mais curta passa pela cidade 6 Estágio 1 A partir do nó 1 temos três rotas alternativas 1 2 1 3 e 1 4 Usando f2 x2 do estágio 2 podemos calcular a Tabela 3 Tabela 3 Decisão no estágio 1 Fonte Taha 2008 A solução ótima no estágio 1 mostra que a cidade 1 está ligada à cidade 4 Em seguida a solução ótima no estágio 2 liga a cidade 4 à cidade 5 Por fim a solução ótima no estágio 3 conecta a cidade 5 à cidade 7 Assim a rota completa é dada por 1 à 4 à 5 à 7 e a distância associada é 21 milhas Retomando a aula Ao chegar ao fi nal da oitava aula vamos recordar o que aprendemos 1 Programação Dinâmica Nessa última aula vimos o caso mais conceitual que é a programação dinâmica Vimos que essa ferramenta exige muita experimentação do profissional de engenharia para que 66 Pesquisa Operacional Programação dinâmica Disponível em https ptwikipediaorgwikiProgramaC3A7C3A3o dinC3A2mica Acesso em 09 dez 2019 Programação dinâmica Disponível em httpswww imeuspbrpfanalisedealgoritmosaulasdynamic programminghtml Acesso em 09 dez 2019 Vale a pena ler Vale a pena Minhas anotações Referências possa enxergar qual é a melhor situação para aplicação Vimos também um exemplo de aplicação dessa metodologia para resolução de um problema de redes 2 Recursões Progressiva e Regressiva Nessa última etapa dessa aula estudamos o princípio das recursões progressivas e regressivas que nada mais é do que a confirmação de que podemos achar a mesma solução ótima indo do começo do problema para o final ou viceversa ARENALES M ARMENTANO V A MORABITO R YANASSE H H Pesquisa operacional Rio de Janeiro CampusElsevier 2015 Hillier FS e Lieberman GJ Introdução à Pesquisa Operacional 8ª edição São Paulo McGrawHill 2006 Lachtermacher G Pesquisa operacional na tomada de decisões 5ª edição São Paulo Prentice Hall 2016 NOGUEIRA F Dualidade 2010 16 slides Taha H A Pesquisa Operacional 8ª edição São Paulo Pearson 2008