Oc-windows.ru

IT Новости из мира ПК
3 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Умножение матриц java

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

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

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

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

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

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

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

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

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

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

int min = Integer.MAX_VALUE;

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

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

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

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

for ( int k = i; k

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

MatrixChainOrder(p, k + 1 , j) +

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

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

public static void main(String args[])

int n = arr.length;

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

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

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

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

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

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

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

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

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

Читать еще:  База данных javascript

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

int m[][] = new int [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 1 ; i++) <

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

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

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

return m[ 1 ][n — 1 ];

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

public static void main(String args[])

int size = arr.length;

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

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

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

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

dr.Mazurok

Software developer AI Scientist Ass.prof Odessa National I.I.Mechnikov University

Свежие комментарии

  • Артем Чернобровкин к записи e-olymp 47. Паркет из треугольников
  • Игорь Мазурок к записи e-olymp 47. Паркет из треугольников
  • Илья Черноморец к записи e-olymp112.Торт
  • Игорь Мазурок к записи e-olymp112.Торт
  • Игорь Мазурок к записи А329. Квадрат суммы цифр числа

Новые решения

Tag Archives: оптимальное умножение матриц

e-olymp 1521. Оптимальное умножение матриц

Задача

Имея два двумерных массива $A$ и $B$, мы можем вычислить $C = AB$ используя стандартные правила умножения матриц:

Число колонок в массиве $A$ должно совпадать с числом строк массива $B$. Обозначим через $rows(A)$ и $columns(A)$ соответственно количество строк и колонок в массиве $A.$ Количество умножений, необходимых для вычисления матрицы $C$ (ее количество строк совпадает с $A$, а количество столбцов с $B$) равно $rows(A)$ $columns(B)$ $columns(A).$ Например, если A имеет размер 10 × 20, B имеет размер 20 × 15, то для их умножения необходимо совершить 10 × 15 × 20, или 3000 умножений для вычисления матрицы $C.$

Перемножать несколько матриц можно несколькими способами. Например, если у нас имеются матрицы $X$, $Y$ и $Z$, то вычислить $XYZ$ можно либо как $(XY)Z$, либо как $X(YZ)$. Пусть $X$ имеет размер 5 × 10, $Y$ имеет размер 10 × 20, $Z$ имеет размер 20 × 35. Подсчитаем количество умножений, необходимых для перемножения трех матриц в каждом из этих двух случаях:

Читать еще:  Функция main java

$5 × 20 × 10 = 1000$ умножений для определения матрицы (XY), имеющей размер $5 × 20.$
Потом $5 × 35 × 20 = 3500$ умножений для нахождения конечного результата.
Общее количество умножений: $4500.$
$X(YZ)$

$10 × 35 × 20 = 7000$ умножений для определения матрицы (YZ), имеющей размер $10 × 35.$
Потом $5 × 35 × 10$ умножений для нахождения конечного результата.
Общее количество умножений: $8750.$
Очевидно, что при вычислении $(XY)Z$ требуется меньшее количество умножений.

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

Входные данные
Для каждой последовательности перемножаемых матриц Вам будут даны лишь размеры матриц. Каждый тест состоит из количества $n (n leq 10)$ перемножаемых матриц, за которым следуют $n$ пар целых чисел, описывающих размеры матриц (количество строк и столбцов); размеры матриц задаются в порядке их перемножения. Последний тест содержит $n = 0$ и не обрабатывается.

Выходные данные
Пусть матрицы пронумерованы $A1, A2,ldots, An.$ Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с 1. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

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

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

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

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

Читать еще:  Java io fileinputstream

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

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

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

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

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

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

int min = Integer.MAX_VALUE;

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

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

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

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

for ( int k = i; k

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

MatrixChainOrder(p, k + 1 , j) +

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

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

public static void main(String args[])

int n = arr.length;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

return m[ 1 ][n — 1 ];

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

public static void main(String args[])

int size = arr.length;

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

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

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

Ссылка на основную публикацию
Adblock
detector
×
×