Programação dinâmica

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde Agosto de 2013).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoScirusBing. Veja como referenciar e citar as fontes.

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. 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. 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.

Exemplo Sequência de Fibonacci[editar | editar código-fonte]

Como exemplo simples de programação dinâmica, com alguma frequência, alguns textos, utilizam a determinação da
Sequência de Fibonacci, quando implementada de forma recursiva. Isso porque quando a forma recursiva é implementada
sem maiores cuidados, sem memorização, o seu cálculo de tempo cresce exponencialmente. Observe que a rigor esse caso não é um problema de programação dinâmica, visto que o cálculo do n-ésimo número
de Fibonacci cresce linearmente, e não exponencialmente. Porém este exemplo ainda assim é utilizado, pois a
simplicidade é grande.

    Se  n <= 1  então           F(n) :=   1
                caso contrário  F(n) := F(n-1) + F(n-2)

Quando implementada de forma recursiva "ingênua" (naive), sem memorização, a dupla chamada à F na segunda linha,
causa a necessidade da repetição de cálculos, que cresce exponencialmente.

Exemplo Multiplicação de Cadeia de Matrizes[editar | editar código-fonte]

Imaginemos o processo de multiplicação de n matrizes M = M1 x M2 x ... x Mn com dimensões m0 x m1, m1 x m2, ... , mn-1 x mn, respectivamente. O problema em essência é trivial, pois se multiplicarmos sequencialmente as matrizes obteremos facilmente o resultado esperado.

O maior desafio que reside neste problema é otimizar o desempenho do programa que o resolve. Ou seja, multiplicar as matrizes de modo (ordem ótima) que o número de multiplicações escalares seja mínimo.

Multiplicação de matrizes não é comutativa (em geral, A x B ≠ B x A), mas associativa, o que significa que A x (B x C) = (A x B) x C.

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

Problema[editar | editar código-fonte]

Multiplicar M = M1 x M2 x M3 x M4 com dimensões 200 x 2; 2 x30; 30 x 20; 20 x 5, respectivamente. Quantas multiplicações são realizadas nessa sequencia?

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


Organização dos parênteses Computação do custo Custo
M1 x ((M2 x M3) x M4) 2 x 30 x 20 + 2 x 20 x 5 + 200 x 2 x 5 3.400
(M1 x (M2 x M3)) x M4 2 x 30 x 20 + 200 x 2 x 20 + 200 x 20 x 5 29.200
(M1 x M2) x (M3 x M4) 200 x 2 x 30 + 30 x 20 x 5 + 200 x 30 x 5 45.000


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

Solução[editar | editar código-fonte]

Para resolver este problema, tudo que precisamos é saber qual o melhor índice k tal que M = (M1 x M2 x ... x Mk) x (Mk+1 x Mk+2 x ... x Mn) 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 Mi x Mi+1 x ... x Mj.

Portanto,

                         C(i, j) = min {C(i,k) + C(k+1, j) + mi-1mkmj},


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


  • C(i, k) = Mi x Mi+1 x ... x Mk é o número mínimo de operações para realizar de i até k;
  • C(k+1, j) = Mk+1 x Mk+2 x ... x Mj é o número mínimo de operações para realizar de (k+1) até j;
  • mi-1mkmj é o número mínimo de operações para realizar esse produto.


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:


  1. Os C(i,i) são calculados para 1 ≤ i ≤ n. Claramente, C(i,i) = 0;
  2. Os C(i,i+1) são calculados para 1 ≤ i ≤ n-1;
  3. Os C(i,i+2) são calculados para 1 ≤ i ≤ 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) = M1 x M2 = 12.000;
C(2,3) = M2 x M3 = 1.200; e
C(3,4) = M3 x M4 = 3.000.


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) + m0m1m3; C(1,2) + C(3,3) + m0m2m3} = min {9.200; 132.000}


Para k variando de 2 a 3 temos:


C(2,4) = min {C(2,2) + C(3, 4) + m1m2m4; C(2,3) + C(4,4) + m1m3m4} = min {3.300; 1.400}


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


C(1,4) = min {C(1,1) + C(2, 4) + m0m1m4; C(1,2) + C(3,4) + m0m2m4; C(1,3) + C(4,4) + m0m3m4 } = min {3.400; 45.000; 29.200}


Por fim, a solução ótima:


M = (M1 x ((M2 x M3) x M4) → 3.400 operações.

Conclusão[editar | editar código-fonte]

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 polinimial, ou seja O(n3).

Implementação em Java[editar | editar código-fonte]

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 ovalor 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.
     *Parametros: s é a matriz que contém as posições de melhor multiplicação;
     *            i é o índice inical;
     *            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.
     *Retonro: 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 Bibliograficas[editar | editar código-fonte]

  1. DASGUPTA, S., PAPADIMITRIOU, C., VAZIRANI, U. Algoritmos, São Paulo: McGraw-Hill, 2009.
  2. CORMEN, T. H., LEISERSON, C. E., RIVEST, R. L., STEIN, C. Introduction to Algorithms, 3ª Edição, Institute of Technology Massachusetts.
  3. SZWARCCFITER, J. L. Grafos e Algoritmos Computacionais, Editora Campus Ltda, 1984.


Links externos[editar | editar código-fonte]

Veja também[editar | editar código-fonte]