Dinamik alqoritmlərin yazılması

6.1 Dinamiki alqoritmlərin hazırlanması zamanı əsas addımlar.

Dinamiki alqoritmlərin hazırlanması zamanı əsas addımlar

1. Alt tapşırıqların müəyyən edilməsi:

Məsələni daha kiçik alt tapşırıqlara bölün, onları bir-birindən asılı olmayaraq həll etmək mümkün olsun. Bu alt tapşırıqlar üst-üstə düşməlidir ki, əvvəlki hesablama nəticələrindən istifadə etmək mümkün olsun.

2. Vəziyyətlərin müəyyən edilməsi:

Məsələni həll edərkən bütün mümkün vəziyyətləri müəyyən edin. Vəziyyətlər bir addımdan digərinə keçmək üçün lazım olan bütün məlumatları təsvir etməlidir.

3. Rekurent əlaqənin formalaşdırılması:

Cari vəziyyət üçün məsələnin həllinin əvvəlki vəziyyətlər üçün həllərdən necə asılı olduğunu müəyyən edin. Bu əlaqə, alt tapşırıqların həllərindən istifadə edərək optimal həllin necə əldə ediləcəyini ifadə etməlidir.

4. Əsas halların müəyyən edilməsi:

Hər hansı əlavə hesablama olmadan birbaşa olaraq məsələnin həlli məlum olan əsas halları müəyyən edin.

5. Cədvəlin doldurulması:

Bütün alt tapşırıqların həllərini saxlamaq üçün cədvəl (adətən array və ya matrisa) yaradın. Rekurent əlaqə ilə əsas hallardan istifadə edərək cədvəli aşağıdan yuxarı və ya yuxarıdan aşağı doldurun.

6. Optimizasiya (memoizasiya):

Əgər rekursiv yanaşma istifadə edilirsə, alt tapşırıqların nəticələrini yadda saxlamaq və onların təkrar hesablanmasını aradan qaldırmaq üçün memoizasiya əlavə edin.

Dinamiki alqoritmlərin zaman və yaddaş mürəkkəbliyi

Zaman mürəkkəbliyi:

• Dinamiki alqoritmlərin zaman mürəkkəbliyi, adətən, alt tapşırıqların sayından və hər bir alt tapşırığın hesablanması üçün tələb olunan vaxtdan asılı olaraq ifadə edilir.
• Çox vaxt zaman mürəkkəbliyi O(n) və ya O(n^2) olur, burada n giriş məlumatlarının ölçüsüdür.

Yaddaş mürəkkəbliyi:

• Yaddaş mürəkkəbliyi saxlanılmalı olan vəziyyətlərin sayından asılıdır.
• Bəzi hallarda, istifadə olunan yaddaş miqdarını O(n) və ya O(1) qədər azaltmaq üçün optimizasiyadan istifadə etmək mümkündür.

6.2 Çanta problemi.

Çanta problemi — kombinator optimizasiya üzrə klassik problem, müxtəlif sahələrdə, o cümlədən informatikada, iqtisadiyyatda və logistika idarəçiliyində yaranır. Problemin əsas məqsədi - məhdud resurslardan maksimum effektiv istifadə etməkdir.

Çanta probleminin təsviri

Bizim müəyyən çəkini W daşıya bilən çantamız var. Eyni zamanda, n dənə əşya var, hər bir əşyanın müəyyən çəkisi wt[i] və dəyəri val[i] var. Hansı əşyaları seçmək lazımdır ki, çantanın çəki tutumunu keçmədən, əşyaların ümumi dəyərini maksimuma çatdıraq?

Çanta probleminin növləri

1. 0/1 Çanta problemi (0/1 Knapsack Problem):

Hər bir əşyanı ya tam götürmək, ya da heç götürməmək olar (hissə-hissə götürmək olmaz).

2. Fraqmental çanta problemi (Fractional Knapsack Problem):

Hər bir əşyanı bölmək və onun istənilən hissəsini götürmək olar.

3. Çoxsaylı çanta problemi (Multiple Knapsack Problem):

Bütün çantaların fərqli çəki məhdudiyyətləri var.

0/1 Çanta probleminin alqoritm nəzəriyyəsi baxımından formalaşdırılması:

Rekursiv əlaqə:

