Dynamisk programmering 1.4
- Hur ser den triangulära matrisen M ut?
Svar: a) Eftersom radnumret representerar första matrisen i kedjan i delproblemet och kolumnnumret sista matrisen i kedjan så måste radnumret alltid vara mindre än kolumnnumret, vilket innebär att matrisen M är högertriangulär. - Fundera nu vidare på steg 3 för matriskedjemultiplikationsproblemet. Försök komma fram till en lämplig beräkningsordning och skriv sedan en algoritm som beräknar delproblemens värden enligt din beräkningsordning.
- Om du har några frågor som du vill ha besvarade på föreläsningen så kan du skriva dom som kommentar till denna sida.
- Läs sida 251-260 i Kleinberg-Tardos, helst före föreläsningen.
- På föreläsningen 14 september klockan 12-13 i sal D1 kommer vi förutom att ta upp frågorna arbeta med steg 3 i dynamisk programmering för olika problem, däribland matriskedjemultiplikation.