pt.wikipedia.org

Programação dinâmica – Wikipédia, a enciclopédia livre

Origem: Wikipédia, a enciclopédia livre.

Programação dinâmica é um método para a construção de algoritmos para a resolução de problemas computacionais, em especial os de otimização combinatória.^[1] Ela é aplicável a problemas nos quais a solução ótima pode ser computada a partir da solução ótima previamente calculada e memorizada - de forma a evitar recálculo - de outros subproblemas que, sobrepostos, compõem o problema original.

O que um problema de otimização deve ter para que a programação dinâmica seja aplicável são duas principais características: subestrutura ótima e superposição de subproblemas^[2]. Um problema apresenta uma subestrutura ótima quando uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. A superposição de subproblemas acontece quando um algoritmo recursivo reexamina o mesmo problema muitas vezes.

Problemas de programação dinâmica podem ser abordados de forma top-down ou bottom-up.

Como os próprios nomes sugerem, a abordagem top-down aborda o problema de forma recursiva comum, ou seja, no exemplo do algoritmo de Fibonacci (mais abaixo), começamos pelo n-ésimo número e em, recursivamente, ir calculando os valores de F[ n-1 ], F[ n-2 ], F[ n-3 ],..., F[ 2 ], F[ 1 ]. Nesta abordagem, os valores são armazenados em uma tabela e, para a i-ésima iteração, verifica-se se F[ i ] já foi calculado.

Na abordagem bottom-up, vamos calculando os subproblemas menores e aumentando a complexidade com o passar do tempo, ou seja, para o exemplo de Fibonacci, começaríamos calculando F[ 1 ], depois F[ 2 ], F[ 3 ], e assim por diante até F[ n ]. Observe que, nesta abordagem, na nós sabemos que, na i-ésima iteração, F[ i-1 ] já foi resolvido, logo não precisamos verificar toda vez como na top-down. Ao consultar o exemplo 1, do Algoritmo de Fibonacci, isso deve ficar mais claro.

Em geral, ambas as abordagens tem o mesmo tempo assintótico de execução^[^{carece de fontes]}.

Como exemplo simples de programação dinâmica, com alguma frequência, alguns textos, utilizam a determinação recursiva da Sequência de Fibonacci.

$F(n)=\left\lbrace {\begin{matrix}1&{\text{se }}n\leq 1\\F(n-1)+F(n-2)&{\text{caso contrário}}\end{matrix}}\right\rbrace$

Quando implementada de forma recursiva sem maiores cuidados e sem memorização, a dupla chamada a F na segunda linha causa a necessidade da repetição de cálculos, que faz com que o tempo cresça exponencialmente.

Para implementar em PD, tem-se os seguintes pseudocódigos:

ALGORITMO FIBONACCI-TOPDOWN(n)
    Criar vetor F com n posicoes, iniciando em 1
    F[1] = 1
    F[2] = 2
    Para i = 3 até n faça
        F[i] = -1
    retorne FIBONACCI-RECURSIVO-TOPDOWN(N)
FIM

Esse primeiro irá inicializar as posições 1 e 2 com o valor 1 e o resto com "-1". Esse primeiro algoritmo somente cria e inicializa o vetor, e ao final chama o algoritmo que de fato irá calcular os valores de Fibonacci:

ALGORITMO FIBONACCI-RECURSIVO-TOPDOWN(n)
    se F[n] > 0 entao
        retorne F[n]
    F[n] = FIBONACCI-RECURSIVO-TOPDOWN(n - 1) + FIBONACCI-RECURSIVO-TOPDOWN(n - 2)
    retorne F[n]
FIM

Este segundo algoritmo, a princípio, irá ir até à posição 1 e 2 e, então, somar o valor de ambas (1 + 1). Em segunda, o algoritmo recursivo irá adicionar esse valor ao valor da posição 3. Observe que, ao tentar calcular F[3], o algoritmo irá calcular F[1] e F[2], mas F[1] e F[2] já foram calculados, e a primeira linha do pseudocódigo verifica se F[n] já existe e, caso seja verdadeiro, irá apenas retornar seu valor. Com isso, o tempo de execução será Θ(n).

Imaginemos o processo de multiplicação de $n$ matrizes $M=M_{1}\times M_{2}\times \ldots \times M_{n}$ com dimensões $m_{0}\times m_{1},m_{1}\times m_{2},\dotsc ,m_{n-1}\times m_{n}$ , respectivamente. O problema em essência é trivial, pois se multiplicarmos sequencialmente as matrizes obteremos facilmente o resultado esperado.

É interessante lembrar que a multiplicação de matrizes não é comutativa (em geral, $A\times B\neq B\times A$ ), mas associativa, o que significa que $A\times (B\times C)=(A\times B)\times C$ .

