Från Googlehemsida

Hoppa till: navigering, sök

Dynamisk programmering används inom den gren av matematik som heter optimeringslära och inom datalogi. Inom datalogi blir termen dynamisk missvisande eftersom det inte handlar om dynamik i orders rätta bemärkelse. Ordet härrör från att linjäroptimering (linjärprogrammering) redan fanns och då passade dynamisk in tyckte han som kom på det.

Dynamisk programmering är applicerbar på problem som uppvisar en optimal delstruktur, det vill säga att delproblemen tillsammans bidrar till att bilda den optimala lösningen. Det är viktigt att dessa delproblem ej är för stora delar av problemet, då kallas programmerings metodiken dekomposition (Divide-and-Conquer) i vilket bland annat Quicksort räknas till. Vanligen sägs att då delproblem kan lösas inom en additativ konstant så är delproblem "rätt" storlek.

Det andra kriteriet för att dynamisk programmering ska vara användbar är att delproblem är överlappande. Med det menas att en rekursiv algoritm ej generar nya delproblem, utan att samma delproblem räknas flera gånger. Ett exempel är Fibonaccis's talföljd där för att beräkna F(5) = F(4) + F(3) måste F(3) beräknas båda för F(5) och F(4), F(4) = F(3) + F(2).


[redigera] Hur man går till väga

  1. Bestäm strukturen hos optimala lösningen
  2. Ställ upp rekursion för optimalvärdet
  3. Beräkna delproblemens optimalvärden från små till stora
  4. Konstruera optimallösningen (ev. med hjälp av extradata från steg 3)