Cvičenie 6 – Backtrack

Ciele cvičení:

  • rozumieť princípom generovania postupností technikou backtracking
  • vedieť aplikovať backtracking na riešenie kombinatoricko-optimalizačných problémov

Variácie (dla zwariowanych)

Navrhnite a upravte program na generovanie váriácií s opakovaním tak, aby ste generovali variácie s opakovaním z prvkov ľubovoľnej zadanej množiny?

Rýchlo sa rozdeliť a každý svojou cestou…

Dvaja zlodeji spoločne získali lup pozostávajúci z n predmetov. Každý z predmetov má svoju cenu. Po akcii chcú isť každý svojou cestou. Vytvorte program, ktorý nájde čo najspravodlivejšie rozdelenie predmetov medzi zlodejov, t.j. chceme minimalizovať rozdiel medzi cenou lupu prvého zlodeja a druhého zlodeja.

  • Navrhnite ako tento problém riešiť pre k zlodejov.

Nepriateľské čísla

Na telesnú chodia rôzne čísla (v jednej triede nie sú 2 rovnaké čísla). Medzi niektorými číslami sú priateľstvá, naopak niektoré čísla sa doslova nenávidia. Čísla sa nemajú rady, ak je jedno z čísel deliteľom toho druhého. Napríklad čísla 8 a 4 sa nenávidia, lebo 4 je deliteľom 8. Aby rozcvička na telesnej prebehla bez konfliktov, učiteľ musí nájsť také usporiadanie čísel v triede do radu, aby medzi žiadnymi 2 číslami stojacimi vedľa seba nepanovala nenávisť.

Pre zadanú množinu n rôznych čísel nájdite všetky bezkonfliktné usporiadania čísel do radu. Snažte sa, aby vaše riešenie bolo čo najefektívnejšie.

Problém dám na šachovnici (pre dámy aj pánov)

Nájdite také rozmiestnenie n dám na šachovnici n x n, aby sa navzájom neohrozovali.

  • V prípade potreby sa môžete obmedziť na n = 8.

Chemický sklad

Úloha z Palmy: http://palma.strom.sk/PAZ1bS3/U2l/ Riešenie môžete odoslať cez systém Palma.

Variácie (dla zdolnych)

  • Vytvorte program na generovanie variácií s h-opakovaním prvkov zo zadanej množiny. h-opakovanie znamená, že každý prvok sa môže vo vygenerovanej postupnosti nachádzať nanajvýš h krát.
  • Navrhnite, ako nerekurzívne generovať všetky k-prvkové variácie s opakovaním z prvkov n-prvkovej množiny.