Programaçao dinamica

Da Wikipédia, a enciclopédia livre
Ir para a navegação Saltar para pesquisar
Figura 1. Encontrando o caminho mais curto em um grafo usando a subestrutura ótima; uma linha reta indica uma única aresta; uma linha ondulada indica um caminho mais curto entre os dois vértices que conecta (entre outros caminhos, não mostrados, compartilhando os mesmos dois vértices); a linha em negrito é o caminho geral mais curto do início ao objetivo.

A programação dinâmica é um método de otimização matemática e um método de programação de computador. O método foi desenvolvido por Richard Bellman na década de 1950 e encontrou aplicações em vários campos, da engenharia aeroespacial à economia .

Em ambos os contextos, refere-se à simplificação de um problema complicado, dividindo-o em subproblemas mais simples de maneira recursiva . Embora alguns problemas de decisão não possam ser separados dessa maneira, as decisões que abrangem vários pontos no tempo geralmente se separam recursivamente. Da mesma forma, na ciência da computação, se um problema pode ser resolvido de forma ótima dividindo-o em subproblemas e, em seguida, encontrando recursivamente as soluções ótimas para os subproblemas, diz-se que ele tem subestrutura ótima .

Se os subproblemas podem ser aninhados recursivamente dentro de problemas maiores, de modo que os métodos de programação dinâmica sejam aplicáveis, então existe uma relação entre o valor do problema maior e os valores dos subproblemas. [1] Na literatura de otimização esta relação é chamada de equação de Bellman .

Visão geral

Otimização matemática

Em termos de otimização matemática, a programação dinâmica geralmente se refere à simplificação de uma decisão, dividindo-a em uma sequência de etapas de decisão ao longo do tempo. Isso é feito definindo uma seqüência de funções de valor V 1 , V 2 , ..., V n tomando y como um argumento que representa o estado do sistema nos momentos i de 1 a n . A definição de V n ( y ) é o valor obtido no estado y na última vez n . Os valores V i em tempos anteriores i =  n  −1,  n  − 2, ..., 2, 1 pode ser encontrado trabalhando para trás, usando uma relação recursiva chamada equação de Bellman . Para i  = 2, ...,  n , V i −1 em qualquer estado y é calculado a partir de V i maximizando uma função simples (geralmente a soma) do ganho de uma decisão no tempo i  − 1 e a função V i no novo estado do sistema se esta decisão for tomada. Como V i já foi calculado para os estados necessários, a operação acima produz V i−1 para esses estados. Finalmente, V 1 no estado inicial do sistema é o valor da solução ótima. Os valores ótimos das variáveis ​​de decisão podem ser recuperados, um a um, rastreando os cálculos já realizados.

Teoria de controle

Na teoria de controle , um problema típico é encontrar um controle admissível.que faz com que o sistemaseguir uma trajetória admissívelem um intervalo de tempo contínuoque minimiza uma função de custo

A solução para este problema é uma lei ou política de controle ótimo, que produz uma trajetória ótimae uma função de custo para ir . Este último obedece à equação fundamental da programação dinâmica:

uma equação diferencial parcial conhecida como equação de Hamilton-Jacobi-Bellman , na quale. Acha-se que minimizarem termos de,, e a função desconhecidae então substitui o resultado na equação de Hamilton-Jacobi-Bellman para obter a equação diferencial parcial a ser resolvida com condição de contorno. [2] Na prática, isso geralmente requer técnicas numéricas para alguma aproximação discreta da relação de otimização exata.

Alternativamente, o processo contínuo pode ser aproximado por um sistema discreto, o que leva a uma seguinte relação de recorrência análoga à equação de Hamilton-Jacobi-Bellman:

no-ª etapa deintervalos de tempo discretos igualmente espaçados, e ondeedenotar aproximações discretas parae. Esta equação funcional é conhecida como equação de Bellman , que pode ser resolvida para uma solução exata da aproximação discreta da equação de otimização. [3]

Exemplo da economia: o problema de economia ótima de Ramsey

Em economia, o objetivo geralmente é maximizar (em vez de minimizar) alguma função dinâmica de bem-estar social . No problema de Ramsey, essa função relaciona quantidades de consumo a níveis de utilidade . Falando livremente, o planejador enfrenta o trade-off entre consumo contemporâneo e consumo futuro (via investimento em estoque de capital que é usado na produção), conhecido como escolha intertemporal . O consumo futuro é descontado a uma taxa constante. Uma aproximação discreta para a equação de transição do capital é dada por

Ondeé o consumo,é capital eé uma função de produção que satisfaz as condições de Inada . Um estoque de capital inicialé assumido.

Deixarseja consumo no período t , e suponha que o consumo produz utilidade enquanto o consumidor viver. Suponha que o consumidor esteja impaciente, de modo que desconta a utilidade futura por um fator b a cada período, onde. Deixarser capital no período t . Suponha que o capital inicial seja um determinado valor, e suponha que o capital e o consumo deste período determinem o capital do próximo período como, onde A é uma constante positiva e. Suponha que o capital não pode ser negativo. Então o problema de decisão do consumidor pode ser escrito da seguinte forma:

sujeito apara todos

Escrito desta forma, o problema parece complicado, porque envolve a solução para todas as variáveis ​​de escolha. (O capitalnão é uma variável de escolha – o capital inicial do consumidor é dado como dado.)

A abordagem de programação dinâmica para resolver esse problema envolve dividi-lo em uma sequência de decisões menores. Para isso, definimos uma sequência de funções de valor , paraque representam o valor de ter qualquer quantidade de capital k em cada momento t . Não há (por suposição) nenhuma utilidade em ter capital após a morte,.

O valor de qualquer quantidade de capital em qualquer momento anterior pode ser calculado por indução reversa usando a equação de Bellman . Neste problema, para cada, a equação de Bellman é

