Opakování
Vzorové písemné práce
2 vzorové písemné práce na webu předmětu
Struktura písemné práce: 7 otázek
1. 1 přehledová otázka
2. otázky na propagaci a konzistenční algoritmy
3. otázky na stromové prohledávání prohledávání
4. otázky na lokální prohledávání a optimalizace
5. 1 otázka na řešení problému v OPL
Hlavní typy otázek pro 2,3,4
* příklady k vypočítání (jako vzorové příklady - někdy kratší verze)
3 pojem (a příklad)
kód algoritmu (a příklad)
* porovnání pojmů/algoritmů (a příklady)
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
2
Opakování
Příklady s řešeními na webu I.
Příklady 1. M binarizace M AC-1 vs. AC-3
M konzistence mezí vs. hranová konzistence Příklady 2.
M strom stavového prostoru: backtracking vs. kontrola dopředu vs. pohled dopředu Příklady 3.
M omezení s váhami Příklady 4.
M přehled konzistenčních algoritmů M algoritmus AC-4 M algoritmus DAC
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
3
Opakování
Příklady s řešeními na webu II
Příklady 5.
& strom stavového prostoru: backtracking vs. kontrola dopředu & pohled zpět: Gaschnigův skok zpět Příklady 6.
& přehled prohledávacích algoritmů
& problém rozvrhování výuky v OPL
Příklady 7.
M binarizace
& podpora hodnoty
M konzistence mezívs. hranová konzistence & algoritmus DAC, nalezení řešení bez navracení
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
4
Opakování
Příklady s řešeními na webu III
Příklady 8.
& strom stavového prostoru: backtracking vs. kontrola dopředu vs. pohled dopředu & problém plánování projektu v OPL Příklady 9.
& stromový CSP, nalezení řešení bez navracení & algoritmus PC-2
& problém rozvrhování výuky jedné místnosti v OPL
& strom stavového prostoru: kontrola dopředu vs. pohled dopředu bez iniciální konzistence M rozvrhování úkolů pro zaměstnance na směny
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
5
Opakování
Příklady s řešeními na webu IV
Příklady 10
& nalezení podpory
& algoritmus DAC a nalezení řešení bez navracení & problém přiřazení poboček k obchodům v OPL 3 BBS-DBS, DDS M rozvrhování na směny
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
6
Opakování
Pojem: směrová konzistence a šířka grafu
Co to je šířka grafu a jaký je její význam? Použité pojmy objasněte.
Šířka grafu je minimum z šířek všech jeho uspořádaných grafů.
Šířka uspořádaného grafu je maximum z šířek jeho vrcholů.
Šířka vrcholu v uspořádaném grafu je počet hran vedoucích z tohoto vrcholu do předchozích vrcholů.
Uspořádaný graf je graf s lineárním uspořádáním vrcholů.
Šířka grafu nám říká, jak silnou úroveň směrové i-konzistence potřebujeme, abychom nalezli řešení problému bez navracení.
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
7
Opakování
Algoritmus: lokální prohledávání
Napište (nebo alespoň slovně popište) algoritmus prohledávání s tabu seznamem. Je Váš algoritmus kombinován s nějakou další metodou lokálního prohledávání?
proceduře TSHC(MaxZmen)
6 : = náhodné ohodnoceni proměnných      % iniciál ní přiřazení PocetZmen := 0
while E(0) > 0 a PocetZmen<MaxZmen do
vyber (V,a) s nejlepší evaluací tak, že
není v tabu seznamu a nebo splňuje aspirační kriterium
přidej (V,c> do tabu seznamu, kde c je současná hodnota V
smaž nejstarší položku v tabu seznamu
při řad' a do V
PocetZmen := PocetZmen+1 return 0
Algoritmus je kombinován s metodou stoupání/hill climbing.
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 8
Opakování
Příklady stručněji: omezení s váhami
Jaká je úroveň konzistence pro následující CSP problém s váhami s omezeními cl a c2?
P=({cl,c2},{X,Y}) dom(X)=dom(Y)={r,s} con(cl)={X,Y}
def(r,r)=l, def(r,s)=2, def(s,r)=4, def(s,s)=6
con(c2)={Y}
def(r)=0, def(s)=l
Výsledek: blevel(P)=l. Nutno uvést stručný postup, např. I
Spočítáme (ci ® C2) ^0 0 = = min(jL/Cl ®c2 (r, r), juCi®C2(r, s), jl/Ci®C2 (s,r), jl/ci ®c2(s, s)) =1 = min(l + 0,2 + 1,4 + 0,6 + 1) = 1
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
9
Opakování
Příklady stručněji: omezení s váhami II
A jaká je úroveň splnění pro problém Pl =({cl ,c2},{Y})?
M výsledek: úroveň splnění pro Y=r: 1, pro Y=s: 3, postup:! Spočítáme
(ci <g> c2) ^Y (r) = min(jUCl0C2(n r),jUCl0c2(s,r)) = min(l + 0,4 + 0) = 1
(ci <g> c2) ^Y (s) = min(jUCl0c2(r,s),jUc10c2(s,s)) = min(2 + 1,6 + 1) = 31 I
P=({cl,c2},{X,Y}) dom(X)=dom(Y)={r,s} con(cl)={X,Y}
def(r,r)=l, def(r,s)=2, def(s,r)=4, def(s,s)=6
con(c2)={Y}
def(r)=0, def(s)=l
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
10
Opakování
Doménové proměnné
Celočíselné proměnné dvar int+
Sudoku: hodnota pole dvar int+ sudoku[l ..Size][l ..Size] in 1 ..Size;l
forall (i in 1 ..Size) allDifferent(all (j in 1 ..Size) sudoku[i][j]);     //ruzne pro kazdy radek I
přiřazení pracovníků:pracovník vyrábí produktl
dvar int+ W[l ..nbWorkers] in 1 ..nbProducts;!
total == sum (w in 1 ..nbWorkers) effectivity[w][W[w]];l
Binární proměnné dvar boolean
problém baťohu: je předmět v baťohu?ldvar boolean take[l ..nbltems];!
sum (i in Items) (take[i] * weights [i]) <= capacity;!
Sudoku: hodnota pole dvar boolean sudoku[l ..Size][l ..Size][l ..Size];l forall (i,k in 1 ..Size) sum (j in 1 ..Size) sudoku[i][j][k] == 1 I navíc: forall (i, j in 1 ..Size) sum(k in 1 ..Size) sudoku[i][j][k] == 1;
Hana Rudová, Omezující podmínky, 16. prosince 2019 11 Opakování
Rozvrhování: zdroje
Jeden zdroj
3 jednotková doba trvání úlohy: dvar int, allDifferent(casy)
odlišné doby trvání úloh: dvar interval, dvar sequence, noOverlap(casy)l
3 Více zdrojů
nepožadujeme určení zdroje pro úlohu I
-i* bez doménových proměnných pro určení zdroje úlohy
cumulFunction, pulse(casy[uloha], zdroju[uloha])l požadujeme určení zdroje pro úlohu
včetně doménových proměnných pro určení zdroje úlohy
dvar interval přirazeni ... optional
alternative(casy[uloha], ... prirazeni[uloha][zdroje], zdroju[uloha])
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
12
Opakování
Rozvrhování
Vztahy mezi úlohami a precedence endBeforeStart, endAtStart, ...
tuple Závislost { int Před; int Po; } {Závislost} závislosti = ...;
forall (zav in závislosti) endBeforeStart(casy[zav.Před], casy[zav.Po]);l
3 Volitelné úlohy presenceOf(dvar interval)
dvar interval při razeni[1..Uloh][1..Strojů] optional;l
forall (u in L.Uloh, s not in mozne[u] ) presenceOf( pri razeni [u] [s] ) == 0; forall (u in L.Uloh, s in pri kazane [u]) presenceOf( pri razeni [u] [s] ) == l;l
Dovolená: práce lidí se nepřekrývá s jejich dovolenoul řešení: přidáme dodatečné intervalové proměnné
dvar interval casy[u in 1..Prace+Dovolenel size trváni[u]; forall (u in 1..Prace+Dovolene)   noOverlap(casy);l
cumulFunction nástroje = sum (p in 1..Prače)   pulse( casy[p],nástrojů[p] );
Hana Rudová, Omezující podmínky, 16. prosince 2019 13 Opakování
Optimalizace
Problém baťohu: maximalizace součtu cen předmětů v baťohul
maximize sum (i in nbltems) (take[i] * pricesfi] );l
Minimalizace času dokončení poslední úlohyl
minimize sum (u in 1 ..Počet) endOf( casy[u]);
zadány poslední operace úlohy:!
minimize sum (u in 1 ..Počet) endOf( casy[u][Posledni] );l
Maximalice (váženého) počtu realizovaných úlohl
maximize sum (u in 1 ..Počet) (vahy[u] * presenceOf(casy[u]));
Hana Rudová, Omezující podmínky, 16. prosince 2019 14 Opakování
Určete čas a místnost pro výuku množiny předmětů. Datová instance:
1. rozvrh tvoříte pro 3 vyučovací dny a každý den má 10 hodin
2. máte zadáno 14 předmětů
3. délka výuky předmětu je 4 nebo 5 hodin (určeno pro každý předmět předem)
4. máte k dispozici 3 místnosti
5. máte zadány 3 třídy (skupiny žáků)
6. každá třída má v zadání určeno 4 až 5 předmětů, které bude navštěvovat Omezující podmínky:
7. 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)
8. v každé místnosti je nejvýše jeden předmět v danou dobu
9. 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
Účelová funkce:
10. 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). Tj. minimalizujte součet koncových časů výuky posledních předmětů všech tříd.
Hana Rudová, Omezující podmínky, 16. prosince 2019 15 Opakování
Školní rozvrh: vstupní proměnné
i nt Dny = 3; int Hodin = 10; int Predmetu = 14; int Mistnosti = 3; int Tridy = 3;l
range rTridy = 1..Tridy;
range rMistnosti = 1..Mistnosti;l
I
tupl e predmetyTrid{ key int predmet; int trida; i nt trvani;}
// napr. trida 1 ma predmety 1,2,3; trida 2 ma predmety 4,5, ...
// predmety 1,2,3,4,5 maji trvani 4,4,5,5,4
// predmet je klic, tj. napr. <2> odkazuje na cely tuple <2,1,4>
{predmetyTrid} PredmetyTrid = {<1,1,4>,<2,1,4>,<3,1,5>,<4,2,5>,<5,2,4>,...};
Hana Rudová, Omezující podmínky, 16. prosince 2019 16 Opakování
Školní rozvrh: model
Doménové proměnnél
// přiřazeni času předmětům v maximálním rozmezi Dny*Hodin, zajištěni trváni dvar interval casy[p in PredmetyTrid] in 0 .. Dny*Hodin size p.trváni;l
// volitelný interval pro přiřazeni předmětů a třid do mistnosti dvar interval při razeni[PredmetyTrid][rMistnosti] optional;l
Každý předmět je vyučován právě v jedné místnosti I
forall(p in PredmetyTrid)
alternative(casy[p.předmět], all(m in rMistnosti) prirazeni[p] [m]);l
V každé místnosti je nejvýše jeden předmět v danou dobul
// sekvence rozvrhu mistnosti z důvodu nepřekrýváni dvar sequence rozvrhMistnosti[m in rMistnosti] in all (p in PredmetyTrid) prirazeni[p][m];
forall(m in rMistnosti) noOverlap(rozvrhMistnosti[m]);
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
17
Opakování
Školní rozvrh: model II
Každý předmět je vyučován pro konkrétní třídu (skupinu žáků), tj. pro každou třídu je zadána množina jejích předmětůl
// sekvence rozvrhu tříd z důvodu nepřekrýváni dvar sequence rozvrhTridy[t in rTridy] in
all (m in rMistnosti, p in PredmetyTrid : p.trida == t) pri razeni [p] [m];
I
a tedy každá třída může mít vždy nejvýše jeden předmět v danou dobul
f orali (t in rTridy)
noOverlap(rozvrhTridy[t]);l
Výuka předmětu musí probíhat bez přerušeníl
forali (p in PredmetyTrid)
startOf(časy[p]) % Hodin <= (Hodin-p.trváni);
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
18
Opakování
Školní rozvrh: optimalizace
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). Tj. minimalizujeme součet koncových časů výuky posledních předmětů všech tříd.l
I
// čas konce posledního předmětu každé třídy dexpr int maxTridy[t in rTridy] =
max(p in PredmetyTrid : p.trida == t) endOf(casy[p]);
// součet koncových časů poslednich hodin všech třid minimize sum(t in rTridy) maxTridy[t] ;
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
19
Opakování
Rozvrhování vyšetření pacientů v nemocnici
Každý pacient musí absolvovat vyšetření zadaného typu, která probíhají na různých pracovištích. Cílem řešení je pro každé vyšetření pacienta určit, ve kterém čase bude probíhat a které pracoviště bude vyšetření realizovat. Dále:
Vyšetření jednoho pacienta se nesmí překrývat.
Vyšetření na jednom pracovišti se nesmí překrývat.
Každý typ vyšetření má stanovenu délku provádění a pracoviště, na kterých ' může být prováděno.
Některý typ vyšetření musí proběhnout před realizací jiného typu vyšetření (pokud je pacient absolvuje oba). Jsou proto zadány dvojice typů vyšetření určující, které vyšetření musí být realizováno před zahájením dalšího vyšetření.
Vyšetření pacientů se závažnějším typem onemocnění by měla být dokončena dříve, aby mohli dříve nastoupit na operaci. Cílem je tedy minimalizovat vážený součet dokončení nejpozdějších vyšetření pacientů.
Hana Rudová, Omezující podmínky, 16. prosince 2019 20 Opakování
Jednoduché zadání
Příklad jednoduchého zadání s řešením:
počet pacientů 2, počet typů vyšetření 2, počet pracovišť 2 3 doby trvání vyšetření daného typu: 1, 2;
pracoviště pro vyšetření daného typu: 1:1,2, 2:1;
typy vyšetření pro pacienty: 1:1,2,2:1;
priority pacientů: 1,10;
precedence pro dané typy vyšetření: 1 před 2;
3 dvě optimální řešení s kvalitou 1 3:
M pacient, vyšetření, čas, pracoviště M 1,1,0,1; 1,2,1,2; 2,1,0,2 * 1,1,0,2; 1,2,1,2; 2,1,0,1.
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9 21
Vstupní
Konstanty a intervaly
i nt NbPaci ents = ...; i nt NbMedi cals = ...; i nt NbRooms = ...;
range RPacients = 1..NbPacients; range RMedicals = 1..NbMedicals; range RRooms = 1..NbRooms;
Vyšetření: typ, místnostil
tuple Tmedical{ int duration; {int} rooms; }
Tmedical Medicals[RMedicals] = ...;
Pacient: typy vyšetřeníl tuple pMedical{ int pacient; int medical; }
{pMedical} PMedicals = ...;
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
data a typy
i
// [<2,{1,3}>, <2,{2,4}>, <3,{1,2,3}>]
// {<1,1>,<1,2>,<2,2>,<2,3>,<3,1>, ...}
22 Opakování
Vyšetření pacienta
tuple Tmedical{ int duration; {int} rooms; }
Tmedical Medicals[RMedicals] = ...;
tuple pMedical{ int pacient; int medical; }
{pMedical} PMedicals = ...; Časy vyšetření paciental
dvar interval times[pm in PMedicals] size Medicals[pm.medical].duration;
Nepřekrytí vyšetření paciental
dvar sequence seqPacient[p in RPacients] in
all(pm in PMedicals: pm.pacient == p) times[pm];l
forall (p in RPacients) noOverlap(seqPacient[p]);
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
23
Opakování
Vyšetření na jednom pracovišti
dvar interval times[pm in PMedicals] size Medi cals[pm.medi cal].du rati on;
Proměnné pro výběr místnosti pro vyšetření paciental
dvar interval assigned[PMedicals][RRooms] optional;
Na každém pracovišti maximálně jedno vyšetřeníl I
forall (pm in PMedicals)
alternative (times[pm],
all (r in RRooms: r in Medicals [pm.medical].rooms) assigned[pm] [r]) ;l
forall (r in RRooms)
noOverlap(al1 (pm in PMedicals: r in Medicals [pm.medical].rooms) assi gned [pm][r]);
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
24
Opakování
Precedence
tuple pMedical{ int pacient; int medical; }
{pMedical} PMedicals = ...;
dvar interval times[pm in PMedicals] size Medicals[pm.medical].duration;
Typy a vstupní datal
tuple Tprec{
int before; I int after; }l
{Tprec} Prec = ...;
Omezení na precedencel
forall (pr in Prec, pmB in PMedicals, pmA in PMedicals:
pmB.pacient == pmA.pacient && pmB.medical == pr.before && pmA.medical == pr.after) endBeforeStart(times[pmB],times[pmA]);
Hana Rudová, Omezující podmínky, 16. prosince 2019 25 Opakování
Minimalizace vážených časů posledních vyšetření
Typy a vstupní datal
int Priorities[RPacients] =
Minimalizacel
dexpr int pacientMax[p in RPacients]
= max (pm in PMedicals: pm.pacient == p) endOf(times[pm]);l
minimize sum (p in RPacients) Priorities[p]*pacientMax[p] ;
Hana Rudová, Omezující podmínky, 1 6. prosince 201 9
26
Opakování