Obsah

IN19 Metody konstrukce efektivních algoritmů

Zadanie

(Rozděl a panuj. Dynamické programování. Hladové strategie. Backtracking. Meze použitelnosti i jednotlivých technik. Příklady algoritmů postavených na jednotlivých technikách.)

Vypracovanie

Rozdeľ a panuj

Túto techniku je možné ľahko popísať týmito krokmi.

  1. Problém rozdeľ na prodproblémy
  2. Vyrieš podproblémy
  3. Z riešení podproblémov zostav riešenie

Problém 1, Maximálny a minimálny prvok

Problém nájdenia maximálneho a minimálneho prvku postupnosti
S[1..n]. Zložitostné kritérium - počet porovnaní prvkov.

Riešenie

Algoritmus 1, Naivný algoritmus riešiaci problém maximálneho prvku

Max(S) 
1 max ← S[1] 
2 for i = 2 to n do 
3   if S[i] > max then max ← S[i] fi 
4 od

Procedúra Max nájde najväčší prvok, podobne sa nájde medzi ostatnými prvkami najmenší prvok. Časová zložitosť tohto algoritmu je zrejme (n - 1), pokud k tomu přidáme složitost hledání minimálního prvku (n-2) (hľadáme už len medzi n-1 prvkami) máme 2n-3.

  1. Pole rozdeľ na 2 rovnaké postupnosti
  2. Nájdi minimum a maximum oboch postupností
  3. Maximálny prvok postupnosťí je väčší z maximálnych prvkov podpostupností, podobne minimálny

Algoritmus 2, Rozdeľ a panuj algoritmus riešiaci problém maximálneho a minimálneho prvku

function Maxmin(x, y) **predpoklad x < y 
1  if y = x + 1 then return (max(S[x], S[y]),min(S[x], S[y])) fi 
2  if y = x + 2 
3    then použitím 3 porovnaní utrieď S[x], S[x + 1], S[y] 
4    return (max, min) 
5  fi 
6  if y > x + 2 then 
7    (max1, min1) ← Maxmin(x, ⌊(x + y)/2⌋) 
8    (max2, min2) ← Maxmin(⌊(x + y)/2⌋ + 1, y) 
9    return (max(max1, max2), min(min1, min2)) 
10 fi