sujeito a

Este problema é muito mais simples do que o que escrevemos antes, porque envolve apenas duas variáveis ​​de decisão,e. Intuitivamente, em vez de escolher todo o seu plano de vida ao nascer, o consumidor pode dar um passo de cada vez. No instante t , seu capital atualé dado, e ele só precisa escolher o consumo atuale salvando.

Para realmente resolver esse problema, trabalhamos de trás para frente. Por simplicidade, o nível atual de capital é denotado como k .já é conhecido, então usando a equação de Bellman uma vez que podemos calcular, e assim sucessivamente até chegarmos a, que é o valor do problema de decisão inicial para todo o tempo de vida. Em outras palavras, uma vez que sabemos, podemos calcular, que é o máximo de, Ondeé a variável de escolha e.

Trabalhando para trás, pode-se mostrar que a função de valor no tempoé

onde cadaé uma constante, e a quantidade ideal para consumir no momentoé

que pode ser simplificado para

Vemos que é ótimo consumir uma fração maior da riqueza atual à medida que se envelhece, consumindo finalmente toda a riqueza restante no período T , o último período da vida.

Programação de computadores

Existem dois atributos principais que um problema deve ter para que a programação dinâmica seja aplicável: subestrutura ótima e subproblemas sobrepostos . Se um problema pode ser resolvido combinando soluções ótimas para subproblemas não sobrepostos , a estratégia é chamada de " dividir e conquistar ". [1] É por isso que merge sort e quick sort não são classificados como problemas de programação dinâmica.

Subestrutura ótima significa que a solução para um dado problema de otimização pode ser obtida pela combinação de soluções ótimas para seus subproblemas. Tais subestruturas ótimas são geralmente descritas por meio de recursão . Por exemplo, dado um grafo G=(V,E) , o caminho mais curto p de um vértice u para um vértice v exibe uma subestrutura ótima: pegue qualquer vértice intermediário w neste caminho mais curto p . Se p é realmente o caminho mais curto, então ele pode ser dividido em subcaminhos p 1 de u para w e p 2 dew para v tais que estes, por sua vez, são de fato os caminhos mais curtos entre os vértices correspondentes (pelo simples argumento recortar e colar descrito em Introdução aos Algoritmos ). Assim, pode-se facilmente formular a solução para encontrar caminhos mais curtos de maneira recursiva, que é o que o algoritmo de Bellman-Ford ou o algoritmo de Floyd-Warshall faz.

A sobreposição de subproblemas significa que o espaço de subproblemas deve ser pequeno, ou seja, qualquer algoritmo recursivo que resolva o problema deve resolver os mesmos subproblemas repetidamente, em vez de gerar novos subproblemas. Por exemplo, considere a formulação recursiva para gerar a série de Fibonacci: F i = F i −1 + F i −2 , com caso base F 1  =  F 2  = 1. Então F 43F 42  +  F 41 e F 42F 41  +  F40 . Agora F 41 está sendo resolvido nas subárvores recursivas tanto de F 43 quanto de F 42 . Mesmo que o número total de subproblemas seja realmente pequeno (apenas 43 deles), acabamos resolvendo os mesmos problemas repetidamente se adotarmos uma solução recursiva ingênua como essa. A programação dinâmica leva em conta este fato e resolve cada subproblema apenas uma vez.

Figura 2. O gráfico do subproblema para a sequência de Fibonacci. O fato de não ser uma árvore indica subproblemas sobrepostos.

Isso pode ser alcançado de duas maneiras: [ citação necessária ]

  • Abordagem de cima para baixo : Esta é a queda direta da formulação recursiva de qualquer problema. Se a solução para qualquer problema pode ser formulada recursivamente usando a solução para seus subproblemas, e se seus subproblemas estão sobrepostos, então pode-se facilmente memorizar ou armazenar as soluções para os subproblemas em uma tabela. Sempre que tentamos resolver um novo subproblema, primeiro verificamos a tabela para ver se ele já foi resolvido. Se uma solução foi registrada, podemos usá-la diretamente, caso contrário, resolvemos o subproblema e adicionamos sua solução à tabela.
  • Abordagem de baixo para cima : uma vez que formulamos a solução para um problema recursivamente em termos de seus subproblemas, podemos tentar reformular o problema de maneira bottom-up: tente resolver os subproblemas primeiro e use suas soluções para construir e chegar a soluções para subproblemas maiores. Isso também geralmente é feito em forma de tabela, gerando iterativamente soluções para subproblemas cada vez maiores usando as soluções para pequenos subproblemas. Por exemplo, se já conhecemos os valores de F 41 e F 40 , podemos calcular diretamente o valor de F 42 .

Algumas linguagens de programação podem memorizar automaticamente o resultado de uma chamada de função com um conjunto específico de argumentos, a fim de acelerar a avaliação de chamada por nome (esse mecanismo é chamado de chamada por necessidade ). Algumas linguagens possibilitam a portabilidade (por exemplo , Scheme , Common Lisp , Perl ou D ). Algumas linguagens possuem memoização automática incorporada, como o tabled Prolog e J , que suporta memoização com o advérbio M .. [4] Em qualquer caso, isso só é possível para um referencialmente transparentefunção. A memoização também é encontrada como um padrão de design facilmente acessível em linguagens baseadas em reescrita de termos, como Wolfram Language .

Bioinformática

A programação dinâmica é amplamente utilizada em bioinformática para tarefas como alinhamento de sequências , dobramento de proteínas , previsão de estrutura de RNA e ligação proteína-DNA. Os primeiros algoritmos de programação dinâmica para ligação proteína-DNA foram desenvolvidos na década de 1970 independentemente por Charles DeLisi nos EUA [5] e Georgii Gurskii e Alexander Zasedatelev na URSS. [6] Recentemente, esses algoritmos tornaram-se muito populares em bioinformática e biologia computacional , particularmente nos estudos de posicionamento de nucleossomos e ligação de fatores de transcrição .

