Matrislərin optimal vurulması#9647
İki matris A və B verildikdə, standart matris vurma qaydalarından istifadə edərək C = AB hesablaya bilərik:
Matris A-nın sütunlarının sayı matris B-nin sətirlərinin sayı ilə eyni olmalıdır. Tutaq ki, matris A ölçüsü m × n, matris B ölçüsü n × p-dir. Onda matris C ölçüsü m × p olacaq və onun hesablanması üçün m * n * p vurma əməliyyatı yerinə yetirilməlidir.
Məsələn, əgər A ölçüsü 10 × 20, B ölçüsü 20 × 15-dirsə, onda matris C-nin hesablanması üçün 10 × 20 × 15 = 3000 vurma əməliyyatı yerinə yetirilməlidir.
Bir neçə matrisin vurulması bir neçə üsulla həyata keçirilə bilər. Məsələn, əgər bizdə X, Y və Z matrisləri varsa, XYZ-ni ya (XY)Z kimi, ya da X(YZ) kimi hesablamaq olar. Tutaq ki, X ölçüsü 5 × 10, Y ölçüsü 10 × 20, Z ölçüsü 20 × 35-dir.
Üç matrisin hər iki halda vurulması üçün lazım olan vurma əməliyyatlarının sayını hesablayın:
(XY)Z
5 × 20 × 10 = 1000 vurma əməliyyatı (XY) matrisinin ölçüsü 5 × 20-ni təyin etmək üçün.
Sonra 5 × 35 × 20 = 3500 vurma əməliyyatı son nəticəni tapmaq üçün.
Ümumi vurma əməliyyatlarının sayı: 4500.
X(YZ)
10 × 35 × 20 = 7000 vurma əməliyyatı (YZ) matrisinin ölçüsü 10 × 35-ni təyin etmək üçün.
Sonra 5 × 35 × 10 vurma əməliyyatı son nəticəni tapmaq üçün.
Ümumi vurma əməliyyatlarının sayı: 8750.
Aydındır ki, (XY)Z hesablanarkən daha az vurma əməliyyatı tələb olunur.
Verilmiş matrislərin vurulma ardıcıllığına görə onların vurulmasının optimal ardıcıllığını tapmaq lazımdır. Optimal ardıcıllıq, matrislərin vurulması üçün elementar vurma əməliyyatlarının sayının minimal olduğu ardıcıllıqdır.
Birinci sətir vurulacaq matrislərin sayı n-i (n ≤ 10) ehtiva edir. Sonra matrislərin vurulma ardıcıllığına görə ölçülərini təsvir edən n cüt tam ədəd gəlir.
Bütün matrislərin vurulması üçün kifayət edən minimal vurma əməliyyatlarının sayını çıxış edin.
Nümunə 1
Nümunə 2