Основи динамічного програмування

5.1 Визначення динамічного програмування.

Динамічне програмування (Dynamic Programming, DP) — це метод оптимізації, що використовується для вирішення складних задач шляхом розбиття їх на простіші підзадачі. Динамічне програмування ефективно використовується для задач, які можна розділити на перекриваючі підзадачі з оптимальною структурою підзадач.

Принципи роботи:

1. Оптимальна підструктура:

Задача має оптимальну підструктуру, якщо її оптимальне рішення можна побудувати з оптимальних рішень її підзадач. Це означає, що можна вирішити велику задачу, вирішивши кілька менших підзадач.

2. Перекриваючі підзадачі:

Задача має перекриваючі підзадачі, якщо її підзадачі повторюються декілька разів у процесі вирішення задачі. Динамічне програмування ефективно вирішує задачі з перекриваючими підзадачами шляхом запам'ятовування результатів вже вирішених підзадач (мемоізація).

3. Мемоізація та табуляція:

Мемоізація (зверху вниз): Рекурсивний підхід, при якому результати підзадач зберігаються в пам'яті для уникнення повторних обчислень.

Табуляція (знизу вверх): Ітеративний підхід, при якому результати підзадач обчислюються і зберігаються в таблиці (зазвичай масиві) і використовуються для обчислення кінцевого результату.

Приклади задач, що вирішуються методом динамічного програмування

5.2 Задача про рюкзак.

Задача:

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

Важливо! На відміну від аналогічної задачі, яка добре вирішувалася жадібним алгоритмом, у цій задачі ділити предмети не можна.

Рішення:

Створюється таблиця, де рядки відповідають предметам, а стовпці — можлива вмістимість рюкзака. Значення в комірці представляє максимальну вартість для даного числа предметів і вмістимості.

Часова складність: O(n * W), де n — кількість предметів, W — вмістимість рюкзака.

Приклад коду на Python:

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 Задача про знаходження найменшого шляху

Задача:

Знайти найкоротші шляхи між всіма парами вершин зваженого графу.

Рішення:

Використовується таблиця, де рядки та стовпці відповідають вершинам графу. Значення в комірці представляє найкоротшу відстань між двома вершинами.

Часова складність: O(V^3), де V — кількість вершин

Приклад коду на Python:

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 Порівняння динамічного програмування з іншими методами.

Порівняння з методом грубої сили (brute force):

Часова складність:

• Груба сила: часто має експоненційну часову складність (наприклад, O(2^n) для задачі Фібоначчі).
• Динамічне програмування: зменшує часову складність до поліноміальної (наприклад, O(n) для задачі Фібоначчі).

Просторова складність:

• Груба сила: може використовувати менше пам'яті, але часові витрати високі.
• Динамічне програмування: може використовувати більше пам'яті для збереження проміжних результатів (наприклад, O(n) для задачі Фібоначчі з мемоізацією), але виграє в часі.

Порівняння з методом жадібних алгоритмів (greedy algorithms):

Оптимальність:

• Жадібні алгоритми: не завжди знаходять глобально оптимальне рішення, але працюють швидше і простіше в реалізації.
• Динамічне програмування: знаходить глобально оптимальне рішення, але вимагає більше обчислювальних ресурсів.

Приклади задач:

• Жадібні алгоритми: задача про рюкзак з дробами (fractional knapsack), мінімальне остове дерево (MST).
• Динамічне програмування: задача про рюкзак (цілочисельна), найбільша спільна підпослідовність (LCS).