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á.

Dyunamick0 programovanie je sp;sob mn8vrhu algoritmov, pri ktorom sa sna69me identifikovať a využiť u ý existujúce riešmia.

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.

Riešenie hlavolamov:

  • Sudoku, hľadanie cesty v bludisku, krížovky, scrabble

Parsovanie:

  • Chceme zistiť, či je zápis platný pre daný programovací jazyk.

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, napríklad pomocou Bellmanovho-Fordovho alebo Floydovho-Warshallovho algoritmu.

Editačná vzdialenosť: Hľadanie minimálneho počtu úprav, teda vložení, odstránení a nahradení, potrebných na premenu jedného textového reťazca na druhý.

Príklad (Python): Hľadanie cesty v bludisku

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

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

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 v podstate vylepšená a optimalizovaná verzia hrubej sily. Namiesto slepého generovania všetkých ú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ť.

Príklad (Python): Generovanie permutácií 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

Riešenie spätným prehľadávaním (Python)

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

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)

Príklad (Python): 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, [])

Min-konfliktová heuristika

Príklad (Python): Min-konflikty pre N kráľovien (zjednodušené)

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

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

Príklad (Python): Riešiteľ sudoku

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

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

Použitie

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)

Vysvetlenie (dôležité pre študentov)

  • Č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)

Zložitosť

  • V najhoršom prípade: O(9^(n²)) (veľmi veľké)

  • V praxi:

    • výrazne menej vďaka obmedzeniam

Možné vylepšenia (pre pokročilých)

  • výber bunky s najmenším počtom možností (MRV heuristika)
  • dopredná kontrola
  • použitie množín namiesto cyklov

Existujú dva hlavné spôsoby implementácie tejto techniky:

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. Tieto uložené výsledky potom používame na výpočet odpovede pre väčší problém, až kým sa nedostaneme k finálnemu cieľu.

Bibliografia

Reload?