В этой статье описывается алгоритм задачи умножения матрицы Java (динамическое программирование). Поделитесь этим для вашей ссылки, следующим образом:
Описание задачи: Учитывая N-матрицы: A1, A2, ..., AN, где AI и AI+1 многочисленны, i = 1, 2 ..., N-1. Определите порядок расчета расчета матрицы непрерывного продукта, чтобы количество умножений, необходимых для расчета матрицы непрерывного продукта в этом порядке, наименьшее. Входные данные - это количество матриц и размер каждой матрицы, а результатом вывода является порядок расчета и минимальное количество умножений для непрерывного продукта матрицы.
Анализ проблем: Поскольку умножение матрицы удовлетворяет закону ассоциации, может быть много различных заказов расчета для расчета непрерывного продукта матрицы. Этот порядок расчета может быть определена путем добавления кронштейнов. Если порядок расчета матрицы непрерывного продукта полностью определяется, то есть непрерывный продукт был полностью связан с скобком, то в этом порядке можно неоднократно вызовать стандартный алгоритм для умножения двух матриц.
Полный продукт матрицы с полной скобкой может быть рекурсивно определен как:
(1) единственная матрица полностью скобки;
(2) Матричный продукт A полностью внедрено, затем A может быть представлен как продукт из 2 полностью скобкуемых продуктов Matrix B и C и добавленные кронштейны, то есть A = (BC)
Например, существует 5 различных способов полностью скобки матричного продукта A1A2A3A4: (A1 (A2 (A3A4))), (A1 ((A2A3) A4)), ((A1A2) (A3A4)), ((A1 (A2A3))). Каждый метод полного скопления соответствует порядок расчета продукта, подключенного к матрице, который определяет количество расчета, необходимого для изготовления продукта.
См. Следующий пример, вычислите три умножения матрицы {a1, a2, a3}; Размеры 10*100, 100*5, 5*50 соответственно. Рассчитайте необходимое количество раз в этом порядке ((A1*A2)*A3): 10x100x5+10x5x50 = 7500 раз, рассчитайте необходимое количество раз в этом порядке (A1*(A2*A3): 10*5*50+10*100 = 75000 раз
Таким образом, вопрос: как определить порядок операций, чтобы сумма расчета могла быть сведена к минимуму.
Алгоритм идеи:
Пример: предположим, что вы хотите рассчитать продукт умножения матрицы A1A2A3A4A5A6, где размеры каждой матрицы:
A1: 30*35; A2: 35*15; A3: 15*5; A4: 5*10; A5: 10*20; A6: 20*25
Рекурсивные отношения:
Расчет дизайна a [i: j], 1≤i≤j≤n и минимальное количество требуемых умножений m [i, j], тогда оптимальное значение исходной проблемы составляет m [1, n].
Когда i = j, a [i: j] = ai, следовательно, m [i] [i] = 0, i = 1,2,…, n
Когда я <j, если оптимальный порядок a [i: j] отключается между AK и AK+1, i <= k <J, то: m [i] [j] = m [i] [k]+m [k+1] [j]+pi-1pkpj. Поскольку положение точки отключения k не известно во время расчета, K еще не определен. Тем не менее, есть только Ji возможным для позиции K. Следовательно, k - это позиция, где положение JI минимизирует сумму расчета.
Таким образом, существуют рекурсивные отношения следующим образом:
Создайте оптимальное решение:
Если позиция разъединения k соответствующего m [i] [j] обозначается как s [i] [j], после расчета оптимального значения m [i] [j], соответствующее оптимальное решение может быть построено рекурсивно из S [i] [j]. Число в S [i] [J] показывает, что лучший способ вычислять матричную цепь a [i: j] должен быть отключен между матрицей АК и АК+1, то есть оптимальные скобки должны быть (a [i: k]) (a [k+1: j). Следовательно, из информации, записанной S [1] [n], мы видим, что оптимальные скобки для расчета [1: N] составляют (a [1: s [1] [n]]) (a [s [1] [n] +1: n]). Далее рекурсивно оптимальные скобки для A [1: S [1] [S [1] [S [1] [N]]) составляют (a [S [1] [S [1] [N]]+1: S [1] [S [1] [S [1] [S [1] [N]]). Точно так же можно определить, что оптимальные скобки a [s [1] [n] +1: n] нарушаются при s [1] [n] +1] [n] ... Если мы продолжим повторять это, мы, наконец, можем определить оптимальные полные скобки [1: n] и построить оптимальное решение проблемы.
Matrix; Matrix Public Class {public static void matrixchain (int [] p, int n, int [] [] m, int [] [] s) {for (int i = 1; i <= n; i ++) {m [i] [i] = 0; } for (int r = 2; r <= n; r ++) {for (int i = 1; i <= n-r+1; i ++) {int j = i+r-1; m [i] [j] = m [i + 1] [j] + p [i-1]*p [i]*p [j]; s [i] [j] = i; for (int k = i+1; k <j; k ++) {int t = m [i] [k]+m [k+1] [j]+p [i-1]*p [k]*p [j]; if (t <m [i] [j]) {m [i] [j] = t; s [i] [j] = k; }}}}} public static void traceback (int i, int j, int [] [] s) {if (i == j) return; Traceback (i, s [i] [j], s); Traceback (s [i] [j] + 1, j, s); System.out.println ("Умножьте" + i + "," + s [i] [j] + "и" + (s [i] [j] + 1) + "," + j); } public static void main (string [] args) {System.out.println ("wulin.com Результаты теста:"); Matrix MC = New Matrix (); int n = 7; int p [] = {30, 35, 15, 5, 10, 20, 25}; int m [] [] = new int [n] [n]; int s [] [] = new int [n] [n]; int l = p.length-1; MC.Matrixchain (P, L, M, S); for (int i = 1; i <n; i ++) {for (int j = 1; j <n; j ++) {System.out.print (m [i] [j]+"/t"); } System.out.println (); } System.out.println (); for (int i = 1; i <n; i ++) {for (int j = 1; j <n; j ++) {System.out.print (s [i] [j]+""); } System.out.println (); } mc.traceback (1, 6, s); }}Результаты работы:
Для получения дополнительной информации об алгоритмах Java, читатели, которые заинтересованы в этом сайте, могут просмотреть темы: «Учебное пособие по структуре данных Java и алгоритм», «Сводка операции Java Dom Node», «Сводка Java File и каталог
Я надеюсь, что эта статья будет полезна для всех Java Programming.