Dİ-ni real tapşırıqlarda tətbiq etmək

7.1 Dinamik alqoritmlərin optimallaşdırılması.

Dinamik alqoritmlərin optimallaşdırılması onların vaxt və yaddaş effektivliyini artırmağa yönəlir. Optimallaşdırma üçün bir neçə yanaşma mövcuddur, o cümlədən memoization tətbiqi, yaddaş istifadəsinin azaldılması və rekursiyanın optimallaşdırılması.

1. Memoization:

Memoization – bu texnikadır, hansı ki hesablamaların nəticələri saxlanılır ki, təkrarən eyni altvəzifəni hesablamaqdan yayınsın.

Nümunə:

Pul əskinaslarının dəyişdirilməsi məsələsində, əgər rekursiv yanaşmadan istifadə edilərsə, artıq hesablanmış cəmlər üçün nəticələri saxlamaq olar ki, təkrardan hesablamaların qarşısı alınsın.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
        
        

2. Cədvəl həlli (Bottom-Up):

Tablica həlli (bottom-up) əsas vəziyyətdən hədəf vəzifəyə qədər bütün mümkün altvəzifələrin həlli üçün bir cədvəl qurur. Bu, rekursiv çağırışlarla bağlı yüklənmələrdən yayınmağa imkan verir.

Nümunə:

Rükzak məsələsində hər bir cəm üçün minimal pul əskinaslarının cədvəlini qurmaq.

def fibonacci(n):
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
        
        

3. Yaddaş istifadəsinin azaldılması:

Bəzi məsələlərdə yaddaş istifadəsini optimallaşdırmaq olar, yəni aralıq nəticələri saxlamaq üçün istifadə olunan cədvəlin və ya massivlərin ölçüsünü azaltmaqla.

Nümunə:

Rükzak məsələsində yalnız cari və əvvəlki sətri saxlamaqla, iki ölçülü cədvəl əvəzinə bir ölçülü massivdən istifadə etmək olar.

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

4. Tail Rekursiya:

Tail rekursiya – bu, funksiyanın sonunda yerinə yetirilən rekursiv çağırışdır. Bu, kompilyatora və ya interpretatora çağırış stekini optimallaşdırmağa imkan verir.

Nümunə:

Fibonacci rəqəmlərinin hesablanması məsələsində nəticə toplayıcı ilə tail rekursiyadan istifadə etmək olar.

7.2 Dinamik proqramlaşdırmanın real məsələlərdə tətbiqi.

Dinamik proqramlaşdırma müxtəlif sahələrdə geniş tətbiq olunur, o cümlədən komputer elmləri, iqtisadiyyat, bioinformatika və əməliyyat araşdırmaları. Onun real məsələlərdə istifadəsinin bir neçə nümunəsi:

1. Marşrutların optimallaşdırılması və logistika:

Logistika və nəqliyyat sistemlərində dinamik proqramlaşdırma optimal marşrutları tapmaq və xərcləri minimallaşdırmaq üçün istifadə olunur.

Nümunə:

Kommi-voyajer problemi (Travelling Salesman Problem, TSP) — bütün şəhərlərdən keçən ən qısa yolu tapmaq.

def tsp(graph, start):
    n = len(graph)
    dp = [[None] * (1 << n) for _ in range(n)]

    def visit(city, visited):
        if visited == (1 << n) - 1:
            return graph[city][start]
        if dp[city][visited] is not None:
            return dp[city][visited]
        result = float('inf')
        for next_city in range(n):
            if visited & (1 << next_city) == 0:
                result = min(result, graph[city][next_city] + visit(next_city, visited | (1 << next_city)))
        dp[city][visited] = result
        return result

    return visit(start, 1 << start)

2. Bioinformatikada ardıcıllıqların düzülməsi:

Bioinformatikada dinamik proqramlaşdırma DNT, RNT və zülalları düzülmək üçün istifadə olunur.

Nümunə:

Needleman-Wunsch alqoritmi ardıcıllığın qlobal düzülməsi üçün və Smith-Waterman alqoritmi lokal düzülmə üçün istifadə olunur.

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
        

3. Maliyyə hesablamaları və iqtisadi planlaşdırma:

Dinamik proqramlaşdırma investisiya portfellərinin optimallaşdırılması, risklərin idarə olunması və istehsal planlaması üçün istifadə edilir.

Nümunə:

Sikkə dəyişmə problemi və çanta problemi aktivlərin idarə olunması və resursların optimal paylanması üçün istifadə olunur.

4. Ehtiyatların və istehsalın idarə edilməsi:

İstehsal və ehtiyatların idarə olunmasında dinamik proqramlaşdırma prosesləri optimallaşdırmaq və xərcləri minimallaşdırmaq üçün kömək edir.

Nümunə:

Ehtiyatların idarə olunma modeli (Inventory Management Model) məhsulların saxlanma və sifariş xərclərini minimallaşdırmaq üçün istifadə olunur.

5. Maşın öyrənməsi və süni intellekt:

Maşın öyrənməsində dinamik proqramlaşdırma alqoritmləri optimallaşdırmaq və qlobal optimumları tapmaq üçün istifadə olunur.

Nümunə:

Dinamik proqramlaşdırmaya əsaslanan öyrənmə alqoritmləri, misal üçün, neyron şəbəkələrdə backpropagation metodu.