Prednáška 11

Oznamy

• DÚ2 je zverejnená, odovzdávajte do piatka 13.11. 22:00
• Nezabudnite, že ak z cvičení za týždeň neodovzdáte úspešne ani jeden príklad, dostanete -5 bodov. Takisto je vhodné nazbierať z DÚ a cvičení aspoň polovicu bodov, lebo inak budete mať problém získať celkovo dosť bodov z predmetu.
• Na DÚ pracujte samostatne. Ak nájdeme prípad opisovania, všetky zúčastnené strany dostanú z úlohy 0 bodov.
• Plán na dnes: najskôr si ukážeme dva rekurzívne algoritmy na triedenie, potom sa vrátime k minulej téme prehľadávania s návratom.
• Od budúceho týždňa prednáša kolega Kostolányi, začínate novú tému práca so smerníkmi a pamäťou. Rekurzia sa ale ešte párkrát počas semestra vráti.

Rýchle triedenia prostredníctvom paradigmy „rozdeľuj a panuj”

Doposiaľ sme prebrali tri triediace algoritmy: Bubble Sort, Insertion Sort a Max Sort. Všetky sú jednoduché, ale pomalé: majú kvadratickú zložitosť O(n²).

Dnes pridáme ďalšie dve triedenia, ktoré budú pre veľké polia omnoho rýchlejšie: Merge Sort a Quick Sort. Obe sú založené na paradigme rozdeľuj a panuj (angl. divide and conquer, lat. divide et impera).

Rozdeľuj a panuj je paradigma rekurzívneho riešenia problémov pracujúca v troch fázach:

• Rozdeľuj – problém rozdelíme na menšie časti (t.j. podproblémy), ktoré sa dajú riešiť samostatne.
• Vyrieš podproblémy – rekurzívne vyriešime úlohu pre každý podproblém.
• Panuj – riešenia podproblémov spojíme do riešenia pôvodného problému.

Triedenie zlučovaním (Merge Sort)

Triedenie zlučovaním (angl. Merge Sort) pracuje nasledovne:

• Pole rozdelíme na dve približne rovnaké časti
• Každú časť zvlášť rekurzívne utriedime
• Vo fáze „panuj” sa tieto dve utriedené postupnosti zlúčia (angl. merge) do výsledného utriedeného poľa.

Triedenie zlučovaním tak bude vyzerať nasledovne (pričom zostáva doimplementovať funkciu merge):

void mergesort(int a[], int left, int right) {
/* Funkcia utriedi prvky pola a[] od indexu left po index right (vratane). */
    
    /* Trivialne pripady: */
    if (left >= right) {
        return;           
    }
    
    /* Rozdeluj -- spocitaj priblizny stred triedeneho useku: */
    int middle = (left + right) / 2;
          
    /* Rekurzivne vyries podproblemy: */
    mergesort(a, left, middle);
    mergesort(a, middle + 1, right);
       
    /* Panuj -- zluc obe utriedene casti do jednej: */ 
    merge(a, left, middle, right);
}

Zlúčenie dvoch utriedených podpostupností

Zostáva doprogramovať zlúčenie dvoch utriedených podpostupností a[left..middle], a[middle+1..right] do jednej utriedenej postupnosti. Zlúčenú postupnosť budeme postupne ukladať do pomocného poľa aux, pričom postupovať budeme nasledovne:

• Prvým prvkom poľa aux bude menší z prvkov a[left] a a[middle+1].
  • Ostanú nám postupnosti a[left+1..middle] a a[middle+1..right] alebo a[left..middle] a a[middle+2..right].
• Vo všeobecnosti máme postupnosti a[i..middle] a a[j..right].
  • Ďalším prvkom poľa aux bude menčí z prvkov a[i] a a[j]
  • Ostanú nám postupnosti a[i+1..middle] a a[j..right] alebo a[i..middle] a a[j+1..right].
• Toto robíme dovtedy, kým niektorú z postupností nevyčerpáme celú. Potom už len na koniec poľa aux dokopírujeme zvyšok druhej postupnosti.

Po spojení oboch postupností do utriedeného poľa aux toto pole prekopírujeme naspäť do poľa a.

