Рубрики

Java-программа для умножения матричных цепочек | ДП-8

Учитывая последовательность матриц, найдите наиболее эффективный способ умножения этих матриц вместе. Проблема на самом деле не в том, чтобы выполнить умножения, а просто в том, чтобы решить, в каком порядке выполнять умножения.

У нас есть много вариантов умножения цепочки матриц, потому что умножение матриц является ассоциативным. Другими словами, независимо от того, как мы заключим в скобки продукт, результат будет одинаковым. Например, если бы у нас было четыре матрицы A, B, C и D, мы бы имели:

    (ABC)D = (AB)(CD) = A(BCD) = ....

Однако порядок, в котором мы заключаем в скобки продукт, влияет на количество простых арифметических операций, необходимых для вычисления продукта, или на эффективность. Например, предположим, что A представляет собой матрицу 10 × 30, B представляет собой матрицу 30 × 5 и C представляет собой матрицу 5 × 60. Потом,

    (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations
    A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

Очевидно, что первая скобка требует меньше операций.

Дан массив p [], который представляет цепочку матриц так, что i-я матрица Ai имеет размерность p [i-1] xp [i]. Нам нужно написать функцию MatrixChainOrder (), которая должна возвращать минимальное количество умножений, необходимое для умножения цепочки.

  Input: p[] = {40, 20, 30, 10, 30}   
  Output: 26000  
  There are 4 matrices of dimensions 40x20, 20x30, 30x10 and 10x30.
  Let the input 4 matrices be A, B, C and D.  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  (A(BC))D --> 20*30*10 + 40*20*10 + 40*10*30

  Input: p[] = {10, 20, 30, 40, 30} 
  Output: 30000 
  There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30. 
  Let the input 4 matrices be A, B, C and D.  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  ((AB)C)D --> 10*20*30 + 10*30*40 + 10*40*30

  Input: p[] = {10, 20, 30}  
  Output: 6000  
  There are only two matrices of dimensions 10x20 and 20x30. So there 
  is only one way to multiply the matrices, cost of which is 10*20*30

/ * Наивная рекурсивная реализация, которая просто следует

   указанное выше оптимальное свойство подструктуры * /

class MatrixChainMultiplication {

    // Матрица Ai имеет размерность p [i-1] xp [i] для i = 1..n

    static int MatrixChainOrder(int p[], int i, int j)

    {

        if (i == j)

            return 0;

  

        int min = Integer.MAX_VALUE;

  

        // помещаем круглые скобки в разные места между первым

        // и последняя матрица, рекурсивно вычислить количество

        // умножения для каждого размещения в скобках и

        // вернуть минимальное количество

        for (int k = i; k < j; k++) {

            int count = MatrixChainOrder(p, i, k) + 

                        MatrixChainOrder(p, k + 1, j) + 

                        p[i - 1] * p[k] * p[j];

  

            if (count < min)

                min = count;

        }

  

        // Возвращаем минимальное количество

        return min;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        int arr[] = new int[] { 1, 2, 3, 4, 3 };

        int n = arr.length;

  

        System.out.println("Minimum number of multiplications is " 

                               + MatrixChainOrder(arr, 1, n - 1));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

Minimum number of multiplications is 30

Решение для динамического программирования

Джава

// Динамическое программирование Python реализации Matrix
// Цепное умножение.
// Подробнее о следующем алгоритме смотрите в книге Кормена

class MatrixChainMultiplication {

    // Матрица Ai имеет размерность p [i-1] xp [i] для i = 1..n

    static int MatrixChainOrder(int p[], int n)

    {

        / * Для простоты программы, одна дополнительная строка и одна

        дополнительный столбец размещается в m [] []. 0-й ряд и 0-й

        столбец m [] [] не используется * /

        int m[][] = new int[n][n];

  

        int i, j, k, L, q;

  

        / * m [i, j] = минимальное количество необходимых скалярных умножений

        вычислить матрицу A [i] A [i + 1] ... A [j] = A [i..j] где

        размерность A [i] равна p [i-1] xp [i] * /

  

        // стоимость равна нулю при умножении одной матрицы.

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

            m[i][i] = 0;

  

        // L - длина цепи.

        for (L = 2; L < n; L++) {

            for (i = 1; i < n - L + 1; i++) {

                j = i + L - 1;

                if (j == n)

                    continue;

                m[i][j] = Integer.MAX_VALUE;

                for (k = i; k <= j - 1; k++) {

                    // q = стоимость / скалярное умножение

                    q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];

                    if (q < m[i][j])

                        m[i][j] = q;

                }

            }

        }

  

        return m[1][n - 1];

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        int arr[] = new int[] { 1, 2, 3, 4 };

        int size = arr.length;

  

        System.out.println("Minimum number of multiplications is " 

                            + MatrixChainOrder(arr, size));

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Выход:

Minimum number of multiplications is 18

Пожалуйста, обратитесь к полной статье о матричном умножении | DP-8 для более подробной информации!

Рекомендуемые посты:

Java-программа для умножения матричных цепочек | ДП-8

0.00 (0%) 0 votes