Úvod do programování s omezujícími podmínkami Obsah přednášky Ukázkový příklad: sudoku Základní pojmy: omezení, ... Jak řešíme problémy s omezujícími podmínkami Příklady a aplikace Složitost a úplnost Hana Rudová, Omezující podmínky, 23. září 201 9 2 Úvod do CP Sudoku: problém 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Příklad převzat z přednášky Ch.Schulte, University of Uppsala Hana Rudová, Omezující podmínky, 23. září 2019 3 Úvod do CP Sudoku: řádky 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 4 Úvod do CP Sudoku: sloupce 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 5 Úvod do CP Sudoku: bloky 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Přiřaď prázdným polím čísla tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 6 Úvod do CP Propagace v bloku: vstup 8 6 3 Žádné pole v bloku nemůže obsahovat čísla 3,6,8 Hana Rudová, Omezující podmínky, 23. září 201 9 7 Úvod do CP Propagace v bloku: promazání hodnot 1,2,4,5,7,9 8 1,2,4,5,7,9 1,2,4,5,7,9 6 3 1,2,4,5,7,9 1,2,4,5,7,9 1,2,4,5,7,9 Žádné pole v bloku nemůže obsahovat čísla 3,6,8 * propagace do dalších polí v bloku Řádky a sloupce: podobně Hana Rudová, Omezující podmínky, 23. září 2019 8 Úvod do CP Propagace: jedno pole 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 9 1,2,3,4,5,6,7,8,9 Úvod do CP Propagace: jedno pole a řádek 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 10 Úvod do CP Propagace: jedno pole a sloupec 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 Úvod do CP Propagace: jedno pole a blok 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Odstranění čísel z polí tak, že: čísla odlišná na řádku, ve sloupci a v bloku Hana Rudová, Omezující podmínky, 23. září 201 9 12 Úvod do CP Iterativní propagace 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Iterování propagací pro řádky, sloupce, bloky Pokud stále zůstává více možností: prohledávání Hana Rudová, Omezující podmínky, 23. září 2019 13 Úvod do CP Sudoku a programování s omezujícími podmínkami 2 5 9 7 3 2 9 6 2 4 9 7 6 9 1 8 4 1 6 3 8 6 8 Proměnné: pro každé pole mají hodnoty: čísla ' udržování množiny možných čísel Omezení: vyjadřují odlišnosti ^ relace mezi proměnnými Modelování: proměnné, hodnoty, omezení Řešení: propagace, prohledávání Hana Rudová, Omezující podmínky, 23. září 201 9 14 Úvod do CP Dána Omezení (constraint) 3 množina (doménových) proměnných Y = {yi,... ,yk} 3 konečná množina hodnot (doména) D = D\ u ... u Dk Omezení (podmínka) c na Y je podmnožina D\ x ... x Dk tj. relace «• omezuje hodnoty, kterých mohou proměnné nabývat současně I 3 Příklad: I 3 proměnné: A,B domény: {0,1} pro A {1,2} pro B -•omezení: A^B nebo (A,B) e {(0,1 ),(0,2),(1,2)} I Omezení c definováno na proměnných yi,.. .y^ je splněno, pokud pro hodnoty d\ e Di, ...dk^Dk platí (di,... dk) ^ c 3 příklad (pokračování): omezení splněno pro (0,1), (0,2), (1, 2), není splněno pro (1,1) Hana Rudová, Omezující podmínky, 23. září 201 9 Úvod do CP Problém splňování podmínek (CSP) Dána M konečná množina proměnných X = {x\,..., xn} M konečná množina hodnot (doména) D = D\ u ... u D 3 konečná množina omezení C = {ci,..., cm} 3 omezení je definováno na podmnožině X Problém splňování podmínek je trojice (X,D,C) (constraint satisfaction problem) I 3 Příklad: 3 proměnné: A,B, C -•domény: A e {0,1} B = l C e {0,1,2} M omezení: A =/= B B =/= C Hana Rudová, Omezující podmínky, 23. září 201 9 16 Úvod do CP Řešení CSP & Částečné ohodnocení (přiřazení) proměnných (d\,..., dk),k < n M některé proměnné mají přiřazenu hodnotu Úplné ohodnocení (přiřazení) proměnných (di,..., dn) 3 všechny proměnné mají přiřazenu hodnotu I Řešení CSP I úplné ohodnocení proměnných, které splňuje všechna omezení (di,...,dn) g Di x ... x Dn je řešení (X,D,C) ±> pro každé a e C na x^,.. .Xik platí (d^,... dik) e a I Hledáme: jedno řešení nebo všechna řešení nebo optimální řešení vzhledem k účelové funkci, tj. řešíme optimalizační problém s podmínkami (constraint optimization problem) Hana Rudová, Omezující podmínky, 23. září 2019 17 Úvod do CP Přístup CP k programování Formulace daného problému pomocí omezení: modelování Řešení vybrané reprezentace pomocí M doménově specifických metod M obecných metod Hana Rudová, Omezující podmínky, 23. září 201 9 18 Úvod do CP Obecné metody Algoritmy propagace omezení (konzistenční algoritmy) umožňují odstranit nekonzistentní hodnoty z domén proměnných M zjednodušují problém 3 udržují ekvivalenci mezi původním a zjednodušeným problémem používají se pro výpočet lokální konzistence I 3 aproximují tak globální konzistenci A e {0,1}, B = 1, C g {0,1,2}, A + B, A + Cl po propagaci: A = 0, B = 1, C g {1,2} I Prohledávací algoritmy M prohledávání stavového prostoru řešení příklady: backtracking, metoda větví a mezí Hana Rudová, Omezující podmínky, 23. září 201 9 19 Úvod do CP Prohledávání: příklad Prohledávání pomocí větvení vytvoření podproblému s dodatečnou informací umožní další propagaci omezení X: {4,5}, Y: {4,5} X >=Y I X=4 X£4 X = 4, Y = 4 X >=Y X = 5, Y: {4,5} X >=Y Hana Rudová, Omezující podmínky, 23. září 201 9 20 Úvod do CP Doménově specifické metody Specializované algoritmy 3 Nazývány řešiče omezení (constraint solvers) 3 Příklady: program pro řešení systému lineárních rovnic 3 knihovny pro lineární programování 3 implementace unifikačního algoritmu I Programování s omezujícími podmínkami 3 široký pojem zahrnující řadu oblastí 3 lineární algebra, globální optimalizace, lineární a celočíselné programování, ... 3 Existence doménově specifických metod => použití místo obecných metod hledání doménově specifických metod tak, aby mohly být použity místo obecných metod Hana Rudová, Omezující podmínky, 23. září 2019 21 Úvod do CP Algebrogram * Přiřaďte cifry 0, ... 9 písmenům S, E, N, D, M, O, R, Y tak, aby platil * SEND + MORE MONEY M různá písmena mají přiřazena různé cifry J SaM nejsou 0 3 Jediné řešení: 9567 + 1085 10652 Proměnné:IS,E,N,D,M,0,R,Y 3 Domény: 1 ..9 pro S,M 0..9 pro E,N,D,0,R,Y Hana Rudová, Omezující podmínky, 23. září 201 9 22 Algebrogram: alternativy pro omezení rovnosti 1 omezení rovnosti 1000*S + 100*E + 10*N + D SEND + 1000*M + 100*0 + 10*R + E + MORE = 10000*M + 1000*0 + 100*N + 10*E + Y MONEY 5 omezení rovnosti použití „přenosových" proměnných P1,P2,P3,P4 s doménami 0..1 D + E = 10*P1 + Y, PI + N + R = 10*P2 + E, P2 + E + 0 = 10*P3 + N, P3 + S + M = 10*P4 + 0 P4 M Hana Rudová, Omezující podmínky, 23. září 201 9 23 Úvod do CP Algebrogram: alternativy pro omezení nerovnosti i 28 omezení nerovnosti: X + Y pro X,Y e {S,E,N,D,M,0,R,Y} I 1 omezení pro nerovnost pro proměnné xi,...,xn s doménami Di,... ,Dn: al l_di fferent (x\,... ,xn) := {(di,..., dn) , ^ í^j pro i =/= j} Hana Rudová, Omezující podmínky, 23. září 201 9 24 Úvod do CP Optimalizační problém s podmínkami (COP) Problém splňování podmínek (X, D, C) Účelová funkce obj : Sol — W M Optimalizační problém s podmínkami (constraint optimization problem) M nalezení řešení d pro (X,D, C) takové, že obj(d) je optimálni ± optimální = maximální nebo minimálni Hana Rudová, Omezující podmínky, 23. září 201 9 25 Úvod do CP Problém batohu (knapsack problem) Je dán batoh velikosti man předmětů různé velikosti a ceny. Vyberte takové předměty, aby se vešly do batohu a jejich celková cena byla maximální. Batoh velikosti m Předměty velikosti Vi,..., vn a ceny ci,..., cn 3 ProměnnéJxi,... ,xn M Domény:l0..1 n 3 Omezení:!^ Ví.Xí < m i=l n Účelová funkceJmaximize ^ qxi i=l Hana Rudová, Omezující podmínky, 23. září 201 9 26 Úvod Aplikace: přehled Operační výzkum 3 optimalizační problémy rozvrhování, plánování, alokace zdrojů Zpracování přirozeného jazyka 3 konstrukce parserů Počítačová grafika geometrické vztahy při analýze scény Databáze obnovení/zajištění konzistence dat 3 Molekulární biologie 3 DNA sekvencování 3 ... Hana Rudová, Omezující podmínky, 23. září 201 9 27 Příklad aplikace z MU: univerzitní rozvrhování Timetabling - Mozilla Firefox File Edit View History Bookmarks Tools Help <£D - - ^ í https://www.5rma5.puľ"due.edu/Tlmetabling/5electPnmaľYRote.do ahl ► ) H-|Google Timetable B Filter Export PDF Refresh Timetable Legend PHYS 112 [268] M o n PHYS 114 (273) M o n Tue 7:30a OLS 252 Lee 1 15 1 3 9:00a 9:30a ENGR 126R Lee 1 4 54 OLS 274 Lee 1 11:00a 11:30a 12:00p 12:30p 1:00p 1:30p 2:00p 2:30p 3:00p 3:30p 4:00p 4:30p 5:00p MA154Lec2 OLS 274 Lee3 PHYS 219 Lee 1 OLS 274 L 10 24 1 CGT163Lee1 ENGR 126A Lee 1 EP' 4. 3.0 OLS 252 Lee 1 15 1 3 PHYS 272 Lee 1 PHYS 221 Lee 1 PHYS 241 Lee 1 PHYS 241 Lee 2 PHYS 241 Lee 3 ENGR 126R Lee 1 OLS 274 Lee 1 4 54 PHYS 272 Lee 1 PHYS 221 Lee 1 PHYS 241 Lee 1 MA 154 Lee 2 OLS 274 Lee 3 PHYS 219 Lee 1 10 24 1 ENGR 126H Lee 1 4 69 PSY 335 SOC100 Lee 10 32 4 4 HIST 152 Lee 1 14 PHYS 241 Lee 3 ;GT163LabP 1 ■ 3R 126.A _i\ ENGR 126H Lee 1 4.69. 0 =■31 ?.?.:: .i: ' SOC100Lec10 32 4 4 HIST 152 Lee 1 14 CGT163Lec2 4 4 MA 154 Lee 2 10 9:30a 10:00a 10:30a 11:00a 11:30a 12:00p ANTH 205 Lee 1 16 61 PHYS 172H Lee 1 40 8 4 MA165 Lee 5 15 12:30p PHYS 2 1:00p 1:30p !:CCp 2:30p 3:00p 3:30p 4:00p 4:30p 5:00p 8 Lee 1 PHYS 218 Lee 2 MGMT201 Lec1 0.6.0 CGT163LabP2 4 5 4 PSY 200 Lee 1 24 38 MGMT201 Lec2 16 ANTH 205 Lee 1 16 61 ENGR 100H Lee 1a MA 165 Lee 5 4 6 15 Weekl ENGR 100H Lee 1b 4 6 Week 4 ENGR 100H Lee 1 www.smas.purdue.edu £g Proxy: None ^ O I rozvrhovací systém Unitime http://www.unitime.org International Timetabling Competition 2019 co-organized by Fl MU: https://www.itc2019.org Hana Rudová, Omezující podmínky, 23. září 2019 28 Úvod do CP Univerzitní rozvrhování: proměnné a omezení Doménové proměnné čas výuky předmětu I: Timel, hodnoty: možné časy místnost výuky předmětu I: Rooml, hodnoty: identifikátory místností I Omezující podmínky M zakázaný čas: Timel ^ Prohibited I minimální velikost místnosti: Rooml > ConstSize identifikátory místností uspořádány podle velikosti M ConstSize: nejmenší identifikátor místnosti s velikostí Size I v jedné místnosti v každém čase nejvýše jeden předmět jeden vyučující učí nejvýše jeden předmět v každém čase Hana Rudová, Omezující podmínky, 23. září 2019 29 Úvod do CP Univerzitní rozvrhování: optimalizace Optimalizační kritéria výuka v preferovaných časech cena za výuku předmětu I ve vybraném čase: CostTimel CostTime = CostTimel + CostTime2 + ■ ■ ■ I 3 výuka v preferovaných místnostech I cena za výuku předmětu I ve vybraném čase: CostRooml M CostRoom = CostRooml + CostRoom2 + ■ ■ ■ I dva předměty jednoho studenta by se neměly překrývat dva předměty IJ zároveň navštěvuje SIJ studentů 3 CostOverlap = ^ SIJ I IJ: timeOverlap(IJ) minimize (WTime * CostTime + WRoom * CostRoom + WOverlap * CostOverlap) Hana Rudová, Omezující podmínky, 23. září 201 9 30 Úvod do CP