Рубрики

Матричное умножение | ДП-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

1) Оптимальная подструктура:
Простое решение — поместить круглые скобки во все возможные места, рассчитать стоимость каждого размещения и вернуть минимальное значение. В цепочке матриц размера n мы можем поместить первый набор скобок n-1 способами. Например, если данная цепочка имеет 4 матрицы. пусть цепочка будет ABCD, тогда есть 3 способа разместить первый набор внешней стороны скобок: (A) (BCD), (AB) (CD) и (ABC) (D). Поэтому, когда мы помещаем набор скобок, мы делим проблему на подзадачи меньшего размера. Следовательно, задача обладает оптимальным свойством субструктуры и может быть легко решена с помощью рекурсии.

Минимальное количество умножения, необходимое для умножения цепочки размером n = минимум всех n-1 мест размещения (эти места размещения создают подзадачи меньшего размера)

2) Перекрывающиеся подзадачи
Ниже приводится рекурсивная реализация, которая просто следует указанному выше оптимальному свойству подструктуры.

C ++

/ * Наивная рекурсивная реализация, которая просто
следует вышеуказанному оптимальному свойству субструктуры * /
#include<bits/stdc++.h>

using namespace std;

  
// Матрица 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]);

  

    cout << "Minimum number of multiplications is "

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

}

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

С

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

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

#include<stdio.h>
#include<limits.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;

}

Джава

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

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

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

  

    }

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

python3

# Наивная рекурсивная реализация, которая
# просто следует вышеуказанному оптимальному
# свойство подструктуры

import sys

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

def MatrixChainOrder(p, i, j):

  

    if i == j:

        return 0

  

    _min = sys.maxsize

      

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

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

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

    # умножения для каждой скобки

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

    for k in range(i, j):

      

        count = (MatrixChainOrder(p, i, k) 

             + MatrixChainOrder(p, k+1, j)

                   + p[i-1] * p[k] * p[j])

  

        if count < _min:

            _min = count;

      

  

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

    return _min;

  

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

arr = [1, 2, 3, 4, 3];

n = len(arr);

  

print("Minimum number of multiplications is ",

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

  
# Этот код предоставлен Арианом Гаргом

C #

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

PHP

<?php 
// Наивная рекурсивная реализация
// это просто следует выше
// оптимальное свойство подструктуры

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

function MatrixChainOrder(&$p, $i, $j)

{

    if($i == $j)

        return 0;

    $min = PHP_INT_MAX;

  

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

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

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

    // каждая скобка размещения и возврата

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

    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;

}

  
// Код драйвера

$arr = array(1, 2, 3, 4, 3);

$n = sizeof($arr);

  

echo "Minimum number of multiplications is " .

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

  
// Этот код предоставлен ita_c
?>

Выход:

Minimum number of multiplications is 30

Временная сложность вышеуказанного наивного рекурсивного подхода является экспоненциальной. Следует отметить, что вышеуказанная функция снова и снова вычисляет одни и те же подзадачи. См. Следующее дерево рекурсии для цепочки матриц размера 4. Функция MatrixChainOrder (p, 3, 4) вызывается два раза. Мы видим, что существует множество подзадач, вызываемых более одного раза.

Поскольку те же самые подзадачи вызываются снова, эта проблема имеет свойство Перекрывающиеся подзадачи. Таким образом, задача матричного умножения имеет оба свойства (см. Это и это ) задачи динамического программирования. Как и другие типичные проблемы динамического программирования (DP) , повторных вычислений с одинаковыми подзадачами можно избежать, создавая временный массив m [] [] по принципу «снизу вверх».

Решение для динамического программирования
Ниже приведена реализация задачи матричного умножения с использованием динамического программирования.

C ++

// Смотрите книгу Кормена для деталей
// следующий алгоритм
#include<bits/stdc++.h>

using namespace std;

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

int MatrixChainOrder(int p[], int n)

{

  

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

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

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

  

    cout << "Minimum number of multiplications is "

         << MatrixChainOrder(arr, size);

  

    getchar();

    return 0;

}

  
// Этот код добавлен
// Аканкша Рай

С

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

}

Джава

// Динамическое программирование Java реализации 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));

    }

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

питон

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

import sys

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

def MatrixChainOrder(p, n):

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

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

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

    m = [[0 for x in range(n)] for x in range(n)]

  

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

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

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

  

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

    for i in range(1, n):

        m[i][i] = 0

  

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

    for L in range(2, n):

        for i in range(1, n-L+1):

            j = i+L-1

            m[i][j] = sys.maxint

            for k in range(i, j):

  

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

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

arr = [1, 2, 3 ,4]

size = len(arr)

  

print("Minimum number of multiplications is " +

       str(MatrixChainOrder(arr, size)))

# Этот код предоставлен Бхавья Джайном

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

PHP

<?php
// Динамическое программирование Python
// матричного умножения.

  
// Смотрите книгу Кормена для деталей
// следующий алгоритм Matrix Ai имеет
// размерность p [i-1] xp [i] для i = 1..n

function MatrixChainOrder($p, $n)

{

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

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

    выделено в м [] []. 0-й ряд и 0-й

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

    $m[][] = array($n, $n);

  

    / * 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] = PHP_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];

}

  
// Код драйвера

$arr = array(1, 2, 3, 4);

$size = sizeof($arr);

  

echo"Minimum number of multiplications is ".

              MatrixChainOrder($arr, $size);

  
// Этот код предоставлен Мукулом Сингхом
?>


Выход:

Minimum number of multiplications is 18

Сложность времени: O (n ^ 3)
Вспомогательное пространство: O (n ^ 2)

Умножение матричной цепочки (решение AO (N ^ 2))
Печать скобок в матричной задаче умножения

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

Приложения:
Минимальное и максимальное значения выражения с * и +

Ссылки:
http://en.wikipedia.org/wiki/Matrix_chain_multiplication
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/chainMatrixMult.htm

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

Матричное умножение | ДП-8

0.00 (0%) 0 votes