Optimalizace & soft omezení: modely (dokončení) Omezení nad polookruhy 3 Semiring-based CSP c-polookruh (JA, + , x,0,1) J4. množina polookruhu (množina preferencí) M 0 g J4. (úplné nesplnění), 1 e J4. (úplné splnění) + komutativní, idempotentní, asociativní operace s jednotkovým prvkem 0, s absorbujím prvkem 1 x komutativní, asociativní operace, distributivní nad +, s jednotkovým prvkem 1, s absorbujím prvkem 0 J x se používá ke kombinaci preferencí několika omezení min u fuzzy CSP 0 minimum (nesplnění), 1 maximum (splnění) ^ Částečné uspořádání ((axb) < (c xb)) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat (platí pro CSP s váhami) př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotonie Hana Rudová, Omezující podmínky, 9. prosince 2019 3 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup + x 0 1 uspořádání kombinace CSP {0,1} v a 0 1 Fuzzy CSP (0,1) max min 0 1 CSP s váhami N u { + 00} min + + 00 0 Důležité vlastnosti: 3 striktní monotonie: Va, b,c e JA: ((a < c) a (b J= 0)) => ((a x b) < (c xb)) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat (platí pro CSP s váhami) př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotonie M idempotence: Va e JA: ax a = a (platí pro fuzzy CSP) omezení, které je v problému obsaženo, může být do něj přidáno beze změny významu př. x > l@10,x > l@10,x = 0@oo, přiřazení x = 0 má pro CSP s váhami úroveň konz. 20 Rudová, Omezující podmínky, 9. prosince 2019 3 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup + x 0 1 uspořádání kombinace CSP {0,1} v a 0 1 Fuzzy CSP (0,1) max min 0 1 CSP s váhami N u { + 00} min + + 00 0 Důležité vlastnosti: 3 striktní monotonie: Va, b,c e JA: ((a < c) a (b J= 0)) => ((a x b) < (c xb)) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat (platí pro CSP s váhami) př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotonie M idempotence: Va e JA: ax a = a (platí pro fuzzy CSP) omezení, které je v problému obsaženo, může být do něj přidáno beze změny významu př. x > l@10,x > l@10,x = 0@oo, přiřazení x = 0 má pro CSP s váhami úroveň konz. 20 M striktní monotonie a idempotence x zároveň pouze pro dvouprvkové JA, tj. jen pro CSP Rudová, Omezující podmínky, 9. prosince 2019 3 Optimalizace & soft omezení: modely Instance omezení nad polookruhy Přístup A + x 0 1 uspořádání kombinace CSP {0,1} v a 0 1 Fuzzy CSP (0,1) max min 0 1 CSP s váhami N u { + 00} min + + 00 0 Důležité vlastnosti: 3 striktní monotonie: Va, b,c e JA: ((a < c) a (b J= 0)) => ((a x b) < (c xb)) fakt, že něco lze lokálně zlepšit nelze globálně ignorovat (platí pro CSP s váhami) př. a = 0.3, c = 0.4, b = 0.2 pro fuzzy CSP: není striktní monotonie M idempotence: Va e JA: ax a = a (platí pro fuzzy CSP) omezení, které je v problému obsaženo, může být do něj přidáno beze změny významu př. x > l@10,x > l@10,x = 0@oo, přiřazení x = 0 má pro CSP s váhami úroveň konz. 20 M striktní monotonie a idempotence x zároveň pouze pro dvouprvkové JA, tj. jen pro CSP 3 Existující vztahy: CSP = fuzzy CSP na dvouprvkové JA fuzzy CSP lze polynomiálně transformovat na CSP s váhami Hana Rudová, Omezující podmínky, 9. prosince 2019 3 Optimalizace & soft omezení: modely Definice omezení nad polookruhy Systém (S,D, V): S c-polookruh, D konečná doména, V uspořádaná množina proměnných Soft omezení (def, con): rozsah omezení con c y, def : D|Cřm| — J4. Soft problém je (C, con) nad (S,D, V), kde con ^ V, C množina omezení Hana Rudová, Omezující podmínky, 9. prosince 2019 4 Optimalizace & soft omezení: modely Definice omezení nad polookruhy Systém (S,D, V): S c-polookruh, D konečná doména, V uspořádaná množina proměnných Soft omezení (def, con): rozsah omezení con c y, def : D|Cřm| — J4. Soft problém je (C, con) nad (.S,D, V), kde con ^ V, C množina omezení Projekce n-tic t ly * příklad: (1,2,3,4,5) i|SÄe)d'e)= (4.1.5) Hana Rudová, Omezující podmínky, 9. prosince 2019 4 Optimalizace & soft omezení: modely Definice omezení nad polookruhy Systém (S,D, V): S c-polookruh, D konečná doména, V uspořádaná množina proměnných Soft omezení (def, con): rozsah omezení con c y, def : D|Cřm| — J4. Soft problém je (C, con) nad (S,D, V), kde con ^ V, C množina omezení Projekce n-tic t ly * příklad: (1,2,3,4,5) i|SÄe)d'e)= (4.1.5) Kombinace c = Ci ® c 2 Ci = (defí, co^i) and c 2 = (def2, COYI2) c = (def, con), con = coni u con2, def (t) = defľ(t iccZ) x c2) ^{x,y}'- aa 2, ab 4, ba 2, bb 1 problém P2 = ({ci,c2}, {x}): Sol(P2) = (ci ® c2) ^{x}- a 2, b 1 Úroveň konzistence: blevel(P) = Sol(P) tt0 3 příklad (pokračování): blevel{P\) = blevel(P2) = 1 Sol(P) = ((g) C) U con Hana Rudová, Omezující podmínky, 9. prosince 2019 Optimalizace & soft omezení: modely Optimalizace & soft omezení: algoritmy Soft propagace 3 Klasická propagace: eliminace nekonzistentních hodnot z domén proměnných M Soft propagace: propagace preferencí (cen) nad fc-ticemi hodnot proměnných 3 snaha o získání realističtějších preferencí výpočet realističtějších příspěvků pro cenovou funkci Hana Rudová, Omezující podmínky, 9. prosince 2019 7 Optimalizace & soft omezení: algoritmy Soft propagace 3 Klasická propagace: eliminace nekonzistentních hodnot z domén proměnných M Soft propagace: propagace preferencí (cen) nad fc-ticemi hodnot proměnných 3 snaha o získání realističtějších preferencí výpočet realističtějších příspěvků pro cenovou funkci ^ C je soft ^-konzistentní, jestliže pro všechny podmnožiny (k - 1) proměnných W a libovolnou další proměnnou y platí ®{cí I Ci e C a coyií ^ W} — (® {ci | Ci G Ca coyií ^ (W u {j7})}) coyií označuje proměnné v omezení a 3 uvažování (def) pouze omezení ve W stejné jako: uvažování (def) omezení ve W a omezení spojující y s W, s následnou projekcí na W Hana Rudová, Omezující podmínky, 9. prosince 2019 7 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) k = 2,W = {x} : cx = (®{Cy,cxy,cx}) D-{x} Hana Rudová, Omezující podmínky, 9. prosince 2019 8 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) 3 k = 2,W = {x} : cx = {®{cy,cxy,cx}) tt{x} 3 CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def((a)) = 0 Hana Rudová, Omezující podmínky, 9. prosince 2019 8 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) M k = 2,W = {x} : cx = (®{cy,cXy,cx}) tt{x} 3 CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def((a)) = 0 Fuzzy CSP: úroveň preference všech hodnot x v cx je stejná jako úroveň preference daná (®{cy,cxy,cx}) tt{x} Hana Rudová, Omezující podmínky, 9. prosince 2019 8 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) M k = 2,W = {x} : cx = (®{Cy,cxy,cx}) tt{x} 3 CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def((a)) = 0 Fuzzy CSP: úroveň preference všech hodnot x v cx je stejná jako úroveň preference daná (®{cy,cxy,cx}) tt{x} M Příklad na fuzzy CSP: J4. = (0,1), + = max, x = min, 0, 1 x,y e {a,b} 9 Cx ■ CL . . . 0.9, fc... 0.1, C-y • & • • • 0.9, fc... 0.5, 0.8, ab ... 0.2, ba...0, bb ... 0 3 není SAC: cx dává 0.9 na x = a, ale (®{cy, cxy, cx}) ^{X} dává 0.8 na x = a ®{cy,cXy,cx} dává na (a, a) : ®{cy,cxy,cx} dává na (a,b) : projekce cxy,cx}) ^{X} dává na (a) : Hana Rudová, Omezující podmínky, 9. prosince 2019 8 Optimalizace & soft omezení: algoritmy Soft hranová konzistence (SAC) M k = 2,W = {x} : cx = (®{Cy,cxy,cx}) tt{x} 3 CSP: libovolná hodnota v doméně x může být rozšířena o hodnotu v doméně y tak, že je cxy splněno hodnoty a v doméně x, které nelze rozšířit na y, mají def((a)) = 0 Fuzzy CSP: úroveň preference všech hodnot x v cx je stejná jako úroveň preference daná (®{cy,cxy,cx}) tt{x} M Příklad na fuzzy CSP: J4. = (0,1), + = max, x = min, 0, 1 x,y e {a,b} 9 Cx ■ CL . . . 0.9, b...0.1, 0.9, b...0.5, 0.8, ab ... 0.2, ba...0, bb ... 0 3 není SAC: cx dává 0.9 na x = a, ale (®{cy, cxy, cx}) ^{X} dává 0.8 na x = a ®{cy,cXy,cx} dává na (a, a) : min(0.9,0.8,0.9) = 0.8 ®{cy,cxy,cx} dává na (a,b) : min(0.5,0.2,0.9) = 0.2 projekce (<8>{cy,cxy,cx}) ^{X} dává na (a) : max(0.8,0.2) = 0.8 Hana Rudová, Omezující podmínky, 9. prosince 2019 8 Optimalizace & soft omezení: algoritmy Výpočet SAC Základní algoritmus pro výpočet SAC: 3 pro každé x a y změnit definici cx tak, aby korespondovala s (®{Cy,CXy,CX}) tt{x} M iterace až do dosažení stability Hana Rudová, Omezující podmínky, 9. prosince 2019 9 Optimalizace & soft omezení: algoritmy Výpočet SAC Základní algoritmus pro výpočet SAC: pro každé x a y změnit definici cx tak, aby korespondovala s (®{Cy,CXy,CX}) tt{X} 3 iterace až do dosažení stability x idempotentní (fuzzy CSP) M zajištěna ekvivalence, tj. původní i nový (po dosažení SAC) problém mají stejné řešení 3 zajištěno ukončení algoritmu Hana Rudová, Omezující podmínky, 9. prosince 2019 9 Optimalizace & soft omezení: algoritmy Výpočet SAC 3 Základní algoritmus pro výpočet SAC: 3 pro každé x a y změnit definici cx tak, aby korespondovala s (®{Cy,CXy,CX}) tt{x} 3 iterace až do dosažení stability x idempotentní (fuzzy CSP) 3 zajištěna ekvivalence, tj. původní i nový (po dosažení SAC) problém mají stejné řešení 3 zajištěno ukončení algoritmu 3 x není idempotentní (CSP s váhami) 3 pro každé u, v e SA existuje w e JA taková, že v x w = u 3 w se nazývá rozdíl mezi u a v, maximální rozdíl se značí u - v ±> nutno požadovat novou vlastnost pro systém (a rozšířit projekci a kombinaci) s novou vlastností zajištěna ekvivalence, při striktní monotonii zajištěno i ukončení tato vlastnost platí pro CSP s váhami Hana Rudová, Omezující podmínky, 9. prosince 2019 9 Optimalizace & soft omezení: algoritmy Řešení COP Cíl: nalezení úplného řešení s optimální hodnotou cenové funkce 3 Prohledávání lokální prohledávání i* přímé zahrnutí optimalizačního kriteria do evaluace (hodnota obj. funkce) stromové prohledávání i* metoda větví a mezí + její rozšíření Hana Rudová, Omezující podmínky, 9. prosince 2019 10 Optimalizace & soft omezení: algoritmy Řešení COP Cíl: nalezení úplného řešení s optimální hodnotou cenové funkce 3 Prohledávání lokální prohledávání i* přímé zahrnutí optimalizačního kriteria do evaluace (hodnota obj. funkce) stromové prohledávání i* metoda větví a mezí + její rozšíření CSP s omezeními: minimalizace součtu vah omezení minXCecc(^) «• velmi častá optimalizační úloha váha (cena) omezení: 0 = úplné splnění, (0, oo) částečné nesplnění, oo úplné nesplnění M hodnota cenové funkce: cena přiřazení/řešení M maximalizace je duální problém 3 algoritmy pro fuzzy CSP na podobných principech Hana Rudová, Omezující podmínky, 9. prosince 2019 10 Optimalizace & soft omezení: algoritmy COP jako série CSP problémů 3 Triviální metoda řešení Řešení COP jako CSP a nalezení iniciální hodnoty cenové funkce W1 M Opakované řešení CSP (í = 1...) s přidáním omezení XCecc(^) < Wl M Když řešení nového CSP neexistuje, pak poslední Wl dává optimum Hana Rudová, Omezující podmínky, 9. prosince 2019 Optimalizace & soft omezení: algoritmy COP jako série CSP problémů 3 Triviální metoda řešení Řešení COP jako CSP a nalezení iniciální hodnoty cenové funkce W1 M Opakované řešení CSP (í = 1...) s přidáním omezení XCecc(^) < Wl M Když řešení nového CSP neexistuje, pak poslední Wl dává optimum Výpočetně zbytečně náročné Efektivní rozšíření obtížné Hana Rudová, Omezující podmínky, 9. prosince 2019 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB 3 Prohledávání stromu do hloubky M přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F M omezení pouze na minulých proměnných O, omezení na minulých i budoucích proměnných Cpp, omezení pouze na budoucích proměnných C> Hana Rudová, Omezující podmínky, 9. prosince 2019 12 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB 3 Prohledávání stromu do hloubky M přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F M omezení pouze na minulých proměnných O, omezení na minulých i budoucích proměnných Cpp, omezení pouze na budoucích proměnných C> Výpočet mezí horní mez UB: cena nejlepšího dosud nalezeného řešení 3 dolní mez LB: dolní odhad minimální ceny pro současné částečné přiřazení Hana Rudová, Omezující podmínky, 9. prosince 2019 12 Optimalizace & soft omezení: algoritmy Metoda větví a mezí (branch&bound) BB 3 Prohledávání stromu do hloubky M přiřazené=minulé proměnné P, nepřiřazené=budoucí proměnné F M omezení pouze na minulých proměnných O, omezení na minulých i budoucích proměnných Cpp, omezení pouze na budoucích proměnných C> Výpočet mezí horní mez UB: cena nejlepšího dosud nalezeného řešení 3 dolní mez LB: dolní odhad minimální ceny pro současné částečné přiřazení Ořezávání: LB > UB (cíl: minimalizace) M víme, že rozšíření současného částečného řešení už bude mít horší (vyšší) cenu LB než dosud nalezené řešení UB M lze proto ořezat tuto část prohledávacího prostoru M příklad: pokud nalezneme řešení s cenou 10 odřízneme všechny větve, které mají cenu vyssi nez 9 Hana Rudová, Omezující podmínky, 9. prosince 2019 12 Optimalizace & soft omezení: algoritmy Metoda větví a mezí: výběr hodnoty M Algorimus metody větví a mezí generický algoritmus rozšiřitelný jako implementace backtrackingu S možná rozšíření zejména o: pohled dopředu, výpočet dolní meze LB(d) vrací dolní odhad ceny pro každé částečné přiřazení d 3 použití při rozšíření o jednu proměnnou LB(di-i,a) Hana Rudová, Omezující podmínky, 9. prosince 2019 13 Optimalizace & soft omezení: algoritmy Metoda větví a mezí: výběr hodnoty M Algorimus metody větví a mezí generický algoritmus rozšiřitelný jako implementace backtrackingu S možná rozšíření zejména o: pohled dopředu, výpočet dolní meze LB(d) vrací dolní odhad ceny pro každé částečné přiřazení d 3 použití při rozšíření o jednu proměnnou LB(di-i,a) M Optimistický výběr hodnoty proceduře Select-Value-BB while D[ i s not empty vyber a smaž libovolný a e D[ takový, že min LB{at-\,a) if Consistent(aí_i,Xí = a) a LB(ät-i,a) < UB return a (jinak ořezej a) return null (konzistentní' hodnota neexistuje) Hana Rudová, Omezující podmínky, 9. prosince 2019 13 Optimalizace & soft omezení: algoritmy Algoritmus metody větví a mezí proceduře Branch-Bound((X,D, C), UB,f^) rozdíly od backtrackingu i : = 1, D[ := Di (inicializace čitače proměnných, kopirováni domény) Reseni := null (řešeni dosud nenalezeno) repeat while 1 < i < n přiřazeni xt : = Select-Value-BB if Xi is null (žádná hodnota nebyla vrácena) i := i-1 (zpětná fáze) else i := í + 1 (dopředná fáze) D't := Dt if i = 0 if Reseni is not null return UB, Reseni else return , ,nekonzistentni ' ' else Reseni := x\,...,xn (uloženi hodnot dosud nejlepšiho přiřazeni) spočítej cenu současného přiřazení W = SCecc(^)' UB:=mm{W, UB} i := 1, nastav D'k na Dk pro k = 1... n until true end Branch-Bound Hana Rudová, Omezující podmínky, 9. prosince 2019 14 Optimalizace & soft omezení: algoritmy Dolní mez Kvalita dolní meze: velmi důležitá pro efektivitu BB Dolní mez lze ovlivnit pomocí 3 ceny minulých proměnných x vzdálenost (součet vah omezení na minulých proměnných) 3 lokální ceny budoucích proměnných vzhledem k minulým proměnným 3 NC* M lokální ceny budoucích proměnných ^ AC* 3 globální ceny budoucích proměnných prohledávání ruská panenka Hana Rudová, Omezující podmínky, 9. prosince 2019 Optimalizace & soft omezení: algoritmy NC* algoritmus Projekce ceny hodnot (j, *) pro každou proměnnou j do dolní hranice LB ceny řešení J J OJ) 0,2) 0,3) 0 © \® lb=6 >—y lb=8 Hodnotu a proměnné j značíme (j,a) obrázek: proměnná j má nejprve tři hodnoty (j, 1), (j, 2), (j, 3), jejichž cena je 2,4 a 5 Všechny hodnoty proměnné j značíme (j, *) Hana Rudová, Omezující podmínky, 9. prosince 201 9 16 Optimalizace & soft omezení: algoritmy NC* algoritmus 3 Projekce ceny hodnot (j, *) pro 3 Smazání hodnot (j,a) převyšující každou proměnnou j do dolní (nebo rovné) horní hranici UB hranice LB ceny řešení L-D = U i_D=o UB=10 UB=10 Hodnotu a proměnné j značíme (j,a) 3 obrázek: proměnná j má nejprve tři hodnoty (j, 1), (j, 2), (j, 3), jejichž cena je 2,4 a 5 Všechny hodnoty proměnné j značíme (j, *) Hana Rudová, Omezující podmínky, 9. prosince 2019 16 Optimalizace & soft omezení: algoritmy AC* algoritmus (A) Projekce ceny hrany (i,a)(j,b) do ceny hodnoty (i, a), pokud je tato cena zahrnuta ve všech hranách (i,a)(j, *) ub=11 ub=11 (1,2)0,1) — (1,2)0*, 2) — (í,2) (í,2)0,3) — Hana Rudová, Omezující podmínky, 9. prosince 2019 17 Optimalizace & soft omezení: algoritmy AC* algoritmus (A) Projekce ceny hrany (i,a)(j,b) do 3 ceny hodnoty (í, a), pokud je tato cena zahrnuta ve všech hranách (í,a)(j, *) ub=11 ub=11 (í,2)(j,l) — (1,2)0', 2) — (í,2) (í, 2)0,3) — Hana Rudová, Omezující podmínky, 9. prosince 201 9 17 NC* algoritmus (B) projekce ceny hodnot pro každou proměnnou (C) smazání hodnot s cenou > UB ub=11 ub=11 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) 3 n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou ........ „ statické uspořádání proměnných M první podproblem obsahuje pouze n-tou proměnnou í-tý podproblem obsahuje posledních i proměnných ((n - i + 1)... n) 3 podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhů Hana Rudová, Omezující podmínky, 9. prosince 2019 18 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou ........ „ statické uspořádání proměnných M první podproblem obsahuje pouze n-tou proměnnou í-tý podproblem obsahuje posledních i proměnných ((n - i + 1)... n) 3 podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhů Při řešení podproblému (n - i + 1) M problém zahrnuje proměnné xuXí+i,...,xn M mějme částečné přiřazení pro tento podproblem (aucií+i,clí+j) s nepřiřazenými proměnnými Xí+j+i, ...,xn Hana Rudová, Omezující podmínky, 9. prosince 2019 18 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou ........ „ statické uspořádání proměnných M první podproblem obsahuje pouze n-tou proměnnou í-tý podproblem obsahuje posledních i proměnných ((n - i + 1)... n) 3 podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhů Při řešení podproblému (n - i + 1) M problém zahrnuje proměnné xuXí+i,...,xn M mějme částečné přiřazení pro tento podproblem (aucií+i,clí+j) s nepřiřazenými proměnnými Xí+j+i, ...,xn 3 do dolní meze lze zahrnout optimální cenu (n-í- j) podproblému optim(Xi+j+i,xn) 3 LB((auai+i,...,ai+j)) = dist((auai+i,... ,ai+j)) + optim(xi+j+i,... ,xn) distiiduOLi+i,cií+j)) vzdálenost (součet vah omezení na minulých proměnných) optimální řešení přechozích problémů použita pro: výběr hodnoty, pro zlepšení iniciální horní meze Hana Rudová, Omezující podmínky, 9. prosince 2019 18 Optimalizace & soft omezení: algoritmy Prohledávání ruská panenka (Russion doll search) n po sobě jdoucích BB prohledávání, každé má navíc jednu proměnnou ........ „ statické uspořádání proměnných M první podproblem obsahuje pouze n-tou proměnnou í-tý podproblem obsahuje posledních i proměnných ((n - i + 1)... n) 3 podproblémy řešeny pomocí BB s využitím LB a UB z předchozích běhů Při řešení podproblému (n - i + 1) M problém zahrnuje proměnné xuXí+i,...,xn M mějme částečné přiřazení pro tento podproblem (aucií+i,clí+j) s nepřiřazenými proměnnými Xí+j+i, ...,xn 3 do dolní meze lze zahrnout optimální cenu (n-í- j) podproblému optim(Xi+j+i,xn) 3 LB((auai+i,...,ai+j)) = dist((auai+i,... ,ai+j)) + optim(xi+j+i,... ,xn) distiiduOLi+i,cií+j)) vzdálenost (součet vah omezení na minulých proměnných) optimální řešení přechozích problémů použita pro: výběr hodnoty, pro zlepšení iniciální horní meze Vnořená prohledávání se vyplatí vzhledem k prořezání stavového prostoru Hana Rudová, Omezující podmínky, 9. prosince 2019 18 Optimalizace & soft omezení: algoritmy