Cvičenie 6
V moodli odovzdávajte riešenie úloh Hamiltonovská kružnica a Graph color (môžete ich spojiť do jedného textového súboru, ak budú dostatočne viditeľne oddelené).
- Informácie o tom, ako získať DLV a smodels sú na stránke predmetu ASP.
Choice
Napíšte program, ktorý bude mať dva stabilné modely: jeden v ktorom platí predikát a/0 a jeden v ktorom neplatí.
2-choice.sma :- not b. b :- not a.
Choice 2
Napíšte program, ktorý bude mať pre nejaký vstupný predikát a/1 stabilné modely, z ktorých v každom bude predikát b/1 platný pre nejakú podmožinu X z { X | a(X)}. Teda prea(1). a(2).
dostaneme modely ( predikát a vynechávam ):- {}
- { b(1) }
- { b(2) }
- { b(1), b(2) }
Ináč povedané pre každé X z a(X) sa chceme nezávisle na ostatných rozhodnúť či v modeli bude alebo nebude b(X).
2-choice2.sma(1). a(2). a(3). b(X) :- not notb(X), a(X). notb(X) :- not b(X), a(X).
N-Queens
Máme šachovnicu NxN políčok, rozmiestnite na ňu N dám tak aby sa žiadne neohrozovali. Riešenie cez predikát q(X,Y) znamenajúci, že na políčku X,Y je kráľovná.
Choose
Napíšte program, tak aby v každom modeli bol chosen(X) pravdivý práve pre jedno X z option(X).
2-choose.sm#hide. #show b(X). a(1). a(2). a(3). a(4). b(X) :- not notChosen(X), a(X). notChosen(X) :- b(Y), X != Y, a(X), a(Y).2-choose.dlv
a(1). a(2). a(3). a(4). b(X) :- not notChosen(X), a(X). notChosen(X) :- b(Y), X != Y, a(X), a(Y).
Graph coloring
Napíšte program, ktorého modely budú zodpovedať rôznym zafarbeniam grafu farbami col1..colN tak aby žíadne dva vrcholy spojené hranou nemali rovnakú farbu.
Graf je zadaný predikátmi node/1 a edge/2, možné farby predikátom color/1. Výsledné zafarbenie bude dané predikátom nodeColor( node, color ).
Mozny vstup:
2-graphcolor-input.smcolor(c1). color(c2). color(c3). node(a). node(b). node(c). edge(a,b). edge(b,c). edge(a,c).
Hamiltonovská kružnica
Zadaný je (neorientovaný) graf, pomocou predikátov edge/2 a node/1. Napíšte program ktorého modely budú zodpovedať možným hamiltonovským kružniciam na tomto grafe. Hrany vybrané do hamiltonovskej kružnice nech sú reprezentované predikátom ham/2.
Vstup:
ham-vstup.dlv%input: % d - a - e % | X | / | % c - b - f nd(a). nd(b). nd(c). nd(d). edge(A,B) :- nd(A), nd(B), A<B. node(A) :- nd(A). node(e). edge(a,e). edge(b,e). node(f). edge(b,f). edge(e,f).