Рубрики

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

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

using System;

  

class GFG {

  

    // Матрица 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 = int.MaxValue;

  

        // поместить скобки в разных местах

        // между первой и последней матрицей, рекурсивно

        // рассчитать количество умножений для каждого

        // поместим скобки и вернем

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

        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()

    {

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

        int n = arr.Length;

  

        Console.Write("Minimum number of multiplications is "

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

    }

}

  
// Этот код предоставлен Sam007.

Выход:

Minimum number of multiplications is 30

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

C #

// Динамическое программирование C # реализации
// Матричное умножение цепей.
// Смотрите книгу Кормена для деталей
// следующий алгоритм

using System;

  

class GFG {

  

    // Матрица Ai имеет размерность p [i-1] xp [i]

    // для i = 1..n

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

    {

  

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

        дополнительная строка и один дополнительный столбец

        выделено в м [] []. 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] = int.MaxValue;

                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()

    {

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

        int size = arr.Length;

  

        Console.Write("Minimum number of "

                      + "multiplications is " + MatrixChainOrder(arr, size));

    }

}

  
// Этот код предоставлен Sam007

Выход:

Minimum number of multiplications is 18

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

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

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

0.00 (0%) 0 votes