Aplikácie backtrackingu

Riešenie hlavolamov:

  • Sudoku, hľadanie cesty v bludisku, krížovky, scrabble

Parsovanie:

  • Chceme zistiť, či je zápis platný pre daný programovací jazyk.

Riadenie robotov (agentov):

- Markovovský rozhodovací proces (MDP)
- V každom stave je množina možných akcií.
- Ako vybrať takú postupnosť akcií aby sme dosiahli želaný konečný stav?

Rozvrhovanie:

- Ako priradiť študentov do rozvrhových jednotiek tak, aby bola dodržanbá kapacita miestnosti a aby každý mal správne navrhnutý rozvrh?
- Ako priradiť stavebné stroje na stavby tak, aby sa dodržali postupy a termíny?

Príklad na problém rozvrhovania:

Máme A strojov, B stavieb a C dní.

Je daná množina obmedzení:

Pre každú stavbu je potrebná množina strojov A(n)

  • napr. stavba a vyžaduje bager a žeriav.

Niektoré stroje vyžadujú použitie iných strojov.

- napr. pred bagrom je potrebné použiť buldozér.

Naplánujte využitie strojov na ďalší mesiac.

Zostavenie rozvrhu pre študentov

Máme A študentov, B miestností a C predmetov.

Pre každý predmet rozmiestnite študentov do miestností tak, aby sa zmestili a aby v jednom čase boli na jednom mieste.

  • https://www.geeksforgeeks.org/dsa/n-queen-problem-backtracking-3/

    Riešenie pomocou programovania s obmedzeniami:

Constraint programming

Backtracking

Programátorská technika na riešenie kombinátorických úloh s obmedzeniami

  • Máme danú množinu množných riešení
  • Hľadáme správne riešenie

Naivné prehľadávanie

  1. Postupne generuj všetky možné riešenia
  2. Over či je riešenie vhodné.
  3. Ak je riešenie vhodné, skonči. Inak pokračuj.

Backtracking

  • Rekurzívny algoritmus
  • Je definované finálne riešenie.
  • Je definované čiastkové riešenie.
  • Vieme povedať či čiastkové riešenie vedie k finálnemu riešeniu alebo nie.

KLasický šachový príklad: 8 kráľovien

  • Máme šachovnicu 8x8 štvorcov a 8 kráľovien.
  • Umiestnite 8 kráľovien tak, aby žiadna kráľovná neohrozila inú.
  • Kráľovná vie ohroziť inú po stranách a po diagonálach po celej šachovnici.

Klasický šachový príklad: 8 kráľovien

Finálne riešenie:

  • 8 kráľovien tak, aby žiadna kráľovná neohrozila inú.

Čiastkové riešenie:

  • niekoľko kráľovien tak, aby žiadna kráľovná neohrozila inú.
  • neplatné, ak je niektorá kráľovná v ohrození.

Naivné riešenie (hrubou silou)

  • Generuj všetky možné umiestnenia kráľovien.
  • Ak je umiestnenie dobré, skonči

Čiastkové riešenie

  • Šachovnica má štvorcový tvar.
  • Každý štvorček šachovnice môže byť prázdny alebo obsadený.
  • V jednom stĺpci môže byť iba jedna kráľovná.

Backtracking riešenie


i = 1

BACKTRACK(pre stĺpec i)
Ak i == 9 skonči lebo finálne riešenie sme našli.
for n=1 do 8
    Umiestni i-tú kráľovnú do n-tého riadka a i-tého stĺpca.
    Ak nie je kráľovná ohrozená,
        BACKTRACK(i+1)
        ak čiastkové riešenie existuje, ukonči.
    Inak zdvihni kráľovnú
pokračuj ďalším n
ukonči, čiastkové riešenie neexistuje.

Pomocné funkcie pre BT riešenia

  • Zisti či je pridanie je i-tá kráľovná na n-tej pozícii ohrozená
  • Vypíš šachovnicu.

Min-Konflikt heuristika

  1. Náhodne rozmiestni kráľovné po šachovnici.
  2. Vyber kráľovnú, ktorá je najviac ohrozená.
  3. Ukonči ak žiadna nie je ohrozená
  4. Inak ju priemestni na najmenej ohrozené miesto v aktuálnom stĺpci.
  5. Pokračuj krokom 2 alebo ukonči po maximálnom počte iterácií.

Bibliografia

  • Helsgaun, Keld. "CBack: a simple tool for backtrack programming in C." Software: Practice and Experience 25.8 (1995): 905-934.
  • Steven S. Kiena: The Algorithm Design Manual, p. 231
  • https://en.wikipedia.org/wiki/Backtracking
  • https://www.geeksforgeeks.org/backtracking-algorithms/

Dynamické programovanie

https://www.spiceworks.com/tech/devops/articles/what-is-dynamic-programming/

Dynamic programming is a computer programming technique where an algorithmic problem is first broken down into sub-problems, the results are saved, and then the sub-problems are optimized to find the overall solution — which usually has to do with finding the maximum and minimum range of the algorithmic query.

Richard Bellman

Reload?