void merge(int a[], int left, int middle, int right) {
    int aux[maxN];
    int i = left;       // index v prvej postupnosti
    int j = middle + 1; // index v druhej postupnosti
    int k = 0;          // index v poli aux
    
    while (i <= middle && j <= right) { 
        // Kym su obe postupnosti a[i..middle], a[j..right] neprazdne,
        // mensi z prvkov a[i], a[j] uloz do aux[k] a posun indexy
        if (a[i] <= a[j]) {                         
            aux[k] = a[i];
            i++;
            k++;
        } else {
            aux[k] = a[j];
            j++;
            k++;
        }
    }
    
    while (i <= middle) {  
        // Ak nieco ostalo v prvej postupnosti, dokopiruj ju na koniec
        aux[k] = a[i];
        i++;
        k++;
    }
    
    while (j <= right) { 
        // Ak nieco ostalo v druhej postupnosti, dokopiruj ju na koniec
        aux[k] = a[j];
        j++;
        k++;
    }
    
    for (int t = left; t <= right; t++) { 
        // Prekopiruj pole aux naspat do pola a
        a[t] = aux[t - left];
    }
}

Výsledný program

#include <iostream>
using namespace std;

const int maxN = 1000;

void merge(int a[], int left, int middle, int right) {
    int aux[maxN];
    int i = left;
    int j = middle + 1;
    int k = 0;
    
    while (i <= middle && j <= right) {
        if (a[i] <= a[j]) {
            aux[k] = a[i];
            i++;
            k++;
        } else {
            aux[k] = a[j];
            j++;
            k++;
        }
    }
    
    while (i <= middle) {
        aux[k] = a[i];
        i++;
        k++;
    }
    
    while (j <= right) {
        aux[k] = a[j];
        j++;
        k++;
    }
    
    for (int t = left; t <= right; t++) {
        a[t] = aux[t - left];
    }
}

void mergesort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }
    
    int middle = (left + right) / 2;
          
    mergesort(a, left, middle);
    mergesort(a, middle+1, right);
       
    merge(a, left, middle, right);
}

int main() {
    int N;
    int a[maxN];
    
    cout << "Zadaj pocet cisel: ";
    cin >> N;
    cout << "Zadaj " << N << " cisel: ";
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    
    mergesort(a,0,N-1);
    
    cout << "Utriedene cisla:";
    for (int i = 0; i < N; i++) {
        cout << " " << a[i];
    }                        
    cout << endl;
}

Ukážka na príklade

Uvažujme pole a = {6, 1, 5, 7, 2, 4, 8, 9, 3, 0}.

Volanie mergesort(a,0,9) potom utriedi pole a pomocou nasledujúcich rekurzívnych volaní (namiesto mergesort(a,l,h) budeme písať vždy len sort(l,h) a namiesto merge(a,l,m,h) len merge(l,m,h)):

sort(0,9) sort(0,4) sort(0,2) sort(0,1) sort(0,0) 
          .         .         .         sort(1,1)
          .         .         .         merge(0,0,1)
          .         .         sort(2,2)
          .         .         merge(0,1,2)
          .         sort(3,4) sort(3,3)
          .         .         sort(4,4)
          .         .         merge(3,3,4)
          .         merge(0,2,4)
          sort(5,9) sort(5,7) sort(5,6) sort(5,5)
          .         .         .         sort(6,6)
          .         .         .         merge(5,5,6)
          .         .         sort(7,7)
          .         .         merge(5,6,7)
          .         sort(8,9) sort(8,8)
          .         .         sort(9,9)
          .         .         merge(8,8,9)
          .         merge(5,7,9)
          merge(0,4,9)

Pole a sa počas týchto volaní mení nasledovne:

merge(a,0,0,1): |6|1|5 7 2 4 8 9 3 0  -> |1 6|5 7 2 4 8 9 3 0
merge(a,0,1,2): |1 6|5|7 2 4 8 9 3 0  -> |1 5 6|7 2 4 8 9 3 0
merge(a,3,3,4):  1 5 6|7|2|4 8 9 3 0  ->  1 5 6|2 7|4 8 9 3 0
merge(a,0,2,4): |1 5 6|2 7|4 8 9 3 0  -> |1 2 5 6 7|4 8 9 3 0
merge(a,5,5,6):  1 2 5 6 7|4|8|9 3 0  ->  1 2 5 6 7|4 8|9 3 0
merge(a,5,6,7):  1 2 5 6 7|4 8|9|3 0  ->  1 2 5 6 7|4 8 9|3 0
merge(a,8,8,9):  1 2 5 6 7 4 8 9|3|0| ->  1 2 5 6 7 4 8 9|0 3|
merge(a,5,7,9):  1 2 5 6 7|4 8 9|0 3| ->  1 2 5 6 7|0 3 4 8 9|
merge(a,0,4,9): |1 2 5 6 7|0 3 4 8 9| -> |0 1 2 3 4 5 6 7 8 9|