Exemplos: algoritmos de computador

Algoritmo de Dijkstra para o problema do caminho mais curto

Do ponto de vista da programação dinâmica, o algoritmo de Dijkstra para o problema do caminho mais curto é um esquema de aproximação sucessiva que resolve a equação funcional de programação dinâmica para o problema do caminho mais curto pelo método Reaching . [7] [8] [9]

Na verdade, a explicação de Dijkstra da lógica por trás do algoritmo, [10] ou seja ,

Problema 2. Encontre o caminho de comprimento total mínimo entre dois nós dadose.

Usamos o fato de que, seé um nó no caminho mínimo depara, o conhecimento deste último implica o conhecimento do caminho mínimo depara.

é uma paráfrase do famoso Princípio da Otimalidade de Bellman no contexto do problema do caminho mais curto .

Sequência de Fibonacci

O uso de programação dinâmica no cálculo do enésimo membro da sequência de Fibonacci melhora muito seu desempenho. Aqui está uma implementação ingênua, baseada diretamente na definição matemática:

função fib(n)
     se n <= 1 return n
     return fib(n − 1) + fib(n − 2)

Observe que se chamarmos, digamos, fib(5), produzimos uma árvore de chamadas que chama a função no mesmo valor muitas vezes diferentes:

  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Em particular, fib(2)foi calculado três vezes a partir do zero. Em exemplos maiores, muitos outros valores de fib, ou subproblemas , são recalculados, levando a um algoritmo de tempo exponencial.

Agora, suponha que temos um objeto map simples, m , que mapeia cada valor de fibque já foi calculado para seu resultado e modificamos nossa função para usá-lo e atualizá-lo. A função resultante requer apenas tempo O ( n ) em vez de tempo exponencial (mas requer espaço O ( n )):

var m := map (0 → 0, 1 → 1)
 função fib(n)
     se a chave n não estiver no mapa m
        m[n] := fib(n − 1) + fib(n − 2)
    retornar m[n]

Essa técnica de salvar valores que já foram calculados é chamada de memorização ; essa é a abordagem de cima para baixo, pois primeiro dividimos o problema em subproblemas e depois calculamos e armazenamos valores.

Na abordagem de baixo para cima , calculamos os valores menores de fibprimeiro e, em seguida, construímos valores maiores a partir deles. Este método também usa tempo O( n ) pois contém um loop que se repete n − 1 vezes, mas só ocupa espaço constante (O(1)), em contraste com a abordagem top-down que requer espaço O( n ) para armazenar o mapa.

function fib(n)
     if n = 0
         return 0
     else 
        var previousFib := 0, currentFib := 1
         repeat n − 1 times  // loop é ignorado se n = 1 
            var newFib := previousFib + currentFib
            anteriorFib := currentFib
            currentFib := newFib
        return currentFib

Em ambos os exemplos, calculamos apenas fib(2)uma vez e, em seguida, usamos para calcular ambos fib(4)e fib(3), em vez de computar sempre que um deles é avaliado.

O método acima realmente levatempo para n grande porque a adição de dois inteiros combits cada um levaTempo. (O enésimo número de fibonacci tembits.) Além disso, há uma forma fechada para a sequência de Fibonacci, conhecida como fórmula de Binet , da qual o-th termo pode ser calculado em aproximadamentetempo, que é mais eficiente do que a técnica de programação dinâmica acima. No entanto, a recorrência simples fornece diretamente a forma de matriz que leva a uma aproximadamentealgoritmo por exponenciação matricial rápida .

Um tipo de matriz 0–1 balanceada

Considere o problema de atribuir valores, seja zero ou um, às posições de uma matriz n × n, com n par , de modo que cada linha e cada coluna contenha exatamente n / 2 zeros e n / 2 uns. Perguntamos quantas atribuições diferentes existem para um determinado. Por exemplo, quando n = 4 , cinco soluções possíveis são

Existem pelo menos três abordagens possíveis: força bruta , retrocesso e programação dinâmica.

A força bruta consiste em verificar todas as atribuições de zeros e uns e contar aquelas que possuem linhas e colunas balanceadas ( n /2 zeros e n /2 uns). Como existempossíveis atribuições eatribuições sensatas, esta estratégia não é prática, exceto talvez até.

O retrocesso para este problema consiste em escolher alguma ordem dos elementos da matriz e colocar recursivamente uns ou zeros, enquanto verifica se em cada linha e coluna o número de elementos que não foram atribuídos mais o número de uns ou zeros são pelo menos n / 2 . Embora mais sofisticada que a força bruta, essa abordagem visitará cada solução uma vez, tornando-a impraticável para n maior que seis, pois o número de soluções já é 116.963.796.250 para n  = 8, como veremos.

A programação dinâmica permite contar o número de soluções sem visitar todas. Imagine valores retroativos para a primeira linha – quais informações precisaríamos sobre as linhas restantes para poder contar com precisão as soluções obtidas para cada valor da primeira linha? Consideramos k × n placas, onde 1 ≤ kn , cujaas linhas contêmzeros euns. A função f à qual a memoização é aplicada mapeia vetores de n pares de inteiros para o número de placas admissíveis (soluções). Há um par para cada coluna, e seus dois componentes indicam respectivamente o número de zeros e uns que ainda não foram colocados naquela coluna. Buscamos o valor de(argumentos ou um vetor deelementos). O processo de criação de subproblemas envolve iterar sobre cada um dos possíveis atribuições para a linha superior do quadro e passando por cada coluna, subtraindo um do elemento apropriado do par para essa coluna, dependendo se a atribuição para a linha superior continha um zero ou um nessa posição. Se qualquer um dos resultados for negativo, a atribuição é inválida e não contribui para o conjunto de soluções (a recursão pára). Caso contrário, temos uma atribuição para a linha superior do quadro k × n e computamos recursivamente o número de soluções para o quadro restante ( k − 1) × n , somando o número de soluções para cada atribuição admissível da linha superior e retornando a soma, que está sendo memorizada. O caso base é o subproblema trivial, que ocorre para um1 × n placa. O número de soluções para esta placa é zero ou um, dependendo se o vetor é uma permutação de n / 2 e n /2 pares ou não.

