Izpitno vprašanje RAČ2PRA 17000

Iz MaFiRaWiki

Vprašanje

Na praktičnem primeru demonstriraj način reševanja problema iskanja optimalnega zaporedja množenj matrik - tako določitve števila množenj kot načina množenja. Če je optimalnih načinov množenja več, moraš prikazati vse!

Odgovor

Imamo zaporedje matrik A1, ... An dimenzij d0 x d1, ... ,dn-1 x dn. Radi bi izračunali produkt A1* ... * An. Zanima nas, kako postaviti oklepaje, da bomo pri računanju izvedli najmanj operacij.

  • dinamični pristop
  • karakteristična enačba:

Ni,j ... število operacij pri množenju od Ai do Aj matrik

N_{i,j} = \min_{i\leq k<j}{\{N_{i,k}+N_{k+1,j}+d_id_{k+1}d_{j+1}\}}

  • Postopek:
    • začetno stanje-glavna diagonala
    • računamo po diagonalah
    • Ni,j dobi vrednosti iz prejšnjih vrednosti v i-ti vrstici in j-tem stolpcu
    • za vrstni red množenja, si moramo zapomniti še k pri računanju

Primer

Matrike: A0: 5 x 5, A1: 5 x 4, A2: 4 x 7, A3: 7 x 3

tabela dimenzij
d0 d1 d2 d3 d4
5 5 4 7 3


A0 A1 A2 A3
A0 0 100; 0 240; 1 219; 0
A1 0 140; 1 144; 1
A2 0 84; 2
A3 0

N_{0,1} = \min_{0\leq k<1}{\{N_{0,k}+N_{k+1,1}+d_0d_{k+1}d_{2}\}}

k=0: N0,1 = 0+0+100 = 100


N_{1,2} = \min_{1\leq k<2}{\{N_{1,k}+N_{k+1,2}+d_1d_{k+1}d_{3}\}}

k=1: N1,2 = 0+0+140 = 140


N_{2,3} = \min_{2\leq k<3}{\{N_{2,k}+N_{k+1,3}+d_2d_{k+1}d_{3}\}}

k=2: N2,3 = 84


N_{0,2} = \min_{0\leq k<2}{\{N_{0,k}+N_{k+1,2}+d_0d_{k+1}d_{3}\}}

k=0: N0,2 = 0+140+175 = 315

k=1: N0,2 = 100+0+140 = 240


N_{1,3} = \min_{1\leq k<3}{\{N_{1,k}+N_{k+1,3}+d_1d_{k+1}d_{4}\}}

k=1: N1,3 = 0+84+60 = 144

k=2: N1,3 = 140+0+105 = 245


N_{0,3} = \min_{0\leq k<3}{\{N_{0,k}+N_{k+1,3}+d_0d_{k+1}d_{4}\}}

k=0: N0,3 = 0+144+75 = 219

k=1: N0,3 = 100+84+60 = 244

k=2: N0,3 = 240+0+105 = 345


Rešitev:

Optimalno zmnožimo zaporedje matrik A0 do A3 tako, da matriko A0 zmnožimo z zaporedjem matrik A1 do A3 (k = 0). A1 do A3 optimalno zmnožimo tako, da matriko A1 zmnožimo z zaporedjem matrik A2 do A3 (k = 1). Optimalni način množenja A0 x (A1 x (A2 x A3)) in potrebno je 219 skalarnih množenj.

Osebna orodja