Dynamické programovanie

Pri niektorých úlohách nestačí skúsiť všetky možnosti. Počet možností rastie príliš rýchlo a rovnaké čiastkové výpočty sa opakujú znova a znova.

Dynamické programovanie rieši tento problém tým, že si výsledky už vyriešených podproblémov zapamätá.

Dynamické programovanie je spôsob návrhu algoritmov, pri ktorom sa snažíme identifikovať a využiť už existujúce riešenia.

Cieľ prezentácie

Na konci by sme mali vedieť:

  • rozlíšiť dynamické programovanie od spätného prehľadávania,
  • nájsť stav a menší podproblém,
  • použiť memoizáciu alebo tabuláciu,
  • vysvetliť, kde sa pri backtrackingu vykonáva krok späť.

Kedy ho používame?

Typické otázky:

  • Aká je najlepšia možná hodnota?
  • Koľkými spôsobmi sa dá dosiahnuť cieľ?
  • Aké je najkratšie alebo najlacnejšie riešenie?

Myšlienka dynamického programovania:

  • vypočítaj podproblém raz,
  • ulož jeho výsledok,
  • pri ďalšom výskyte ho už len použi.

Základná myšlienka

Zložité problémy rozkladá na jednoduchšie podproblémy, každý podproblém rieši iba raz a jeho výsledok si uloží.

Ide o „pamätanie si minulosti“, aby sa ďalšie kroky dali riešiť efektívnejšie.

Správne fungovanie tejto techniky závisí od dvoch kľúčových vlastností:

Prekrývajúce sa podproblémy: Problém sa dá rozdeliť na menšie podproblémy, ktoré sa používajú viackrát.

Optimálna podštruktúra: Optimálne riešenie celého problému sa dá zostaviť kombináciou optimálnych riešení jeho podproblémov.

Príklady použitia dynamického programovania

Fibonacciho čísla: Výpočet postupnosti sčítaním dvoch predchádzajúcich čísel.

Problém batohu: Hľadanie najhodnotnejšej kombinácie predmetov, ktoré sa zmestia do batoha s obmedzenou nosnosťou.

Algoritmy najkratšej cesty: Určenie najkratšej cesty v sieti alebo grafe.

Editačná vzdialenosť: Hľadanie minimálneho počtu úprav potrebných na premenu jedného textového reťazca na druhý.

Ďalšie príklady: počet ciest v mriežke, plánovanie úloh, rozdelenie mincí alebo najdlhšia spoločná podpostupnosť.

Motivačný príklad: schody

Z každého schodu môžeme vystúpiť o 1 alebo 2 schody. Koľkými spôsobmi sa dostaneme na vrchol?

def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

Pri výpočte ways(5) sa rovnaké hodnoty počítajú opakovane. Dynamické programovanie ich vypočíta raz a uloží.

Schody: memoizácia a tabulácia

Memoizácia rieši problém zhora nadol a výsledky ukladá počas rekurzie:

from functools import lru_cache

@lru_cache
def ways(n):
    if n <= 1:
        return 1
    return ways(n - 1) + ways(n - 2)

Tabulácia rieši najmenšie prípady ako prvé:

def ways(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Obe riešenia majú časovú zložitosť O(n).

Praktický príklad: problém batohu (Knapsack)

Do batoha sa zmestí capacity kilogramov. Vyberáme predmety tak, aby bola ich celková hodnota čo najväčšia.

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)

    for weight, value in zip(weights, values):
        for current in range(capacity, weight - 1, -1):
            dp[current] = max(
                dp[current],
                dp[current - weight] + value
            )

    return dp[capacity]

print(knapsack([2, 3, 4], [4, 5, 7], 7))

dp[current] znamená najlepšiu hodnotu pre danú nosnosť. Kapacitu prechádzame odzadu, aby sme jeden predmet nepoužili viackrát.

Dynamické programovanie verzus backtracking

Dynamické programovanie Spätné prehľadávanie
ukladá výsledky podproblémov ukladá aktuálnu cestu rozhodnutí
využíva opakujúce sa podproblémy skúša možnosti v rozhodovacom strome
hľadá optimum, počet alebo dosiahnuteľnosť hľadá jedno alebo všetky platné riešenia
batoh, Fibonacci, edit distance Sudoku, permutácie, 8 kráľovien

DP si pamätá výsledky. Backtracking si pamätá cestu.

Príklad: cesta v bludisku