Por exemplo, nas duas primeiras placas mostradas acima as sequências de vetores seriam

((2, 2) (2, 2) (2, 2) (2, 2)) ((2, 2) (2, 2) (2, 2) (2, 2)) k = 4
  0 1 0 1 0 0 1 1

((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) k = 3
  1 0 1 0 0 0 1 1

((1, 1) (1, 1) (1, 1) (1, 1)) ((0, 2) (0, 2) (2, 0) (2, 0)) k = 2
  0 1 0 1 1 1 0 0

((0, 1) (1, 0) (0, 1) (1, 0)) ((0, 1) (0, 1) (1, 0) (1, 0)) k = 1
  1 0 1 0 1 1 0 0

((0, 0) (0, 0) (0, 0) (0, 0)) ((0, 0) (0, 0), (0, 0) (0, 0))

O número de soluções (sequência A058527 no OEIS ) é

Links para a implementação MAPLE da abordagem de programação dinâmica podem ser encontrados entre os links externos .

Tabuleiro de damas

Considere um tabuleiro de xadrez com n × n quadrados e uma função de custo c(i, j)que retorna um custo associado ao quadrado (i,j)( isendo a linha, jsendo a coluna). Por exemplo (em um tabuleiro de xadrez 5 × 5),

5 6 7 4 7 8
4 7 6 1 1 4
3 3 5 7 8 2
2 6 7 0
1 *5*
1 2 3 4 5

portantoc(1, 3) = 5

Digamos que houvesse um verificador que pudesse começar em qualquer quadrado da primeira fileira (ou seja, linha) e você quisesse saber o caminho mais curto (a soma dos custos mínimos em cada fileira visitada) para chegar à última fileira; assumindo que o verificador poderia mover-se apenas diagonalmente para a esquerda, diagonalmente para a direita ou para a frente. Ou seja, um verificador em (1,3)pode mover para (2,2), (2,3)ou (2,4).

5
4
3
2 x x x
1 o
1 2 3 4 5

Este problema apresenta uma subestrutura ótima . Ou seja, a solução para todo o problema depende de soluções para subproblemas. Vamos definir uma função q(i, j)como

q ( ​​i , j ) = o custo mínimo para atingir o quadrado ( i , j ).

Começando em rank ne descendo até rank 1, calculamos o valor desta função para todos os quadrados em cada rank sucessivo. Escolher o quadrado que contém o valor mínimo em cada posto nos dá o caminho mais curto entre posto ne posto 1.

A função q(i, j)é igual ao custo mínimo para chegar a qualquer um dos três quadrados abaixo dele (já que esses são os únicos quadrados que podem alcançá-lo) mais c(i, j). Por exemplo:

5
4 UMA
3 B C D
2
1
1 2 3 4 5

Agora, vamos definir q(i, j)em termos um pouco mais gerais:

A primeira linha desta equação trata de um tabuleiro modelado como quadrados indexados no 1limite mais baixo e nno limite mais alto. A segunda linha especifica o que acontece na primeira fila; fornecendo um caso base. A terceira linha, a recursão, é a parte importante. Ele representa os A,B,C,Dtermos no exemplo. A partir dessa definição, podemos derivar um código recursivo direto para q(i, j). No pseudocódigo a seguir, né o tamanho da placa, c(i, j)é a função de custo e min()retorna o mínimo de um número de valores:

função minCost(i, j)
     se j < 1 ou j > n
         retorna infinito
     senão se i = 1
         retorna c(i, j)
     else 
        retorna  min ( minCost(i-1, j-1), minCost(i-1, j), Custo mín(i-1, j+1) ) + c(i, j)

Esta função calcula apenas o custo do caminho, não o caminho real. Discutimos o caminho real abaixo. Isso, como o exemplo dos números de Fibonacci, é terrivelmente lento porque também exibe o atributo de subproblemas sobrepostos . Ou seja, ele recalcula os mesmos custos de caminho repetidamente. No entanto, podemos computá-lo muito mais rápido de forma ascendente se armazenarmos os custos de caminho em uma matriz bidimensional q[i, j]em vez de usar uma função. Isso evita recomputação; todos os valores necessários para array q[i, j]são calculados antecipadamente apenas uma vez. Os valores pré-calculados para (i,j)são simplesmente consultados sempre que necessário.

Também precisamos saber qual é o caminho mais curto real. Para fazer isso, usamos outro array p[i, j]; uma matriz predecessora . Esta matriz registra o caminho para qualquer quadrado s. O predecessor de sé modelado como um deslocamento relativo ao índice (em q[i, j]) do custo de caminho pré-calculado de s. Para reconstruir o caminho completo, procuramos o antecessor de s, depois o antecessor desse quadrado, depois o antecessor desse quadrado e assim por diante recursivamente, até chegarmos ao quadrado inicial. Considere o seguinte código:

função computeShortestPathArrays()
     para x de 1 a n
        q[1, x] := c(1, x)
    para y de 1 a n
        q[y, 0] := infinito
        q[y, n + 1] := infinito
    para y de 2 a n
         para x de 1 a n
            m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
            q[y, x] := m + c(y, x)
            se m = q[y-1, x-1]
                p[y, x] := -1
            senão se m = q[y-1, x]
                p[y, x] := 0
            outro
                p[y, x] := 1

Agora o resto é uma simples questão de encontrar o mínimo e imprimi-lo.

função computaShortestPath()
    computeShortestPathArrays()
    minÍndice := 1
    min := q[n, 1]
    para i de 2 a n
         se q[n, i] < min
            minIndex := i
            min := q[n,i]
    printPath(n, minIndex)
function printPath(y, x)
     print (x)
     print ("<-")
     if y = 2
         print (x + p[y, x])
     else
        printPath(y-1, x + p[y, x])

Alinhamento de sequência

Em genética , o alinhamento de sequências é uma aplicação importante onde a programação dinâmica é essencial. [11] Normalmente, o problema consiste em transformar uma sequência em outra usando operações de edição que substituem, inserem ou removem um elemento. Cada operação tem um custo associado e o objetivo é encontrar a sequência de edições com o menor custo total .

O problema pode ser declarado naturalmente como uma recursão, uma sequência A é editada de forma otimizada em uma sequência B por:

  1. inserindo o primeiro caractere de B e realizando um alinhamento ideal de A e a cauda de B
  2. excluindo o primeiro caractere de A e realizando o alinhamento ideal da cauda de A e B
  3. substituindo o primeiro caractere de A pelo primeiro caractere de B e realizando alinhamentos ideais das caudas de A e B.

Os alinhamentos parciais podem ser tabulados em uma matriz, onde a célula (i,j) contém o custo do alinhamento ótimo de A[1..i] a B[1..j]. O custo na célula (i,j) pode ser calculado adicionando o custo das operações relevantes ao custo de suas células vizinhas e selecionando o ótimo.

Existem diferentes variantes, veja algoritmo Smith-Waterman e algoritmo Needleman-Wunsch .

Quebra- cabeça Torre de Hanói

Um conjunto de modelos das Torres de Hanói (com 8 discos)
Uma solução animada do quebra-cabeça da Torre de Hanói para T(4,3) .

A Torre de Hanói ou Torres de Hanói é um jogo matemático ou quebra -cabeça . Consiste em três hastes e vários discos de tamanhos diferentes que podem deslizar em qualquer haste. O quebra-cabeça começa com os discos em uma pilha ordenada em ordem crescente de tamanho em uma haste, a menor no topo, formando assim uma forma cônica.

O objetivo do quebra-cabeça é mover toda a pilha para outra haste, obedecendo as seguintes regras:

  • Apenas um disco pode ser movido por vez.
  • Cada movimento consiste em pegar o disco superior de uma das hastes e deslizá-lo sobre outra haste, em cima dos outros discos que já podem estar presentes naquela haste.
  • Nenhum disco pode ser colocado em cima de um disco menor.

A solução de programação dinâmica consiste em resolver a equação funcional

S(n,h,t) = S(n-1,h, not(h,t)); S(1,h,t); S(n-1,not(h,t),t)

onde n denota o número de discos a serem movidos, h denota a haste inicial, t denota a haste alvo, not(h,t) denota a terceira haste (nem h nem t), ";" denota concatenação, e

S(n, h, t) := solução de um problema que consiste em n discos que devem ser movidos da haste h para a haste t.

Para n=1 o problema é trivial, ou seja, S(1,h,t) = "mova um disco da haste h para a haste t" (só resta um disco).

O número de movimentos requeridos por esta solução é 2 n  − 1. Se o objetivo é maximizar o número de movimentos (sem ciclagem) então a equação funcional de programação dinâmica é um pouco mais complicada e 3 n  − 1 movimentos são necessários. [12]

Quebra- cabeça de queda de ovo

A seguir, uma descrição da instância desse famoso quebra -cabeça envolvendo N=2 ovos e um prédio com H=36 andares: [13]

Suponha que desejamos saber de quais andares em um prédio de 36 andares é seguro jogar ovos e quais farão com que os ovos se quebrem ao pousar (usando a terminologia do inglês americano , em que o primeiro andar fica no nível do solo). Fazemos algumas suposições:
  • Um ovo que sobrevive a uma queda pode ser usado novamente.
  • Um ovo quebrado deve ser descartado.
  • O efeito de uma queda é o mesmo para todos os ovos.
  • Se um ovo quebrar ao cair, ele quebrará se cair de uma janela mais alta.
  • Se um ovo sobrevive a uma queda, então sobreviveria a uma queda mais curta.
  • Não está descartado que as janelas do primeiro andar quebrem os ovos, nem que os ovos possam sobreviver às janelas do 36º andar.
Se apenas um ovo estiver disponível e quisermos ter certeza de obter o resultado correto, o experimento pode ser realizado apenas de uma maneira. Solte o ovo da janela do primeiro andar; se sobreviver, solte-o da janela do segundo andar. Continue subindo até quebrar. Na pior das hipóteses, este método pode exigir 36 excrementos. Suponha que 2 ovos estejam disponíveis. Qual é o menor número de excrementos de ovos que funciona em todos os casos?

Para derivar uma equação funcional de programação dinâmica para este quebra-cabeça, seja o estado do modelo de programação dinâmica um par s = (n,k), onde

n = número de ovos de teste disponíveis, n = 0, 1, 2, 3, ..., N  − 1.
k = número de andares (consecutivos) ainda a serem testados, k = 0, 1, 2, ..., H  − 1.

Por exemplo, s = (2,6) indica que dois ovos de teste estão disponíveis e 6 andares (consecutivos) ainda não foram testados. O estado inicial do processo é s = ( N , H ) onde N denota o número de ovos de teste disponíveis no início do experimento. O processo termina quando não há mais ovos de teste ( n = 0) ou quando k = 0, o que ocorrer primeiro. Se a terminação ocorrer no estado s = (0, k ) ek  > 0, o teste falhou.

Agora deixe

W ( n , k ) = número mínimo de tentativas necessárias para identificar o valor do piso crítico no pior cenário dado que o processo está no estado s = ( n , k ).

Então pode-se mostrar que [14]

W ( n , k ) = 1 + min{max( W ( n − 1, x − 1), W ( n , kx )): x = 1, 2, ..., k }

com W ( n ,0 ) = 0 para todo n  > 0 e W (1, k ) = k para todo  k . É fácil resolver essa equação iterativamente aumentando sistematicamente os valores de nk .

Solução de DP mais rápida usando uma parametrização diferente

Observe que a solução acima levatempo com uma solução DP. Isso pode ser melhorado paratempo por busca binária no ótimona recorrência acima, uma vez queestá aumentando emenquantoestá diminuindo em, portanto, um mínimo local deé um mínimo global. Além disso, armazenando o valor idealpara cada célula na tabela DP e referindo-se ao seu valor para a célula anterior, o valor idealpara cada célula pode ser encontrado em tempo constante, melhorando-o paraTempo. No entanto, existe uma solução ainda mais rápida que envolve uma parametrização diferente do problema:

Deixarser o número total de andares tal que os ovos quebram quando caem doº andar (O exemplo acima é equivalente a tomar).

Deixarser o piso mínimo do qual o ovo deve cair para ser quebrado.

Deixarser o número máximo de valores deque são distinguíveis usandotenta eovos.

Entãopara todos.

Deixarser o piso de onde o primeiro ovo é descartado na estratégia ótima.

Se o primeiro ovo quebrou,é deparae distinguível usando no máximotenta eovos.

Se o primeiro ovo não quebrou,é deparae distinguível usandotenta eovos.

Portanto,.

Então o problema é equivalente a encontrar o mínimode tal modo que.

Para isso, poderíamos calcularpara aumentar, o que levariaTempo.

Assim, se tratarmos separadamente o caso de, o algoritmo levariaTempo.

Mas a relação de recorrência pode de fato ser resolvida, dando, que pode ser calculado emtempo usando a identidadepara todos.

Desdepara todos, podemos pesquisar binários emencontrar, dando umalgoritmo. [15]

Multiplicação em cadeia de matrizes

A multiplicação em cadeia de matrizes é um exemplo bem conhecido que demonstra a utilidade da programação dinâmica. Por exemplo, as aplicações de engenharia geralmente precisam multiplicar uma cadeia de matrizes. Não é surpreendente encontrar matrizes de grandes dimensões, por exemplo 100×100. Portanto, nossa tarefa é multiplicar matrizes. A multiplicação de matrizes não é comutativa, mas associativa; e podemos multiplicar apenas duas matrizes de cada vez. Então, podemos multiplicar essa cadeia de matrizes de muitas maneiras diferentes, por exemplo:

((A 1 × A 2 ) × A 3 ) × ... A n
A 1 ×(((A 2 ×A 3 )× ... ) × A n )
(A 1 × A 2 ) × (A 3 × ... A n )

e assim por diante. Existem inúmeras maneiras de multiplicar essa cadeia de matrizes. Todos eles produzirão o mesmo resultado final, mas levarão mais ou menos tempo para serem computados, com base em quais matrizes específicas são multiplicadas. Se a matriz A tiver dimensões m×n e a matriz B tiver dimensões n×q, então a matriz C=A×B terá dimensões m×q e exigirá multiplicações escalares m*n*q (usando um algoritmo simplista de multiplicação de matrizes para fins de ilustração).

Por exemplo, vamos multiplicar as matrizes A, B e C. Vamos supor que suas dimensões sejam m×n, n×p, ep×s, respectivamente. A matriz A×B×C será de tamanho m×s e pode ser calculada de duas maneiras mostradas abaixo:

  1. Ax(B×C) Esta ordem de multiplicação de matrizes exigirá multiplicações escalares nps + mns.
  2. (A×B)×C Esta ordem de multiplicação de matrizes exigirá cálculos escalares mnp + mps.

Vamos supor que m = 10, n = 100, p = 10 es = 1.000. Assim, a primeira maneira de multiplicar a cadeia exigirá 1.000.000 + 1.000.000 cálculos. A segunda maneira exigirá apenas 10.000+100.000 cálculos. Obviamente, a segunda maneira é mais rápida, e devemos multiplicar as matrizes usando esse arranjo de parênteses.

Portanto, nossa conclusão é que a ordem dos parênteses é importante e que nossa tarefa é encontrar a ordem ótima dos parênteses.

Neste ponto, temos várias opções, uma das quais é projetar um algoritmo de programação dinâmica que dividirá o problema em problemas sobrepostos e calculará o arranjo ótimo de parênteses. A solução de programação dinâmica é apresentada a seguir.

Vamos chamar m[i,j] o número mínimo de multiplicações escalares necessárias para multiplicar uma cadeia de matrizes da matriz i para a matriz j (ie A i × .... × A j , ou seja, i<=j). Dividimos a cadeia em alguma matriz k, tal que i <= k < j, e tentamos descobrir qual combinação produz o mínimo m[i,j].

A fórmula é:

       se i = j, m[i,j]= 0
        se i < j, m[i,j]= min sobre todos os valores possíveis de k (m[i,k]+m[k+1,j] +) 

onde k varia de i a j  − 1.

  • é a dimensão da linha da matriz i,
  • é a dimensão da coluna da matriz k,
  • é a dimensão da coluna da matriz j.

Esta fórmula pode ser codificada como mostrado abaixo, onde o parâmetro de entrada "chain" é a cadeia de matrizes, ou seja:

função OptimalMatrixChainParenthesis(chain)
    n = comprimento(cadeia)
    para i = 1, n
        m[i,i] = 0     // Como não são necessários cálculos para multiplicar uma matriz 
    para len = 2, n
         para i = 1, n - len + 1
            j = i + len -1
            m[i,j] = infinito       // Para que o primeiro cálculo seja atualizado 
            para k = i, j-1
                 q = m[i, k] + m[k+1, j] +
                if q < m[i, j]      // A nova ordem dos parênteses é melhor do que a que tínhamos 
                    m[i, j] = q     // Atualiza 
                    s[i, j] = k     // Grava em qual k dividir, ou seja, onde colocar os parênteses

Até agora, calculamos valores para todos os possíveis m [ i , j ] , o número mínimo de cálculos para multiplicar uma cadeia da matriz i para a matriz j , e registramos o "ponto de divisão" s [ i , j ] correspondente . Por exemplo, se estamos multiplicando a cadeia A 1 ×A 2 ×A 3 ×A 4 , e acontece que m [1, 3] = 100 e s [1, 3] = 2 , isso significa que o posicionamento ideal de parênteses para matrizes 1 a 3 ée para multiplicar essas matrizes serão necessários 100 cálculos escalares.

Este algoritmo produzirá "tabelas" m [, ] es [, ] que terão entradas para todos os valores possíveis de iej. A solução final para toda a cadeia é m[1, n], com divisão correspondente em s[1, n]. Desvendar a solução será recursiva, começando de cima e continuando até chegarmos ao caso base, ou seja, multiplicação de matrizes simples.

Portanto, o próximo passo é realmente dividir a cadeia, ou seja, colocar os parênteses onde eles (otimamente) pertencem. Para isso, podemos usar o seguinte algoritmo:

função PrintOptimalParenthesis(s, i, j)
     se i = j
        imprima "A"
    outro
        imprimir "("
        PrintOptimalParenthesis(s, i, s[i, j])
        PrintOptimalParenthesis(s, s[i, j] + 1, j)
        imprimir ")"

Claro, este algoritmo não é útil para a multiplicação real. Esse algoritmo é apenas uma maneira amigável de ver como é o resultado.

Para realmente multiplicar as matrizes usando as divisões apropriadas, precisamos do seguinte algoritmo:

   function  MatrixChainMultiply ( chain  from  1  to  n )        // retorna a matriz final, ou seja, A1×A2×... ×An 
      OptimalMatrixChainParenthesis ( chain  from  1  to  n )    // isso produzirá s[ . ] e m[. ] "tables" 
      OptimalMatrixMultiplication ( s ,  chain  de  1  a  n )   // na verdade multiplica

   function  OptimalMatrixMultiplication ( s ,  i ,  j )    // retorna o resultado da multiplicação de uma cadeia de matrizes de Ai para Aj de maneira ótima 
      se  i  <  j 
         // continua dividindo a cadeia e multiplicando as matrizes nos lados esquerdo e direito 
         LeftSide  =  OptimalMatrixMultiplication ( s ,  i ,  s [ i ,  j ]) 
         RightSide  =  OptimalMatrixMultiplication ( s ,  s [ i ,  j ]  + 1 ,  j ) 
         return  MatrixMultiply ( LeftSide ,  RightSide )  
      else  if  i  =  j 
         return  Ai    // matriz na posição i 
      else  
         print  "error, i <= j must hold"

    function  MatrixMultiply ( A ,  B )     // função que multiplica duas matrizes 
      se  colunas ( A )  =  linhas ( B )  
         para  i  =  1 ,  linhas ( A ) 
            para  j  =  1 ,  colunas ( B ) 
               C [ i ,  j ]  =  0 
               para  k  =  1 ,  colunas ( A ) 
                   C [i ,  j ]  =  C [ i ,  j ]  +  A [ i ,  k ] * B [ k ,  j ]  
               return  C  
      else  
          print  "erro, dimensões incompatíveis."

História

O termo programação dinâmica foi originalmente usado na década de 1940 por Richard Bellman para descrever o processo de resolução de problemas onde é preciso encontrar as melhores decisões uma após a outra. Em 1953, ele refinou isso para o significado moderno, referindo-se especificamente ao aninhamento de problemas de decisão menores dentro de decisões maiores, [16] e o campo foi posteriormente reconhecido pelo IEEE como um tópico de análise e engenharia de sistemas. A contribuição de Bellman é lembrada no nome da equação de Bellman , resultado central da programação dinâmica que reafirma um problema de otimização de forma recursiva .

Bellman explica o raciocínio por trás do termo programação dinâmica em sua autobiografia, Eye of the Hurricane: An Autobiography :

Passei o trimestre de outono (de 1950) na RAND . Minha primeira tarefa foi encontrar um nome para os processos de decisão em vários estágios. Uma pergunta interessante é: "De onde veio o nome programação dinâmica?" Os anos 1950 não foram bons anos para a pesquisa matemática. Tivemos um cavalheiro muito interessante em Washington chamado Wilson. Ele era secretário de Defesa e, na verdade, tinha um medo e ódio patológicos da palavra "pesquisa". Não estou usando o termo de ânimo leve; Estou usando precisamente. Seu rosto ficaria inundado, ele ficaria vermelho e ficaria violento se as pessoas usassem o termo pesquisa em sua presença. Você pode imaginar como ele se sentiu, então, sobre o termo matemático. A RAND Corporation era empregada pela Força Aérea, e a Força Aérea tinha Wilson como chefe, essencialmente. Por isso, senti que tinha que fazer algo para proteger Wilson e a Força Aérea do fato de que eu estava realmente fazendo matemática dentro da RAND Corporation. Que título, que nome, eu poderia escolher? Em primeiro lugar, eu estava interessado em planejar, em tomar decisões, em pensar. Mas planejamento, não é uma boa palavra por vários motivos. Decidi, portanto, usar a palavra "programação". Eu queria passar a ideia de que isso era dinâmico, era multiestágio, variava no tempo. Eu pensei, vamos matar dois coelhos com uma cajadada só. Tomemos uma palavra que tem um significado absolutamente preciso, ou seja, dinâmico, no sentido físico clássico. Também tem uma propriedade muito interessante como adjetivo, que é a impossibilidade de usar a palavra dinâmica em sentido pejorativo. Tente pensar em alguma combinação que possivelmente lhe dê um significado pejorativo. É impossível. Assim, eu pensei que programação dinâmica era um bom nome. Era algo que nem mesmo um congressista poderia se opor. Então eu usei como um guarda-chuva para minhas atividades. ou seja, dinâmico, no sentido físico clássico. Também tem uma propriedade muito interessante como adjetivo, que é a impossibilidade de usar a palavra dinâmica em sentido pejorativo. Tente pensar em alguma combinação que possivelmente lhe dê um significado pejorativo. É impossível. Assim, eu pensei que programação dinâmica era um bom nome. Era algo que nem mesmo um congressista poderia se opor. Então eu usei como um guarda-chuva para minhas atividades. ou seja, dinâmico, no sentido físico clássico. Também tem uma propriedade muito interessante como adjetivo, que é a impossibilidade de usar a palavra dinâmica em sentido pejorativo. Tente pensar em alguma combinação que possivelmente lhe dê um significado pejorativo. É impossível. Assim, eu pensei que programação dinâmica era um bom nome. Era algo que nem mesmo um congressista poderia se opor. Então eu usei como um guarda-chuva para minhas atividades.

—  Richard Bellman, Eye of the Hurricane: An Autobiography (1984, página 159)

A palavra dinâmica foi escolhida por Bellman para capturar o aspecto variável dos problemas no tempo, e porque soava impressionante. [11] A palavra programação referia-se ao uso do método para encontrar um programa ótimo , no sentido de um cronograma militar para treinamento ou logística. Esse uso é o mesmo das expressões programação linear e programação matemática , sinônimo de otimização matemática . [17]

Falta a explicação acima sobre a origem do termo. Como Russell e Norvig em seu livro escreveram, referindo-se à história acima: "Isso não pode ser estritamente verdade, porque seu primeiro artigo usando o termo (Bellman, 1952) apareceu antes de Wilson se tornar secretário de Defesa em 1953". [18] Além disso, há um comentário em um discurso de Harold J. Kushner , onde ele se lembra de Bellman. Citando Kushner ao falar de Bellman: "Por outro lado, quando lhe fiz a mesma pergunta, ele respondeu que estava tentando ofuscar a programação linear de Dantzig adicionando dinâmica. Talvez ambas as motivações fossem verdadeiras."

Algoritmos que usam programação dinâmica

Veja também

Referências

  1. ^ a b Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C. (2001), Introdução aos Algoritmos (2ª ed.), MIT Press & McGraw–Hill, ISBN  0-262-03293-7 . pág. 344.
  2. ^ Kamien, MI ; Schwartz, NL (1991). Otimização Dinâmica: O Cálculo das Variações e Controle Ótimo em Economia e Gestão (Segunda ed.). Nova York: Elsevier. pág. 261. ISBN 978-0-444-01609-6.
  3. ^ Kirk, Donald E. (1970). Teoria de Controle Ótimo: Uma Introdução . Penhascos de Englewood, NJ: Prentice-Hall. págs. 94-95. ISBN 978-0-13-638098-6.
  4. ^ "M. Memorando" . Vocabulário J. Software J. Recuperado em 28 de outubro de 2011 .
  5. ^ DeLisi, Biopolymers, 1974, Volume 13, Edição 7, páginas 1511-1512, julho de 1974
  6. ^ Gurskiĭ GV, Zasedatelev AS, Biofizika, 1978 set-out;23(5):932-46
  7. ^ Sniedovich, M. (2006), "algoritmo de Dijkstra revisitado: a conexão de programação dinâmica" (PDF) , Journal of Control and Cybernetics , 35 (3): 599-620. Versão online do artigo com módulos computacionais interativos.
  8. ^ Denardo, EV (2003), Programação Dinâmica: Modelos e Aplicações , Mineola, NY: Dover Publications , ISBN 978-0-486-42810-9
  9. ^ Sniedovich, M. (2010), Programação Dinâmica: Fundamentos e Princípios , Taylor & Francis , ISBN 978-0-8247-4099-3
  10. ^ Dijkstra 1959 , p. 270
  11. ^ a b c Eddy, SR (2004). "O que é Programação Dinâmica?". Biotecnologia da Natureza . 22 (7): 909-910. doi : 10.1038/nbt0704-909 . PMID 15229554 . S2CID 5352062 .  
  12. ^ Moshe Sniedovich (2002), "OR/MS Games: 2. The Towers of Hanoi Problem", INFORMS Transactions on Education , 3 (1): 34–51, doi : 10.1287/ited.3.1.45 .
  13. ^ Konhauser JDE, Velleman, D., e Wagon, S. (1996). Para que lado a bicicleta foi? Dolciani Mathematical Expositions – No 18. The Mathematical Association of America .
  14. ^ Sniedovich, Moshe (2003). "Jogos OR/MS: 4. A alegria de cair de ovos em Braunschweig e Hong Kong" . INFORMA Transações sobre Educação . 4 : 48-64. doi : 10.1287/ited.4.1.48 .
  15. ^ Dean Connable Wills, Conexões entre combinatória de permutações e algoritmos e geometria
  16. ^ Stuart Dreyfus. "Richard Bellman sobre o nascimento da programação dinâmica" .
  17. ^ Nocedal, J.; Wright, SJ (2006). Otimização Numérica . Springer. pág. 9 . ISBN 9780387303031.
  18. ^ Russel, S.; Norvig, P. (2009). Inteligência Artificial: Uma Abordagem Moderna (3ª ed.). Prentice Hall. ISBN 978-0-13-207148-2.

Leitura adicional

Links externos