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



Yüklə 116,49 Kb.
səhifə6/7
tarix11.09.2022
ölçüsü116,49 Kb.
#63558
1   2   3   4   5   6   7
Dinamik proqramlaşdırma 1

Üst-üstə düşən alt tapşırıqlar:

DP məsələsində üst-üstə düşən alt tapşırıqlar olmalıdır. Bu o deməkdir ki, eyni funksiyanın bir neçə dəfə hesablandığı bəzi ümumi hissə olmalıdır. Məsələn: F(5) və F(6) məsələsinin hər ikisi F(4) və F(3) kimi alt məsələlərə malikdir. Məhz bu səbəbdən hesablanan qiymətləri massivimizdə saxlamışıq.


  • Optimal struktur:

Tutaq ki, sizdən g(x) funksiyasını minimuma endirmək tələb olunur. Bilirsiniz ki, g(x)-in qiyməti g(y) və g(z)-dən asılıdır. İndi g(y) və g(z) hər ikisini minimuma endirməklə g(x)-ni minimuma endirə bilsək, yalnız bu halda problemin optimal alt quruluşa malik olduğunu deyə bilərik. Əgər g(x) g(y)-i minimuma endirməklə minimuma endirilirsə və g(z)-ni minimuma endirmək və ya maksimuma çatdırmaq g(z)-ə təsir etmirsə, onda bu məsələnin optimal alt strukturu yoxdur. Sadə dillə desək, əgər problemin optimal həlli onun alt probleminin optimal həllindən tapıla bilərsə, o zaman problemin optimal alt quruluş xassəsinə malik olduğunu deyə bilərik.
Nəticələr cədvəldə və qrafikdə təqdim olunur [39].

Cədvəl. Fibonaççi ədədinin hesablanması nəticələrinin cədvəli.



Fibonaççi ədədi

40

42

43

44

45

Yerinə yetirilmə vaxtı, ms



Rekursiv
metod

11929

26963

41552

66825

104383

Dinamik proqramlaşdırma

1125

1174

1282

1350

1406


Şəkil . Fibonaççi ədədinin hesablanması nəticələrinin qrafiki.

Yuxarıda təqdim olunan nəticələrdən aydın görünür ki, dinamik proqramlaşdırmadan istifadə edərək hesablama vaxtı rekursiya ilə hesablama vaxtı ilə müqayisədə xeyli aşağıdır. Fərq xüsusilə 40-cı və daha böyük Fibonaççi ədədi hesablanarkən nəzərə çarpır.


Dinamik proqramlaşdırmada vəziyyəti başa düşmək üçün bir nümunəyə baxaq. N elementdən r elementi neçə üsulla seçə bilərik? Bu nCr(n,r) kimi göstərilir. İndi bir element götürək.

Bu ikisinin cəmi bizə üsulların ümumi sayını verir, yəni:

Əgər nCr(n,r) –i n və r-i parametr kimi qəbul edən funksiya saysaq və nCr - i funksiyanın qiyməti kimi qəbul etsək, onda yuxarıda dediyimiz münasibəti bu cür yaza bilərik:
nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)
Bu, rekursiv münasibətdir. Onu başa çatdırmaq üçün baza registrlərini təyin etməliyik. Bilirik ki, nCr(n,r)=n, həmçinin nCn(n,r)=1 . Bu iki bərabərliyi əsas başlanğıc kimi qəbul edərək, nCr -i hesablayan alqoritmi bu şəkildə qura bilərik:
Procedure nCr(n, r):
if r is equal to 1
Return n
else if n is equal to r
Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)
Proseduru qrafik şəkildə nəzərdən keçirsək, bəzi rekursiyaların bir dəfədən çox çağırıldığını görə bilərik. Məsələn: n = 8 və r = 5 götürsək, alırıq:

Biz dp massivindən istifadə edərək təkrar çağırışdan qaça bilərik. 2 parametr olduğu üçün bizə 2D massivi lazım olacaq. Biz dp massivinin bütün elementlərinə -1 mənimsədirik, burada -1 qiymətin hələ hesablanmadığını bildirir. Prosedurumuz belə olacaq:



Yüklə 116,49 Kb.

Dostları ilə paylaş:
1   2   3   4   5   6   7




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin