Programaçao dinamica - Dynamic programming

Figura 1. Encontrando o caminho mais curto em um gráfico usando a subestrutura ideal; 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 otimizada dividindo-o em subproblemas e, em seguida, encontrando recursivamente as soluções ótimas para os subproblemas, então é dito que ele tem uma subestrutura ótima .

Se os subproblemas podem ser aninhados recursivamente dentro de problemas maiores, de forma que métodos de programação dinâmica sejam aplicáveis, então há uma relação entre o valor do problema maior e os valores dos subproblemas. Na literatura de otimização, essa 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 sequência de funções de valor V 1 , V 2 , ..., V n tomando y como um argumento que representa o estado do sistema nos tempos 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 podem ser encontrados trabalhando para trás, usando uma relação recursiva chamada de 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 essa decisão for tomada. Como V i já foi calculado para os estados necessários, a operação acima resulta em 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 por 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 sistema siga uma trajetória admissível em um intervalo de tempo contínuo que minimiza uma função de custo

A solução para este problema é uma lei ou política de controle ótima , que produz uma trajetória ótima e uma função de custo de execução . 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 qual e . Descobrimos que minimizar em termos de , e a função desconhecida e então substituir o resultado na equação de Hamilton – Jacobi – Bellman para obter a equação diferencial parcial a ser resolvida com condição de contorno . 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 -ésimo estágio de intervalos de tempo discretos igualmente espaçados, e onde e denotam aproximações discretas para e . 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.

