Programação dinâmica

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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. 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 devido à sua simplicidade.

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 "ingênua" (naïve), sem memorização, a dupla chamada a F na segunda linha causa a necessidade da repetição de cálculos, que cresce exponencialmente.

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

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.

Problema[editar | editar código-fonte]

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.

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

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 1 até (j -1), fornece o custo mínimo de multiplicações. Daí, note que:


  • C(i, k) = M_{i} \times M_{i+1} \times \ldots \times M_{k} é o número mínimo de operações para realizar de i até k;
  • C(k+1, j) = M_{k+1} \times M_{k+2} \times \ldots \times M_{j} é o número mínimo de operações para realizar de (k+1) até j;
  • m_{i-1}m_{k}m_{j} é 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 \leq i \leq n. Claramente, C(i,i) = 0;
  2. Os C(i,i+1) são calculados para 1 \leq i \leq n-1;
  3. 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.

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(n^3) .

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, Sanjoy. Algoritmos. São Paulo: McGraw Hill, 2009.
  2. Cormen, Thomas. Algoritmos: Teoria e Prática. 3. ed. [S.l.]: Campus, 2009.

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

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