Množenje zaporedja matrik II

Množenje zaporedja matrik II

Avtor: Matija Lokar

Več o projektu...

Matrično množenje

  • Zaporedje množenj matrik:

    • Izračunaj A=A*A*…*A
    • A ima dimenzije d d
    • Problem: Kako postaviti oklepaje?

Ideja – razmišljajmo rekurzivno

  • Zadnja operacija bo zmnožila dve matriki

  • A = B * C

    • B so “leve” matrike
    • C so "desne" matrike
  • Če želimo, da je to optimalno, moramo tako do B, kot tudi do C, priti na optimalni način

  • Vprašanje:

    • Koliko matrik spada v B?
    • Če znamo to vedno določiti – imamo rešitev
    • Problem razpade na dva manjša problema ISTE vrste – rešimo enako

Rekurzivni postopek

  • Če je v zaporedju le ena matrika

    • dela
  • Če sta v zaporedju dve matriki (velikosti dx dy in dy dz) dx dy dz dela

  • Če je več matrik

    • zapB naj bodo ustrezne (PROBLEM) matrike z leve
    • zapC naj bodo ustrezne matrike z desne
    • R1 = resitev(zapB)
    • R2 = resitev(zapC)
    • R = resitev(B*C) // delo , ki ga rabimo za to zadnje množ.

    • Delo:

      • R1 + R2 + R

Rekurzivni pristop

  • Podproblem:

    • Poišči opt. rešitev za A*A*…*A.
    • N: št. op. za ta podproblem
    • Optimalna rešitev za celotni problem: N.

  • Optimalna rešitev – definirana z optimalnimi rešitvami podproblemov

    • Zadnje množenje optimalne rešitve naj bo pri i
    • (A*…*A)*(A*…*A).
    • Podroblema A*…*A in A*…*A moramo rešiti optimalno!
    • Optimalna rešitev N = št. op za N + št. op. za N + št. op. za zadnje množenje

Karakteristična enačba

  • A : d d dimenzionalna matrika

    • Karakteristična enačba za N

  • Podproblemi niso neodvisni – se prekrivajo – nastopajo večkrat pri "višjih " problemih
(slika6.jpg)

Zakaj rekurzija ni OK?

  • Poglejmo za 4 matrike

  • Osenčeni deli bi se po nepotrebnem računali

    • Prevelika časovna zahtevnost
(slika5.jpg)

Algoritem

  • Zaradi prekrivanja ne uporabimo rekurzije.
  • Konstruiramo rešitve "lahkih" podproblemov in gremo navzgor.
  • N je enostaven problem (nič dela), zato začnimo z njim
  • Nato za verige dolžine 2, 3, ...
(Image4.jpg)
(slika4.jpg)

Kako računamo

  • Začetno stanje – glavna diagonala
  • Računamo po diagonalah
  • N dobi vrednost iz prejšnjih vrednosti v i-ti vrstici in j-tem stolpcu
  • Če potrebujemo dejanski vrstni red računanja, si moramo zapomniti še ustrezen k pri računanju!
(slika1.jpg)
(slika3.jpg)

Zgled

  • M : , M : , M : , M :

(slika3.jpg)

Zgled

