Dinamik proqramlaşdırmanın əsasları

5.1 Dinamik proqramlaşdırmanın tərifi.

Dinamik proqramlaşdırma (Dynamic Programming, DP) — mürəkkəb məsələlərin daha sadə alt məsələlərə bölünməsi ilə həll olunması üçün istifadə edilən optimizasiya metodudur. Dinamik proqramlaşdırma optimal alt strukturuna malik və bir-birini örtüşən alt məsələlərə bölünə bilən məsələlərin həlli üçün effektiv üsuldur.

İş prinsipləri:

1. Optimal alt struktur:

Əgər məsələnin optimal həlli onun alt məsələlərinin optimal həllərindən qurula bilirsə, deməli bu məsələ optimal alt strukturuna malikdir. Bu, böyük bir məsələni bir neçə kiçik alt məsələni həll etməklə həll etməyə imkan verir.

2. Bir-birini örtüşən alt məsələlər:

Əgər məsələnin alt məsələləri həll zamanı dəfələrlə təkrarlanırsa, bu məsələ bir-birini örtüşən alt məsələlərə malikdir. Dinamik proqramlaşdırma, artıq həll edilmiş alt məsələlərin nəticələrini yadda saxlayaraq (memonizasiya), belə məsələləri effektiv həll edir.

3. Memonizasiya və tabelalaşdırma:

Memonizasiya (yuxarıdan aşağı): Rekursiv yanaşmadır, burada alt məsələlərin nəticələri yadda saxlanılır ki, təkrar hesablamalar qarşısı alınsın.

Tabelalaşdırma (aşağıdan yuxarı): Iterativ yanaşmadır, burada alt məsələlərin nəticələri hesablanır və cədvəldə (adətən massivdə) saxlanılır və son nəticənin hesablanmasında istifadə olunur.

Dinamik proqramlaşdırma metodu ilə həll olunan məsələlərin nümunələri

5.2 Sırt çantası məsələsi.

Məsələ:

Tərəfimizdə bir neçə əşya var, hərəsinin çəkisi və dəyəri məlumdur. Məqsəd, müəyyən edilmiş daşıma qabiliyyəti olan sırt çantasına maksimal ümumi dəyəri təmin edəcək əşyaları seçməkdir.

Vacibdir! Oxşar bir hesab problemi ilə müqayisədə, hansı ki, bu, açgözlü algoritmlə yaxşı həll edilirdi, bu məsələdə əşyaları hissələrə bölmək olmaz.

Həll:

Bir cədvəl yaradılır, burada sətirlər əşyaları, sütunlar isə sırt çantasının mümkün həcmini ifadə edir. Hücrədəki dəyər isə bu ədəd əşya və həcm üçün maksimal dəyəri göstərir.

Zaman mürəkkəbliyi: O(n * W), burada n — əşyaların sayı, W — sırt çantasının həcmi.

Python-dan kod nümunəsi:

def knapsack(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
            
    for i in range(1, n + 1):
        for w in range(W + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
            else:
                dp[i][w] = dp[i - 1][w]
            
    return dp[n][W]
        
        

5.3 Ən qısa yolu tapmaq məsələsi

Məsələ:

Bütün çəkili qrafın təpələri arasında ən qısa yolları tapmaq.

Həll:

Cədvəl istifadə olunur, burada sətirlər və sütunlar qrafın təpələrinə uyğun gəlir. Hüceyrədəki dəyər iki təpə arasındakı ən qısa məsafəni göstərir.

Vaxt mürəkkəbliyi: O(V^3), burada V — təpələrin sayı

Python-da kod nümunəsi:

def floyd_warshall(graph):
    v = len(graph)
    dist = list(map(lambda i: list(map(lambda j: j, i)), graph))
            
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
            
    return dist
        
        

5.4 Dinamik proqramlaşdırmanın digər metodlarla müqayisəsi.

Brute force metodu ilə müqayisə:

Zaman mürəkkəbliyi:

• Brute force: tez-tez eksponensial zaman mürəkkəbliyinə malikdir (məsələn, O(2^n) Fibonacci məsələsi üçün).
• Dinamik proqramlaşdırma: zaman mürəkkəbliyini polinomial mürəkkəbliyə azaldır (məsələn, Fibonacci məsələsi üçün O(n)).

Məkan mürəkkəbliyi:

• Brute force: daha az yaddaş istifadə edə bilər, amma zaman xərcləri yüksək olur.
• Dinamik proqramlaşdırma: ara nəticələrin saxlanması üçün daha çox yaddaş istifadə edə bilər (məsələn, memoization ilə Fibonacci məsələsi üçün O(n)), amma zamanda üstünlük qazanır.

Greedy algorithms metodu ilə müqayisə:

Optimality:

• Greedy algorithms: həmişə qlobal optimal həll tapmır, amma daha tez işləyir və həyata keçirmə daha sadədir.
• Dinamik proqramlaşdırma: qlobal optimal həll tapır, amma daha çox hesablamalı resurs tələb edir.

Məsələlərə misallar:

• Greedy algorithms: fractional knapsack məsələsi, minimum spanning tree (MST).
• Dinamik proqramlaşdırma: integer knapsack məsələsi, ən böyük ümumi alt ardıcıllıq (LCS).