Пусть известно, что для перемножения матрицы размера 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.
Определим через 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;кц