Hər bir əşya i və hər bir mümkün çəki w üçün (0 -dan W -a qədər), optimal həll aşağıdakı kimi ifadə edilə bilər:

• Əgər i-ci əşya çantaya daxil edilməzsə, onda optimal dəyəri i − 1 əşyaları üçün və w çəkisi ilə bərabər olacaq.
• Əgər i-ci əşya çantaya daxil edilərsə, onda optimal dəyəri həmin əşyanın dəyəri ilə i − 1 əşyaları üçün w − wt[i] çəkisi ilə olan optimal dəyərin cəminə bərabər olacaq.

Zaman və yaddaş mürəkkəbliyi

Zaman mürəkkəbliyi:

Bu alqoritmin zaman mürəkkəbliyi O(nW) təşkil edir, burada n — əşyaların sayı, W — çantanın tutumu. Bu, n × W ölçülü cədvəli doldurmaq lazım olduğu ilə bağlıdır.

Yaddaş mürəkkəbliyi:

Yaddaş mürəkkəbliyi də O(nW) təşkil edir, çünki aralıq nəticələr üçün cədvəl lazımdır.

0/1 çanta probleminin tətbiq nümunəsi

def knapsack(W, wt, val, n):
    # Aralıq dəyərləri saxlamaq üçün cədvəl yaradırıq
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
        
    # Cədvəli aşağıdan yuxarıya doldururuq
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i - 1] <= w:
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]
        
    return dp[n][W]
        
# İstifadəyə nümunə
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print(f"Çantanın maksimum dəyəri: {knapsack(W, wt, val, n)}")
        

6.3 Pulları dəyişmək məsələsi.

Pulları dəyişmək məsələsi — dinamik proqramlaşdırmanın klassik məsələsi, hansı ki müəyyən məbləği verilmiş nominallı sikkələr dəsti ilə tərtib etmək üçün minimal sayda sikkələrin və ya müxtəlif kombinasiyaların tapılmasını nəzərdə tutur. Bu məsələnin iki əsas variantı var:

Minimal sikkə sayı (Minimum Coin Change Problem):

Verilmiş məbləği əldə etmək üçün lazım olan minimal sikkə sayını tapın.

Kombinasiya sayı (Number of Ways to Make Change):

Verilmiş nominallarla müəyyən məbləğe çatmağın mümkün kombinasiya sayını tapın.

Variant 1. Minimal sikkə sayı

Məsələnin açıqlanması

Verilənlər:

• Verilmiş nominallarla məhdudiyyətsiz sikkə dəsti.
• Hədəf məbləğ S.

Tələb olunur:

• Hədəf məbləğini S təmin etmək üçün lazım olan minimal sikkə sayını tapın.

Dinamik proqramlaşdırma vasitəsilə həll

Rekursiv nisbət:

• Deyək ki, dp[i] məbləği i təmin etmək üçün lazım olan minimal sikkələr sayını göstərir.
• Hər sikkə c üçün, əgər i ≥ c, onda: dp[i] = min(dp[i], dp[i − c] + 1)

Əsas hallar:

• dp[0] = 0 (məbləğ 0 üçün 0 sikkə tələb olunur).

Zaman və yaddaş mürəkkəbliyi:

• Zaman mürəkkəbliyi: O(n ⋅ S), burada n — nominalların sayı, S — hədəf məbləğdir.
• Yaddaş mürəkkəbliyi: O(S), çünki hər məbləğ üçün minimal sikkələrin sayını saxlamaq üçün massiv tələb olunur 0 -dan S-ə qədər.

Python-da realizasiya nümunəsi

def min_coins(coins, S):
    dp = [float('inf')] * (S + 1)
    dp[0] = 0
        
    for i in range(1, S + 1):
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)
        
    return dp[S] if dp[S] != float('inf') else -1
        
# İstifadə nümunəsi
coins = [1, 2, 5]
S = 11
print(f"Sayı {S} üçün minimal sikkələr sayı: {min_coins(coins, S)}")
        
        

Pulları dəyişmək məsələsi dinamik proqramlaşdırmanın elastikliyini göstərir. Bu, alqoritmik texnikaları öyrətmək və araşdırmaq üçün istifadə olunur, çünki rekursiv nisbətlərdən və əsas hallardan necə istifadə edərək problemləri səmərəli həll edə biləcəyimizi göstərir.