Odhad zložitosti

Zlučovanie dvoch postupností, ktoré spolu obsahujú N prvkov, trvá čas O(N). Prečo?

V algoritme máme log₂ N úrovní rekurzie:

• na prvej spracovávame úseky dĺžky N,
• na druhej N/2, na tretej N/4 atď,
• po log₂ N úrovniach dostaneme úseky dĺžky 1.

Na každej úrovni je každý prvok najviac v jednom zlučovaní, teda celkový čas zlučovaní na každej úrovni je O(N). Celkový čas výpočtu je O(N log N).

Quick Sort

Quick Sort je tiež založený na metóde rozdeľuj a panuj. Postupuje ale nasledovne:

• V rámci fázy rozdeľuj vyberie niektorý prvok poľa (napríklad jeho prvý prvok), ktorý nazve pivotom. Prvky poľa následne preusporiada na tri skupiny: v ľavej časti poľa budú prvky menšie ako pivot, za nimi pivot samotný a napokon v pravej časti prvky väčšie alebo rovné ako pivot.
• Rekurzívne utriedi prvú a tretiu skupinu (druhá skupina má iba jeden prvok)
• Vo fáze panuj už potom nemusí robiť nič – po utriedení spomínaných dvoch skupín totiž vznikne utriedené pole.

Základ triedenia tak bude vyzerať nasledovne (pričom zostáva implementovať funkciu partition):

void quicksort(int a[], int left, int right) {
/* Utriedi cast pola a[] od indexu left po index right (vratane) */

    /* Trivialne pripady: */ 
    if (left >= right) {
        return; 
    }
    
    /* Rozdel pole na tri podpostupnosti: */ 
    int middle = partition(a, left, right); 
    // Po vykonani funkcie: 
    // a[left..middle-1] su mensie ako pivot 
    // a[middle] je pivot
    //  a[middle+1..right] su vacsie ako pivot
    
    /* Rekurzivne utried a[left..middle-1], a[middle+1..right]: */    
    quicksort(a, left, middle-1);  
    quicksort(a, middle+1, right);   
}

Funkcia partition

Funkcia partition na vstupe dostane pole a spolu s hraničnými indexami left a right. Prvok a[left] vyberie ako pivot a postupnosť a[left..right] preusporiada tak, aby pre nejakú hodnotu middle takú, že left <= middle <= right platilo nasledovné:

• Prvky a[left],...,a[middle-1] sú menšie, než pivot.
• Prvok a[middle] je pivot.
• Prvky a[middle+1],...,a[right] sú väčšie alebo rovné ako pivot.

Hodnotu middle potom funkcia partition vráti ako svoj výstup.

Funkcia partition udržiava nasledujúce invarianty:

• Prvok a[left] je pivot.
• Prvky a[left+1],...,a[lastSmaller] sú menšie ako pivot.
• Prvky a[lastSmaller+1],...,a[unknown-1] sú väčšie alebo rovné ako pivot.
• Prvky a[unknown],...,a[right] sa ešte s pivotom neporovnávali.

Funkcia partition zakaždým porovnáva prvok a[unknown] s pivotom:

• Ak je menší ako pivot, je nutné „presunúť ho doľava”; vymení ho teda s a[lastSmaller+1] a hodnotu lastSmaller zvýši o jedna.
• Ak je väčší alebo rovný ako pivot, môže ostať na svojom mieste.

Následne zvýši index unknown o jedna a tento postup opakuje, až kým prejde cez všetky prvky danej časti poľa.

Nakoniec je ešte nutné vymeniť a[left] s a[lastSmaller], čím sa pivot dostane na svoje miesto.

void swap (int &x, int &y) {
    int tmp = x;
    x = y;
    y = tmp;
}

int partition(int a[], int left, int right) {
    // Ak za pivot chceme zvolit iny prvok, vymenime ho najprv s a[left]
    int pivot = a[left];     
    int lastSmaller = left;
    
    for (int unknown = left + 1; unknown <= right; unknown++) {
        if (a[unknown] < pivot) {
            lastSmaller++;
            swap(a[unknown], a[lastSmaller]);
        }
    }   
    swap(a[left],a[lastSmaller]); 
    return lastSmaller;
}