Bludisko riešime skúšaním možných ciest. Ak cesta nevedie do cieľa, vrátime posledný krok späť.

Ide o ukážku spätného prehľadávania.

Tento konkrétny algoritmus nie je dynamické programovanie: hľadá cestu a pri neúspechu odstráni posledný krok. DP verzia by si napríklad ukladala najlepší výsledok pre každú pozíciu.

Bludisko: rekurzívna funkcia

def solve_maze(maze, x, y, path):
    n = len(maze)

    # cieľ
    if x == n - 1 and y == n - 1:
        path.append((x, y))
        return True

    # kontrola platnosti
    if x >= 0 and y >= 0 and x < n and y < n and maze[x][y] == 1:
        path.append((x, y))
        maze[x][y] = 0  # označ ako navštívené

        # pohyb: dole, vpravo
        if solve_maze(maze, x + 1, y, path) or solve_maze(maze, x, y + 1, path):
            return True

        path.pop()  # krok späť
        return False

    return False

Bludisko: spustenie

maze = [
    [1, 0, 0],
    [1, 1, 0],
    [0, 1, 1]
]

path = []
solve_maze(maze, 0, 0, path)
print(path)

Naivné prehľadávanie

  1. Postupne generuj všetky možné riešenia
  2. Over či je riešenie vhodné
  3. Ak je riešenie vhodné, skonči. Inak pokračuj

Príklad (Python): Naivné generovanie permutácií

from itertools import permutations

nums = [1, 2, 3]

for p in permutations(nums):
    print(p)

Spätné prehľadávanie

Programátorská technika na riešenie kombinátorických úloh s obmedzeniami

  • Máme danú množinu možných riešení
  • Hľadáme správne riešenie

Ako funguje spätné prehľadávanie?

  • Rekurzívny algoritmus
  • Je definované finálne riešenie
  • Je definované čiastkové riešenie
  • Vieme povedať či čiastkové riešenie vedie k finálnemu riešeniu alebo nie

Spätné prehľadávanie je vylepšená verzia hrubej sily. Namiesto slepého generovania úplných riešení postupuje cez „rozhodovací strom“ možností:

Vyber: Urob rozhodnutie, ktorým sa posunieš ďalej po jednej možnej vetve.

Preskúmaj: Pokračuj po tejto konkrétnej vetve pomocou rekurzie.

Vyhodnoť (orež): Skontroluj, či aktuálne čiastkové riešenie neporušuje pravidlá alebo obmedzenia.

Vráť sa späť: Ak pravidlá porušuje, zruš posledné rozhodnutie, napríklad pomocou pop, a vyskúšaj ďalšiu dostupnú možnosť.

[]
├── [1]
│   ├── [1, 2]
│   └── [1, 3]
├── [2]
└── [3]

Orezanie neplatnej vetvy je hlavná výhoda oproti slepému generovaniu všetkých úplných riešení.

Permutácie pomocou spätného prehľadávania

def backtrack(nums, path, used):
    if len(path) == len(nums):
        print(path)
        return

    for i in range(len(nums)):
        if used[i]:
            continue

        used[i] = True
        path.append(nums[i])

        backtrack(nums, path, used)

        path.pop()       # späť
        used[i] = False  # späť

nums = [1, 2, 3]
backtrack(nums, [], [False]*len(nums))

Klasický šachový príklad: 8 kráľovien

8 kráľovien: kontrola pozície

N = 8

def is_safe(board, row, col):
    # kontrola stĺpca
    for i in range(col):
        if board[i] == row:
            return False

    # diagonály
    for i in range(col):
        if abs(board[i] - row) == abs(i - col):
            return False

    return True

8 kráľovien: riešenie

def solve(col, board):
    if col == N:
        print(board)
        return True

    for row in range(N):
        if is_safe(board, row, col):
            board[col] = row

            if solve(col + 1, board):
                return True

            board[col] = -1  # krok späť

    return False

board = [-1] * N
solve(0, board)

Vykreslenie šachovnice

def print_board(board):
    N = len(board)
    for row in range(N):
        for col in range(N):
            if board[col] == row:
                print("Q", end=" ")
            else:
                print(".", end=" ")
        print()

print_board(board)

Rozvrhovanie (problém s obmedzeniami)

Jednoduché priraďovanie (CSP)

students = ["A", "B", "C"]
rooms = ["R1", "R2"]

