Programacao Dinamica - Conceitos e Problemas de Otimizacao

CAPÍTULO 7 Programação Dinâmica Em momentos anteriores nessas notas problemas foram tratados por estratégias gulosa que operavam eficientemente Infelizmente para a maioria dos problemas a dificuldade não está em determinar qual critério guloso utilizar pois não há estratégia gulosa que conduza à solução ótima Para problemas como esses é importante usar outras estratégias A Divisão e Conquista pode servir como uma alternativa mas as versões conhecidas podem não ser suficientemente fortes para evitar uma busca de forçabruta KLEINBERG TARDOS 2005 Neste capítulo lidase com a Programação Dinâmica É fácil dizer o que é programação dinâmica depois de trabalhar com alguns exemplos A ideia básica vem de uma intuição a partir da divisão e conquista e é essencialmente o oposto de uma estratégia gulosa A Programação Dinâmica implica explorar o espaço de todas as soluções possíveis por cuidadosamente decompor o problema em subproblemas e então construir soluções corretas para problemas maiores e maiores Podese considerar que a Programação Dinâmica opera perigosamente próxima a algoritmos de forçabruta Apesar disso essa estratégia opera sobre um conjunto exponencialmente grande de subproblemas sem a necessidade de examinar todos eles explicitamente KLEINBERG TARDOS 2005 Na estratégia de Programação Dinâmica soluções ótimas de tamanho menor auxiliam na busca por uma solução ótima maior 1 Problemas de Otimização Neste capítulo lidase com problemas os quais buscam por uma solução chamada de solução ótima Esses problemas são chamados de problemas de otimização Uma solução ótima é uma resposta para o problema que obtém a melhor mínima ou máxima avaliação possível dada por uma função Essa função é denominada de função objetivo Um algoritmo para um problema de otimização sempre encontra a solução ótima Soluções que não são ótimas podem ou não satisfazer restrições relacionadas ao problema As soluções que satisfazem as restrições do problema mas não possuem a melhor avaliação possível pela função objetivo são chamadas de solução admissíveis nãoótimas Toda solução ótima é uma solução admissível 71 Organização de Intervalos com Pesos Anteriormente fora conhecido um problema de identificar o conjunto maximal de intervalos quando visitouse o conceito de algoritmos gulosos agora trabalhase com uma variação desse problema chamado de problema de Intervalos com Pesos Considere um conjunto de intervalos I I₁ I₂ Iₙ onde cada intervalo Iᵢ inicia no tempo si ℤ termina no tempo fi ℤ e possui o valor vi ℤ precisase encontrar o conjunto de intervalos que maximiza o valor de ᵢₛvi onde S é um subconjunto de intervalos sem sobreposição de tempo KLEINBERG TARDOS 2005 Supõese que o os intervalos estejam organizados em uma ordem crescente de tempos de fim F fI₁ fI₂ fIₙ Agora supõese a existência de uma função p I I pIᵢ determina o intervalo Iⱼ que é o primeiro intervalo compatível antes de Iᵢ na lista F Considere a solução ótima O Se Iₙ O não há intervalos compatíveis entre pIₙ e Iₙ Ainda considerando que Iₙ pertence a solução ótima considerase como potenciais candidatos a solução ótima I₁ I₂ pIₙ Caso Iₙ O devese considerar como potenciais candidatos a solução ótima I₁ I₂ Iₙ₁ Pensando na recorrência para a programação dinâmica considerase OPTIᵢ como 2 o valor da solução ótima para os intervalos I₁ I₂ Iᵢ Por questões de convenção assumese que OPTI₀ 0 A recorrência representando a solução ótima considerando o problema é dado por OPTIᵢ 0 para i 0 maxvIᵢ OPTpIᵢ OPTIᵢ₁ para i 0 71 Então se está assumindo que Iᵢ pertence a solução ótima sse vIᵢ OPTpIᵢ OPTIᵢ₁ Um algoritmo recursivo para resolver a recorrência pode ser visualizado abaixo Algoritmo 38 ARPIP Algoritmo Recursivo para o Problema de Intervalos com Peso Input um conjunto de itens I 12 n si ℤ fi ℤ vi ℤ o intervalo Iⱼ 1 if j 0 then 2 return 0 3 else 4 return maxvIⱼ ARPIPI s f v pIⱼ ARPIPI s f v Iⱼ₁ Teorema 711 O Algoritmo 38 calcula o valor e OPTIⱼ Prova Por definição OPTI₀ 0 linha 1 e 2 Para algum j 0 supõese por indução que o algoritmo calcula corretamente o valor OPTIᵢ para um i j Pela hipótese da indução sabese que o algoritmo encontra a solução para OPTIₚIⱼ e para OPTIⱼ₁ e por essa razão OPTIⱼ maxvIⱼ ARPIPI s f v pIⱼ ARPIPI s f v Iⱼ₁ ARPIPI s f v Iⱼ 72 Infelizmente ao executar o Algoritmo 38 percebese que a árvore de subproblemas cresce muito rapidamente o que impacta no tempo de execução nãopolinomial A árvore cresce rapidamente porque há recálculo de subproblemas A próxima tentativa irá utilizar uma memória para evitar tais recálculos KLEINBERG TARDOS 2005 Tal método é conhecido como Memoização CORMEN et al 2012 No novo algoritmo a memoização é implementada através de um vetor M indexado de 0 a n Assuma que Mi 1 para todo i 1 2 n O Algoritmo 39 exibe o pseudocódigo Algoritmo 39 AMIP Algoritmo Memoizado para Intervalos com Peso Input um conjunto de itens I 1 2 n si ℤ fi ℤ vi ℤ o intervalo Ij 1 if j 0 then 2 return 0 3 else 4 if Mj 1 then 5 Mj maxvIj AMIPI s f v pIj AMIPI s f v Ij1 6 return Mj Para encontrar a solução a partir do vetor M podese utilizar o Algoritmo 40 Algoritmo 40 AESPA Algoritmo para encontrar solução a partir de AMIP Input um conjunto de itens I 1 2 n si ℤ fi ℤ vi ℤ o intervalo Ij vetor M 1 if j 0 then 2 não gera saída 3 else 4 if vj MpIj Mlj1 then 5 dar saída Ij concatenada com o resultado de AESPAI s f v pIj M 6 else 7 dar saída o resultado de AESPAI s f v Ij1 M 8 return Mj 711 Complexidade A complexidade de tempo dos Algoritmo 39 e 40 é On 72 O Problema da Mochila Antes de começar a analisar o problema da mochila apresentase um problema mais simples que chamaremos aqui de Subconjunto de Somas O Subconjunto de Somas é um problema no qual dado um conjunto dos itens I 1 2 n uma função de peso w I ℤ e um limite de peso W ℤ desejase encontrar um subconjunto de S I com a maior soma sS ws tal que sS ws W KLEINBERG TARDOS 2005 Podese tentar resolver por programação dinâmica utilizando o OPTi para denotar o valor da solução ótima para a subsolução 1 2 n Desse modo considerando O a solução ótima se i O então OPTi OPTi 1 senão OPTi wi OPTi 1 O problema nessa tentativa está em que ao aceitar i não implica a rejeição de qualquer outro item Isso indica a necessidade de trabalhar com mais subproblemas A recorrência que funciona para o problema de Subconjunto de Somas utiliza a ideia de considerar o limite de peso W no qual se um item é adicionado a subsolução ele diminui seu peso ao valor de W Logo utilizase a seguinte recorrência OPTi p 0 para i 0 ou p 0 OPTi 1 p para p wi maxOPTi 1 p wi OPTi 1 p wi para p wi 73 na qual w é o valor corrente de peso restante a ser considerado para os subproblemas O Problema da Mochila ou Knapsack Problem é muito semelhante ao de Subconjunto de Somas Nele além do conjunto de itens I da função de peso w para cada item e do limite de peso W considerase que cada item tem um valor associado dado pela função v I ℝ Devese buscar o subconjunto S I no qual sS vs tal que sS ws W Podemos então utilizar uma função de recorrência muito semelhante à proposta para o problema do Subconjunto de Somas Segue a recorrência adaptada OPTi p 0 para i 0 ou p 0 OPTi 1 p para p wi maxOPTi 1 p vi OPTi 1 p wi para p wi 74 O Algoritmo 41 proposto pode ser visualizado abaixo já com a memorização Algoritmo 41 Algoritmo para o Problema da Mochila Input um conjunto de itens I 1 2 n uma função de pesos w I ℤ uma função de valor v I ℝ e um peso limite W ℤ Matriz de memorização 1 Criar matriz M ℝI1W1 2 M0 w 0 w 0 1 2 W 3 foreach i 1 2 n do 4 for w 0 to W do 5 if w wi then 6 Mi w Mi 1 w 7 else 8 Mi w maxMi 1 w vi Mi 1 w wi 9 return Mn W 721 Complexidade A complexidade do algoritmo de programação dinâmica proposto é de ΘIW ou seja não pode ser considerado resolvível em tempo polinomial Desafio Pense sobre o projeto de um algoritmo que encontre os itens presentes na solução ótima para o problema da mochila 73 Subsequentia Comum Mais Longa Um filamento de DNA consiste em uma cadeia de moléculas denominadas bases Dentre essas bases têmse Adenina A Guanina G Citosina C e Timina T Dois indivíduos podem ser considerados semelhantes se suas cadeias de DNA também o são Nesse contexto emerge a necessidade de comparar duas cadeias que compartilhem de uma terceira cadeia formada em uma mesma ordem mas não necessariamente na mesma sequência Chamase esse problema de Subsequentia Comum Mais Longa SCML ou Longest Common Subsequence CORMEN et al 2012 Considere que as cadeias X x1 x2 xm e Y y1 y2 yn procurase encontrar a subsequência mais longa Z z1 z2 zk Para compreender as propriedades o teorema a seguir assuma que dada uma cadeia W Wi w1 w2 wi é o prefixo de W até o iésimo símbolo A seguir há um importante teorema quanto a esse problema que define a subestrutura ótima Teorema 731 Sejam X x1 x2 xm e Y y1 y2 yn as sequências e Z z1 z2 zk uma subsequência mais longa de X e Y têmse 1 Se xm yn então zk xm yn e Zk1 uma subsequência mais longa de Xm1 e Yn1 2 Se xm yn então zk xm implica que Z é uma subcadeia mais longa de Xm1 e Y 3 Se xm yn então zk yn implica que Z é uma subcadeia mais longa de X e Yn1 Prova Para o item 1 se zk xm então podemos anexar a xm yn a Z para obter a subsequência comum mais longa de comprimento k1 contradizendo de que Z é uma subsequência comum mais longa Desse modo devese ter zk xm yn O prefixo Zk1 é uma subsequência comum de comprimento k 1 de Xm1 e Yn1 Desejase mostrar que ela é uma subsequência comum mais longa Supõese por contradição que há uma sequência comum W de Xm1 e Yn1 com comprimento maior que k 1 Então anexar xm yn a W produz uma subsequência máxima de X e Y cujo o comprimento é maior que k o que é uma contradição Para o item 2 se zk xm então Z é a subsequência comum de Xm1 e Y Se existisse uma subsequência comum W de Xm1 e Y com comprimento maior que k então W seria também uma subsequência comum de Xm e Y contradizendo a suposição de que Z é uma subsequência comum mais longa Para o item 3 a prova é simétrica à explicação ao item 2 Segue a recorrência da subsequência mais longa considerando as cadeias X x1 x2 e Y y1 y2 OPTm n 0 para m 0 ou n 0 OPTm 1 n 1 1 quando xm yn max OPTm 1 n OPTm n 1 quando xm yn 75 Algoritmo 42 Algoritmo para encontrar o comprimento da Subsequentia Comum Mais Longa Input duas palavras X x1 x2 xm e Y y1 y2 yn 1 Criar matriz M Zm1n1 2 Criar matriz B mn 3 for i 0 to m do 4 Mi0 0 5 for j 0 to n do 6 M0j 0 7 for i 1 to m do 8 for j 1 to n do 9 if xi yj then 10 Mi j Mi 1 j 1 1 11 Bi j 12 else 13 if Mi 1 j Mi j 1 then 14 Mi j Mi 1 j 15 Bi j 16 else 17 Mi j Mi j 1 18 Bi j 19 return M B 731 Complexidade A complexidade de tempo computacional para se determinar a subsequência comum mais longa é de ΘXY devido a dominância assintótica da complexidade do Algoritmo 43 Algoritmo 43 SCMLalg Algoritmo para encontrar a Subsequência Comum Mais Longa Input duas palavras X x₁ x₂ xₘ e Y y₁ y₂ yₙ as matrizes M e B geradas no Algoritmo 42 os inteiros i e j correspondentes aos índices de X e Y analisados na chamada atual uma String result 1 if i 0 j 0 then 2 return 3 if Bi j then 4 SCMLalgX Y i 1 j 1 result 5 result result xᵢ 6 else 7 if Bi j then 8 SCMLalgX Y i 1 j result 9 else 10 SCMLalgX Y i j 1 result 74 Multiplicação de Cadeias de Matrizes O problema de Multiplicação de Cadeias de Matrizes busca determinar quais matrizes multiplicar primeiro para reduzir o número de operações em uma multiplicação A multiplicação de matrizes é uma operação binária que demanda Θnml para multiplicar as matrizes Aₙₓₘ e Bₘₓₗ Dada um conjunto de matrizes A₁A₂ Aⱼ arranjadas respeitando os requisitos de linha e coluna necessários para que ocorra a multiplicação desejase saber qual a ordem de multiplicações tal que o número de operações seja o mínimo possível Considere Aᵢⱼ como a matriz resultante da multiplicação entre as matrizes da sequência Aᵢ Aᵢ₁ Aⱼ Considere também p₀ p₁ pⱼ os valores de linha e coluna tal que Aᵢ tenha pᵢ₁ linhas e pᵢ colunas A recorrência para encontrar o valor ótimo de número de operações pode ser visualizada abaixo OPTi j 0 se ij minikjOPTi k OPTk 1 j pᵢ₁pₖpⱼ 76 onde OPTi j representa o valor mínimo de operações para realizar a multiplicação das matrizes Aᵢ Aᵢ₁ Aⱼ O Algoritmo 44 descreve a resolução do problema A matriz M realiza a memorizaçāo dos valores e S possui dados necessários para construir a solução O Algoritmo 45 exibe como construir a solução Algoritmo 44 Encontra ordem de multiplicação das matriz Input o conjunto p 1 Criar tabela Mₙₓₙ 2 Criar tabela Sₙₓₙ 3 for i 1 to n do 4 Mi i 0 5 for l 2 to n do 6 for i 1 to n l 1 do 7 j i l 1 8 Mi j 9 for k i to j 1 do 10 q Mi k Mk 1 j pᵢ₁pₖpⱼ 11 if q Mi j then 12 Mi j q 13 Si j k Algoritmo 45 PRINTOPTIMALPARENS Input a matriz s os inteiros i e j 1 if i j then 2 print A 3 else 4 print 5 PRINTOPTIMALPARENSS i Si j 6 PRINTOPTIMALPARENSS Si j 1 j 7 print