Застосування ДП у реальних задачах

7.1 Оптимізація динамічних алгоритмів.

Оптимізація динамічних алгоритмів спрямована на покращення їхньої часової та просторової ефективності. Існує декілька підходів до оптимізації, включаючи використання мемоізації, скорочення використаної пам'яті та оптимізацію рекурсії.

1. Мемоізація:

Мемоізація — це техніка, при якій результати обчислень зберігаються, щоб уникнути повторних обчислень тієї самої підзадачі.

Приклад:

У задачі про розмін монет, якщо використовувати рекурсивний підхід, можна зберігати результати для вже обчислених сум, щоб уникнути повторних обчислень.

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. Табличне рішення (Bottom-Up):

Табличне рішення (bottom-up) будує таблицю рішень для всіх можливих підзадач від базового випадку до цільової задачі. Це дозволяє уникнути накладних витрат на рекурсивні виклики.

Приклад:

У задачі про рюкзак побудова таблиці мінімальних кількостей монет для кожної суми від 0 до S.

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. Скорочення використаної пам'яті:

У деяких задачах можна оптимізувати використання пам'яті, скорочуючи розмір таблиці або масиву, використовуваного для зберігання проміжних результатів.

Приклад:

У задачі про рюкзак можна використовувати одновимірний масив замість двовимірної таблиці, якщо зберігати тільки поточний і попередній ряди.

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. Хвостова рекурсія:

Хвостова рекурсія — це рекурсивний виклик, який виконується в кінці функції. Це дозволяє компілятору або інтерпретатору оптимізувати стек викликів.

Приклад:

У задачі обчислення чисел Фібоначчі можна використовувати хвостову рекурсію з накопичувачем результату.

7.2 Застосування динамічного програмування у реальних задачах.

Динамічне програмування знаходить широке застосування в різних галузях, включаючи комп'ютерні науки, економіку, біоінформатику та операційні дослідження. Ось кілька прикладів його використання у реальних задачах:

1. Оптимізація маршрутів та логістика:

У задачах логістики та транспортних систем динамічне програмування використовується для знаходження оптимальних маршрутів та мінімізації витрат.

Приклад:

Задача комівояжера (Travelling Salesman Problem, TSP) — знайти найкоротший шлях, проходячи через усі міста.

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. Вирівнювання послідовностей у біоінформатиці:

У біоінформатиці динамічне програмування використовується для вирівнювання ДНК, РНК та білкових послідовностей.

Приклад:

Алгоритм Нідлмана-Вунша (Needleman-Wunsch) для глобального вирівнювання послідовностей та алгоритм Сміта-Ватермана (Smith-Waterman) для локального вирівнювання.

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. Фінансові розрахунки та економічне планування:

Динамічне програмування застосовується для оптимізації інвестиційних портфелів, управління ризиками та планування виробництва.

Приклад:

Задача про розмін монет і задача про рюкзак використовуються для управління активами та оптимального розподілу ресурсів.

4. Управління запасами та виробництвом:

У виробництві та управлінні запасами динамічне програмування допомагає оптимізувати процеси та мінімізувати витрати.

Приклад:

Модель управління запасами (Inventory Management Model) для мінімізації витрат на зберігання та замовлення продукції.

5. Машинне навчання та штучний інтелект:

У машинному навчанні динамічне програмування використовується для оптимізації алгоритмів та знаходження глобальних оптимумів.

Приклад:

Алгоритми навчання на основі динамічного програмування, такі як метод зворотного поширення в нейронних мережах.