Výsledný program

#include <iostream>
using namespace std;

const int maxN = 1000;

void swap (int &x, int &y) {
    int tmp = x;
    x = y;
    y = tmp;
}

int partition(int a[], int left, int right) {
    int pivot = a[left];
    int lastSmaller = left;
    
    for (int unknown = left + 1; unknown <= right; unknown++) {
        if (a[unknown] < pivot) {
            lastSmaller++;
            swap(a[unknown], a[lastSmaller]);
        }
    }   
    swap(a[left],a[lastSmaller]); 
    return lastSmaller;
}

void quicksort(int a[], int left, int right) {
    if (left >= right) {
        return; 
    }
    
    int middle = partition(a, left, right);
        
    quicksort(a, left, middle-1);  
    quicksort(a, middle+1, right);   
}

int main() {
    int N;
    int a[maxN];
    
    cout << "Zadaj pocet cisel: ";
    cin >> N;
    cout << "Zadaj " << N << " cisel: ";
    for (int i = 0; i <= N-1; i++) {
        cin >> a[i];
    }
    
    quicksort(a,0,N-1);
    
    cout << "Utriedene cisla:";
    for (int i = 0; i <= N-1; i++) {
        cout << " " << a[i];
    }                        
    cout << endl;
}

Ukážka na príklade

Opäť uvažujme pole a = {6, 1, 5, 7, 2, 4, 8, 9, 3, 0}.

Volanie quicksort(0,9) potom utriedi pole a pomocou nasledujúcich rekurzívnych volaní (namiesto quicksort(a,l,h) píšeme zakaždým len sort(l,h)):

sort(0,9) sort(0,5) sort(0,-1)
          .         sort(1,5) sort(1,0)
          .         .         sort(2,5) sort(2,4) sort(2,2)
          .         .         .         .         sort(4,4)
          .         .         .         sort(6,5)
          sort(7,9) sort(7,8) sort(7,7)
                    .         sort(9,8)
                    sort(10,9)

Volania funkcie partition sú počas tohto behu nasledovné:

partition(a,0,9): |6 1 5 7 2 4 8 9 3 0| -> |0 1 5 2 4 3|6|9 7 8|
partition(a,0,5): |0 1 5 2 4 3|6 9 7 8  -> |0|1 5 2 4 3|6 9 7 8
partition(a,1,5):  0|1 5 2 4 3|6 9 7 8  ->  0|1|5 2 4 3|6 9 7 8
partition(a,2,5):  0 1|5 2 4 3|6 9 7 8  ->  0 1|3 2 4|5|6 9 7 8
partition(a,2,4):  0 1|3 2 4|5 6 9 7 8  ->  0 1|2|3|4|5 6 9 7 8
partition(a,7,9):  0 1 2 3 4 5 6|9 7 8| ->  0 1 2 3 4 5 6|8 7|9|
partition(a,7,8):  0 1 2 3 4 5 6|8 7|9  ->  0 1 2 3 4 5 6|7|8|9

Cvičenie:

• Ako sa bude Quick Sort správať, keď na vstupe dostane už utriedené pole?
• Ako sa bude správať, keď na vstupe dostane zostupne utriedené pole?

Odhad zložitosti

V ideálnom prípade pivot rozdelí pole na dve rovnako veľké časti. Vtedy je čas výpočtu O(N log N), podobne ako pre Mergesort.

Nepríjemné je, keď pivot je vždy najmenší alebo najväčší prvk v danom úseku. Vtedy je čas O(N²).

• Aby sme sa vyhli problémom, ak je vstupné pole (takmer) utriedené, môžeme ho pred triedením náhodne premiešať
• V praxi sa ako pivot vyberá náhodný prvok z intervalu.

Iná implementácia

Občas sa možno stretnúť aj s nasledujúcou implementáciou triedenia Quick Sort. Skúste samostatne odôvodniť jej správnosť.

void quicksort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }
    
    /* partition */
    int pivot = a[(left + right)/2];
    int i = left;
    int j = right;
    
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            swap(a[i],a[j]);
            i++; j--;
        }
    }
    
    /* rekurzia */    
    quicksort(a, left, j);
    quicksort(a, i, right);   
}

Triediace algoritmy: zhrnutie

