Müasir cəmiyyətdə informasiyanın həcmi planetin 20 IL əvvəl mövcud olan bütün informasiya həcmini üstələyir. Bütün daxil olan məlumatların emalı çox vaxt aparır

1.3. “Dinamik proqramlaşdırma” üsulu ilə həll nümunələri


Bir nümunəyə baxaq. İtalyan riyaziyyatçısı Fibonaççi dovşan populyasiyasının ideallaşdırılmış artımını nəzərə alaraq bir sıra silsilələr kəşf etdi.
Silsilə:
1, 1, 2, 3, 5, 8, 13, 21, ......
Qeyd edə bilərik ki, ilk iki ədəddən sonrakı hər bir ədəd əvvəlki iki ədədin cəmidir. İndi bizə n-ci Fibonaççi ədədini hesablayacaq F(n) funksiyasını formalaşdıraq:


F(n) = nth Fibonacci Number
Əvvəlcədən məlumdur ki,
F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3
Ümumiləşdirmə aparaq:
F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

İndi onu rekursiv funksiya kimi yazmaq istəsək, əsas məlumat kimi F(1) və F(2) olur. Beləliklə, Fibonacci funksiyamız aşağıdakı kim olacaq:

Procedure F(n): //A function to return n_th Fibonacci Number
if n is equal to 1
Return 1
else if n is equal to 2
Return 1
end if
Return F(n-1) + F(n-2)

İndi biz F(6) çağırsaq, o, F(5) və F(4) çağıracaq, bunlar da daha bir neçəsini çağıracaq. Onu qrafik olaraq təqdim edək:

Şəkildən göründüyü kimi, F(6) hesablanan zaman F(5) və F(4) çağırılır. Sonra F(5) öz növbəsində F(4) və F(3)-ü çağırır. F(5) hesablandıqdan sonra qətiyyətlə demək olar ki, F(5) –in hesablanması üçün çağırılan bütün funksiyalar ona qədər hesablanmışdı. Bu o deməkdir ki, F(4) –ü biz artıq hesablamışdıq. Amma F(6) hesablanan zaman biz yenə də F(4)-ü hesablamaq məcburiyyətində qalacağıq. Buna həqiqətənmi ehtiyac var? Biz elə edə bilərik ki, F(4) ilk dəfə hesablanan kimi onun qiymətinin yadda saxlayaq. Biz bu qiyməti dp adlı massivdə saxlayaraq, lazım olduqda istifadə edəcəyik. Əvvəlcə dp massivinin bütün elementlərinə -1 (və ya hesablamamızda əldə edilməyəcək hər hansı digər bir qiymət) qiyməti mənimsədilir. Onda F(6) hesablanan zaman modifikasiya edilmiş F(n) belə formalaşdırılacaq:
Procedure F(n):
if n is equal to 1
Return 1
else if n is equal to 2
Return 1
else if dp[n] is not equal to -1 //That means we have already calculated dp[n]
Return dp[n]
else
dp[n] = F(n-1) + F(n-2)
Return dp[n]
end if

Biz əvvəlki kimi eyni tapşırığı yerinə yetirdik, lakin sadə bir optimallaşdırma ilə, yəni yadda saxlama (memoization) üsulundan istifadə etdik. Əvvəlcə dp massivinin bütün dəyərləri -1-ə bərabər olacaqdır. F(4) çağırıldıqda onun boş olub olmadığını yoxlayırıq. F(4)-ün qiyməti -1-ə bərabərdirsə, onun qiymətini hesablayırıq və dp[4] -də yadda saxlayırıq. Əgər -1 -dən başqa hər hansı bir qiymətə bərabərdirsə, bu o deməkdir ki, biz artıq onun qiymətini hesablamışıq. Beləliklə, biz artıq hesablanmış qiymətdən istifadə edəcəyik.

Bu sadə optimallaşdırma metodu yadda saxlama (memoization) üsulundan istifadə edilən dinamik proqramlaşdırma adlanır.
Qarşıya qoyulan məsələ bəzi xüsusiyyətlərə malik olduqda dinamik proqramlaşdırma ilə həll edilə bilər. Bunlara aiddir:

• 
  Alt məsələ:
  

Dinamik proqramlaşdırma məsələsi bir və ya bir neçə alt məsələyə bölünə bilər. Məsələn: F(4) daha kiçik alt tapşırıqlara F(3) və F(2) –yə bölünə bilər. Alt problemlər bizim əsas problemimizə bənzədiyi üçün eyni texnika ilə həll edilə bilər.

•