Rešitev: op
Možno: M*((M*M)* M) ali (M*((M*M))* M
M*M = ( op)


{}
{}
{,}

{}
{}

{}
(slika3.jpg)

Zgled

Rešitev: op
Možno: M*((M*M)* M) ali
(M*((M*M))* M
M*M = ( op) (M)

1: M * M = z op
M * M = op
op + op + op = op
2: M * M = z op
M * M = op
op + op + op = op


{}
{}
{,}

{}
{}

{}
(slika3.jpg)

Časovna zahtevnost

  • O(n)
  • n polj matrike
  • Na vsakem polju n dela
  • Običajno nam pri dinamičnem pristopu ne uspe tako drastičen prihranek
  • V najslabšem primeru pri dinamičnem programiranju – še vedno eksponentna zahtevnost
  • V praksi običajno dokaj hitro

Algoritem – rekurzivna formulacija

  • A ima dimenzije p p

    • Opomba: namenoma drugačne oznake kot prej – da dosežemo poudarek na ideji!!
  • Računamo A
  • m[i,j] = minimalno število "navadnih" množenj (množenj realnih števil) za izračun A
  • Ker A lahko dobimo z razdelitvijo v A in A
  • m[i,j] = 0, if i = j
    = min { m[i,k] + m[k+1,j] + ppp }, if i < j
  • s[i,j]: vrednost k, pri katerem dosežemo zgornji minimum

Algoritem

Množenje zaporedja matrik(p) :
  n = len(p) - 1 # predpostavimo tabele od 1 dalje
  for i in range(1, n+1) : m[i,i] = 0
  for v in range(2, n+1) :
    for i in range(1, n – v + 2) :
      j = i + v - 1
      m[i,j] = ∞
      for k in range (i, j) :
        q = m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j]
        if (q < m[i,j]) :
          m[i,j] = q  # stevilo op.
          s[i,j] = k  # kje razdelimo
   return (m, s)

Konstrukcija rešitve

izpišiZOklepaji(s,i,j) {
  if (i == j) :
    print(A[i], end=' ') # ime matrike
  else :
    print("(", end=' ')
    izpišiZOklepaji(s,1,s[i,j])
    print("*", end=' ')
    izpišiZOklepaji(s,s[i,j]+1,j)
    print(")", end=' ')

"Nematematična" uporaba

  • Gradbeniki gradijo ograjo na mostu
  • Vnaprej imajo dane sestavne dele ograje in njihov vrstni red
  • Hkrati lahko spajajo po dva in dva dela
  • Čas, potreben za spajanje posameznih delov je odvisen od dolžine in teže delov, ki jih spajajo
  • Kako naj spajajo dele, da bodo porabili najmanj časa?

Rezanje

  • Na žagi je potrebno desko dolžine 10m prerezati na drugem, četrtem in sedmem metru
  • Hkrati lahko opravimo le en rez
  • Cena rezanja je odvisna od dolžine kosa, ki ga režemo (denimo € za vsak m dolžine)

  • 1. možnost:

    • m režemo pri m in dobimo prvi del
    • m režemo pri m in dobimo drugi del in ostanek m
    • m režemo na m in dobimo tretji del
    • Cena: + + = €

  • 2. možnost:

    • Režemo pri m in dobimo dva dela: m in m
    • m del režemo pri m in dobimo prvi in drugi del
    • m del režemo pri m in dobimo tretji del
    • Cena: + + = €

  • 3. možnost:

    • Režemo pri m
    • m del režemo pri m in dobimo prvi del
    • m del režemo pri m in dobimo drugi in tretji del
    • Cena: + + = €
  • 4. možnost: ...

Združevanje političnih strank

  • Imamo nekaj (n) majhnih političnih strank. Ker so premajhne, da bi pomenile kaj pametnega na političnem prizorišču, so se odločile za združitev. A glede na svoje statute se vedno lahko združijo le z eno drugo stranko. Prav tako se določene stranke med sabo ne marajo preveč. Glede na politično prepričanje so se pripravljene povezati le s stranko, ki zavzema na politični lestvici ravno sosednji položaj. No, brihtni možje so le ugotovili, da lahko stranke oštevilčimo takole S, S, S, S ... S , kjer se je vsaka stranka pripravljena združiti s tisto levo ali tisto desno od sebe. Seveda, ko se npr. združita stranki S in S, se je združena stranka sedaj pripravljena pogovarjati o združitvi s stranko S in s stranko S. Napor (oziroma pravilneje, denar), ki je potreben za združitev dveh strank, je odvisen od skupnega števila njunih članov (saj je potrebno ljudi prepričevati ...).
  • Zato so najeli tebe, znanega svetovalca, da jim pomagaš izdelati plan združevanj tako, da bo celoten proces združevanja stal kar se da malo.

  • Problem najprej reši na primeru, ko imamo strank s podatki:

    • članov, članov, članov, članov, članov, članov, članov, članov, članov, članov
  • Kako bi problem rešil za splošno število strank?

Splošno

  • Zaporedje n operacij in n + 1 argumentov
  • Posamezna operacija združi dva sosednja argumenta
  • Zapletenost posamezne operacije odvisna od kompleksnosti obeh argumentov
  • Določiti vrstni red izvajanja operacij tako, da minimiziramo skupno kompleksnost
0%
0%