Jednoduché triedenia: Bubble Sort, Insertion Sort, Max Sort.

• Jednoduché, ale pomalé: zložitosť Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n^2)} .

Rekurzívne triedenia založené na technike rozdeľuj a panuj.

• Rýchlejšie, zložitejšie.
• Merge Sort: zložitosť Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n\log n)} .
• Quick Sort: zložitosť Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n^2)} v najhoršom prípade, pre väčšinu vstupov Syntaktická analýza (parsing) neúspešná (MathML (experimentálne): Neplatná odpověď („Math extension cannot connect to Restbase.“) od serveru „https://wikimedia.org/api/rest_v1/“:): {\displaystyle O(n\log n)} , väčšinou rýchlejší ako Merge Sort.

Reálnu rýchlosť triedení na náhodne zvolenom veľkom vstupe možno porovnať napríklad nasledujúcim programom:

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

const int maxN = 100000;

void insertionsort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int prvok = a[i];
        int kam = i;
        while (kam > 0 && a[kam - 1] > prvok) {
            a[kam] = a[kam - 1];
            kam--;
        }
        a[kam] = prvok;
    }
}

void merge(int a[], int left, int mid, int right) {
    int aux[maxN];
    int i = left;
    int j = mid + 1;
    int k = 0;

    while ((i <= mid) && (j <= right)) {
        if (a[i] <= a[j]) {
            aux[k] = a[i];
            i++;
            k++;
        } else {
            aux[k] = a[j];
            j++;
            k++;
        }
    }

    while (i <= mid) {
        aux[k] = a[i];
        i++;
        k++;
    }

    while (j <= right) {
        aux[k] = a[j];
        j++;
        k++;
    }

    for (int k = left; k <= right; k++) {
        a[k] = aux[k - left];
    }
}

void mergesort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = (left + right) / 2;

    mergesort(a, left, mid);
    mergesort(a, mid + 1, right);

    merge(a, left, mid, right);
}

void swap(int &x, int &y) {
    int tmp = x;
    x = y;
    y = tmp;
}

int partition(int a[], int left, int right) {
    int pivot = a[left];
    int lastSmaller = left;

    for (int unknown = left + 1; unknown <= right; unknown++) {
        if (a[unknown] < pivot) {
            lastSmaller++;
            swap(a[unknown], a[lastSmaller]);
        }
    }
    swap(a[left], a[lastSmaller]);
    return lastSmaller;
}

void quicksort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }

    int mid = partition(a, left, right);

    quicksort(a, left, mid - 1);
    quicksort(a, mid + 1, right);
}

int main() {
    int N;
    int a1[maxN];
    int a2[maxN];
    int a3[maxN];

    cout << "Zadaj pocet nahodnych cisel v poli: ";
    cin >> N;

    srand(time(NULL));
    for (int i = 0; i <= N - 1; i++) {
        a1[i] = rand() % 1000;
        a3[i] = a2[i] = a1[i];
    }

    clock_t start1, end1, start2, end2, start3, end3;

    start1 = clock();
    insertionsort(a1, N);
    end1 = clock();

    start2 = clock();
    mergesort(a2, 0, N - 1);
    end2 = clock();

    start3 = clock();
    quicksort(a3, 0, N - 1);
    end3 = clock();

    cout << "Insertion sort: " 
	 << (end1 - start1) * 1.0 / CLOCKS_PER_SEC << " CPU sekund" << endl;
    cout << "Merge sort: " 
	 << (end2 - start2) * 1.0 / CLOCKS_PER_SEC << " CPU sekund" << endl;
    cout << "Quick sort: " 
	 << (end3 - start3) * 1.0 / CLOCKS_PER_SEC << " CPU sekund" << endl;

}

Pre N = 100000 môžeme dostať napríklad nasledujúci výstup (líši sa od počítača k počítaču a od volania k volaniu):

Insertion sort: 7.474 CPU sekund
Merge sort: 0.076 CPU sekund
Quick sort: 0.032 CPU sekund

Prehľadávanie s návratom (backtracking)

• Videli sme ako rekurzívne generovať všetky postupnosti spĺňajúce určité požiadavky
• Ak máme špeciálne požiadavky, napr. že žiadne číslo sa neopakuje, môžeme buď generovať všetky k-tice a testovať to pred výpisom, alebo už počas generovania urezávať neperspektívne vetvy výpočtu, čo je rýchlejšie
• Táto technika sa dá použiť na riešenie rôznych hlavolamov, videli sme problém 8 dám.
• Dá sa použiť aj na reálne problémy, ale pozor, čas výpočtu prudko (exponenciálne) rastie s dĺžkou postupností, takže vhodné len pre malé vstupy.
• Dnes ešte jeden problém riešený prehľadávaním s návratom, kde medzi možnými riešeniami hľadáme najlepšie.

