v Řešení vybraných příkladů k předmětu PA163 Programování s omezujícími podmínkami Hana Rudová Fakulta informatiky, Masarykova univerzita 15. září 2019 Poděkování Řešení příkladů jsou převzata z domácích úkolů studentů předmětu. Všem děkuji za pěkná řešení, která jsou zde použita. 1 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Příklady 1. — zadání 1. Uvedený CSP převeďte pomocí duálního problému na binární CSP. Máte zadány proměnné A, B, C, D, E, F, jejich doména je {0,1} a omezení jsou ci : A + B + F = l c2: A-C + D = l c3: D + E-F>0 c4: B + E-F = 0 2. Popište rozdíl mezi algoritmy AC-1 a AC-3 a ukažte podrobně, jak tyto algoritmy pracují na následujícím příkladu. A e {!,..., W}, S g {1,..., 10}, C g {1,..., 10}, B B AC-1: A> B,A < C + 4 : (1 (2... 10,1... 9,1 10,1... 10,1. .10) (2. 10,1... 10,1 10) ^> (2. 10,1... 9,1. 10) ^ (2. 10,1. ..10) ^ .9,1... 10) Následně jsou ještě jednou zrevidovány všechny hrany nedojde k žádné změně a tím algoritmus končí. AC-3: Fronta by postupně vypadala takto: (AB, BA, AC, CA) (BA, AC, CA) (AC, CA) -> (CA) -> () 3.příklad Pro případ X Y + C bych propagační pravidla zvolil následovně: min(X) max(X) min(Y) max(Y) > min(Y) + C < max(Y) + C > < min(X) -max(X) C -C (D (2) (3) (4) Pro případ kdy Y e {1,...,20}, X e {1,..., 5}U{15,..., 20}, X = 3+Y (pro přehlednost byly proměnné přejmenovány: X/Y, Y/X) by propagace pomocí těchto pravidel vypadala následovně: (min(X),max(X)),(min(Y),max(Y)) = (1, 20), (1, 20) ^ (4, 20), (1, 20) (4, 20), (1, 20) ^% (4, 20), (1, 20) (4, 20), (1,17) Tedy X e {4, 5} U {15,..., 20} a Y e {1,..., 17}. Při použití hranové konzistence by z domény proměnné Y zmizely také hodnoty 3 až 11, jelikož ty by v doméně proměnné X neměly oporu. Konečný výsledek by tedy byl X e {4,5} U {15,..., 20} are {1,2}U{12,...,17} 3 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Příklady 2 — zadání Ukažte, jak vypadá graf stavového prostoru pro řešení problému • proměnné A, B, C mohou nabývat hodnot 0,1, 2,4 • omezení: c\ : A = B * 2, C2 : B > C algoritmem 1. backtrackingu 2. kontroly dopředu (forward checking) 3. pohledu dopředu (look ahead) bez iniciální konzistence při uspořádání proměnných A, B, C. V řešení uveďte pro každý algoritmus jeden graf stavového prostoru. V každém uzlu grafu uveďte, které domény proměnných se v důsledku propagací změnily a která omezení tyto změny způsobila. 4 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Příklady 2. — řešení Notace Zachována notace z přednášky. • Vnitřní stav: W • Splnitelné přiřazení: O • Fail stav: ■ U algoritmů forward checking a look ahead je u každého uzlu, kde je potřeba, zobrazeno omezení a změny, které byly propagovány. Backtracking B FAIL kvůli nesplnění c\ FAIL kvůli nesplnění C'2 5 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Forward Checking 6 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Příklady 3. - zadání Máme zadán systém omezení C = cl, c2, c3, c4, c5 nad polookruhem (N U {+00}, min, +, +00,0) cl: Timel e {1-3} @ Timel (preference odpovídá hodnotě) c2: Timel e {1--3} @ 2 * Timel (preference odpovídá dvojnásobku hodnoty) c3: Time',3, e {1--3} @ 3 * Time',3, (preference odpovídá trojnásobku hodnoty) c4: Timel < Timel @ (0,5) (pokud omezení platí, ak je reference 0 pokud neplatí, pak je preference 5) c5: Time',3, < Timel @ (0, 5) (jako c4) 1. O jakou instanci omezení nad polookruhy se jedná? 2. Ukažte, jakým způsobem se spočítá úroveň konzistence tohoto problému. 3. Ukažte, jak se spočítá 0 C 4{Timei,Time2,Time3} 4. Ukažte, jak se spočítá 0 C 4{twi,tw2} 5. Ukažte, jak se spočítá 0 C 4{iwi} Ve všech případech (body 2-5) uveďte postup řešení 7 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Příklady 3. - řešení 1. Jedná se o CSP s váhami. 2. Úroveň konzistence problému odpovídá 0 C = min(Mec(l,l,l),Mec(l,l,2),Mec(l,l,3).Mec(l,2,l), /íec(l,2,2),/í0c(l,2,3),/i0c(l,3,l),/iec(l,3,2),Mec(l,3,3), A®c(2,1, l),/x®c(2,1,2),/Í0C(2, l,3),/íec(2,2,1), /ie c(2, 2, 2), /ie c(2, 2, 3), /í0 c(2, 3,1), /í0 c(2, 3, 2), Me c(2, 3, 3), M0 c(3,1,1), /xe c(3,1, 2), /*e c(3,1, 3), M© c(3, 2,1), Me c(3, 2, 2), M0 c(3, 2, 3), M© c(3, 3,1), M© c(3, 3, 2), Me c(3, 3, 3)) = min(16,19, 22,13,16,19,15,18, 21,12, 20, 23,14, 22, 25,11,19, 22,13,16, 24,15,18, 26,17, 20,28) = 11 3- © C ii-{Timel,Time2,Time3} (1,1 1) = min (/<© c (1, 1 1) ) = min (16) = 16 © C ^{Timel,Time2,Time3} (1,1 2) = min (M©c (1, 1 2) ) = min (19) = 19 © C ^{Timel,Time2,Time3} (1,1 3) = min (^©C (1, 1 3) ) = min(22) = 22 © C ^{Timel,Time2,Time3} (1,2 1) = min (1, 2 1) ) = min(13) = 13 © C -U"{Timel,T!me2.Time3} (1,2 2) = min (m© c (1,2 2) ) = min(16) = 16 © C -U"{Timel,Time2,Time3} (1,2 3) = min (/<© c (1, 2 3) 1 = min (19) = 19 © C ii-{Timel,Time2,Time3} (1,3 1) = min (/'ec (1, 3 1) ) = min (15) = 15 © C ii-{Timel,Time2,Time3} (1,3 2) = min (m©c (1, 3 2) ) = min (18) = 18 © C ^{Timel,Time2,Time3} (1,3 3) = min (M©C (1, 3 3) ) = min (21) = 21 © C -U-{Timel,r!me2,Time3} (2,1 1) = min (2, 1 1) ) = min (12) = 12 © C •D-{Timel,Time2,rij?ie3} (2,1 2) = min 2, 1 2) ) = min(20) = 20 © C -U-{Ti??iel,Time2,Time3} (2,1 3) = min v/'© C % 1 3) = min(23) = 23 © C ^{Timel,Time2,Time3} (2,2 1) = min ÍM©c % 2 1) ) = min (14) = 14 © C ^{Timel,Time2,Time3} (2,2 2) = min ÍM©c [2, 2 2) ) = min(22) = 22 © C -U-{Timel,r!me2,Time3} (2,2 3) = min ÍMffic % 2 3) ) = min(25) = 25 © C |l-{Timel,Ti?7je2.Time3} (2,3 1) = min !m© c '2, 3 1) = min(ll) = 11 © C -U-{Timel,Time2,Time3} (2,3 2) = min í/<© c 2, 3, 2) = min (19) = 19 © C ii-{Timel,Time2,Time3} (2,3, 3) = min /<© c 2, 3, 3) = min(22) = 22 © C ii-{Timel,Time2,Time3} (3,1, 1) = min ÍM©c 3, 1, 1) = min (13) = 13 © C ^{Timel,Time2,Time3} (3,1, 2) = min f®c 3, 1, 2) = min(16) = 16 © C -U-{Timel,r!me2,Time3} (3, h 3) = min V© c 3, 1, 3) = min (24) = 24 © C -U-{T2'mel,Tirae2,ríme3} (3,2, 1) = min M©c 3,2, 1) = min(15) = 15 © C -U-{Ti??iel,Time2,Time3} (3,2, 2) = min /'©c 3, 2, = min (18) = 18 © C ^{Timel,Time2,Time3} (3,2, 3) = min M©c 3, 2, 3); = min(26) = 26 © C ii-{Timel,Time2,Time3} (3,3, 1) = min M©c 3, 3, i); = min(17) = 17 © C -U-{Timel,T!me2,Time3} (3, 3, 2) = min Mffic 3, 3, 2); = min(20) = 20 © C |!-{Timel,Ti?7je2.Time3} (3, 3, 3) = min Mffic 3, 3, 3); = min (28) = 28 8 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 4. ec4{Tirael = min(16,19, 0 c ^-{Timel. = min(13,16, 0 c ^-{Timel. = min(15,18, Timel. = min(12,20, Timel = min(14, 22, Timel = min(ll, 19, Timel = min(13,16, Timel. = min(15,18, Timel, = min(17, 20, *Time2} 22) = 16 ,Time2} (1,2) 19) = 13 Time'2} (1,3) 21) = 15 Time'2} (2,1) 23) = 12 ,Time'2} (2, 2) 25) = 14 Time'2} (2,3) 22) = 11 ,Time2} (3,1) 24) = 13 ,Time2} (3,2) 26) = 15 Time:2} (3, 3) 28) = 17 : min(/i0C(l, 1, l),/í®c(l, l,2),/i0c(l, 1,3)) min(M©c(l,2,l),M©c(l,2,2),p©c(l,2,3)) min(M© c(l, 3,1), m® c(l, 3, 2), M© c(l, 3, 3)) min(M© c(2,1,1), M0 c(2,1, 2), M© c(2,1, 3)) min(^e c(2, 2,1), /i© c(2, 2, 2), /<© c(2, 2, 3)) min(M© c(2, 3,1), M© c(2, 3, 2), M© c(2, 3, 3)) min(M© c(3,1,1), m® c(3,1, 2), M© c(3,1, 3)) min(M© c(3, 2,1), /*© c(3, 2, 2), /i© c(3, 2, 3)) min(Mec,(3, 3,1), /x© c(3, 3, 2), /í©c(3, 3, 3)) ; 5- 0 c 4{Timei} (1) = min(Me c(l, 1, l),Mec(l, 1, 2), MecU, 1, 3), M0c(l, 2,1), /i0c(l,2,2),Mec(l,2,3),M©c(l,3,l),Mec(l,3,2),Mec(l,3,3)) = = min(16,19, 22,13,16,19,15,18, 21) = 13 0C přimel} (2) = min(/t0c(2,1, l),/i©c(2,1, 2), M©c(2,1, 3), /,©c(2, 2,1), /tec(2,2,2),pec(2,2,3),/iec.(2,3,l),/íec(2,3,2),Mec(2,3,3)) = = min(12, 20, 23,14, 22, 25,11,19, 22) = 11 0 c 4{twi} (3) = min(M© c(3,1,1), M© c(3,1, 2), m© c(3,1,3), /x© c(3, 2,1), ^© c(3, 2, 2), M© c(3, 2, 3), M© c(3, 3,1), M© c(3, 3, 2), M© c(3, 3, 3)) = = min(13,16, 24,15,18, 26,17, 20, 28) = 13 9 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Příklady 4. — zadání 1. Uveďte plné i zkrácené názvy všech typů konzistence a konzistenčních algoritmů, které znáte. Uveďte jednotlivé pojmy a algoritmy systematicky se začleněním do skupin dle jejich typu. (Popisy algoritmů, typů konzistencí ani skupin neuvádějte, toto není součástí řešení, stačí uvádět pouze názvy se zkratkami.) 2. Ukažte podrobně, jak je aplikován algoritmus AC-4 pro zajištění hranové konzistence v následujícím příkladu (včetně postupných změn datových struktur). A,B, C g {0,1,2,3}, A z DA odstraníme hodnotu 3 a do Q přidáme (A, 3) Celkem: A g {0,1, 2}, B g {0,1, 2, 3}, C g {0,1, 2,3} Q = {(A,3)} Hrana (VB,VA): SAfi = {(B,l),(B,2),(B,3)} SA,i = {(B,2),(B,3)} SA,2 = {(B,3)} counter [(B, Ä), 0] = 0 => z Db odstraníme hodnotu 0 a do Q přidáme (B,0) counter [(B, Ä), 1] = 1 counter[(B, A),2] = 2 counter[(B, A),3] =3 Celkem: A g {0,1, 2}, B g {1, 2, 3}, C g {0,1, 2, 3} Q = {{A, 3), (B, 0)} Hrana (Vb, Vfc): komentář: Se i zůstane prázdná, protože 0 už není v doméně B Sc,2 = {(£>!)} Äc,3 = {(S,2)} komentář: counter [(B, C), 0] se nemění (je stále 0), protože 0 už není v doméně B counter[(B,C),l] = 1 counter [(B, C), 2] = 1 counter[(B, C), 3] = 0 => z Dg odstraníme hodnotu 3 a do Q přidáme (B, 3) Celkem: A g {0,1, 2}, B g {1, 2}, C g {0,1, 2, 3} Q = {(A, 3), (S, 0), (B, 3)} Hrana (Vc,Vb): Sb,i = Sb,iU{(C,2)} = {(A,0),(C,2)} Sb,2 = Sb,2 u {(C, 3)} = {(A, 0), (A, 1), (C, 3)} counter[(C, B), 0] = 0 => z odstraníme hodnotu 0 a do Q přidáme (C, 0) counter[(C, B), 1] = 0 (komentář: v Db už není hodnota 0) => z odstraníme hodnotu 1 a do Q přidáme (C, 1) couníer[(C,S),2] = 1 counter [(C, B), 3] = 1 Celkem: A g {0,1, 2}, S g {1, 2}, C g {2, 3} Q = {(A, 3), (B, 0), (S, 3), (C, 0), (C, 1)} Nyní je inicializace ukončena a pokračuje se v hlavním cyklu postupným výběrem prvků z Q, abychom zareagovali na odstranění jednotlivých hodnot proměnných v Q. Vybereme a smažeme (A, 3): Q = {(£,()),(£, 3), (C, 0), (C, 1)} Nic se nemění, (A, 3) nepodporoval žádný prvek (Sa,3 = 0)- Vybereme a smažeme (B,0): Q = {(B,3),(C,0),(C,l)} Nic se nemění, (B,0) nepodporoval žádný prvek (Sb,o = 0)- 12 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Vybereme a smažeme (B, 3): counter[(A,B),0] = 2 counter[(A, B), 1] = 1 counter[(A, B), 2] = 0 =3- z Da odstraníme hodnotu 2 a do Q přidáme (A 2) .4e{o,i},Be{i,2},Ce{2,3) Q = {(C,0),(C,1),(A,2)} Vybereme a smažeme (C, 0): Q = {(C,1),(A,2)} Nic se nemění, (C, 0) nepodporoval žádný prvek (Sc,o — 0)- Vybereme a smažeme (C, 1): Q = {(A,2)} Nic se nemění, (C, 1) nepodporoval žádný prvek (í>c,i = 0)- Vybereme a smažeme (A, 2): Q = 0 (A, 2) je podporou pro hodnotu, která byla odstraněna (Sa,2 = {{B,3)}), snížíme counter[(B,A),3], do Q se nic nepřidává Výsledek: .4 g {0,1}, B e {1, 2}, C g {2, 3}. 13 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 3. příklad Řešení pro algoritmus DAC Hrany grafu jsou (XI, X2), (X2, XI), (XI, X3), (X3, XI), (X2, X4), (X4,X2), na běh algoritmu mají vliv pouze hrany (XI, X2), (XI,X3), (X2,X4). Algoritmus prochází proměnné v opačném pořadí než je jejich uspořádání: Procházíme proměnnou X4: Jediná zasažená hrana je (X2, X4), z domény X2 odstraníme hodnotu 4, X2 g {1,2, 5} Procházíme proměnnou X3: Jediná zasažená hrana je (XI, X3), z domény XI odstraníme hodnotu 2, XI g {1,4, 5} Procházíme proměnnou X2: Jediná zasažená hrana je (XI, X2), z domény XI odstraníme hodnotu 4, XI g {1,5} Procházíme proměnnou XI: Není zasažena žádná hrana, nic se nemění. Výsledek DAC: XI g {1,5},X2 g {1,2,5},X3 g {1,3,4,5},X4 g {1,2,3,5}. 14 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Řešení pro algoritmus AC Na začátku inicializujeme frontu: Q = {(A4, A2), (A2, A4), (A3, XI), (XI, A3), (A2.A1), (AI, A2)}. Hlava fronty je vlevo. Vybereme a smažeme (A4, A2) A4 G {1,2,5} Q = {(A2, A4), (A3, AI), (AI, A3), (A2, AI), (AI, A2)} Vybereme a smažeme (A2, A4) A2 G {1,2,5} Q = {(A3, AI), (AI, A3), (A2, AI), (AI, A2)} Vybereme a smažeme (A3, AI) A3 G {1,4,5} Q = {(AI, A3), (A2, AI), (AI, A2)} Vybereme a smažeme (A1,A3) AI G {1.4.5} Q = {(A2,A1),(A1,A2)} Vybereme a smažeme (A2, AI) A2 G {1,5}, do fronty přidáme (A4,A2) Q = {(A1,A2),(A4,A2)} Vybereme a smažeme (A1,A2) AI G {1,5}, do fronty přidáme (A3,A1) Q = {(A4,A2),(A3,A1)} Vybereme a smažeme (A4, A2) A4G {1.5} Q = {(A3,A1)} Vybereme a smažeme (A3, AI) A3 G {1,5} Q = 0 Výsledek AC: AI G {1, 5}, A2 G {1, 5}, A3 G {1, 5}, A4 G {1, 5}. 15 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Příklady 5. — zadání 1. Ukažte, jak vypadá graf stavového prostoru pro řešení problému • proměnné: A g {2,3}, S g {1,2, 3}, C g {1,2, 3}, D g {1,2} • omezení: c\ : A ^ B, c2 : B = C, C3 : B 7^ D, C4 : C 7^ D algoritmem (a) backtrackingu (b) kontroly dopředu (forward checking) při uspořádání proměnných A, B, C a při uspořádání hodnot od nejmenší k největší. Ve vašem řešení uveďte pro každý algoritmus jeden graf stavového prostoru. V každém uzlu grafu uveďte, které domény proměnných se v důsledku propagací změnily a která omezení tyto změny způsobila. 2. Nalezněte první řešení problému • proměnné: XI g {a, b, c], X2 e {b, c}, X3 e {a,b}, X 4 g {c, d} • omezení: a : XI = X2, c2 : XI ^ X3, c3 : XI = X4 algoritmem Gaschnigova skoku zpět při uspořádání proměnných X1,X2,X3,X4 a při uspořádání hodnot a,b,c,d. Jako součást řešení popište postupné změny hodnot proměnných, hodnot latesti, hodnoty i (hlavní cyklus algoritmu) a hodnoty k (při výběru hodnoty) a dále uveďte, které omezení bylo kontrolované v daném kroku (včetně uvedení úspěchu resp. neúspěchu), např. postupným zaznamenáváním změn hodnot a uvedením kontrolovaných omezení do tabulky se sloupci i, XI, latesti, X2,latesÍ2, X3,latest^, X4,latest4, k, omezení, úspěch/neúspěch nebo postupným uváděním těchto informací (ve strukturovaném textu). 16 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 Příklady 5. — řešení 1. příklad Používané značení: • vnitřní uzel, O řešení, ■ chybné přiřazení. Backtracking 17 FI MU: PA163 Programování s omezujícími podmínky: řešené příklady 12. září 2018 2. príklad Slovní popis: Z D[ se výbere: Z D'2 se výbere: Skok zpet k XI: Z D'2 se výbere: Z D'3 se výbere: Z D'A se výbere: Skok zpet k XI: Z L>2 se výbere: Z Dí, se výbere: Z D4 se výbere: hodnota a hodnota b - není konzistentní s XI (omezení ci) hodnota c - není konzistentní s XI (omezení ci) z L>í se vybere hodnota 6 hodnota b - je konzistentní s XI (omezení ci) hodnota a - je konzistentní s XI (omezení C2) hodnota c - není konzistentní s XI (omezení C3) hodnota d - není konzistentní s XI (omezení C3) z L>í se vybere hodnota c hodnota b - není konzistentní s XI (omezení ci) hodnota c - je konzistentní s XI (omezení ci) hodnota a - je konzistentní s X2 (omezení C2) hodnota c - je konzistentní s XI (omezení C3) První řešení: XI = c, X2 = c, X3 = a, X4 = c. V jednom kroku je nastavena hodnota proměnné, nastaven čítač k, realizován konzistenční test a aktualizovaná hodnota latesU (prvotní inicializace latesU na 0 není uvedena v samostatném kroku). V tabulce uvedena vybraná hodnota z D[ jako Xi, nicméně ke skutečnému přiřazení by došlo až po ukončení procedury výběru hodnoty. i XI, latesti X2, latesÍ2 X3, latests X4, latesti k omezení, úspěch/neúspěch 1 a,0 - - - 1 - 2 a,0 6,1 - - 1 ci, neúspěch 2 a,0 c,l - - 1 ci, neúspěch 1 6,0 - - - 1 - 2 6,0 6,1 - - 1 ci, úspěch 3 6,0 6,1 a, 1 - 1 C2, úspěch 3 6,0 6,1 a, 2 - 2 - 4 6,0 6,1 a, 2 c,l 1 C3, neúspěch 4 6,0 6,2 a, 2 d,l 1 C3, neúspěch 1 c,0 - - - 1 - 2 c,0 6,1 - - 1 ci, neúspěch 2 c,0 c,l - - 1 ci, úspěch 3 c,0 c,l a, 1 - 1 C2, úspěch 3 c,0 c,l a, 2 - 2 - 4 c,0 c,l a, 2 c,l 1 C3, úspěch 4 c,0 c,l a, 2 c,2 2 - 4 c,0 c,l a, 2 c, 3 3 - 18 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 Příklady 6. — zadání 1. Uveďte plné i zkrácené názvy všech prohledávacích algoritmů, které znáte. Uveďte jednotlivé algoritmy systematicky se začleněním do skupin dle jejich typu. (POZOR: Popisy algoritmů, skupin ani další pojmy neuvádějte! Toto není součástí řešení, je nutné uvádět pouze názvy a případné zkratky.) 2. Napište řešení následujícího příkladu v OPL. Kód řádně okomentujte. Určete čas a místnost pro výuku množiny předmětů. Problém řešte obecně, přičemž si vytvořte jednu datovou instanci, která bude mít následující hodnoty parametrů: (a) rozvrh tvoříte pro 3 vyučovací dny a každý den má 10 hodin (b) máte zadáno 14 předmětů (c) délka výuky předmětu je 4 nebo 5 hodin (d) máte k dispozici 3 místnosti (e) máte zadány 3 třídy (skupiny žáků) (f) každá třída má v zadání určeno 4 až 5 předmětů, které bude navštěvovat Do řešení zahrňte tyto omezující podmínky: (g) výuka předmětu musí probíhat souvisle bez přerušení (tj. nesmí např. začínat jeden den večer a končit druhý den ráno) (h) v každé místnosti je nejvýše jeden předmět v danou dobu (i) pro každou třídu je zadána množina jejích předmětů; každá třída může mít vždy nejvýše jeden z těchto předmětů v danou dobu A aplikujte následující účelovou funkci: (j) Jednotlivé předměty by měly být do rozvrhu umístěny tak, aby výuka všech tříd skončila co nejdříve (např. třetí den dopoledne). Minimalizujte tedy nejpozdější koncový čas výuky posledních předmětů všech tříd. 19 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 Příklady 6. — řešení 1. příklad • Generuj a testuj - Generate and Test • Stromové prohledávání — Backtracking (BT) — Pohled dopředu — Look Ahead (LA) * Kontrola dopředu - Forward Checking (FC) * Částečný pohled dopředu - Partial Look-Ahead (PLA) * Úplný pohled dopředu - Full Look-Ahead (FLA) * Opravdový úplný pohled dopředu - Real Full Look-Ahead (RFLA) — Pohled zpět — Look Back * Gaschnigův skok zpět - Gashnig's Backjumping (GBJ) * Konflikty řízený skok zpět - Conflict-Directed Backjumping (CBJ) * Učení skoku zpět - Jumpback Learning * Dynamický backtracking (DB) * Backmarking — Neúplná stromová prohledávání * Randomizovaný backtracking - Random Search (RS) * Randomizovaný backtracking s učením * Omezení počtu návratů - Bounded-Backtrack Search (BBS) * Omezení hloubky - Depth-Bounded Search (DBS) * Prohledávání s kreditem - Credit Search (CS) * Iterativní rozšiřování - Iterative Broadening (IB) * Prohledávání s diskrepancemi ■ Omezené diskrepance - Limited Discrepancy Search (LDS) ■ Vylepšené omezené diskrepance - Improved Limited Discrepancy Search (ILDS) ■ Hloubkou omezené diskrepance - Depth-Bounded Discrepancy Search (DDS) • Lokální prohledávání (LS) — Největšího stoupání - Hill Climbing (HC) — Minimalizace konfliktů - Minimum Conflict (MC) — Náhodná procházka - Random Walk (RW) — Tabu prohledávání - Tabu Search (TS) — Simulované žíhání - Simulated Annealing (SA) — Kombinace algoritmů (HC+MC, HC+TS, MC + RW, HC + RW, ...) — Greedy SAT (GSAT) • Iterativní dopředně prohledávání - Iterative Forward Search (IFS) • Hybridní prohledávání — Lokální prohledávání před stromovým prohledáváním — Stromové prohledávání před lokálním prohledáváním — Stromové prohledávání doplněné lokálním prohledáváním — Lokální prohledávání doplněné stromovým prohledáváním 20 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 2. příklad Dny = 3; Hodin = 10; Předmětu = 14; Trváni = [4,5,5,4,4,5,4,5,4,5,4,5,4,5]; Mistnosti = 3; Tridy = 3; PredmetyTrid = { <1,1>, <1,2>, <1,3>, <1,4>, <1,5>, <2,6>, <2,7>, <2,8>, <2,9>, <3,10>, <3,11>, <3,12>, <3,13>, <3,14> >; using CP; // přirazení všech hodnot z datového souboru int Dny = ...; int Hodin = ...; int Předmětu = ...; int Trváni[1..Předmětu] = ...; int Mistnosti = ...; int Tridy = ...; // pomocné range range rTridy = 1..Tridy; range rPredmety = 1..Předmětu; range rMistnosti = 1..Mistnosti; // tuple zaznamenávající přiřazení předmětu ke třídám tuple predmetyTridí int trida; int předmět; > // naplnění tuple z datového souboru ípredmetyTrid}- PredmetyTrid = . . . ; // přiřazení času předmětům v maximálním rozmezí Dny*Hodin, přiřazení trvání dvar interval casy[p in rPredmety] in 0 .. Dny * Hodin size Trváni[p]; // volitelný interval pro přiřazení předmětů a tříd do místnosti dvar interval přirazeni[rMistnosti][PredmetyTrid] optional; // sekvence rozvrhu tříd, z důvodu nepřekrývání dvar sequence rozvrhTridy[t in rTridy] in all (m in rMistnosti, pt in PredmetyTrid : pt.trida == t) přirazeni[m][pt]; // sekvence rozvrhu místnosti, z důvodu nepřekrývání dvar sequence rozvrhMistnosti[m in rMistnosti] in all (pt in PredmetyTrid) přirazeni [m] [pt] ; // minimalizace konce posledního předmětu přes všechny třídy minimize max(p in rPredmety) endOf(easy[p]); subject toí // promazání domén, tak aby předmět nezačínal jeden den a končil druhý forali(p in rPredmety) startOf (easy [p]) 7« Hodin <= (Hodin-Trvani [p]) ; 21 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 // zamezení výuky dvou předmětů pro jednu třídu zároveň forali(t in rTridy) noOverlap(rozvrhTridy[t]); // zamezení výuky dvou předmětů v jedné místnosti forali(m in rMistnosti) noOverlap(rozvrhMistnosti[m]); // pro každý předmět přiřazení jednoho volitelného intervalu (místnosti) forali(pt in PredmetyTrid) alternativě(casy[pt.předmět], all(m in rMistnosti)prirazeni[m][pt]); > // výpis pro kontrolu řešení executeí for(var t=l; t <= Tridy; t++){ writeln("Rozvrh "+t+". třídy:"); for(var p in PredmetyTrid){ if(p.trida==t){ write("Předmět " + p.předmět + ": " + casy[p.předmět].start + "-" + casy[p.předmět].end); for(var m=l; m<=Mistnosti; m++){ if(přirazeni[m][p].present)writeln(" v " + m + ". místnosti"); > > > writelnO ; > > 22 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 Příklady 7. — zadání 1. Uvedený CSP převeďte pomocí duálního problému na binární CSP. Máte zadány proměnné A, D, E, F s doménou {0,1}, dále B e {1, 2}, C e {1, 2, 3} a omezení ci : A + B = C c2 : A + D + E = 1 c3: A + £ - F > 0 c4 : C* + S > 2 2. Uveďte všechny podpory hodnot pro následující problém • proměnné A, B, C mohou nabývat hodnot 3, 4, 5, • A < B, B > C. 3. Ukažte, jak vypadají propagační pravidla konzistence mezí pro omezení y = x — c za předpokladu, že c je konstanta a x, y jsou doménové proměnné. Ukažte průběh propagací (včetně aplikace Vámi navržených propagačních pravidel) při použití konzistence mezí v následujícím příkladu. re{o,...,io} x e {o,...,5,8,9,10} y = x-3 Nastal by v příkladu nějaký rozdíl, pokud bychom místo konzistence mezí použili hranovou konzistenci? 4. Uveďte jednotlivé kroky algoritmu DAC na následujícím příkladu při uspořádání proměnných D, C, B, A. Proměnné a omezení: A, B,C, D € {1, 2, 3, 4} Cl : A+l = B c2: C = A c4 : B + 1 = D Uveďte postup, jakým způsobem najdeme jednotlivá řešení bez navracení. 23 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 Příklady 7. — řešení 1. příklad Podmienku c\ prevedieme na duálnu premennú v\ s doménou {(0,1,1), (0, 2, 2), (1,1, 2), (1, 2, 3)}. Podmienku cg prevedieme na duálnu premennú «2 s doménou {(0, 0,1), (0,1, 0), (1, 0, 0)}. Podmienku c3 prevedieme na duálnu premennú «3 s doménou {(1, 0, 0), (0,1, 0), (1,1,1), (1,1, 0)}. Podmienku c4 prevedieme na duálnu premennú «4 s doménou {(2,1), (3, 0), (3,1)}. Pre každú dvojicu podmienok Cj a Cj zdieľajúcu premenné, zavedieme binárnu podmienku medzi Vi a v j, obmedzujúcu duálně premenné na fc-tice, v ktorých majú zdieľané premenné rovnakú hodnotu. V'2 (0,1,1), (0,2, 2), i?ll (0,0,1), (0,1,0), (1,1, 2), (1,2, 3) (1,0,0) i?ll \R31 i?32 (1,0,0), (0,1,0), (2,1), (3,0), Vi (1,1,1), (1,1,0) i?22 (3,1) .R11&.R32 Obrázek 1: Diagram duálnych premenných a binárnych podmienok medzi nimi Obrázek 2: Diagram podpôr jednotlivých hodnôt Zápis < A, a > znamená hodnota a z domény premennej A. Hodnota 3 & A má podpory {< B, 3 >, < B, 4 >, < B, 5 >}. Hodnota 4 G A má podpory {< B, 4 >, < B, 5 >}. Hodnota 5 G A má podpory {< B, 5 >}. Hodnota 3 G B má podpory {< A, 3 >}. Hodnota 4 e B má podpory {< A, 3 >, < A, 4 >, < C, 3 >}. Hodnota 5 e B má podpory {< A, 3 >, < A, 4 >, < A, 5 >, < C, 3 >, < C, 4 >}. Hodnota 3 G C má podpory {< B, 4 >, < B, 5 >, }. Hodnota 4 G C má podpory {< B, 5 >}. Hodnota 5 G C nemá žiadnu podpora. 24 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 3. příklad Pravidlá: min(Y) > min(X) - C min(X) > min(Y) + C min(X) > min(Y) + C max(X) < max(F) + C Postup: Y = X - 3 min (y) > 0 - 3, max(r) < 10 - 3 Y € {0,..., 7} min(X) > 0 + 3, max(X) < 10 + 3 X e {3, 4, 5, 8, 9,10} Po ukončení propagácie pri použití konzistencie medzí má premenná Y doménu {0,..., 7} a premenná X doménu {3, 4, 5, 8, 9,10}. Ak by sme v príklade použili namiesto konzistencie medzí hranovú konzistenciu, hodnoty 3 a 4 by z domény premennej Y vypadly, pretože nemajú žiadnu doménovú podporu. 4. příklad Algoritmus DAC začína vo vrchole/premennej A (posledná premenná v danom usporiadaní). Následne sa zrevidujú všetky hrany, ktoré do vrcholu A vedú. Pri revízii hrany (B, A) zistíme, že z domény premennej B môžeme odstrániť hodnotu 1 pretože v doméne premennej A neexistuje hodnota, ktorá by s ňou v na základe podmienky c\ bola konzistentná. Takisto sa zreviduje hrana (C, A), no žiadnu hodnotu z domény C neodstraňujeme. Pokračujeme vrcholom B a proces sa opakuje. Do vrcholu B vedie len hrana (D, B). Pri revízii tejto hrany zistíme, že z domény premennej D môžeme odstrániť hodnoty 1 a 2. Ďalej skontrolujeme vrchol C, do ktorého vedie len hrana (D, C). Po jej revízii nenastáva žiadna zmena. Do posledného vrcholu D už nevedú žiadne hrany a algoritmus teda skončí. Po algoritme DAC vypadajú teda domény následovne: A e {1, 2, 3, 4}, B e {2, 3, 4}, C e {1, 2, 3, 4} a D e {3.4}. Obrázek 3: Postup algoritmu DAC Napriek tomu, že tento problém má niekoľko riešení (napr. A = 1, B = 2, C = 1 a D = 3), nie je možné nájsť riešenie bez navrátenia vzhľadom na dané usporiadanie premenných. Toto usporiadanie premenných má šírku 2, DAC nám teda na zabezpečenie nájdenie riešenia bez vracania nestačí. 25 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 Příklady 8. — zadání 1. Ukažte, jak vypadá graf stavového prostoru pro řešení problému • proměnné: A e {1,2,3}, Be{2,3}, C €{1,2,3,4}, L>e{2,3,4} • omezení: c\ : A = B, c2 : C > B, c3 : D < B algoritmem (a) backtrackingu (b) kontroly dopředu (forward checking) (c) pohledu dopředu (look ahead) bez iniciální konzistence při uspořádání proměnných A, B, C, D a při uspořádání hodnot od nejmenší k největší. Ve vašem řešení uveďte pro každý algoritmus jeden graf stavového prostoru. V každém uzlu grafu uveďte, které domény proměnných se v důsledku propagací změnily a která omezení tyto změny způsobila. 2. Napište řešení následujícího příkladu v OPL. Kód řádně okomentujte, Vyřešte následující problém plánování projektu. Projekt se skládá z množiny úkolů U a pracuje na něm m lidí tak, že každý člověk c pracuje pouze na svých předem zadaných úkolech Uc, tj. U = IJ^Li Uc a pro každé dva lidi a, b platí Ua n Ub = 0- Každý úkol má tedy stanoveného člověka, který na něm pracuje, a dále má stanovenu dobu trvání. Úkoly jsou na sobě časově závislé. Časové závislosti jsou následujícího typu: • fc-tý úkol a l-tý úkol musí začínat zároveň, • i-tý úkol musí začít až po ukončení úkolu j-tého úkolu. Každý člověk c smí pracovat nejvýše na wc úkolech zároveň. Určete, kdy mají být jednotlivé úkoly v projektu realizovány tak, aby byl minimalizován součet koncových časů všech úkolů v projektu. Řešení otestujte na následujícím problému (tj. musíte použít odpovídající datovou sadu, kterou odevzdejte jako součást řešení): úkol 1 2 3 4 5 6 7 8 9 10 11 12 13 14 doba trvání 3 2 1 4 2 4 2 1 1 3 2 2 1 1 člověk 1 1 1 1 1 2 2 2 2 2 3 3 3 3 Kapacita lidí: Wl = 2 w2 = 2 w3 = 1 Úkoly začínající zároveň (k a l): 1 a 2, 7 a 8 Úkoly po sobě (i po j): 3 po 1, 6 po 7 26 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 1. příklad Příklady 8. — řešení Graf stavového prostoru pro řešení problému algoritmem backtracking. Fail na úrovní stromu pro proměnnou B nastává z důvodů failu omezení c\. Fail na úrovní stromu pro proměnnou C nastává z důvodů failu omezení c2. Fail na úrovní stromu pro proměnnou D nastává z důvodů failu omezení c3. A B C D Graf stavového prostoru pro řešení problému algoritmem forward checking. A B C D Cl^Be {X,X} => fail ca => C e {X,2,3,4} c3 => D G {XXX} => fail ci => B e {X,3} c2 => C e {X,X,3,4} c3 ^ D e {2,X,X} Graf stavového prostoru pro řešení problému algoritmem look ahead. A B C D ci => B e {X,X} => fail 3 ci => B e {X,3} c2 => C e {X,X,3,4} c3 => í? e {2,X,X} 27 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 2. příklad /****************** *.dat soubor *******************************************/ pocetUkolu = 14; pocetOsob = 3; úkoly = [<3,1>,<2,1>,<1,1>,<4,1>,<2,1>, <4,2>,<2,2>,<1,2>,<1,2>,<3,2>, <2,3>,<2,3>,<1,3>,<1,3>]; limit = [2,2,1]; prec = {<3,1>,<6,7>>; same = {<1,2>,<7,8>>; 28 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 12. září 2018 using CP; tuple Ukol { int trváni; int osoba; > tuple Prec { int Po; int Pred; > tuple Same { int Prvni; int Druha; > int pocetUkolu = ... ; int pocetOsob = ...; Ukol úkoly[1..pocetUkolu] = ...; int limit[1..pocetOsob] = ...; {Prec} prec = ...; {Same} same = ...; // doménové proměnné pro startovni easy dvar interval easy [u in 1..pocetUkolu] size úkoly[u].trváni; // kumulativni funkce pocitajici vytizeni osob v case cumulFunction osoby[o in 1..pocetOsob] = sum (u in 1..pocetUkolu: úkoly[u].osoba == o) pulse(easy[u],1); // minimalizace součtu koncových casu minimize sum (u in 1..pocetUkolu) endOf(easy[u]); subject to { // omezime maximalni zatizeni kazde osoby v kazdem case forall (o in 1..pocetOsob) osoby[o] <= limit [o]; // precedeneni podminky forall (p in prec) endBeforeStart(easy[p.Pred],easy[p.Po]); // stejné startovni easy forall (s in same) startAtStart(easy[s.Prvni],easy[s.Druha]); } 29 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 Příklady 9. — zadání 1. Ukažte podrobně, jak pracuje algoritmus pro řešení stromového CSP na následujícím příkladu při uspořádání proměnných (VI, V2, V'í, V A, V5): • všechny proměnné mají doménu {0,1, 2, 3}, • VI < V2, VI * U3 < 2, U4 = V2 + 1, U3 > U5. Jako součást řešení uveďte stromovou reprezentaci tohoto CSP problému. Dále odvoďte algoritmem řešení bez navracení všechna řešení problému, kdy pro proměnné postupně vybírejte hodnoty od nejmenší k největší. 2. Ukažte podrobně, jak pracuje algoritmus PC-2 na následujícím příkladu a uveďte výsledné domény proměnných. • Proměnné XI, X2, X'í mají doménu {0,1, 2, 3, 4, 5, 6}. • Omezení: XI + 2 < X2, X2 + 1 < X3. Je nějaké nové omezení odvozeno jako důsledek konzistence po cestě? 3. Vyřešte následující rozvrhovací problém v OPL. V jedné místnosti probíhá výuka několika přednášek, které je třeba rozvrhnout bez překrytí. Přednášky mají stanoven nejdřívější čas zahájení a nejpozdější čas dokončení. Některé přednášky na sebe navazují, proto musí být dodrženo pořadí těchto přednášek. Výuku poslední přednášky ukončete co nejdříve. Všechna vstupní data musí být uvedena v samostatném datovém souboru. Při návrhu doménových proměnných, omezení i účelové funkce berte v úvahu efektivitu výpočtu. Řešení otestujte na následujícím problému. přednáška 1 2 3 4 5 doba trvání 1 2 1 3 1 nejdřívější čas 8 8 9 10 10 nejpozdější čas 16 16 16 20 20 Precedence: 2 před 1, 3 před 2, 5 před 4. 4. Ukažte, jak vypadá graf stavového prostoru pro řešení problému • proměnné: A, B,C,D e {0,1, 2, 3, 4, 5}, • omezení: cl : A > 2 * B, c2 : B > C, c3 : C = D + 1 algoritmem (a) kontroly dopředu (forward checking) a (b) pohledu dopředu (look ahead) bez iniciální konzistence při uspořádání proměnných A, B,C,D a při uspořádání hodnot od nejmenší k největší. Ve vašem řešení uveďte pro každý algoritmus jeden graf stavového prostoru. V každém uzlu grafu uveďte, nejen které domény proměnných se v důsledku propagací změnily, ale i jak byly tyto domény postupně upravovány jednotlivými omezeními. 30 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 5. Napište řešení následujícího příkladu v OPL. Je zadán počet dnů a počet zaměstnanců, kteří každý den pracují na jedné směně. Všechny směny jsou stejně dlouhé. Každý zaměstnanec má přitom určeno předem, kdy jeho směna během dne začíná, a každý zaměstnanec pracuje každou směnu právě na jednom z několika alternativních úkolů. Pro každý úkol máme určeno: • jakou má preferenci, • max. počet hodin, který na něm může každý zaměstnanec za celou dobu pracovat a • maximální počet zaměstnanců, kteří můžou na úkolu pracovat zároveň. Přiřaďte úkol každé směně zaměstnance tak, aby byly minimalizován součet preferencí realizovaných hodin úkolů za celou dobu. Při návrhu doménových proměnných, omezení i účelové funkce berte v úvahu efektivitu výpočtu. Řešení otestujte na následujícím problému (tj. musíte použít odpovídající datovou sadu, kterou odevzdejte jako součást řešení): úkol 12 3 4 preference max. počet hodin max. počet zaměstnanců 12 3 4 8 16 8 16 12 12 • počet dnů 5, délka dne: 24, délka směny: 8, počet zaměstnanců: k • počáteční čas směny pro jednotlivé zaměstnance: 6,6,14,14,6,14,6,14,6 31 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 Příklady 9. — řešení 1. příklad Grafová reprezentace: VA=V2+1 Algoritmus prochází strom od poslední proměnné v uspořádání po první a v každém kroku upravuje (omezuje) doménu rodičovské proměnné. - domény na začátku: VI, V2, V3, V A, V5 € {0,1, 2, 3} 1. V3 > V5 => V3 e {1,2,3} 2. V A = V2 + 1 V2 e {0,1, 2} 3. F1*F3 < 2^ Fl e {0,1} 4. VI < V2 => VI e {0,1} - domény na konci: VI € {0,1}, V2 e {0,1, 2}, V3 € {1, 2, 3}, F4 e {1, 2, 3}, € {0,1, 2, 3} Dále jsou konzistentně instanciovány proměnné v pořadí od VI k V5. Je zaručeno, že problém je řešitelný bez navracení díky směrové hranové konzistenci zaručené po zpracování algoritmem pro stromové CSP. VI V2 V3 VA V5 Všechna možná řešení jsou tedy: 32 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 VI V2 V3 VA V5 0 1 1 2 0 0 1 2 2 0 0 1 2 2 1 0 1 3 2 0 0 1 3 2 1 0 1 3 2 2 0 2 1 3 0 0 2 2 3 0 0 2 2 3 1 0 2 3 3 0 0 2 3 3 1 0 2 3 3 2 1 2 1 3 0 33 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 2. příklad Jsou inicializovány binární relace mezi dvojicemi i, j na základě omezení a domén ze zadání: XI {0,...,6} X2 {0,...,6} X3 {0,...,6} • XI + 2 < X2 • X2+1< X3 Ri {(0, 3), (0,4), (0, 5), (0, 6), (1,4), (1, 5), (1, 6), (2, 5), (2, 6), (3, 6)} Ri e {0,1,2,3,4,5,6}} R-2 {(0, 2), (0, 3), (0,4), (0, 5), (0, 6), (1, 3), (1,4), (1, 5), (1, 6), (2,4), (2, 5), (2, 6), (3, 5), (3, 6), (4, 6)} Do fronty Q algoritmu PC-2 jsou iniciálně vloženy tyto cesty pro revizi: Q [(1,3, 2), (1,2, 3), (2,1,3)] Z fronty Q jsou odstraňovány trojice vrcholů (i, m, j) pro revizi, dokud není fronta prázdná. Když dojde k revizi, do fronty jsou přidány všechny trojice vrcholů, které mohou být ovlivněny právě provedenou revizí a které se ve frontě ještě nevskytují. Revize postupně omezují domény proměnných odstraňováním prvků z binárních relací Rij. Inicializace fronta Q [(1,3, 2), (1,2, 3), (2,1,3)] Rl,2 (0, 3) (0, 4) (0, 5) (0, 6) (1, 4) (1, 5) (1, 6) (2, 5) (2, 6) (3, 6) ^2,3 (0, 2) (0, 3) (0,4) (0, 5) (0, 6) (1, 3) (1,4) (1,5) (1, 6) (2,4) (2, 5) (2, 6) (3, 5) (3, 6) (4, 6) ■Rl,3 (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (i, o) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (3, 0) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6) (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6) (5, 0) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6) (6, 0) (6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6) 34 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 1. iterace revidovaná trojice původní fronta nové trojice nová fronta (1,3,2) [(1,3, 2), (1,2, 3), (2,1,3)] [(1,2,3), (2,1,3)] ^2,3 (0, 2) (0, 3) (0,4) (0, 5) (0, 6) (1, 3) (1,4) (1,5) (1, 6) (2,4) (2, 5) (2, 6) (3, 5) (3, 6) (4, 6) Rl,3 (0, 0) (0, 1) (0, 2) (0, 3) (0, 4) (0, 5) (0, 6) (i, o) (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (1, 6) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (2, 6) (3, 0) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5) (3, 6) (4, 0) (4, 1) (4, 2) (4, 3) (4, 4) (4, 5) (4, 6) (5, 0) (5, 1) (5, 2) (5, 3) (5, 4) (5, 5) (5, 6) (6, 0) (6, 1) (6, 2) (6, 3) (6, 4) (6, 5) (6, 6) 2. iterace revidovaná trojice původní fronta nové trojice nová fronta (1,2,3) [(1,2, 3), (2,1,3)] [í2r4^T,(2,3,l)] [(2,1,3), (2, 3,1)] (0,3) (0,4) £V5j £V6J (1,4) (X^) (X^) R'2,3 (0, 2) (0, 3) (0,4) (0, 5) (0, 6) (1, 3) (1,4) (1,5) (1, 6) (2,4) (2, 5) (2, 6) (3, 5) (3, 6) (4, 6) Ri, i^f) £V2? ^) {y% frtf {^) (frrf $<4) frrf {\^) {\^) fyrf i^) frrf (MŤ frtf (0, 5) (0, 6) iÚ*í (1,6) ^) 1^5) ^) 35 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 3. iterace revidovaná trojice původní fronta nové trojice nová fronta (2,1,3) [(2,1,3), (2, 3,1)] [(1,2,3),X1A^] [(2,3,1), (1,2,3)] Ri (0,3) (0,4) £V5j £V6J (1,4) (X^) (X^) R-2 i^r) i^S) {frrf {^) ^6) ix<<í ^ tyrf) (^) (3, 5) (3, 6) (4, 6) Ri i^f) (Skrf ($k^) ^) (0,5) (0,6) Qfrf £r^T {XSS) frrf i^) fyrf (X, <3,2>, <5,4>>; using CP; int number = ...; range Lectures = 1..number; int duration[Lectures] = ...; int earliest[Lectures] = ...; int latest[Lectures] = ...; tuple Prec { int Before; int After;} {Prec} precedences = ...; dvar interval start[1 in Lectures] in earliest[1]..latest[1] size duration[1]; dvar sequence seq in start; minimize max(l in Lectures) endOf(start[1]); subject to { noOverlap(seq); forall (p in precedences) endBeforeStart(start[p.Before].start[p.After]); } 37 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 4. příklad Kontrola dopředu (forward checking) C! : B £ {0} C! : B g {0 c £ {0,1,2} c3 : FAIL c3 : FAIL c3 : FAIL c3 : FAIL 0 D€{i\: 0 0 0 Pohled dopředu (look ahead) bez iniciální konzistence FAIL © 0 38 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 5. příklad pocetDnu = 5; pocetZamestnancu = 9; pocetUkolu = 4; trváni = 8; zaměstnanci = [<1,6>,<2,6><3,14>,<4,14>,<5,6>,<6,14>,<7,6>,<8,14>,<9,6>]; úkoly = [<1,1,8,1>,<2,2,16,2>,<3,1,8,3>,<4,2,16,4>] ; 39 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 7. října 2018 using CP; int pocetZamestnancu = . . . ; int pocetDmi = . . . ; int pocetUkolu = . . . ; int trváni = . . . ; range Zaměstnanci = 1..pocetZamestnancu; range Dny = 1..pocetDnu; range Úkoly = 1..pocetUkolu; tuple Ukol { key int id; int počet; int hodin; int preference; > tuple Zaměstnanec { key int id; int od; > Ukol úkoly[Úkoly] = . . . ; Zaměstnanec zaměstnanci[Zaměstnanci] = ...; dvar interval easy[z in Zaměstnanci][d in Dny] in zaměstnanci[z].od .. (zaměstnanci[z].od+trvani) size trváni; dvar interval přirazeni[z in Zaměstnanci][d in Dny][u in Úkoly] optional; cumulFunction pocetUkol[u in Úkoly][d in Dny] = sum (z in Zaměstnanci) pulse(přirazeni[z][d] [u],1); cumulFunction hodinUkol[u in Úkoly][z in Zaměstnanci] = sum (d in Dny) pulse(přirazeni[z][d][u],trváni); minimize sum (z in Zaměstnanci, d in Dny, u in Úkoly) presenceOf(přirazeni[z][d][u])*ukoly[u].preference; subject to { forali (z in Zaměstnanci, d in Dny) alternative(easy[z][d], all (u in Úkoly) přirazeni[z] [d][u]); forali (u in Úkoly, d in Dny) pocetUkol[u] [d] <= úkoly[u].počet; forali (z in Zaměstnanci, u in Úkoly) hodinUkol[u][z] <= úkoly[u].hodin; > 40 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 Příklady 10. - zadání 1. Uveďte všechny podpory hodnot pro následující problém • proměnné A, B, C, D mohou nabývat hodnot 0,1, 2 • A = B + 1,B D Je zaručeno, že najdeme řešení bez navracení (zdůvodněte Vaši odpověď)? Pokud ano, uveďte postup, jakým způsobem najdeme jednotlivá řešení bez navracení (všechna tato řešení v uvedeném postupu napište). 3. Napište řešení následujícího příkladu v OPL. Máme zadány obchody, ze kterých můžeme odebírat zboží, a několik poboček, kde každá z nich bude odebírat zboží právě z jednoho obchodu. U každé pobočky máme přitom stanoveno, jaká je cena za odběr z daného obchodu. Dále má každý obchod stanoven maximální počet poboček, které může obsluhovat (tj. kapacita obchodu). Určete pro každou pobočku jeden obchod, který ji bude obsluhovat tak, aby byla minimalizována cena za odběr zboží z obchodů všemi pobočkami. Řešení otestujte na následujícím problému (tj. musíte použít odpovídající datovou sadu, kterou odevzdejte jako součást řešení). Data pro tento problém jsou také k dispozici v souboru priklady_l0_obchody_vstup.txt. obchody Tesco Albert Penny Billa Lidi kapacita 1 4 2 1 3 pobočka 1 20 24 11 25 30 pobočka 2 28 27 82 83 74 pobočka 3 74 97 71 96 70 pobočka 4 2 55 73 69 61 pobočka 5 46 96 59 83 4 pobočka 6 42 22 29 67 59 pobočka 7 1 5 73 59 56 pobočka 8 10 73 13 43 96 pobočka 9 93 35 63 85 46 pobočka 10 47 65 55 71 95 Příklad neoptimálního řešení - pobočka/obchod: 1/Tesco, 2/Albert, 3/Albert, 4/Albert, 5/Albert, 6/Penny, 7/Penny, 8/Billa, 9/Lidl, 10/Lidl; cena tohoto řešení:20+27+97+55+96+29+73+43+46+95=581 4. Na prvním stromě ukažte, které větve projde kombinovaný algoritmus omezení počtu návratů (bounded-backtrack search BBS) a omezení hloubky (depth-bounded search DBS) ve variantě DBS(2, BBS(3)). Na druhém stromě uveďte průchod stromu pro DDS(4), tj. prohledávání s hloubkou omezenými diskrepancemi (depth-bounded discrepancy search, DDS). Uveďte, v jakém pořadí jsou prozkoumány jednotlivé větve při výběru hodnot zleva. 41 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 5. Jaká je úroveň konzistence pro následující fuzzy CSP problém P s omezeními cl, c2 a c3 a jaké dostaneme řešení? Jaká je úroveň splnění pro problém Pl=({cl,c2},{A}), tj. pro (clffic2) |!{A}? Uveďte postup řešení. P=({cl,c2,c3},{A,B}) dom(A)=dom(B)={x,y) con(cl)={A,B}, def(x,x)=0.1, def(x,y)=0.2, def(y,x)=0.4, def(y,y)=0.8 con(c2)={A}, def(x)=0.7, def(y)=0.9 con(c3)={B}, def(x)=0.5, def(y)=0.6 6. Napište řešení následujícího příkladu v OPL. V tovární hale se montují výrobky. Každý výrobek se postupně montuje na všech strojích ve stejném pořadí od prvního do posledního, tj. na každém stroji je prováděna právě jedna operace pro každý výrobek a operace jednoho výrobku jsou prováděny postupně jedna za druhou bez překrytí. Doba trvání každé operace je zadána. Na každém stroji se v daném čase může provádět nejvýše jedna operace. Každá operace vyžaduje ke svému provádění jednoho robota, přičemž má předem zadánu množinu robotů, které může použít. Každý robot může v daném čase pracovat na nejvýše jedné operaci. Každá operace vyžaduje ke svému provádění zadaný počet zaměstnanců. Každý zaměstnanec může pracovat nejvýše na jedné operaci a k dispozici je omezený počet zaměstnanců. Určete pro každou operaci její startovní čas a robota, který na ní bude pracovat tak, aby byl minimalizován čas dokončení celé výroby (není nutné určit, kteří zaměstnanci budou na dané operaci pracovat, stačí, aby byl zajištěn jejich dostatečný počet). Řešení otestujte na následujícím problému (tj. musíte použít odpovídající datovou sadu, kterou odevzdejte jako součást řešení). Pro první (jednodušší) variantu použijte první tři výrobky, pro druhou variantu použijte všech pět výrobků. 42 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 operace výrobek stroj doba trvání možní roboti počet zaměstnanců 11 1 1 1 1 3 12 1 2 2 1 2 13 1 3 3 1 2 21 2 1 4 2 2 22 2 2 5 1,2 1 23 2 3 6 2 2 31 3 1 6 1 4 32 3 2 5 1 1 33 3 3 4 1 5 41 4 1 2 1,2 5 42 4 2 2 1,2 5 43 4 3 2 1,2 5 51 5 1 4 2 3 52 5 2 7 1,2 3 53 5 3 6 2 3 pocetStroju = 3; pocetRobotu = 2; pocetZamestnancu = 5; varianta 1: počet Výrobku = 3; varianta 2: pocetVyrobku = 5; Příklad řešení pro menší problém (operace: start, robot) s časem dokončení 22 11: 0,1; 12:1,1; 13: 3,1 21: 1,2; 22: 5,2; 23:12,2 31: 6,1; 32:12,1; 33:18,1 43 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 Příklady 10. - řešení l.příklad Diagram podpôr jednotlivých hodnôt: 0 0 1 1 2 2 C D Podpory hodnôt: • A - podpory - podpory - podpory • B podpory podpory podpory pre hodnotu 0 € A: nemá podporu pre hodnotu lei: pre hodnotu 2 e A: < B, 1 > pre hodnotu 0 e B: < A, 1 >, < C, 1 >, < C, 2 > pre hodnotu 1 e B: < A, 2 >, < C, 2 > pre hodnotu 2 e B: nemá podporu • C pre hodnotu 0 e C: < D, 0 > pre hodnotu 1 e C: < B, 0 >, < D, 1 > podpory ] podpory ] podpory pre hodnotu 2 e C: < B, 0 >, < B, 1 >, < D, 2 > • D podpory pre hodnotu 0 e Ľ: < C, 0 > podpory pre hodnotu 1 e D: < C, 1 > podpory pre hodnotu 2 e D: < C, 2 > 44 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 2.příklad Algoritmus DAC pre dané usporiadanie premenných x\ až xn postupne prechádza premenné Xi v poradí xn až x\ a pre každú premennú reviduje hrany, ktoré vedú do vrchola reprezentujúceho X{. Kroky algoritmu DAC pre zadaný príklad a usporiadanie premenných A, B, C, D, E: 1. Vzhľadom na usporiadanie premenných algoritmus začína vo vrchole E. Do vrcholu E vedie jediná hrana, po jej zrevidovaní je z domény premennej D odstránené hodnota 3. (c4 : e > d) 2. Nasleduje vrchol D, do ktorého vedie jediná hrana a to z vrcholu B. Zrevidováním tejto hrany sa z domény premennej B ostránia hodnoty 2 a 3. (c^ : d = b + 1) 3. Nasleduje vrchol C, do ktorého vedie hrana z vrcholu A, jej zrevidováním sa doména premennej A nijako nezmení, (c-2 : C < A) 4. Nasleduje vrchol B, do ktorého vedie jediná hrana z vrcholu A. Jej zrevidováním sú z domény premennej A odstránené hodnoty 2 a 3. (ci ) 5. Do vrcholu A nevedie žiadna hrana, algoritmus končí. Výsledné domény: A e {0,1}, b e {0,1}, C* e {o, i, 2,3}, d e {o, 1,2}, e e {0,1,2,3} { 0, 1, 2, 3} [0, 1,2-8-f {0, 1r2, 3} {0, t-er*} {o, 45 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 Je zaručené, že nájdeme riešenie bez navrátenia. Zdôvodnienie: • Po aplikácií DAC je daný CSP smerovo hranovo konzistentný. • Pre dané usporiadanie je šírka grafu, ktorým je usporiadanie reprezentované 1. • Pretože graf má šírku 1, je to strom. • Teda máme usporiadanie stromového grafu podmienok, ktorý je smerovo hranovo konzistentný vzhľadom k tomuto usporiadaniu. Preto má daný CSP riešenie bez navrátenia. Nájdenie riešení bez navrátenia (v grafe stavového priestoru nie sú žiadne listy slepej vetvy): CO 0 1 D 1 2 2 E 2 3 3 3 Výsledné riešenia: (A, B, C, D, E) e {(0, 0, 0,1, 2), (0, 0, 0,1, 3), (1,1, 0, 2, 3), (1,1,1, 2,3)} 46 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 3.příklad *.dat soubor * * Shops = {Tesco, Albert, Penny, Billa, Lidi); NbBranches = 10; Capacity = [1,4,2,1,3]; SupplyCost = [ 20, 24, 11, 25, 30 ] 28, 27, 82, 83, 74 ] 74, 97, 71, 96, 70 ] 2, 55, 73, 69, 61 ] 46, 96, 59, 83, 4 ] 42, 22, 29, 67, 59 ] 1, 5, 73, 59, 56 ] 10, 73, 13, 43, 96 ] 93, 35, 63, 85, 46 ] 47, 65, 55, 71, 95 ] ]; *.mod soubor * using CP; {string} Shops = ...; int NbBranches = ...; range Branches = 0..NbBranches-1; int Capacity[Shops] = ...; // maximum number branches assigned to each shop int SupplyCost[Branches] [Shops] = ...; // supply cost between each branchee and each shop dvar boolean Supply[Branches][Shops]; // 1 if store supplied by shop, 0 otherwise dvar int+ TotalCost; // additional domain variable for the optimization cost minimize TotalCost; subject to { forall ( s in Branches ) sum( w in Shops ) Supply[s][w] == 1; forall ( w in Shops ) sum( s in Branches ) Supply[s] [w] <= Capacity[w]; TotalCost == sum( w in Shops , s in Branches ) SupplyCost[s][w] * Supply[s][w]; } 47 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 4.příklad 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1 2 3 4 5 6 7 8 5.příklad Úroveň konzistence problému P spočítáme jako projekci kombinace všech omezení na prázdnou množinu proměnných ffiC jl-0 (kde ffiC = ci ffi c2 ffi c3): eC 40= max{^ec (x, x), ^eC (a;, y), ^ec (ž/,z), Mec (ž/, ž/)} /í0C (x, x) = min{/ici (a;, x), /iC2 (a;), /iC3 (a;)} = min{0.1, 0.7, 0.5} = 0.1 Mec (a;, y) = min{^ci (x, y), fiC2 (x), ^C3 (y)} = min{0.2, 0.7, 0.6} = 0.2 Mec (y, x) = min{^ci (y, x), fiC2 (y), fiC3 (x)} = min{0.4, 0.9, 0.5} = 0.4 Mec (y, y) = min{^ci (y, y), fiC2 (y), fiC3 (y)} = min{0.8, 0.9, 0.6} = 0.6 ®C* ^0= max{0.1, 0.2, 0.4, 0.6} = 0.6 Úroveň konzistence problému P je tedy 0.6 a dostaneme řešení {A/y, B/y}. Úroveň splnění pro problém Pi spočítáme jako ffiC' 4{A} (kde ffiC' = ci ffi c2): eC' 4{A} (a;) = niax{^eC< (x, x), ^eC< (a;, y)} eC' 4{A} (ž/) = niax{^ec< (y,a:),Mec' (y,y)} /i0C' (a;, x) = min{/ici (a;, a;), /iC2 (a;)} = min{0.1, 0.7} = 0.1 /LíeC' (a;, y) = min{^ci (a;, y), fiC2 (x)} = min{0.2, 0.7} = 0.2 Mffic' (y>x) = min{Mci (y, x), Mc2 (y)} = min{0.4, 0.9} = 0.4 Mffic' V) = minÍMc! (y, y), Mc2 (ž/)} = min{0.8, 0.9} = 0.8 ©C1' 4{A} (x) = max{0.1, 0.2} = 0.2 ©C' 4{A} (y) = max{0.4, 0.8} = 0.8 48 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 ó.příklad *.dat soubor * * pocetStroju = 3; pocetRobotu = 2; pocetVyrobku = 5; pocetZamestnancu = 5; operace = [ [<1, {1},3>,<2, {1},2>,<3, {1},2>], [<4,{2},2>,<5,{1,2},1>,<6,{2},2>], [<6,{1},4>,<5,{1},1>,<4,{1},5>], [<2, {1,2},5>,<2, {1,2},5>,<2, {1,2},5>], [<4,{2},3>,<7,{1,2},3>,<6,{2},3>], ] ; *.mod soubor * using CP; int pocetStroju = int pocetRobotu = ...; int pocetVyrobku= ...; int pocetZamestnancu = ...; range Stroje = 1..početStroju; range Roboti = 1..pocetRobotu; range Výrobky = 1..pocetVyrobku; tuple Operace { int trváni; {int} roboti; int lidi; } Operace operace[Výrobky][Stroje] = ...; dvar interval easy[v in Výrobky][s in Stroje] size operace[v][s].trváni; dvar sequence stroj[s in Stroje] in all (v in Výrobky) easy[v][s]; dvar interval přirazeni[v in Výrobky][s in Stroje][r in Roboti] optional; dvar sequence robot[r in Roboti] in all (v in Výrobky, s in Stroje: r in operace[v] [s] .robot i) přirazeni[v] [s] [r]; cumulFunction zaměstnanci = sum (v in Výrobky, s in Stroje) pulse(easy[v][s], operace[v] [s] .lidi) ; minimize max (v in Výrobky) endOf(easy[v][pocetStroju]); subject to { forall (s in Stroje) noOverlap(stroj [s]); 49 FI MU: PA163 Programování s omezujícími podmínkami: řešené příklady 15. září 2019 forall (r in Roboti) noOverlap(robot[r]); zaměstnanci <= pocetZamestnancu; forall (v in Výrobky, s in 1..početStroju-1) endBeforeStart(casy[v][s], casy[v][s+1]); forall (v in Výrobky, s in Stroje) alternativě(casy[v][s], all (r in operace[v][s].roboti) přirazeni[v][s][r]); forall (v in Výrobky, s in Stroje, r in Roboti: r not in operace[v][s].roboti) presenceOf(přirazeni[v][s][r]) == 0; 50