O maior desafio que reside neste problema é, então, otimizar o desempenho do programa que o resolve, ou seja, aproveitar-se da propriedade associativa para encontrar a ordem ótima de se realizar a multiplicação das matrizes, de modo que o número de multiplicações escalares seja mínimo.

Podemos observar que, em geral, multiplicar uma matriz $m\times n$ por uma matriz $n\times p$ exige $m\times n\times p$ operações de multiplicação. As matrizes são multiplicadas aos pares.

Multiplicar $M=M_{1}\times M_{2}\times M_{3}\times M_{4}$ com dimensões $200\times 2$ , $2\times 30$ , $30\times 20$ e $20\times 5$ , respectivamente. Quantas multiplicações são realizadas nessa sequência?

Vamos exemplificar algumas maneiras de realizarmos esta operação:

Organização dos parênteses	Computação do custo	Custo
$M_{1}\times ((M_{2}\times M_{3})\times M_{4})$	$2\times 30\times 20+2\times 20\times 5+200\times 2\times 5$	$3.400$
$(M_{1}\times (M_{2}\times M_{3}))\times M_{4}$	$2\times 30\times 20+200\times 2\times 20+200\times 20\times 5$	$29.200$
$(M_{1}\times M_{2})\times (M_{3}\times M_{4})$	$200\times 2\times 30+30\times 20\times 5+200\times 30\times 5$	$45.000$

Como podemos observar, a ordem da multiplicação faz uma grande diferença no tempo de execução final.

Para resolver este problema, tudo que precisamos é saber qual o melhor índice $k$ tal que $M=(M_{1}\times M_{2}\times \ldots \times M_{k})\times (M_{k+1}\times M_{k+2}\times \ldots \times M_{n})$ onde $k$ varia de 1 até (n−1).

Note que esse problema foi decomposto em dois subproblemas. Mais precisamente defina $C(i,j)$ como o número mínimo de multiplicações (ou o custo mínimo) para realizar o produto $M_{i}\times M_{i+1}\times \ldots \times M_{j}$ .

Portanto,

$C(i,j)=min\left\lbrace C(i,k)+C(k+1,j)+m_{i-1}m_{k}m_{j}\right\rbrace$ ,

onde $k$ varia de i até (j -1), fornece o custo mínimo de multiplicações. Daí, note que:

Esta expressão constitui uma recorrência típica do método de programação dinâmica. Ela sugere um algoritmo recursivo, mas, uma implementação “bottom up” (de baixo para cima) é mais eficiente. Um algoritmo nesta fórmula tem os seguintes passos iterativos:

Os $C(i,i)$ são calculados para $1\leq i\leq n$ . Claramente, $C(i,i)=0$ ;
Os $C(i,i+1)$ são calculados para $1\leq i\leq n-1$ ;
Os $C(i,i+2)$ são calculados para $1\leq i\leq n-2$ ; e assim por diante

Assim, vamos aplicar o algoritmo acima para resolver o exemplo dado anteriormente. Observe que devemos calcular o custo mínimo na ordem crescente da diferença entre $i$ e $j$ . Então, no primeiro passo iterativo, a diferença entre $i$ e $j$ é zero, pois, $i=j$ , o que implica:

$C(1,1)=C(2,2)=C(3,3)=C(4,4)=0$ .

No segundo passo, temos i - j = 1, logo,

$C(1,2)=M_{1}\times M_{2}=12000$

$C(2,3)=M_{2}\times M_{3}=1200$

$C(3,4)=M_{3}\times M_{4}=3000$

No terceiro passo, j - i = 2 e com isso, o $k$ varia de 1 a 2. Utilizando a fórmula recursiva:

$C(1,3)=min(C(1,1)+C(2,3)+m_{0}m_{1}m_{3};$ $C(1,2)+C(3,3)+m_{0}m_{2}m_{3})=min(9200;132000)$

Para $k$ variando de 2 a 3 temos:

$C(2,4)=min(C(2,2)+C(3,4)+m_{1}m_{2}m_{4};C(2,3)+C(4,4)+m_{1}m_{3}m_{4})=min(3300;1400)$

No último passo, j − i = 3 e com isso, o $k=1,2,3$ .

$C(1,4)=min(C(1,1)+C(2,4)+m_{0}m_{1}m_{4};C(1,2)+C(3,4)+m_{0}m_{2}m_{4};C(1,3)+C(4,4)+m_{0}m_{3}m_{4})=min(3400;45000;29200)$

Por fim, a solução ótima:

$M=M_{1}\times ((M_{2}\times M_{3})\times M_{4})\to 3.400$ operações.

Tentar todas as ordens possíveis de multiplicações para avaliar o produto de $n$ matrizes é um processo ordem exponencial em $n$ .

Usando programação dinâmica é possível resolver este problema na ordem polinomial, ou seja $O(n^{3})$ .

package Classes;
/**
 *
 *
 */