Generovanie všetkých podmnožín

Chceme vypísať všetky podmnožiny množiny {0,..,m-1}. Na rozdiel od variácií nám v podmnožine nezáleží na poradí (napr. {0,1} = {1,0}), prvky teda budeme vždy vypisovať od najmenšieho po najväčší. Napr. pre m=2 máme podmnožiny

{}
{0}
{0,1}
{1}

Podmnožinu vieme vyjadriť ako binárne pole dĺžky m, kde a[i]=0 znamená, že i nepatrí do množiny a a[i]=1 znamená, že patrí. Teda môžeme použiť predchádzajúci program pre n=2, k=m a zmeniť iba výpis:

void vypis(int a[], int m) {
    cout << "{";
    bool prve = true;
    for (int i = 0; i < m; i++) {
        if (a[i] == 1) {
            if (prve) {
                cout << "" << i;
                prve=false;
            } else {
                cout << "," << i;
            }
        }
    }
    cout << "}" << endl;
}

• V premennej prve si pamätáme, či máme oddeliť ďalšie vypisované číslo od predchádzajúceho.
  • Ak ešte žiadne nebolo, oddeľovač je prázdny reťazec.
  • Ak už sme niečo vypísali, oddeľovač je čiarka.

Namiesto poľa intov môžeme použiť pole boolovských hodnôt a celý program trochu prispôsobiť tomu, že generujeme podmnožiny:

#include <iostream>
#include <cstring>
using namespace std;

void vypis(bool a[], int m) {
    cout << "{";
    bool prve = true;
    for (int i = 0; i < m; i++) {
        if (a[i]) {
            if (prve) {
                cout << "" << i;
                prve=false;
            } else {
                cout << "," << i;
            }
        }
    }
    cout << "}" << endl;
}

void generuj(bool a[], int i, int m) {
    /* v poli a dlzky k mame rozhodnutie o prvych i
     * prvkoch, chceme vygenerovat vsetky podmnoziny
     * prvkov {i..m-1} */
    if (i == m) {
        vypis(a, m);
    } else {
        a[i] = true;
        generuj(a, i + 1, m);
        a[i] = false;
        generuj(a, i + 1, m);
    }
}

int main() {
    const int maxM = 100;
    int m;
    cin >> m;
    bool a[maxM];
    generuj(a, 0, m);
}

Pre n=3 program vypíše:

{0,1,2}
{0,1}
{0,2}
{0}
{1,2}
{1}
{2}
{}

Cvičenie: Čo by program vypísal, ak by sme prehodili true a false v rekurzii?

Problém batoha (Knapsack problem)

Metódu prehľadávania s návratom využijeme na riešenie tzv. problému batoha. Ide o dôležitý problém, s ktorým sa ešte počas štúdia stretnete. Populárne ho možno sformulovať napríklad takto:

• Zlodej sa vlúpal do obchodu, v ktorom našiel nejaký počet „odcudziteľných” predmetov
• Pozná cenu aj hmotnosť predmetov.
• Z obchodu dokáže odniesť iba lup nepresahujúci nosnosť svojho batoha.
• Ktoré predmety má zlodej odcudziť, aby ich celková hmotnosť nepresahovala nosnosť batoha a aby odišiel s čo najcennejším lupom?

Vstup nášho programu bude vyzerať napríklad nejako takto:

Zadaj pocet predmetov v obchode: 3
Zadaj hmotnost a cenu predmetu cislo 1: 5 9
Zadaj hmotnost a cenu predmetu cislo 2: 4 6
Zadaj hmotnost a cenu predmetu cislo 3: 4 4
Zadaj nosnost batoha: 8

Výstup programu na horeuvedenom vstupe potom bude takýto:

Zober nasledujuce predmety: 2, 3.
Celkova hodnota lupu: 10.

Pri reálnom použití nosnosť batoha môže reprezentovať dostupné zdroje, napr. výpočtový čas na serveri, dostupných pracovníkov, veľkosť rozpočtu a pod, a predmety sú potenciálne úlohy, z ktorých si chceme vybrať podmnožinu, ktorú by sme s danými zdrojmi vedeli vykonať a dosiahnuť čo najvyšší zisk alebo iný ukazovateľ.