Ľahko dokážeme, že tento algoritmus je korektný. Jeho časová zložitosť je:
T(n)= \left\{ \begin{array}{ll} 1 & \mbox{$n = 2$}\\ 3 & \mbox{$n = 3$}\\ T(\lfloor n/2 \rfloor ) + T(\lceil n/2 \rceil) + 2 & \mbox{inak} \end{array} \right.

Indukciou sa dá ľahko dokázať, že T(n) \le \frac{5}{3}n - 2

Časovú zložitosť máme často určenú rekurzívne. Vtedy sa jej dôkaz často oplatí použiť tzv. Master Theorem.

Def. 1, Master Theorem

Ak T(n) \le a \cdot T(\lceil n/b \rceil) + O(n^d) pre kladné a, b, d, potom:
T(n)= \left\{ \begin{array}{ll} O(n^d) & \mbox{$a < b^d$}\\ O(n^d \cdot \log n) & \mbox{$a = b^d$}\\ O(n^{\log_b a}) & \mbox{$a > b^d$}\end{array} \right. Zde n je velikost problému, a je počet podproblémů, n/b je délka jednoho podproblému a O(n^d) udává časovou složitost výpočtu mimo rekurzivní volání, vč. samotného rozdělení problému na podproblémy a sestavení konečného řešení z částečných řešení.

Inými typickými príkladmi použitia Rozdeľ a panuj sú algoritmy mergesort, … .

Dynamické programovanie

  1. Charakterizuj štruktúru optimálneho riešenia optimálne riešenie problému v sebe zahrňuje optimálne riešenia podproblémov
  2. Rekurzívne definuj hodnotu optimálneho riešenia
  3. Vypočítaj hodnotu optimálneho riešenia zdola nahor
  4. Z vypočítaných hodnôt zostav optimálne riešenie

Táto technika je vhodná pre riešenie optimalizačných problémov, u ktorých dochádza k prekrývaniu podproblémov.

Problém 2, Najväčšia spoločná podpostupnosť

Nech X = < x_1,x_2, ..., x_n > a Z = < z_1,z_2, ..., z_m > sú postupnosti symbolov. Z je podpostupnosťou X práve vtedy, ak existuje rastúca postupnosť indexov i_1, i_2, ..., i_k postupnosti X taká, že pre všetky j = 1, …, k platí x_{i_j} = z_j.
Pre dané 2 postupnosti symbolov X a Y hovoríme, že Z je ich spoločnou podpostupnosťou práve ak Z je podpostupnosťou X aj Y.
Problém najdlhšej podpostupnosti je pre dané dve postupnosti X a Y nájsť ich najdlhšiu spoločnú podpostupnosť (NSP).

Štruktúra optimálneho riešenia problému najväčšej podpostupnosti

Označenie: pre postupnosť X = < x_1,x_2, ..., x_n > definujeme jej i-ty prefix (pre i=0,…,n) ako X_i = < x_1, ..., x_i > Nech X = < x_1,x_2, ..., x_n > a Y = < y_1, ..., y_m > sú postupnosti symbolov a nech Z = < z_1, ..., z_k > je ich NSP.

  1. Ak xn = ym, tak zk = xn = yn a Zk-1 je NSP postupností Xn-1 a Ym-1.
  2. Ak x_n \neq y_m a z_k \neq x_n, tak Z je NSP postupností Xn-1 a Y.
  3. Ak x_n \neq y_m a z_k \neq y_m, tak Z je NSP postupností X a Ym-1.

Hodnota optimálneho riešenia

Definujme c[i,j] ako dĺžku NSP postupností Xi a Yj. Platí
c[i,j] = \left\{ \begin{array}{ll} 0 & \mbox{ak i = 0 alebo j = 0}\\ c[i - 1, j - 1] + 1 & \mbox{ak $i, j > 0$ a $x_i = y_j$}\\ max(c[i, j - 1], c[i - 1, j]) & \mbox{ak $i, j > 0$ a $x_i \neq y_j$}\end{array} \right. Poradie výpočtu:
c[1,1],…,c[1,m]
c[2,1],…,c[2,m]
.
.
.
c[n,1],…,c[n,m]

Algoritmus 2, Výpočet optimálneho riešenia

NSP(X, Y) 
1 for i = 1 to m do c[i, 0] ← 0 od 
2 for j = 0 to n do c[0, j] ← 0 od 
3 for i = 1 to m do 
4   for j = 1 to n do 
5     if Xi = Yj then 
6       c[i, j] ← c[i − 1, j − 1] + 1 
7       b[i, j] ← ♣ 
8     else if c[i − 1, j] ≥ c[i, j − 1] then 
9       c[i, j] ← c[i − 1, j] 
10      b[i, j] ← ♠ 
11    else  
12      c[i, j] ← c[i, j − 1] 
13      b[i, j] ← ♥ 
14    fi fi od od 
15 return c, b

Algoritmus 2, Zostavenie optimálneho riešenia

Print NSP(b, X, i, j) 
1 if i = 0 ∨ j = 0 then return fi 
2 if b[i, j] = ♣ then  
3   Print NSP(b, X, i − 1, j − 1) 
4   print xi 
5 else if b[i, j] = ♠ then 
6   Print NSP(b, X, i − 1, j) 
7 else  
8   Print NSP(b, X, i, j − 1) 
9 fi fi

Ďalšími príkladmi dynamického programovanie sú algoritmy: Floydov algoritmus, Warshallov algoritmus, Konštrukcia vyváženého vyhľadávacieho stromu, … .

Hladové algoritmy

  1. Technika je vhodná pre riešenie optimalizačných problémov, ktoré majú optimálnu subštruktúru (Optimálne riešenie problému v sebe obsahuje optimálne riešenie podproblémov).
  2. Pre získanie optimálneho riešenie stačí poznať optimálne riešenie jedného z podproblémov. Tento podproblém vyberáme na základe kritéria lokálnej optimality (KLO), t.j. bez znalosti jeho riešenia.
  3. Vo výpočte postupujeme zhora nadol.

Táto technika však nie je použiteľná pre všetky optimalizačné problémy.

Problém 3, Problém pásky

Je daných n súborov dĺžky m1,…, mn . Súbory sa majú uložiť na pásku. Všetky súbory sa budú z pásky čítať. Prístupový čas k súboru i je rovný súčtu dĺžok súborov uložených pred ním plus jeho dĺžka mi. Úlohou je uložiť súbory na pásku v takom poradí, aby sa súčet jednotlivých prístupových časov k súborom minimalizoval.

Problém má optimálnu štruktúru, pretože ak ako prvý uložíme na pásku súbor i, ostané súbory musíme usporiadať optimálne.

Hladový algoritmus: KLO = vyber spomedzi ešte neuložených súbor najkratší a ulož ho na pásku (t.j. ulož na pásku súbory od najkratsieho po najdlhší)

Dôkaz, že je takýto algoritmus naozaj korektný je možné nájsť v slajdoch k predmetnu Návrh algoritmů II.

Medzi iné hladové algoritmy patrí Dijsktrov algoritmus, Primov a Kruskallov algoritmus pre najlacnejšie kostry, Huffmanove kódy, …

Bactracking

Technika prehľadávania priestoru potencionálnych riešení založená na princípe Rozdeľ a panuj.

  1. Voľba spôsobou reprezentácie potencionálnych riešení
  2. Generovanie potencionálnych riešení technikou rozdeľ a panuj
  3. Testovanie požadovanej vlastnosti
  4. Odrezávanie neperspektívnych ciest

Problém 4, Problém tyčí

Daných je n tyčí dĺžky d1,…,dn a číslo D \in \mathbb{N}. Úlohou je vybrať tyče tak, aby súčet ich dĺžok bol presne D.

Rešenie

  1. Potencionálne riešenia sú všetky spôsoby výberu tyčí. Riešenia budeme reprezentovať ako binárne reťazce, konkrétne pomocou binárneho poľa A[1..n]. A[i]=1 ak tyč i bola vybraná. Binárne reťazce vytvárajú stromovú štruktúru.
  2. Strom prehľadávame do hĺbky: pole A napĺňame zprava
  3. Požadovanú vlastnosť testujeme vtedy, ak máme vygenerované celé potenciálne riešenie.
  4. Cesty odrezávame, keď dĺžka vybraných tyčí prekročí daný limit.

Pozn. Tento problém je riešiteľný dynamickým programovaním v O(nD).

Algoritmus 3, Algoritmus riešiaci problém n-tyčí

Tyč(m, l) 
1  if m = 0 then  
2    if l = 0 then print A fi 
3  else  
4    A[m] ← 0 
5    Tyč(m − 1, l) 
6 
7    if dm ≤ l then  
8      A[m] ← 1 
9      Tyč(m − 1, l − dm) 
10   fi 
11 fi

Pri používaní backtrackingu budeme často potrebovať preskúšať všetky permutácie. Tu je algoritmus na ich zistenie.

Algoritmus 4, Algoritmus pre získanie všetkých permutácií

procedure Permutácie(m) 
1 if m = 1 then kontrola vlastností else Permutácie(m − 1) 
2 for i = m − 1 downto 1 do 
3   vymeň A[m] a A[i] 
4   Permutácie(m − 1) 
5   vymeň A[m] a A[i] 
6 od fi

Predmety

Použitá literatúra

Vypracoval

Ľuboš Pecho, 172463, tomorrow@mail.muni.cz, 18.6.2008