Cvičenie 1

Riešenie tejto úlohy odvzajte v moodli do 9.10.2014 13:09:59.

Naprogramujte riešenie úlohy o gazdovi, koze, kapuste a vlku (ktorú máte spísať v DU1).

Niekoľko poznámok, ktoré by mohli pomôct:

Najjednoduchšie riešenie je buď jednoduchý backtrack (napríklad s obmedzenou hĺbkou) alebo trošku "korektnejšie" prehľadávanie do šírky. Oboje sa dá naprogramovať vcelku ľahko, pokiaľ si dobre zvolíme reprezentáciu stavov a akcií.

Pri prehľadávaní do šírky môže, ale aj nemusí, mať zmysel pamätať si stavy, kde ste boli.

Každý stav vieme jednoducho reprezentovať štyrmi premennými s hodnotami true/false (v plánovaní sa im zvykne hovorit fluenty): gazda_vlavo, koza_vlavo, kapusta_vlavo, vlk_vlavo. Máme tiež štyri možné akcie: prevez_gazdu, prevez_kozu, prevez_kapustu, prevez_vlka; pri prvej akcii sa prevezie len gazda, pri ostatných sa vždy prevezie gazda a dotyčný objekt.

Na reprezentáciu stavu je najjednoduchšie použiť triedu/struct obsahujúci tie potrebené štyri premenné, ale ak sú všetky binárne (boolovské) a nie je ich príliš veľa (napríklad menej ako 32 či 64), tak sa takáto množina veľmi ľahko reprezentuje ako jedno číslo potrebnej veľkosti, kde každý bit bit zodpovedá jednému fluentu... (aj keď napríklad slušný kompilátor c/c++ to vie spraviť aj sám, ak má class/struct obsahujúci iba bool premenné).

Jedna z možných kostier riešenia:

• Predpokladáme nejaké typy State, Action (všetky môžu byť teda napr. čísla)
• Vytvríme si niekoľko pomocných funkcií:
  • bool allowed_state(State s) - vráti true ak je stav povolený (vzhľadom na naše pravidlá)
  • State execute_action(State s, Action a) - vráti nový stav po vykonaní akcie a v stave s, prípadne nejaký nekorektný stav / niečo čo nie je stav, ak sa akcia nedá vykonať (alebo si vytvoríme ďalšiu pomocnú funkciu bool isExecutable(State s, Action a)).
  • Budeme mať frontu, do ktorej budeme vkladať dvojice: State a zoznam Action
  • Vložíme do fronty počiatočný stav a prázdny zoznam akcií
  • Kým vo fronte je nejaký stav, opakujeme:
    • Vyberieme z fronty prvý stav a postupnosť akcií. Ak je cieľový, tak sme skončili.
    • Pre každú akciu:
      • získame nasledujúci stav pomocou execute_action
      • ak je korektný, skontrolujeme ho pomocou allowed_state
      • ak je povolený, pridáme do fronty tento stav spolu s postupnosťou akcií, ku ktorej sme pridali túto akciu