Prvé riešenie: preskúmanie všetkých možných výberov

Najjednoduchšie riešenie problému batoha spočíva v preskúmaní všetkých podmnožín množiny predmetov v obchode – čiže všetkých potenciálnych lupov. Program vypisujúci všetky podmnožiny danej množiny mierne poupravíme – nebudeme nájdené podmnožiny predmetov (potenciálne lupy) vypisovať, ale zakaždým:

• Spočítame celkovú hmotnosť a cenu nájdeného potenciálneho lupu.
• Ak hmotnosť tohto lupu nepresahuje cenu batoha, porovnáme jeho cenu s najlepším doposiaľ nájdeným lupom.
• Ak je cennejší, ako doposiaľ najlepší lup, ide o nového kandidáta na optimálny lup.

Podmnožiny budeme reprezentovať poľom typu bool, v ktorom si pre každý predmet pamätáme, či do danej podmnožiny patrí.

#include <iostream>
using namespace std;

const int maxN = 100;

/* Struktura reprezentujuca jeden predmet */
struct predmet {
    int hmotnost;
    int cena;
}; 

/* Globalne premenne pouzivane v rekurzii: */

// pocet predmetov v obchode
int N;                         
// pole s udajmi o jednotlivych predmetoch
predmet a[maxN];                 
// nosnost batoha
int nosnost;                     

// najcennejsi doposial najdeny potencialny lup (na uvod neinicializovany)
bool najlepsiLup[maxN];          
// jeho cena (kazdy lup bude urcite cennejsi ako -1)
int cenaNajlepsiehoLupu = -1;    

int spocitajHmotnostLupu(bool lup[]) {
    int hmotnost = 0;
    for (int i = 0; i < N; i++) {
        if (lup[i]) {
            hmotnost += a[i].hmotnost;
        }
    }
    return hmotnost;
}

int spocitajCenuLupu(bool lup[]) {
    int cena = 0;
    for (int i = 0; i < N; i++) {
        if (lup[i]) {
            cena += a[i].cena;
        }
    }
    return cena;
}

void vypisLup(bool lup[]) {
    cout << "Zober nasledujuce predmety: ";
    bool prvy = true;
    for (int i = 0; i < N; i++) {
        if (lup[i]) {
            if (prvy) {
                cout << i + 1;
                prvy = false;
            } else {
                cout << ", " << i + 1;
            }        
        }    
    }
    cout << "." << endl;
}

/* Generovanie vsetkych moznych lupov (podmnozin predmetov) */
void generujLupy(bool lup[], int index) {
    /* V poli lup[] dlzky N postupne generujeme podmnoziny predmetov.
       O hodnotach prvkov lup[0],...,lup[index-1] uz je rozhodnute.
       Postupne vygenerujeme vsetky moznosti pre lup[index],...,lup[N-1].
       Kazdy vysledny lup porovname s doposial najlepsim 
       a v pripade potreby optimum aktualizujeme.    
    */
    if (index == N) {                                
        // Lup je vygenerovany; zisti, ci ho batoh unesie.                               
        if (spocitajHmotnostLupu(lup) <= nosnost) {  
            // Ak ano, porovnaj cenu lupu s doposial najlepsim.
            int cenaLupu = spocitajCenuLupu(lup);
            if (cenaLupu > cenaNajlepsiehoLupu) {    
                // Ak je najdeny lup drahsi, uloz ho
                cenaNajlepsiehoLupu = cenaLupu;
                for (int i = 0; i < N; i++) {
                    najlepsiLup[i] = lup[i];
                } 
            }
        }
    } else {                                         
        // Lup este nie je vygenerovany,
        // skus postupne obe moznosti pre lup[index]. 
        lup[index] = false;
        generujLupy(lup, index+1);
        lup[index] = true;
        generujLupy(lup, index+1);
    }
} 

int main() {
    cout << "Zadaj pocet predmetov v obchode: ";
    cin >> N;
    for (int i = 0; i < N; i++) {
        cout << "Zadaj hmotnost a cenu predmetu cislo " << (i+1) << ": ";
        cin >> a[i].hmotnost >> a[i].cena;
    }
    cout << "Zadaj nosnost batoha: ";
    cin >> nosnost;
    
    bool lup[maxN];
    generujLupy(lup, 0);
    
    cout << endl;
    vypisLup(najlepsiLup);
    cout << "Celkova hodnota lupu: " << cenaNajlepsiehoLupu << "." << endl;
}

