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.dlv
color(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.

ham-vstup-ohodnoteny.dlv

%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.

  1. 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 :).

  2. 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ých i-1 predchádzajúcich konštánt).

  3. 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

Vim logo FireFox logo CSS XHTML
Jozef Siska @ KAI FMFI UK YoYo @ KSP KAI (DAI) KSP