12. fejezet - Fejlett programozási módszerek

12.1. Dinamikus programozás

A dinamikus programozást rendszerint valamilyen numerikus paraméterektől függ ő érték optimumának meghatározására használjuk. A lényeg a következő: az optimális megoldást optimális részmegoldásokból állítjuk elő. Az optimális részmegoldásokat egy táblázatban tároljuk, s az optimális megoldást ennek a táblázatnak szisztematikus feltöltésével kaphatjuk meg. A táblázat elemeit rendszerint egy rekurzív összefüggéssel határozhatjuk meg. Az egyik legegyszerűbb példa a dinamikus programozásra a binomiális együtthatók meghatározása. Itt a Pascal háromszög kiszámításával nyerhetők a kivánt együtthatók. A megfelelő rekurzív összefüggés a következő

Természetesen a kezdéshez szükségünk van a

képletekre is.

Function SZORZÁSOK-SZÁMA(P) 
Input: P a mátrixok méreteiből összeállított tömb 
Eredmény: m tömbben a szorzások száma, s tömbben a zárójelezések helye 
1  n = P.hossz − 1 
2  for i = 1 to n do 
3     m[i, i] = 0
4  endfor 
5  for l = 2 to n do 
6     for i = 1 to n − l + 1 do 
7        j = i + l − 1 
8        m[i, j] = 1 
9        for k = i to j − 1 do 
10          q = m[i, k] + m[k + 1, j] × P[i − 1] × P[k] × P[j] 
11          if q ≤ m[i, j] then 
12             m[i, j] = q 
13             s[i, j] = k 
14          endif 
15       endfor 
16    endfor 
15 endfor 
16 return m és s 

A binomiális együtthatók meghatározásánál kicsit nehezebb az a feladat, amikor az A1A2...An mátrixszorzatot kell kiszámolnunk. A mátrixszorzás asszociatív, így a szorzások sorrendje tetszőleges (ezért nem is használtunk zárójeleket az előbbi képletben). Az exponenciális számú lehetséges kiszámítási sorrend közül azt érdemes követni, amely a legkevesebb elemi szorzással jár. Egy i×j és j×k méretű mátrix összeszorzása i ˇ j ˇ k elemi szorzást igényel. Tartalmazza az m mátrix i, j mezője azt, hogy minimálisan mennyi szorzás szükséges az Ai...Aj mátrixszorzat előállításához! Ez a szorzat Ai...Ak és Ak+1...Aj mátrixok szorzataként állhat elő, ahol k i és j között mozoghat. Innen következik a rekurzív összefüggés: m[i, j] a m[i, k]+m[k+1, j]+a[i, j, k] minimális értéke lesz, ahol az a[i, j, k] a Ai...Ak és Ak + 1...Aj mátrixok méreteinek szorzatát jelenti. Ennek alapján a szorzások számát a SZORZÁSOK-SZÁMA algoritmus adja meg.