Exemplo da economia: o problema de Ramsey de economia ideal

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 . Em termos gerais, o planejador enfrenta o trade-off entre o consumo contemporâneo e o consumo futuro (via investimento no 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 está o consumo, é o capital e é uma função de produção que satisfaz as condições Inada . Um estoque de capital inicial é assumido.

Seja o consumo no período t , e suponha que o consumo rende utilidade enquanto o consumidor viver. Suponha que o consumidor esteja impaciente, de forma que ele desconta a utilidade futura por um fator b a cada período, onde . Let be capital no período t . Suponha que o capital inicial seja um determinado montante e que o capital e o consumo desse 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 a para todos

Escrito dessa forma, o problema parece complicado, porque envolve a solução de todas as variáveis ​​de escolha . (O capital não é uma variável de escolha - o capital inicial do consumidor é considerado 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 , para as quais 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 retroativa usando a equação de Bellman . Neste problema, para cada um , 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 momento t , seu capital atual é dado, e ele só precisa escolher o consumo atual e a poupança .

Para realmente resolver esse problema, trabalhamos ao contrário. Para simplificar, o nível atual de capital é denotado como k . já é conhecido, então, usando a equação de Bellman, uma vez que possamos calcular , e assim por diante, até chegarmos a , que é o valor do problema de decisão inicial para toda a vida. Em outras palavras, uma vez que sabemos , podemos calcular , qual é o máximo de , onde está a variável de escolha e .

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

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

que pode ser simplificado para

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

Programação de computador

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 para conquistar ". É por isso que a classificação por mesclagem e a classificação rápida não são classificadas como problemas de programação dinâmica.

Subestrutura ótima significa que a solução para um determinado problema de otimização pode ser obtida pela combinação de soluções ótimas para seus subproblemas. Essas subestruturas ótimas são geralmente descritas por meio de recursão . Por exemplo, dado um gráfico G = (V, E) , o caminho mais curto p de um vértice u para um vértice v exibe uma subestrutura ótima: tome 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 a w e p 2 de w a v de modo que estes, por sua vez, são de fato os caminhos mais curtos entre os vértices correspondentes (pelo simples argumento cortar e colar descrito em Introdução aos algoritmos ). Portanto, pode-se facilmente formular a solução para encontrar os caminhos mais curtos de maneira recursiva, que é o que o algoritmo Bellman-Ford ou o algoritmo Floyd-Warshall fazem.

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 continuamente, ao invés 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 de base F 1  =  F 2  = 1. Então F 43F 42  +  F 41 , e F 42F 41  +  F 40 . Agora F 41 está sendo resolvido nas subárvores recursivas de F 43 e F 42 . Mesmo que o número total de subproblemas seja realmente pequeno (apenas 43 deles), acabamos resolvendo os mesmos problemas continuamente se adotarmos uma solução recursiva ingênua como essa. A programação dinâmica leva em consideração esse fato e resolve cada subproblema apenas uma vez.

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

Isso pode ser alcançado de duas maneiras:

  • Abordagem de cima para baixo : Esta é a consequência 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 ascendente : depois de formularmos a solução para um problema recursivamente como em termos de seus subproblemas, podemos tentar reformular o problema de uma forma ascendente: tente resolver os subproblemas primeiro e usar suas soluções para construir e chegar a soluções para subproblemas maiores. Isso também é geralmente feito em uma forma tabular, gerando soluções iterativamente para subproblemas cada vez maiores, usando as soluções para subproblemas pequenos. Por exemplo, se já sabemos 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 determinado conjunto de argumentos, a fim de acelerar a avaliação de chamada por nome (esse mecanismo é conhecido como chamada por necessidade ). Algumas linguagens tornam isso possível portável (por exemplo , Scheme , Common Lisp , Perl ou D ). Alguns idiomas possuem memoização automática incorporada, como Prolog e J , que suporta memoização com o advérbio M .. Em qualquer caso, isso só é possível para uma função referencialmente transparente . 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ência , dobramento de proteínas , previsão da 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 de forma independente por Charles DeLisi nos EUA e Georgii Gurskii e Alexander Zasedatelev na URSS. Recentemente, esses algoritmos se tornaram 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

O 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 da programação dinâmica para o problema do caminho mais curto pelo método Reaching .

Na verdade, a explicação de Dijkstra da lógica por trás do algoritmo, a saber

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

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

é uma paráfrase do famoso Princípio de Otimização 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 n- é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:

function fib(n)
    if 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:

  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 do zero. Em exemplos maiores, muitos mais valores fibou subproblemas são recalculados, levando a um algoritmo de tempo exponencial.

Agora, suponha que temos um objeto de mapa simples , m , que mapeia cada valor do 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)
function fib(n)
    if key n is not in map m 
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

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

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

function fib(n)
    if n = 0
        return 0
    else
        var previousFib := 0, currentFib := 1
        repeat n − 1 times // loop is skipped if n = 1
            var newFib := previousFib + currentFib
            previousFib := 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 computá-lo toda vez que um deles é avaliado.

O método acima leva tempo para n grande porque a adição de dois inteiros com bits cada leva tempo. (O n th número de Fibonacci tem pedaços.) Além disso, não é uma forma fechada para a sequência de Fibonacci, conhecida como fórmula de Binet , a partir do qual o termo -ésimo pode ser calculado em cerca de tempo, o qual é mais eficiente do que a técnica de programação acima dinâmico . No entanto, a recorrência simples fornece diretamente a forma da matriz que leva a um algoritmo aproximado por exponenciação rápida da matriz .

Um tipo de matriz 0-1 balanceada

Considere o problema da atribuição de valores, zero ou um, para as posições de um n × n matriz, com n mesmo, de modo que cada linha e cada coluna contém exactamente n / 2 zeros e n / 2 queridos. Perguntamos quantas atribuições diferentes existem para um dado . Por exemplo, quando n = 4 , quatro 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 en / 2 uns). Como existem atribuições possíveis e atribuiçõ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 ambos pelo menos n / 2 . Embora mais sofisticada do que a força bruta, essa abordagem visitará todas as soluções uma vez, tornando-se impraticável para n maiores que seis, uma vez que 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 retroceder valores para a primeira linha - quais informações precisaríamos sobre as linhas restantes, a fim de sermos capazes de contar com precisão as soluções obtidas para cada valor da primeira linha? Consideramos k × n placas, onde 1 ≤ kn , cujas linhas contêm zeros e uns. 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. Procuramos o valor de ( argumentos ou um vetor de elementos). O processo de criação de subproblemas envolve a iteração de cada uma das atribuições possíveis para a linha superior do quadro e percorrer todas as colunas, 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 algum dos resultados for negativo, a atribuição é inválida e não contribui para o conjunto de soluções (a recursão para). Caso contrário, temos uma atribuição para a linha superior da placa k × n e calculamos recursivamente o número de soluções para a placa restante ( k - 1) × n , adicionando os números 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 uma placa 1 × n . O número de soluções para este bordo é zero ou um, dependendo de se o vector é 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 damas 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

