Naloge/Dinamično programiranje/rekonstrukcija/resitevAnitaPersuh

Iz PSA
Skoči na: navigacija, iskanje

Postopek reševanja

Imamo zaporedje matrik M0, ... M8 dimenzij d0 x d1, ... ,d7 x d9. Radi bi izračunali produkt M0* ... * M8. Zanima nas, kako postaviti oklepaje, da bomo pri računanju izvedli najmanj operacij. V tabeli imamo že izračunana minimalna števila potrebnih operacij.


  0       1         2        3         4         5        6          7           8
0 0,   432(0),   513(1),   675(2),   954(2),   1206(4), 1368(2),  1593(6),  1818(2,6,7)  
1        0       432(1)   1296(2)   1146(2)    1638(2)  1482(2)   2187(2)    1932(2)
2                  0       486(2)    567(2)     954(2)   945(2)   1440(2)    1395(2)
3                            0       378(3)     630(4)   810(5)   1035(6)    1260(6,7)   
4                                      0       1512(4)  1050(4)   2400(6)    1600(4)
5                                                0       420(5)    945(6)     970(6)
6                                                          0       900(6)     675(6)
7                                                                    0        375(7)
8                                                                               0

Rešitev

Najmanjša vrednost množenja matrik med sabo je 1818. Do te rešitve nas pripeljejo razližne postavitve oklepajev.

Najprej bomo pogledali rešitev če je k = 2.

Prvi oklepaj postavimo za M2
(M0*M1*M2)*(M3*M4*M5*M6*M7*M8)
pogledamo za N12: oklepaj postavivo za M1 
((M0*M1)*M2)*(M3*M4*M5*M6*M7*M8)
pogledamo za N38: imamo dve možnosti ali postavimo za M6 ali pa za M7:
  Najprej bomo pogledali rešitev, če postavimo oklepaj za M6:
  ((M0*M1)*M2)*((M3*M4*M5*M6)*(M7*M8))
  pogledamo za N36: oklepaj postavivo za M5 
  ((M0*M1)*M2)*(((M3*M4*M5)*M6)*(M7*M8))
  pogledamo za N35: oklepaj postavivo za M4 
  ((M0*M1)*M2)*((((M3*M4)*M5)*M6)*(M7*M8))
  Končna rešitev:
  ((M0*M1)*M2)*((((M3*M4)*M5)*M6)*(M7*M8)) 
  Druga rešitev je, če postavimo oklepaj za M7:
  ((M0*M1)*M2)*((M3*M4*M5*M6*M7)*M8)
  pogledamo za N37: oklepaj postavivo za M6 
 ((M0*M1)*M2)*(((M3*M4*M5*M6)*M7)*M8)
  pogledamo za N36: oklepaj postavivo za M5
  ((M0*M1)*M2)*((((M3*M4*M5)*M6)*M7)*M8)
  pogledamo za N35: oklepaj postavivo za M4 
 ((M0*M1)*M2)*(((((M3*M4)*M5)*M6)*M7)*M8)
  Končna rešitev je:
  ((M0*M1)*M2)*(((((M3*M4)*M5)*M6)*M7)*M8)

Če je k = 6

Prvi oklepaj postavimo za M6
(M0*M1*M2*M3*M4*M5*M6)*(M7*M8)
pogledamo za N06: oklepaj postavivo za M2 
((M0*M1*M2)*M3*M4*M5*M6)*(M7*M8)
pogledamo za N02: oklepaj postavivo za M1 
(((M0*M1)*M2)*M3*M4*M5*M6)*(M7*M8)
pogledamo za N36: oklepaj postavivo za M5 
(((M0*M1)*M2)*(M3*M4*M5)*M6)*(M7*M8)
pogledamo za N35: oklepaj postavivo za M4 
(((M0*M1)*M2)*((M3*M4)*M5)*M6)*(M7*M8)
 Končna rešitev je:
(((M0*M1)*M2)*((M3*M4)*M5)*M6)*(M7*M8)

Če je k = 7

Prvi oklepaj postavimo za M7
(M0*M1*M2*M3*M4*M5*M6*M7)*M8
pogledamo za N07: oklepaj postavivo za M6
((M0*M1*M2*M3*M4*M5*M6)*M7)*M8
pogledamo za N06: oklepaj postavivo za M2
(((M0*M1*M2)*M3*M4*M5*M6)*M7)*M8
pogledamo za N02: oklepaj postavivo za M1
((((M0*M1)*M2)*M3*M4*M5*M6)*M7)*M8
pogledamo za N36: oklepaj postavivo za M5
((((M0*M1)*M2)*(M3*M4*M5)*M6)*M7)*M8
pogledamo za N35: oklepaj postavivo za M4
((((M0*M1)*M2)*((M3*M4)*M5)*M6)*M7)*M8
Končna rešitev je:
 ((((M0*M1)*M2)*((M3*M4)*M5)*M6)*M7)*M8

Matrike lahko med sabo, optimalno zmnoživo na več načinov:

((M0*M1)*M2)*((((M3*M4)*M5)*M6)*(M7*M8))

((M0*M1)*M2)*(((((M3*M4)*M5)*M6)*M7)*M8)

(((M0*M1)*M2)*((M3*M4)*M5)*M6)*(M7*M8)

((((M0*M1)*M2)*((M3*M4)*M5)*M6)*M7)*M8