Ugrás a tartalomhoz

Adatstruktúrák és algoritmusok

Házy Attila, Nagy Ferenc (2009)

7. fejezet - Dinamikus programozás

7. fejezet - Dinamikus programozás

A dinamikus programozás és az oszd meg és uralkodj elv közötti legfontosabb különbségeket mutatja a következő táblázat.

A dinamikus programozás lépései:

  1. Jellemezzük az optimális megoldás szerkezetét.

  2. Rekurzív módon definiáljuk az optimális megoldás értékét.

  3. Kiszámítjuk az optimális megoldás értékét alulról felfelé módon.

  4. A kiszámított információk alapján megszerkesztjük az optimális megoldást.

7.1. Definíció. Mátrixok szorzatát teljesen zárójelezettnek nevezzük, ha a szorzat vagy egyetlen mátrixból áll, vagy pedig két, zárójelbe tett teljesen zárójelezett mátrix szorzata

7.1. Példa. Legyenek az mátrixok méretei , és . Számítsuk ki a mátrixot.

Ekkor mérete . A műveletszám (szorzások száma) két mátrix összeszorzásakor: , ha a méretek és .

Első módszer: , műveletszám

Második módszer: , műveletszám

Legyenek az összeszorzandó mátrixok: és legyen az mátrix mérete ().

Legyen az mátrix zárójelezéseinek a száma.

Innen:

Az optimális zárójelezés szerkezete:

Legyen . Az optimális eset az szorzatot -nál vágja szét . Költség költsége + költsége + az összeszorzás költsége. és zárójelezése is optimális kell legyen.

Legyen az kiszámításának minimális költsége

Legyen az a index, ahol az szorzat ketté van vágva.

Legyen

7.2. Példa.

</examend>

7.1. Feladatok

  1. 1. Milyen az optimális zárójelezés, ha a mátrixok méretei: ?

  2. 2. Adható-e egyszerű szabály az optimális zárójelezésre akkor, ha a méretek a vektorban monoton növekednek? És ha monoton csökkennek?