Assim c(1, 3) = 5

Digamos que houvesse um verificador que pudesse começar em qualquer quadrado da primeira classificação (ou seja, linha) e você quisesse saber o caminho mais curto (a soma dos custos mínimos em cada classificação visitada) para chegar à última classificação; assumindo que o verificador só poderia se mover diagonalmente para a esquerda para a frente, 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 exibe 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 ) = custo mínimo para atingir o quadrado ( i , j ).

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

A função q(i, j)é igual ao custo mínimo para chegar a qualquer um dos três quadrados abaixo dela (já que esses são os únicos quadrados que podem alcançá-la) 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 inferior e nno limite superior. 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 do exemplo. A partir dessa definição, podemos derivar código recursivo direto para q(i, j). No pseudocódigo a seguir, né o tamanho do tabuleiro, c(i, j)é a função de custo e min()retorna o mínimo de uma série de valores:

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else
        return min( minCost(i-1, j-1), minCost(i-1, j), minCost(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 continuamente. No entanto, podemos computá-lo muito mais rápido de forma ascendente se armazenarmos os custos do caminho em uma matriz bidimensional em q[i, j]vez de usar uma função. Isso evita recomputação; todos os valores necessários para a matriz 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 em relação ao índice (in q[i, j]) do custo do caminho pré-calculado de s. Para reconstruir o caminho completo, procuramos o predecessor de s, depois o predecessor desse quadrado, depois o predecessor desse quadrado e assim por diante, recursivamente, até chegarmos ao quadrado inicial. Considere o seguinte código:

function computeShortestPathArrays()
    for x from 1 to n
        q[1, x] := c(1, x)
    for y from 1 to n
        q[y, 0]     := infinity
        q[y, n + 1] := infinity
    for y from 2 to n
        for x from 1 to n
            m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
            q[y, x] := m + c(y, x)
            if m = q[y-1, x-1]
                p[y, x] := -1
            else if m = q[y-1, x]
                p[y, x] :=  0
            else
                p[y, x] :=  1

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

function computeShortestPath()
    computeShortestPathArrays()
    minIndex := 1
    min := q[n, 1]
    for i from 2 to n
        if 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ência é uma aplicação importante onde a programação dinâmica é essencial. 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 possui 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. inserir o primeiro caractere de B e realizar um alinhamento ideal de A e da cauda de B
  2. deletando 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] para B [1..j]. O custo na célula (i, j) pode ser calculado somando o custo das operações relevantes ao custo de suas células vizinhas e selecionando o ótimo.

Existem diferentes variantes, consulte o algoritmo Smith – Waterman e o algoritmo Needleman – Wunsch .

Quebra-cabeça da 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 ou quebra-cabeça matemático . Consiste em três hastes e vários discos de diferentes tamanhos que podem deslizar em qualquer haste. O quebra-cabeça começa com os discos em uma pilha organizada 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 às seguintes regras:

  • Apenas um disco pode ser movido por vez.
  • Cada movimento consiste em retirar o disco superior de uma das hastes e deslizá-lo para outra haste, em cima dos demais discos que porventura já estejam 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, não (h, t)); S (1, h, t); S (n-1, não (h, t), t)

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

S (n, h, t): = solução para 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" (resta apenas um disco).

O número de movimentos exigidos 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.

Quebra-cabeça de queda de ovo

A seguir está uma descrição da instância deste famoso quebra - cabeça envolvendo N = 2 ovos e um edifício com H = 36 andares:

Suponha que desejamos saber quais histórias em um prédio de 36 andares são seguras para derrubar ovos e quais farão com que os ovos se quebrem ao pousar (usando a terminologia em inglês dos Estados Unidos , em que o primeiro andar fica ao 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 se quebrar ao ser derrubado, ele quebrará se cair de uma janela mais alta.
  • Se um ovo sobreviver a uma queda, ele sobreviverá a uma queda mais curta.
  • Não está descartado que as janelas do primeiro andar quebrem ovos, nem que os ovos possam sobreviver nas janelas do 36º andar.
Se apenas um ovo estiver disponível e desejamos ter certeza de obter o resultado correto, o experimento pode ser realizado de apenas uma maneira. Solte o ovo da janela do primeiro andar; se sobreviver, jogue-o da janela do segundo andar. Continue subindo até que se quebre. No pior dos casos, esse método pode exigir 36 fezes. Suponha que 2 ovos estejam disponíveis. Qual é o menor número de fezes de ovos que funcionam em todos os casos?

Para derivar uma equação funcional de programação dinâmica para este quebra-cabeça, deixe o estado do modelo de programação dinâmica ser 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 precisam ser 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 cenário de pior caso, dado que o processo está no estado s = ( n , k ).

Então, pode ser mostrado que

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

com W ( n , 0) = 0 para todo n  > 0 e W (1, k ) = k para todo  k . É fácil resolver esta 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 leva tempo com uma solução DP. Isso pode ser melhorado com o tempo por busca binária no ótimo na recorrência acima, uma vez que está aumentando em enquanto está diminuindo em , portanto, um mínimo local de é um mínimo global. Além disso, armazenando o ótimo para cada célula na tabela DP e referindo-se ao seu valor para a célula anterior, o ótimo para cada célula pode ser encontrado em tempo constante, melhorando-o com o tempo. No entanto, existe uma solução ainda mais rápida que envolve uma parametrização diferente do problema:

Let Ser o número total de andares tal que os ovos quebram quando caem do chão (O exemplo acima é equivalente a tirar ).

Let Ser o piso mínimo do qual o ovo deve ser derrubado para ser quebrado.

Let Ser o número máximo de valores de que são distinguíveis usando try and eggs.

Então, para todos .

Seja o piso de onde o primeiro ovo é largado na estratégia ótima.

Se o primeiro ovo quebrou, é de a e distinguível usando no máximo as tentativas e os ovos.

Se o primeiro ovo não quebrou, é de para e distinguível usando tentativas e ovos.

Portanto ,.

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

Para fazer isso, poderíamos calcular em ordem crescente , o que levaria tempo.

Portanto, se lidarmos separadamente com o caso de , o algoritmo levaria tempo.

Mas a relação de recorrência pode de fato ser resolvida, dando , que pode ser computado no tempo usando a identidade para todos .

Pois para todos , podemos pesquisar binário para encontrar , dando um algoritmo.

Multiplicação de cadeia de matriz

A multiplicação da cadeia de matrizes é um exemplo bem conhecido que demonstra a utilidade da programação dinâmica. Por exemplo, as aplicações de engenharia freqüentemente 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. Portanto, 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 várias 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 no qual matrizes específicas são multiplicadas. Se a matriz A tem dimensões m × n e a matriz B tem 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 de multiplicação de matriz simplista 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 e p × s, respectivamente. A matriz A × B × C terá o tamanho m × s e pode ser calculada das duas maneiras mostradas abaixo:

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

Vamos supor que m = 10, n = 100, p = 10 es = 1000. Portanto, a primeira maneira de multiplicar a cadeia exigirá 1.000.000 + 1.000.000 de 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 ideal entre 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 (ou seja, A i × .... × A j , ou seja, i <= j). Dividimos a cadeia em alguma matriz k, de modo que i <= k <j, e tentamos descobrir qual combinação produz m mínimo [i, j].

A fórmula é:

       if i = j, m[i,j]= 0
       if i < j, m[i,j]= min over all possible values of 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 conforme mostrado abaixo, onde o parâmetro de entrada "cadeia" é a cadeia de matrizes, ou seja :

function OptimalMatrixChainParenthesis(chain)
    n = length(chain)
    for i = 1, n
        m[i,i] = 0    // Since it takes no calculations to multiply one matrix
    for len = 2, n
        for i = 1, n - len + 1
            j = i + len -1
            m[i,j] = infinity      // So that the first calculation updates
            for k = i, j-1
                q = m[i, k] + m[k+1, j] + 
                if q < m[i, j]     // The new order of parentheses is better than what we had
                    m[i, j] = q    // Update
                    s[i, j] = k    // Record which k to split on, i.e. where to place the parenthesis

Até agora, calculamos os 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" correspondente s [ i , j ] . 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 as matrizes 1 a 3 é e para multiplicar essas matrizes será necessário um cálculo escalar de 100.

Este algoritmo produzirá "tabelas" m [,] e s [,] que terão entradas para todos os valores possíveis de i e j. 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 do topo 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 o parêntese onde eles (de forma otimizada) pertencem. Para este propósito, poderíamos usar o seguinte algoritmo:

function PrintOptimalParenthesis(s, i, j)
    if i = j
        print "A"i
    else
        print "(" 
        PrintOptimalParenthesis(s, i, s[i, j]) 
        PrintOptimalParenthesis(s, s[i, j] + 1, j) 
        print ")"

Claro, este algoritmo não é útil para multiplicação real. Este algoritmo é apenas uma maneira amigável de ver a aparência do resultado.

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

   function MatrixChainMultiply(chain from 1 to n)       // returns the final matrix, i.e. A1×A2×... ×An
      OptimalMatrixChainParenthesis(chain from 1 to n)   // this will produce s[ . ] and m[ . ] "tables"
      OptimalMatrixMultiplication(s, chain from 1 to n)  // actually multiply

   function OptimalMatrixMultiplication(s, i, j)   // returns the result of multiplying a chain of matrices from Ai to Aj in optimal way
      if i < j
         // keep on splitting the chain and multiplying the matrices in left and right sides
         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   // matrix at position i
      else 
         print "error, i <= j must hold"

    function MatrixMultiply(A, B)    // function that multiplies two matrices
      if columns(A) = rows(B) 
         for i = 1, rows(A)
            for j = 1, columns(B)
               C[i, j] = 0
               for k = 1, columns(A)
                   C[i, j] = C[i, j] + A[i, k]*B[k, j] 
               return C 
      else 
          print "error, incompatible dimensions."

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 em que é necessário encontrar as melhores decisões uma após a outra. Em 1953, ele refinou isso para o significado moderno, referindo-se especificamente a aninhar problemas de decisão menores dentro de decisões maiores, e o campo foi posteriormente reconhecido pelo IEEE como um tópico de engenharia e análise de sistemas . A contribuição de Bellman é lembrada em nome da equação de Bellman , um 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 do outono (de 1950) na RAND . Minha primeira tarefa foi encontrar um nome para 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 para a pesquisa matemática. Tínhamos 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 levianamente; Estou usando precisamente. Seu rosto ficaria vermelho, ele ficaria vermelho e 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. Portanto, senti que precisava fazer algo para proteger Wilson e a Força Aérea do fato de que estava realmente fazendo matemática dentro da RAND Corporation. Que título, que nome, posso 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 transmitir a ideia de que isso era dinâmico, isso era em vários estágios, isso era variável 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, sendo impossível usar a palavra dinâmica em sentido pejorativo. Tente pensar em alguma combinação que possivelmente lhe dê um significado pejorativo. É impossível. Portanto, achei que programação dinâmica era um bom nome. Era algo que nem mesmo um congressista poderia objetar. Então, usei-o 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 do tempo dos problemas, e porque soava impressionante. A palavra programação referia-se ao uso do método para encontrar um programa ótimo , no sentido de uma programação militar para treinamento ou logística. Esse uso é o mesmo que nas frases programação linear e programação matemática , um sinônimo de otimização matemática .

A explicação acima da origem do termo está faltando. Como Russell e Norvig escreveram em seu livro, 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." 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

Leitura adicional

links externos