Notas de Aula - Programação Dinâmica

Por que programação dinâmica é chamada de programação dinâmica?

Para responder a essa pergunta, traduzi o trecho do seguinte artigo: STUART DREYFUS; RICHARD BELLMAN ON THE BIRTH OF DYNAMIC PROGRAMMING; Operations Research, 2002.

No trecho abaixo está o trecho de uma entrevista com o criador da programação dinâmica, Richard Bellman.

"A década de 1950 não foi boa para a pesquisa em matemática. Tivemos um cavalheiro muito interessante em Washington chamado Wilson. Ele foi secretário de Defesa, e realmente tinha um medo patológico e ódio da palavra "pesquisa". Não estou usando o termo levemente; Eu estou usando-o precisamente. Seu rosto ficava vermelho, e ele ficava violento se as pessoas usassem o termo "pesquisa" em sua presença. Você pode imaginar como ele se sentia então, sobre o termo 'matemática'. A RAND Corporation foi contratada pela Força Aérea e a Força Aérea tinha Wilson como seu chefe. Daí, eu senti que tinha que fazer alguma coisa para esconder do Wilson e da Força Aérea do fato de que eu estava realmente fazendo matemática dentro da RAND Corporation.

Que título, nome, eu poderia escolher? Em primeiro lugar eu estava interessado no planejamento, na tomada de decisão, no raciocínio. Mas "planejamento", não é uma boa palavra para várias razões. Decidi, portanto, usar a palavra "programação". Eu queria passar a idéia de que era dinâmica, que era em múltiplos estágios, que variava de acordo com o tempo; eu pensei, vamos matar dois coelhos em uma cajadada só. Vamos usar uma palavra que tem um significado absolutamente preciso: "dinâmica", no sentido clássico da física. Ele também tem uma propriedade muito interessante como um adjetivo, isto é, é impossível usar a palavra "dinâmica" em um sentido pejorativo. Tente pensar de alguma combinação que irá, eventualmente, dar-lhe um sentido pejorativo. É impossível. Assim, eu pensei que "programação dinâmica" era um bom nome. Era algo que nem mesmo um congressista poderia opor-se. Então eu usei-o como um guarda-chuva para as minhas atividades.

"

------------------------------------------------

Em problemas de otimização a gente precisa se preocupar em sempre retornar a melhor solução possível.

Com algoritmos gulosos, a abordagem é tomar sempre decisões locais ótimas a cada passo de forma a conseguir uma solução eficiente, mas não temos garantia do ótimo global.

Com uma busca exaustiva, exploramos todas as possibilidades e selecionamos a melhor delas. Assim, iremos conseguir uma solução ótima. Entretanto, em muitos casos, explorar todas as possibilidades tem um custo muito elevado em termos de desempenho.

A programação dinâmica combina um pouco dessas duas abordagens: Iremos explorar todas as possibilidades, mas evitaremos recalcular possibilidades já exploradas anteriormente.

A forma de fazer isso é armazenar os resultados parciais para reutilizá-los depois quando forem necessários.

Ao projetar o algoritmo de programação dinâmica, podemos fazê-lo top down ou bottom up.

Top down, geralmente é mais simples pois representa naturalmente a estrutura recursiva do problema.

Bottom up, a gente precisa sair do caso base da recursão e "ir subindo" até chegar no início.

Para que a programação dinâmica seja possível, é importante ter certeza que:

• Uma solução ótima para o problema é sempre composta de soluções ótimas para os subproblemas. Em outras palavras, se você dividir o seu problema em 2 problemas menores, por exemplo, uma solução ótima para o problema original será a composição das soluções ótimas desses 2 subproblemas.

Exemplo: Fibonnaci

f(n) = 0 , n=0

1, n=1

f(n-1) + f (n-2)

Uma solução recursiva seria:

long f(int n)

{

    if (n == 0) return 0;

    if (n == 1) return 1;

    return f(n-1) + f(n-2);

}

Agora imagine a árvore de recursão para f(6)

Alguns pontos importantes:

• Para resolver o problema de f(n), você divide em problemas menores: f(n-1) e f(n-2)
• Nesse caso, você não possui 'escolhas' a realizar. Mas de qualquer forma, a solução de f(n) é ótima (afinal, só existe uma) e é composta das soluções ótimas de seus subproblemas: f(n-1) e f(n-2)
• Veja que muitos problemas são resolvidos várias vezes. Por exemplo, o problema f(2) é resolvido 5 vezes!!

Logo, a programação dinâmica se aplica a esse problema.

Em uma abordagem top down, manteremos o mesmo algoritmo, mas guardaremos os resultados para evitar recalcular:

#include<iostream>

#define MAXN 45

#define UNKNOWN -1

using namespace std;

long f[MAXN+1];

long f_cache(int n)

{

    if (f[n] == UNKNOWN)

        f[n] = f_cache(n-1) + f_cache(n-2);

    return f[n];

}

int main()

{

    int n;

    cin >> n;

    if (n > MAXN)

    {

        return -1; // número muito grande

    }

    f[0] = 0;

    f[1] = 1;

    for (int i=2; i <=n ; i++)

        f[i] = UNKNOWN;

    cout << f_cache(n) << endl;

    return 0;

}

Veja que nesse caso, você evitará a recursão se ela já foi calculada antes. Pegue um papel e caneta e exercite a árvore de recursão. Você verá que ela ficará assim:

Neste ponto, já trouxemos um algoritmo que era da ordem de O(1.6^n) para O (n).

Para resolver esse mesmo problema usando uma abordagem bottom up, temos que pensar de baixo pra cima na nossa árvore. Ou seja, devemos começar a resolver os menores problemas possíveis e depois usar essas soluções prontas para compor as demais. Devemos sempre tentar fazer isso eliminando a recursão:

long fib(n)

{

    int i;

    long f[MAXN+1];

    f[0] = 0;

    f[1] = 1;

    for (i=2; i <=n; i++)

        f[i] = f[i-1] + f[i-2];

return f[n];

}