IN19 Metody konstrukce efektivních algoritmů

(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.)

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

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

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:

Indukciou sa dá ľahko dokázať, že

Č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 pre kladné a, b, d, potom:
Zde je velikost problému, je počet podproblémů, je délka jednoho podproblému a 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, … .

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 = a Z = sú postupnosti symbolov. Z je podpostupnosťou X práve vtedy, ak existuje rastúca postupnosť indexov postupnosti X taká, že pre všetky j = 1, …, k platí .
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).

Označenie: pre postupnosť X = definujeme jej i-ty prefix (pre i=0,…,n) ako Nech X = a Y = sú postupnosti symbolov a nech Z = je ich NSP.

1. Ak x_n = y_m, tak z_k = x_n = y_n a Z_k-1 je NSP postupností X_n-1 a Y_m-1.
2. Ak a , tak Z je NSP postupností X_n-1 a Y.
3. Ak a , tak Z je NSP postupností X a Y_m-1.

Definujme c[i,j] ako dĺžku NSP postupností X_i a Y_j. Platí
Poradie výpočtu:
c[1,1],…,c[1,m]
c[2,1],…,c[2,m]
.
.
.
c[n,1],…,c[n,m]

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 

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, … .

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 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, …

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

• do priestoru potencionálnych riešení vnesieme stromovú štruktúru, (binárne reťazce, k-arne reťazce, permutácie, kombinácie)
• stromovú štruktúru prehľadávame do hĺbky
• prehľadávanie zefektívnime odrezávaním ciest, ktoré dokázateľne nevedú k hľadanému riešeniu

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 d₁,…,d_n a číslo . Úlohou je vybrať tyče tak, aby súčet ich dĺžok bol presne D.

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

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.

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 

• FI:IB108 Návrh algoritmů II, prof. RNDr. Ivana Černá, CSc.

• prof. RNDr. Ivana Černá, CSc., slajdy z přednášok

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