Рубрики

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

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

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

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

Выход:

Minimum number of multiplications is  30

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

питон

# Динамическое программирование 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)))

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

Выход:

Minimum number of multiplications is 18

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

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

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

0.00 (0%) 0 votes