Задача 19.
Пусть известно, что для перемножения матрицы размера n*m на матрицу размера m*k требуется n*m*k операций. Необходимо определить, какое минимальное число операций потребуется для перемножения n матриц А1,...Аn, заданных своими размерами n(i)*m(i). При этом можно перемножать любые две рядом стоящие матрицы, в результате чего получается матрица нужного размера.
Замечание:
n(i) - число строк в матрице Ai
m(i) - число столбцов в матрице Ai
n(i)=m(i)+1.
|
Решение задачи 19.
Определим через F[i,j] минимальное число операций, которое требуется для перемножения группы матриц с номерами от i до j включительно. Ясно, что F[i,i]=0. Перемножение матриц в такой группе может производиться различными способами, а именно, производить сначала перемножение наилучшим способом группы от i до k, затем от k+1 до j, наконец перемножить получившиеся матрицы. Понятно, что k может быть величиной от i до j-1. Учитывая требование получить наилучший результат, величина F[i,j] определяется как
F[i,j]=max(F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j]),
где k может быть величиной от i до j-1, n[i], n[k+1], m[j] определяют размеры матриц, получившихся при перемножении в группах.
дляi от 1 до N выполнять
F[i,i]:=0;
дляl от 1 до N-1 выполнять
для i от 1 до N-l выполнять
нц
Kol:=бесконечность;
j:=i+l;
для k от i до j-1 выполнять
если Kol > F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j] то Kol:=F[i,k]+F[k+1,j]+n[i]*n[k+1]*m[j];
все
F[i,j]:=Kol;
кц
|