public class Matriz {
    /*Atributos da classe*/
    /*string: atributo que recebe os dados de saída de printOptmalParents()
    * para poder exibir o resultado da parentização. */
    private static String string;
    /*m: atributo que recebe os valores das multiplicações feitas para o melhor custo*/
    private int m[][];
    /*s: atributo que recebe o valor das posições de melhor multiplicação*/
    private int s[][];
    /*linhas: recebe o valor total das linhas das matrizes.*/
    private int linhas;
    /*colunas: recebe o valor total das colunas das matrizes*/
    private int colunas;
    /*inicoMatriz: atributo tipo flag, para marcar a inicialização de matrizes
    * no método recursiveMatrixChain(int p[], int i, int j)*/
    private boolean inicioMatriz;
    /*Métodos geters e setters para entrada e saída de dados nos atributos*/
    public int[][] getM() {
        return m;
    }
    public void setM(int[][] m) {
        this.m = m;
    }
    public int[][] getS() {
        return s;
    }
    public void setS(int[][] s) {
        this.s = s;
    }
    public int getLinhas() {
        return linhas;
    }
    public void setLinhas(int linhas) {
        this.linhas = linhas;
    }
    public int getColunas() {
        return colunas;
    }
    public void setColunas(int colunas) {
        this.colunas = colunas;
    }
    public Matriz() {
        string = "";
    }
    /*Métodos da Classe*/
    /* Método para calcular o melhor custo.
     *Parametros: p é um vetor com as posições das matrizes.
     *Retorno: int[][].*/
    public static int[][] MatrixChainOrder(int p[]) {
        int retorno[][] = new int[p.length - 1][p.length - 1];
        try {
            int i = 0; //linhas
            int j = 0; //colunas
            int k = 0;
            int q = 0;
            int infinito = Integer.MAX_VALUE; // tipo infinito positivo (para simular o infinito)
            int n = p.length - 1;
            int m[][] = new int[n][n]; // ixj
            int s[][] = new int[n][n];
            for (i = 0; i < n; i++) {
                m[i][i] = 0;
            }
            for (int l = 1; l < n; l++) {
                for (i = 0; i < n - l; i++) {
                    j = i + l;
                    m[i][j] = infinito;
                    for (k = i; k < j; k++) {
                        q = m[i][k] + m[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                        if (q < m[i][j]) {
                            m[i][j] = q;
                            s[i][j] = k + 1;
                        }
                    }
                }
            }
            retorno = s;
        } catch (Exception e) {
            System.out.println("Erro: " + e);
            e.printStackTrace();
        }
        return retorno;
    }
    /*Método para alocar os parênteses de uma forma ótima para a multiplicação.
     *Parâmetros: s é a matriz que contém as posições de melhor multiplicação;
     *            i é o índice inicial;
     *            j é o índice final.
     *Retorno: String.*/
    public String printOptmalParents(int s[][], int i, int j) {
        if (i == j) {
            this.string += "A" + (i + 1) + " ";
        } else {
            this.string += " ( ";
            printOptmalParents(s, i, s[i][j] - 1);
            printOptmalParents(s, s[i][j], j);
            this.string += " ) ";
        }
        return this.string;
    }
    /*Método para inicializar os atributos da classe que serão utilizados em métodos.
     *Parâmetros: p é um vetor com as posições das matrizes.
     *Retorno: não há.*/
    public void inicializaRecursiveMatrixChain(int p[]) {
        int n = p.length - 1;
        this.m = new int[n][n]; // ixj
        this.s = new int[n][n];
        this.inicioMatriz = true;
    }
    /*Método para calcular o melhor custo; porém com chamadas recursivas.
     *Parâmetros: p é um vetor com as posições das matrizes;
     *            i é o índice inicial;
     *            j é o índice final.
     *Retorno: int.*/
    public int recursiveMatrixChain(int p[], int i, int j) {
        int retorno = 0;
        if (this.inicioMatriz) {
            if (i == j) {
                retorno = 0;
            } else {
                this.m[i][j] = Integer.MAX_VALUE;
                for (int k = i; k <= j - 1; k++) {
                    int q = recursiveMatrixChain(p, i, k) + recursiveMatrixChain(p, k + 1, j) + p[i] * p[k + 1] * p[j + 1];
                    if (q < this.m[i][j]) {
                        this.m[i][j] = q;
                        this.s[i][j] = k + 1;
                    }
                }
                retorno = this.m[i][j];
            }
        }
        return retorno;
    }
}

Referências

↑ Dasgupta, Sanjoy (2009). Algoritmos. São Paulo: McGraw Hill
↑ Mota, Guilherme (21 de julho de 2018). «Análise de Algoritmos eEstruturas de Dado» (PDF). UFABC - Universidade Federal do ABC. Consultado em 19 de agosto de 2018
↑ Cormen, Thomas (2009). Algoritmos: Teoria e Prática 3 ed. [S.l.]: Campus

Implementação de algoritmos da Programação Dinâmica