Cvičenie 7 -- DLV Agregates a Weak Constraints
Riešenie úlohy Počítanie odvzajte v moodli do 18.11.2013 18:09:59.
Weak Constraints
Weak constraints sú obmedzenia, ktore neznamenajú nutne zrušenie modelu, ale DLV sa snaží nájsť model, ktorý ich porušuje čo najmenej. Majú dve čísla: váhu a level. Pre každý model sa zrátajú váhy všetkých porušených contraintov pre každý level, potom sa modely porovnávajú tak, že sa najprv porovnajú najvyššie levely, atď.
:~ h(X,Y,Z). [Z:1]
Váhu alabo level (alebo obidve) možno vynechať, ale musí to byť rovnako vo všetkých obmedzeniach v programe.
Kostra
Je zadaný (neorientovany) graf, nájdite jeho kostru (tj vyberte najmenšie množstvo hrán tak, aby bol graf stále spojitý).
Vstup:
../05/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).
Farbenie grafu s co najmenej farbami
Upravte riešenie úlohy z cvičenia 4 o farbení grafu tak, aby hľadala farbenia používajúce najmenej farieb.
graphcolor.dlvcolor(c1). color(c2). color(c3). color(c4). node(a). node(b). node(c). node(d). edge(a,b). edge(b,c). edge(c,d). edge(a,d). nodeColor(Node,Color) :- node(Node), color(Color), not notChosenColorForNode( Color, Node ). notChosenColorForNode( Color1, Node ) :- node(Node), color(Color1), color(Color2), nodeColor(Node,Color2), Color1 != Color2. :- node(Node1), node(Node2), color(Color), nodeColor(Node1,Color), nodeColor(Node2,Color), edge(Node1,Node2).
Ohodnotená hamiltonovská kružnica
Upravte úlohu o hamiltonovskej kružnici tak, aby pracovala s ohodnotenými hranami a hľadala najkratšiu ham. kružnicu.
%input: % d - a - e % | X | / | % c - b - f node(a). node(b). node(c). node(d). edge(a,b,7). edge(a,c,3). edge(a,d,4). edge(b,c,10). edge(b,d,4). edge(c,d,2). node(e). edge(a,e,2). edge(b,e,3). node(f). edge(b,f,3). edge(e,f,3).
Pôvodný program (počíta s nesprávnou aritou predikátu edge)
ham.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). % choose ham(A,B) :- not -ham(A,B), edge(A,B). -ham(A,B) :- not ham(A,B), edge(A,B). % make it directed dir(A,B) :- ham(A,B). dir(B,A) :- ham(A,B). % every node must be reachable (from every node ;) reachable(A,B) :- node(A), node(B), A==B. reachable(A,B) :- reachable(C,B), dir(A,C). :- node(A), node(B), not reachable(A,B). % each node must have deg 2 in ham (or dir) degMoreThan3(N) :- dir(N,A), dir(N,B), dir(N,C), A!=B, B!=C, A!=C. deg2(N) :- dir(N,A), dir(N,B), A!=B, not degMoreThan3(N). :- node(N), not deg2(N).
Počítanie
Predikát a/1 platí pre nejaké konštanty.
-
Nájdite najmenšiu konštantu pre ktorú platí. Reprezentujte jú pomocou predikátu min/1. T.j. min(X) platí, ak X je najmenšia konštanta pre ktorú platí a. Inak povedané min(X) ⇔ ( a(X) ∧ ∄ Y<X a(Y) )
DLV pre všetky konštanty (povolené prirodzené čísla aj všetky symbolické konštanty) jednoznačne definuje predikát/reláciu
<
. Čisla sa porovnávajú ako čísla, všetky čísla sú menšie ako symb. konštanty, ktoré sú v nejakom úplnom usporiadaní (nie nutne abecednom :). -
Spočítajte koľko ich je. Výsledok nech je vo forme predikátu count/1, ktorý platí iba pre jednu hodntou (číslo) - počet platných predikátov a.
Na spočítanie konštánt ich potrebujeme zoradiť - vedieť povedať, ktorá je prvá, ktorá je druhá, atď. Na to by mohol pomôcť predikát, ktorý povie, ktorá je
i
-ta najmenšia konštanta (t.j. ktorá je najmenšia, ak odignorujeme už najdenýchi-1
predchádzajúcich konštánt). -
Spočítajte ich súčet. Výsledok nech je vo forme predikátu sum/1, ktorý platí iba pre jednu hodntou (číslo) - súčet hodnôt pre ktoré platí a (toto samozrejme funguje rozumne, iba ak všetky konštanty pre ktoré a platí sú čísla).
Napríklad pre vstup a(11), a(12), a(13) bude v stabilnom modeli platiť min(11), count(3) a sum(36) .
Aggregate Predicates
Zodpovedná časť manuálu..
Aggregate predicate pozostáva z funkcie, symbolickej množiny, a stráži. Symbolická množina sa expanduje podla toho toho, čo v aktuálnom modeli platí, použije sa na ňu funkcia, a výsledok sa porovná so strážami. (Ak je ako stráž priradenie, tak sa výsledok funkcie priradí do premennej a predikát sa bere za platný.) Príklady sú v DLV manuáli.
worth(Person,X) :- #sum{Price,Item: price(Item,Price),owns(Person,Item} = X, person(Person).
Hamiltonovská kružnica
Upravte riešenie hamiltonovskej kružnice, aby používalo aggregačnú funkciu #count na zistenie, či z vrhola vychádzajú práve 2 hrany