Рубрики

C-программа для умножения матричных цепочек | ДП-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

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

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

#include <limits.h>
#include <stdio.h>

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

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

{

    if (i == j)

        return 0;

    int k;

    int min = INT_MAX;

    int count;

  

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

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

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

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

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

        count = MatrixChainOrder(p, i, k) + 

                MatrixChainOrder(p, k + 1, j) + 

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

  

        if (count < min)

            min = count;

    }

  

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

    return min;

}

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

int main()

{

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

    int n = sizeof(arr) / sizeof(arr[0]);

  

    printf("Minimum number of multiplications is %d ",

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

  

    getchar();

    return 0;

}

Выход:

Minimum number of multiplications is 30

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

С

// Подробнее о следующем алгоритме смотрите в книге Кормена
#include <limits.h>
#include <stdio.h>

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

int MatrixChainOrder(int p[], int n)

{

  

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

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

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

    int m[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;

            m[i][j] = INT_MAX;

            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];

}

  

int main()

{

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

    int size = sizeof(arr) / sizeof(arr[0]);

  

    printf("Minimum number of multiplications is %d ",

           MatrixChainOrder(arr, size));

  

    getchar();

    return 0;

}

Выход:

Minimum number of multiplications is 18

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

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

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

0.00 (0%) 0 votes