Dinaminis programavimas: Skirtumas tarp puslapio versijų

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Ištrintas turinys Pridėtas turinys
IW-Bot-as (aptarimas | indėlis)
S robotas Pridedama: ko
MTSbot (aptarimas | indėlis)
S robotas Prideda: es, uk
Eilutė 48: Eilutė 48:
[[de:Dynamische Programmierung]]
[[de:Dynamische Programmierung]]
[[en:Dynamic programming]]
[[en:Dynamic programming]]
[[es:Programación dinámica (computación)]]
[[fr:Programmation dynamique]]
[[fr:Programmation dynamique]]
[[he:תכנון דינמי]]
[[he:תכנון דינמי]]
Eilutė 53: Eilutė 54:
[[pl:Programowanie dynamiczne]]
[[pl:Programowanie dynamiczne]]
[[sl:Dinamično programiranje]]
[[sl:Dinamično programiranje]]
[[uk:Динамічне програмування]]
[[zh:动态规划]]
[[zh:动态规划]]

06:45, 17 kovo 2006 versija

Dinaminis programavimas - programavimo metodas, paremtas uždavinio skaidymu į mažesnes susijusias problemas, bei tų problemų sprendimų įsiminimu. Taigi laiko sanaudos pakeičiamos atminties sanaudomis. Jis naudojamas, kuomet "Skaldyk ir valdyk" nėra pakankamai efektyvus. Gali būti pritaikomas įvairaus tipo uždaviniams, tačiau šio metodo taikymo galimybę pastebėti ne visuomet lengva.

Fibonačio skaičiai

Apibrėžimas: , , . Reikia apskaičiuoti -tąjį sekos narį. Rekursyvus sprendimas būtų toks:

 int Fibonacci(int n) {
   if (n < 2) {
     return 1;
   } else {
     return Fibonacci(n-1) + Fibonacci(n-2);
   }
 }

Dinamiškai galime parašyti taip:

 int Fibonacci[N];
 
 Fibonacci[0] = Fibonacci[1] = 1;
 for (int i = 2; i < N; i++) {
   Fibonacci[i] = Fibonacci[i-1] + Fibonacci[i-2];
 }

Taip gauname visas reišmes nuo iki .

"Kuprinės" uždavinys

Šio tipo uždaviniai gana dažni. Bendrai jie formuluojami taip: turime daiktų, bei žinome jų dydžius bei vertes . Kuprinės dydis yra , taigi galima paimti tik tiek daiktų, kad jų dydis neviršytų . Reikia surasti tokį daiktų rinkinį, kurio vertė būtų didžiausia.

Dinaminio sprendimo idėja:

  • Tarkime, nagrinėjame -tąjį daiktą, o kuprinėje dar yra talpos vienetų
  • Jeigu daiktą imame, tuomet galime iš daiktų paimti tiek, kad neviršytų
  • Jeigu neimame, tuomet galime iš daiktų paimti tiek, kad neviršytų
  • Iš šių dviejų atvejų, pasirenkme vertingesnį.

Taigi, problemą daiktų atveju galime išspresti, jeigu žinome problemos daiktų daiktų atveju sprendimą. Matematiškai tai atrodo taip: . Sprendimą galima rasti, ieškant nuo apačios, t.y. pirma apskaičiuojant reikšmes su mažesnėmis reikšmėmis. Taip pat, būtina atkreipti dėmesį, kad būtina turėti tam tikras "ribines" reikšmes. Šiuo atveju tai būtų: .

Programos fragmentai:

 for J := 1 to N do
   begin
     F[J, K] := F[J-1, K];
     if D[J] <= K then
       V[J, K] := Max(V[J, K], V[J-1, K-D[J]] + V[J]);
   end;