Optimalizácia č. 1: ukončenie prehľadávania vždy, keď je prekročená nosnosť

Keď je už po vygenerovaní nejakej časti lupu (čiže prvých niekoľko hodnôt poľa lup) jasné, že jeho hmotnosť bude presahovať nosnosť batoha, možno túto vetvu prehľadávania ukončiť.

Okrem samotnej funkcie generujLupy je potrebné prispôsobiť aj funkciu spocitajHmotnostLupu tak, aby ju bolo možné aplikovať aj na „neúplne vygenerované lupy”.

/* Potrebujeme vediet spocitat hmotnost len pre cast predmetov: */

int spocitajHmotnostLupu(bool lup[], int pokial) {
    int hmotnost = 0;
    for (int i = 0; i <= pokial; i++) {
        if (lup[i]) {
            hmotnost += a[i].hmotnost;
        }
    }
    return hmotnost;
}

void generujLupy(bool lup[], int index) {
    if (spocitajHmotnostLupu(lup, index-1) > nosnost) {
        // Ak dosial vygenerovana cast lupu presahuje nosnost batoha, 
        // mozno prehladavanie ukoncit
        return;  
    }
    if (index == N) {
        int cenaLupu = spocitajCenuLupu(lup);
        if (cenaLupu > cenaNajlepsiehoLupu) {
            cenaNajlepsiehoLupu = cenaLupu;
            for (int i = 0; i < N; i++) {
                najlepsiLup[i] = lup[i];
            } 
        }
    } else {
        lup[index] = false;
        generujLupy(lup, index+1);
        lup[index] = true;
        generujLupy(lup, index+1);
    }
}

Optimalizácia č. 2: hmotnosť a cenu lupu netreba zakaždým počítať odznova

Predchádzajúci program vždy znovu a znovu prepočítava hmotnosť a cenu lupu, aj keď sa zoznam vybraných predmetov zmení iba trochu. Namiesto toho môžeme cenu a hmotnosť doposiaľ vygenerovanej časti lupu predávať funkcii generuj ako parameter.

#include <iostream>
using namespace std;

const int maxN = 100;

struct predmet {
    int hmotnost;
    int cena;
}; 

int N;
predmet a[maxN];
int nosnost;

bool najlepsiLup[maxN];
int cenaNajlepsiehoLupu = -1;

void vypisLup(bool lup[]) {
    cout << "Zober nasledujuce predmety: ";
    bool prvy = true;
    for (int i = 0; i < N; i++) {
        if (lup[i]) {
            if (prvy) {
                cout << i + 1;
                prvy = false;
            } else {
                cout << ", " << i + 1;
            }        
        }    
    }
    cout << "." << endl;
}

void generujLupy(bool lup[], int index, int hmotnostLupu, int cenaLupu) {
    if (hmotnostLupu > nosnost) {
        return;
    }
    if (index == N) {
        if (cenaLupu > cenaNajlepsiehoLupu) {
            cenaNajlepsiehoLupu = cenaLupu;
            for (int i = 0; i < N; i++) {
                najlepsiLup[i] = lup[i];
            } 
        }
    } else {
        lup[index] = false;
        generujLupy(lup, index+1, hmotnostLupu, cenaLupu);
        lup[index] = true;
        generujLupy(lup, index+1, hmotnostLupu + a[index].hmotnost, 
                    cenaLupu + a[index].cena);
    }
} 

int main() {
    cout << "Zadaj pocet predmetov v obchode: ";
    cin >> N;
    for (int i = 0; i < N; i++) {
        cout << "Zadaj hmotnost a cenu predmetu cislo " << (i+1) << ": ";
        cin >> a[i].hmotnost >> a[i].cena;
    }
    cout << "Zadaj nosnost batoha: ";
    cin >> nosnost;
    
    bool lup[maxN];
    // Doposial nie je nic vygenerovane; hmotnost aj cena lupu su zatial nulove
    generujLupy(lup, 0, 0, 0); 
    
    cout << endl;
    vypisLup(najlepsiLup);
    cout << "Celkova hodnota lupu: " << cenaNajlepsiehoLupu << "." << endl;
}