ADŠ prednáška 12: Iterovanie cez všetky podmnožiny a cez všetky permutácie.

Zhrnutie prednášky

Prednáška otvára tému riešenia problémov hrubou silou, teda systematickým skúšaním všetkých možností pri generovaní kombinatorických objektov. Úlohy typu problém obchodného cestujúceho vedú na prechádzanie všetkých permutácií (n! možností, prakticky použiteľné do približne 14–15 prvkov), úlohy s výberom z možností na prechádzanie všetkých podmnožín. Podmnožiny n-prvkovej množiny sa kódujú ako n-bitové čísla od 0 do 2^n − 1, takže stačí obyčajný cyklus. Prítomnosť prvku i sa testuje bitovými operáciami (x & (1 << i) alebo (x >> i) & 1), pričom AND zodpovedá prieniku, OR zjednoteniu a XOR symetrickému rozdielu. Na tomto základe sa začína riešiť problém batoha na príklade Robina Hooda v šľachticovom sídle.

• - Riešenie hrubou silou skúša všetky možnosti a zaručuje správnosť, hoci je neefektívne.
• - Mnohé rozhodovacie a optimalizačné problémy sa dajú sformulovať ako hľadanie kombinatorického objektu.
• - Problém obchodného cestujúceho vedie na prechádzanie všetkých permutácií, ktorých je n!, takže je použiteľný len pre malé n (cca do 14–15).
• - Úlohy s výberom spomedzi možností vedú na prechádzanie všetkých podmnožín, ktorých je 2^n.
• - Podmnožina sa kóduje ako n-bitové číslo, kde i-ty bit určuje, či je i-ty prvok vybraný, a cez podmnožiny sa iteruje cyklom od 0 do 2^n − 1.
• - Prítomnosť prvku sa testuje výrazom x & (1 << i) alebo (x >> i) & 1; AND, OR a XOR zodpovedajú prieniku, zjednoteniu a symetrickému rozdielu.
• - Ako príklad slúži problém batoha (knapsack) v podobe Robina Hooda vyberajúceho si cenné predmety zo šľachticovho sídla.

Zhrnutie pripravené s pomocou AI z prepisu videa.