capacity = {
    "R1": 2,
    "R2": 1
}

def assign(i, assignment):
    if i == len(students):
        print(assignment)
        return True

    for room in rooms:
        if assignment.count(room) < capacity[room]:
            assignment.append(room)

            if assign(i + 1, assignment):
                return True

            assignment.pop()  # krok späť

    return False

assign(0, [])

Bonus: Min-konfliktová heuristika

Min-konflikty: výpočet konfliktov

import random

N = 8

def conflicts(board, col, row):
    count = 0
    for c in range(N):
        if c != col:
            if board[c] == row or abs(board[c] - row) == abs(c - col):
                count += 1
    return count

Min-konflikty: hlavný cyklus

def min_conflicts(max_steps=1000):
    board = [random.randint(0, N-1) for _ in range(N)]

    for _ in range(max_steps):
        conflicted = [c for c in range(N) if conflicts(board, c, board[c]) > 0]
        if not conflicted:
            return board

        col = random.choice(conflicted)
        board[col] = min(range(N), key=lambda r: conflicts(board, col, r))

    return None

solution = min_conflicts()
print(solution)

Sudoku (klasický príklad spätného prehľadávania)

  • Máme 9x9 mriežku
  • Niektoré čísla sú predvyplnené

  • Cieľ: doplniť čísla 1–9 tak, aby:

    • v každom riadku boli unikátne
    • v každom stĺpci boli unikátne
    • v každom 3x3 bloku boli unikátne

Sudoku: kontrola kandidáta

def is_valid(board, row, col, num):
    # riadok
    for i in range(9):
        if board[row][i] == num:
            return False

    # stĺpec
    for i in range(9):
        if board[i][col] == num:
            return False

    # 3x3 blok
    start_row = row - row % 3
    start_col = col - col % 3

    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == num:
                return False

    return True

Sudoku: rekurzívny riešiteľ

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == 0:  # prázdne miesto
                for num in range(1, 10):
                    if is_valid(board, row, col, num):
                        board[row][col] = num

                        if solve_sudoku(board):
                            return True

                        board[row][col] = 0  # krok späť

                return False
    return True

Sudoku: zadanie

board = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],

    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],

    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

solve_sudoku(board)

for row in board:
    print(row)

Sudoku: použitie riešiteľa

  • Čiastkové riešenie: čiastočne vyplnená tabuľka
  • Rozhodnutie: aké číslo vložiť do prázdnej bunky
  • Kontrola: funkcia is_valid

  • Spätné prehľadávanie:

    • vlož číslo
    • skús riešiť ďalej
    • ak to nefunguje → vráť (0)

Sudoku: čo sa deje?

  • V najhoršom prípade: približne O(9^n), kde n je počet prázdnych buniek

  • V praxi:

    • výrazne menej vďaka obmedzeniam

Zložitosť a možné vylepšenia

Pri Sudoku môžeme vždy vybrať prázdnu bunku s najmenším počtom kandidátov (MRV). Tým sa nesprávne vetvy odhalia čo najskôr.

Krátke cvičenia

  1. Upravte Fibonacciho funkciu tak, aby vrátila aj počet vykonaných volaní.
  2. Vyriešte počet ciest robota v mriežke, ktorý sa môže pohybovať iba doprava a dole.
  3. Napíšte backtracking, ktorý vypíše všetky podmnožiny zoznamu [1, 2, 3].
  4. Upravte riešenie 8 kráľovien tak, aby vypísalo všetky riešenia, nie iba prvé.

Dve podoby dynamického programovania

Memoizácia (zhora nadol): Problém rozkladáme rekurzívne a pred výpočtom výsledku skontrolujeme úložnú tabuľku, napríklad pole alebo mapu. Ak sa riešenie už v tabuľke nachádza, použijeme ho. Ak nie, vypočítame ho a uložíme na neskôr.

Tabulácia (zdola nahor): Najprv riešime najmenšie podproblémy, postupne z nich skladáme väčšie riešenia a ukladáme ich do tabuľky.

Zhrnutie

  • Dynamické programovanie rieši opakujúce sa podproblémy a výsledky si pamätá.
  • Memoizácia je prístup zhora nadol, tabulácia zdola nahor.
  • Spätné prehľadávanie skúša rozhodnutia a pri neúspechu vykoná pop().
  • Heuristiky a orezávanie môžu exponenciálne zmenšiť prehľadávaný priestor.

Bibliografia

Reload?