Home     Termíny     Cvičení     Projekty     Rezervace termínu

Osnova

• Programování s omezujícími podmínkami (clp)
• Zpět na stránku jen se zadáním

---

Programování s omezujícími podmínkami (clp)

1. Základy CLP
   • Přednášky str. 184-186,194-200
   • Vyzkoušejte příklady na stránkách: 186,197,199

2. Aritmetické podmínky

   Najděte m-místné číslo N (N₁...N_m), kde 0<m<10 a 0<N<10, splňující následující podmínky:

   • číslice N_i jsou navzájem různé
   • k-prvkový prefix čísla N je dělitelný číslem k (0<k≤m), k|N₁...N_k

   př. N=123, 1|1, 2|12, 3|123

   Řešení:

   :-use_module(library(clpfd)).        /* zavedení modulu pro řešení omezení v konečné doméně */
   
   pn(S,N):- N>0,N<10,
      list(S,N),
      domain(S,1,9),                    /* definování domén proměnných */
      all_distinct(S),                  /* omezení */
      p(S,N),                           /* modelování problému */
      labeling([],S).                   /* spuštění solveru - hledání hodnot proměnných */
   
   list([],0):-!.
   list([_|T],N):-N1 is N-1, list(T,N1).
   

   Doplňte predikát p(S,N).

   Řešení:

   pn(S,N):- N>0,N<10,
      list(S,N),
      domain(S,1,9),
      all_distinct(S),
      p(S,N).
   
   p(S,9):-                    /* vyuziti analyzy problemu kvuli preteceni */
    S=[S1,S2,S3,S4,S5,S6,S7,S8,S9],
    p([S1,S2,S3,S4,S5,S6,S7,S8],8),
    sum(S,#=,Sum),
    Sum mod 9 #= 0.
   
   p(S,8):-                    /* vyuziti analyzy problemu kvuli preteceni */
    S=[S1,S2,S3,S4,S5,S6,S7,S8],
    p([S1,S2,S3,S4,S5,S6,S7],7),
    scalar_product([100,10,1],[S6,S7,S8],#=,ScP),  
    ScP mod 8 #=0.
   
   p(S,N):-N<8,p(S).           /* obecna specifikace problemu */
   
   p(S):-p(0,S,0).
   
   p(_,[],_).
   p(N,[S1|S],C):-
      C1 #= C*10+S1,
      N1 is N+1,
      C1 mod N1 #= 0,
      p(N1,S,C1).
   

3. Plánování (predikát cumulative/4)

   Napište program s využitím omezujících podmínek, který najde řešení následujícího problému:
   V jistém muzeu pracuje 5 českých průvodců, 2 z nich umí německy a zbylí 3 umí anglicky. Prohlídky probíhají od 10 hodin, poslední začína v 15 hodin. Dlouhá prohlídka trvá 2 hodiny, krátká hodinu. Jeden průvodce může provádět skupinu nanejvýš 10 lidí, všichni mohou provádět najednou.

   Na jeden den přisly tyto objednávky:

   1. Skupina 20 japonských turistů požaduje anglického průvodce a dlouhou prohlídku.
   2. Skupina 5 holanských turistů požaduje německého průvodce a dlouhou prohlídku .
   3. Skupina 10 slovenských turistů a krátkou prohlídku.
   4. Třída 30 českých žáků chce dlouhou prohlídku.
   5. Zájezd 50 českých turistů požaduje krátkou prohlídku.
   6. Skupina 20 amerických turistů požaduje krátkou prohlídku.
   7. Skupina 20 německých turistů chce dlouhou prohlídku.

   Na kterou hodinu objednat jednotlivé skupiny tak, aby byly zachovány podmínky provádění i požadavky skupin?

   Využijte omezení cumulative/4 popsané v kap. 10.34.10.3 v manuálu http://www.fi.muni.cz/~hanka/sicstus/doc/pdf/sicstus.pdf.

   Řešení:

   :-use_module(library(clpfd)).
   
   muzeum(Starts):-
      muz(Starts,All),
      labeling([],All).
   
   muz(S,A):-
      list(S,7),
      domain(S,10,15),
      R=[R3a,R3b,R4a,R4b,R5a,R5b],
      domain(R,0,3),
      A=[R3a,R3b,R4a,R4b,R5a,R5b|S],
      D=[2,2,1,2,1,1,2],
      R3a+R3b #=1,
      R4a+R4b #=3,
      R5a+R5b #=5,
      cumulative(S,D,[2,0,R3a,R4a,R5a,2,0],3),
      cumulative(S,D,[0,1,R3b,R4b,R5b,0,2],2).
   

   ---

   ^