Lokální prohledávání Lokální prohledávání (LS) 3 Princip M pracuje s úplnými nekonzistentními přiřazeními proměnných snaží se lokálními opravami snížit počet konfliktů Příklad: umístění n dam na šachovnici iniciální přiřazení umístí každou královnu do každého sloupce a řádku bez ohledu na diagonální omezení přesunujeme královnu v jejím sloupci do jiného řádku tak, abychom odstranili co nejvíce konfliktů M LS vyřeší řádově větší problémy než algoritmy založené na prohledávání do hloubky Hana Rudová, Omezující podmínky, 25. listopadu 2019 2 Lokální prohledávání Lokální prohledávání (LS) 3 Princip M pracuje s úplnými nekonzistentními přiřazeními proměnných snaží se lokálními opravami snížit počet konfliktů Příklad: umístění n dam na šachovnici iniciální přiřazení umístí každou královnu do každého sloupce a řádku bez ohledu na diagonální omezení přesunujeme královnu v jejím sloupci do jiného řádku tak, abychom odstranili co nejvíce konfliktů 3 LS vyřeší řádově větší problémy než algoritmy založené na prohledávání do hloubky 3 Přibližná metoda prohledávání 3 neúplná metoda nezaručuje nalezení (vyloučení existence) řešení i když existuje (neexistuje) 3 malé paměťové nároky Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 2 Lokální prohledávání Terminologie lokálního prohledávání & Stav 0: ohodnocení všech proměnných M Evaluace E: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) Globální optimum: stav s nejlepší evaluací Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 3 Lokální prohledávání Terminologie lokálního prohledávání -0 Stav 0: ohodnocení všech proměnných M Evaluace E: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) & Globální optimum: stav s nejlepší evaluací M Lokální změna: změna hodnoty (jedné) proměnné & Okolí o: množina stavů lišící se od daného stavu o jednu lokální změnu Lokální optimum: stav, v jehož okolí jsou stavy s horší evaluací; není globálním optimum minimum Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 3 Lokální prohledávání Terminologie lokálního prohledávání -0 Stav 0: ohodnocení všech proměnných M Evaluace E: hodnota objektivní funkce (počet nesplněných podmínek=počet konfliktů) & Globální optimum: stav s nejlepší evaluací M Lokální změna: změna hodnoty (jedné) proměnné & Okolí o: množina stavů lišící se od daného stavu o jednu lokální změnu Lokální optimum: stav, v jehož okolí jsou stavy s horší evaluací; není globálním optimum M Striktní lokální optimum: stav, v jehož okolí jsou pouze stavy s horší evaluací; není globálním optimum M Ne-striktní lokální optimum: stav, v jehož okolí exisují stavy se stejnou evaluací; není globálním optimum M Plateau: množina stavů se stejnou evaluací minimum Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 3 Lokální prohledávání Algoritmus lokálního prohledávání Algoritmy lokálního prohledávání mají společnou kostru proceduře LS(MaxPokusu,MaxZmen) parametry algoritmu 6 : = náhodné ohodnoceni proměnných for i := 1 to MaxPokusu while GPodminka do for j := 1 to MaxZmen while LPodminka do if E(0)=O then return 0 vyber ô e o(0) if akceptovatelne(č) then 6 := ô 6 := novyStav(fl) return nejlepši 0 Rudová, Omezující podmínky, 25. listopadu 2019 4 Lokální prohledávání Algoritmus lokálního prohledávání Algoritmy lokálního prohledávání mají společnou kostru proceduře LS(MaxPokusu,MaxZmen) parametry algoritmu 6 : = náhodné ohodnoceni proměnných for i := 1 to MaxPokusu while GPodminka do for j := 1 to MaxZmen while LPodminka do if E(0)=O then return 0 vyber ô e o(0) if akceptovatelne(č) then 6 := ô 6 := novyStav(fl) return nejlepši 0 M Jak stanovit MaxPokusu, MaxZmen? 3 pokračovat dokud existuje prirazení s lepší evaluací M restart (MaxPokusu>l) v některých případech diskutabilní Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 4 Lokální prohledávání Metoda největšího stoupání (hill climbing) HC Začíná v náhodně vybraném stavu Hledá vždy nejlepší stav v okolí Okolí = hodnota libovolné proměnné je změněna, velikost okolí n x (d - 1) Útěk ze striktního lokálního minima pomocí restartu proceduře HC(MaxZmen) restart: 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do if E(0) = 0 then return 0 if 0 je striktní lokální optimum then goto restart else 0 := stav z o{0) s nejlepší evaluaci goto restart end HC Hana Rudová, Omezující podmínky, 25. listopadu 2019 5 Lokální prohledávání Metoda minimalizace konfliktu (MC) Okolí u HC je poměrně velké: n x (d - 1) ale pouze změna konfliktní proměnné může přinést zlepšení M konfliktní proměnná = vystupuje v některých nesplněných podmínkách MC mění pouze konfliktní proměnné * okolí = hodnota zvolené proměnné je změněna, velikost okolí d - 1 proceduře MC(MaxZmen) 0 : = náhodné ohodnoceni proměnných PocetZmen := 0 while E(0) > 0 a PocetZmen 0 a PocetZmen (1 - p) 0.02 < p < 0.1 vyber náhodně hodnotu a pro V else vyber hodnotu a, která minimalizuje počet konfliktů pro V if a^současná hodnota V then při řad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 25. listopadu 2019 8 Lokální prohledávání Největší stoupání s náhodnou procházkou procedure HCRW(MaxZmen, p) Rozdíly od MCRW 0 : = náhodné ohodnoceni proměnných PocetZmen := 0 while E(0) > 0 a PocetZmen s nejlepší evaluací if a^současná hodnota V then pri rad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 25. listopadu 2019 9 Lokální prohledávání Tabu seznam Setrvání v lokálním optimu je speciálním případem cyklu Jak se obecně zbavit cyklů? stačí si pamatovat předchozí stavy a zakázat opakování stavu paměťově příliš náročné (mnoho stavů) 3 můžeme si zapamatovat pouze několik posledních stavů (zabrání krátkým cyklům) Hana Rudová, Omezující podmínky, 25. listopadu 2019 10 Lokální prohledávání Tabu seznam Setrvání v lokálním optimu je speciálním případem cyklu Jak se obecně zbavit cyklů? stačí si pamatovat předchozí stavy a zakázat opakování stavu paměťově příliš náročné (mnoho stavů) * můžeme si zapamatovat pouze několik posledních stavů (zabrání krátkým cyklům) Tabu seznam = seznam tabu (zakázaných) stavů M stav lze popsat význačným atributem (není nutné uchovávat celý stav) M (proměnná,hodnota): zachycuje změnu stavu (uložíme původní hodnoty) tabu seznam má fixní délku {tabu tenure) „staré" stavy ze seznamu vypadávají s přicházejímími novými stavy Hana Rudová, Omezující podmínky, 25. listopadu 2019 10 Lokální prohledávání Tabu seznam Setrvání v lokálním optimu je speciálním případem cyklu Jak se obecně zbavit cyklů? stačí si pamatovat předchozí stavy a zakázat opakování stavu paměťově příliš náročné (mnoho stavů) * můžeme si zapamatovat pouze několik posledních stavů (zabrání krátkým cyklům) Tabu seznam = seznam tabu (zakázaných) stavů M stav lze popsat význačným atributem (není nutné uchovávat celý stav) M (proměnná,hodnota): zachycuje změnu stavu (uložíme původní hodnoty) tabu seznam má fixní délku {tabu tenure) „staré" stavy ze seznamu vypadávají s přicházejímími novými stavy Aspirační kritérium = odtabuizovaní stavu M do stavu lze přejít, i když je v tabu seznamu (např. krok vede k celkově lepšímu stavu) Hana Rudová, Omezující podmínky, 25. listopadu 2019 10 Lokální prohledávání Tabu seznam Setrvání v lokálním optimu je speciálním případem cyklu Jak se obecně zbavit cyklů? stačí si pamatovat předchozí stavy a zakázat opakování stavu paměťově příliš náročné (mnoho stavů) 3 můžeme si zapamatovat pouze několik posledních stavů (zabrání krátkým cyklům) Tabu seznam = seznam tabu (zakázaných) stavů 3 stav lze popsat význačným atributem (není nutné uchovávat celý stav) M (proměnná,hodnota): zachycuje změnu stavu (uložíme původní hodnoty) tabu seznam má fixní délku {tabu tenure) „staré" stavy ze seznamu vypadávají s přicházejímími novými stavy Aspirační kritérium = odtabuizovaní stavu M do stavu lze přejít, i když je v tabu seznamu (např. krok vede k celkově lepšímu stavu) 3 Tabu seznam je používán samostatně i v kombinaci s jinými metodami LS Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 10 Lokální prohledávání Algoritmus prohledávání s tabu seznamem M Tabu seznam zabraňuje krátkemu cyklení Povoleny jsou pouze tahy mimo tabu seznam a tahy splňující aspirační kritérium M Tabu seznam (TS) v kombinaci s metodou stoupání (HC): proceduře TSHC(MaxZmen) 0 : = náhodné ohodnoceni proměnných PocetZmen := 0 while E(0) > 0 a PocetZmen do tabu seznamu, kde c je současná hodnota V smaž nejstarši položku v tabu seznamu při řad' a do V PocetZmen := PocetZmen+1 return 0 Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 11 Lokální prohledávání Výběr souseda: přehled M Metoda stoupání (HC) soused s nejlepší evaluací vybrán Tabu prohledávání (TS+HC) M soused s nejlepší evaluací vybrán (metoda stoupání) sousedé z tabu seznamu nemohou být vybráni Hana Rudová, Omezující podmínky, 25. listopadu 2019 12 Lokální prohledávání Výběr souseda: přehled 3 Metoda stoupání (HC) soused s nejlepší evaluací vybrán Tabu prohledávání (TS+HC) soused s nejlepší evaluací vybrán (metoda stoupání) M sousedé z tabu seznamu nemohou být vybráni Minimální konflikt (MC) soused je omezen na náhodně vybranou konfliktní proměnnou M výběr její hodnoty s nejlepší evaluací Náhodná procházka (RW) «• soused vybrán náhodně Hana Rudová, Omezující podmínky, 25. listopadu 2019 12 Lokální prohledávání Výběr souseda: přehled Metoda stoupání (HC) soused s nejlepší evaluací vybrán Tabu prohledávání (TS+HC) M soused s nejlepší evaluací vybrán (metoda stoupání) sousedé z tabu seznamu nemohou být vybráni 3 Minimální konflikt (MC) M soused je omezen na náhodně vybranou konfliktní proměnnou výběr její hodnoty s nejlepší evaluací 3 Náhodná procházka (RW) M soused vybrán náhodně M Min. konflikt (metoda stoupání) s náhodnou procházkou MC+RW (HC+RW) s malou pravděpodobností: náhodný výběr souseda M jinak: minimální konflikt (metoda stoupání) Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 12 Lokální prohledávání Simulované žíhání (simulated annealing) SA M Myšlenka: simulace procesu ochlazování kovů na začátku při vyšší teplotě atomy více kmitají a pravděpodobnost změny krystalické mřížky je vyšší 3 postupným ochlazováním se atomy usazují co „nejlepší polohy" s nejmenší energií a pravděpodobnost změny je menší => na začátku je tedy pravděpodobnost toho, že akceptujeme zhoršování řešení, vyšší Hana Rudová, Omezující podmínky, 25. listopadu 2019 13 Lokální prohledávání Simulované žíhání (simulated annealing) SA 3 Myšlenka: simulace procesu ochlazování kovů na začátku při vyšší teplotě atomy více kmitají a pravděpodobnost změny krystalické mřížky je vyšší 3 postupným ochlazováním se atomy usazují co „nejlepší polohy" s nejmenší energií a pravděpodobnost změny je menší => na začátku je tedy pravděpodobnost toho, že akceptujeme zhoršování řešení, vyšší Akceptování nového stavu vždy při zlepšení při zhoršení pouze za dané pravděpodobnosti, která klesá se snížením teploty Cykly algoritmu «• vnější: simulace procesu ochlazování snižováním teploty T čím nižší bude teplota, tím nižší bude pravděpodobnost akceptování zhoršení M vnitřní: počítáme, kolikrát jsme neakceptovali zhoršení (dán limit Maxlter) Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 13 Lokální prohledávání Metropolisovo kritérium Rozdíl mezi kvalitou nového (5) a existujícího (0) řešení M AE = E(5)-E(0) & E (chybovost) musí být minimalizováno Metropolisovo kritérium 3 lepší (někdy případně i stejně kvalitní) řešení akceptováno: AE > 0 horší řešení (AE > 0) akceptováno pokud U < e~AE/T U náhodné číslo z intervalu (0,1) Hana Rudová, Omezující podmínky, 25. listopadu 2019 14 Lokální prohledávání Metropolisovo kritérium Rozdíl mezi kvalitou nového (5) a existujícího (0) řešení M AE = E(5)-E(0) & E (chybovost) musí být minimalizováno Metropolisovo kritérium 3 lepší (někdy případně i stejně kvalitní) řešení akceptováno: AE > 0 horší řešení (AE > 0) akceptováno pokud U < e AE/T M U náhodné číslo z intervalu (0,1) pomůcka: porovnej e 10/100 vs. e 100/100 Hana Rudová, Omezující podmínky, 25. listopadu 2019 14 Lokální prohledávání Metropolisovo kritérium Rozdíl mezi kvalitou nového (5) a existujícího (0) řešení M AE = E(5)-E(0) & E (chybovost) musí být minimalizováno Metropolisovo kritérium 3 lepší (někdy případně i stejně kvalitní) řešení akceptováno: AE > 0 horší řešení (AE > 0) akceptováno pokud U < e AE/T M U náhodné číslo z intervalu (0,1) pomůcka: porovnej e 10/100 vs. e 100/100 a e 10/100 vs. e 10/1 Hana Rudová, Omezující podmínky, 25. listopadu 2019 14 Lokální prohledávání Algoritmus simulovaného žíhání (akceptuj přiřazeni) proceduře SA( TInit, TEnd, Maxlter ) 6 : = náhodné ohodnoceni proměnných a := 6 (dosud nejlepší nalezené přiřazeni) for T := TInit to TEnd PocetChyb := 0 while PocetChyb < Maxlter vyber lokálni změnu z 0 do ô if E(ô) CSP nad disjunkcemi boolean proměnných SAT je NP-úplný Hana Rudová, Omezující podmínky, 25. listopadu 2019 16 Lokální prohledávání Lokální prohledávání pro SAT problém SAT problém: splnitelnost logické formule v konjunktivní normální formě CNF = konjunkce klauzulí M klauzule = disjunkce literálů (podmínka) literál = atom nebo negace atomu příklad: (A v B) a (-.£ v C) a (-.C v -iA) => CSP nad disjunkcemi boolean proměnných M SAT je NP-úplný LS řeší poměrně velké formule formulace LS je velice přirozená a jeho použití je velice populární M lokální změna je překlápěním (flipping) hodnoty proměnné Algoritmus GSAT (greedy SAT) M postupné překlápění proměnných 3 evaluace udává, jaký je (vážený) počet nesplněných klauzulí Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 16 Lokální prohledávání Algoritmus GSAT procedúre GSAT(A,MaxPokusu,MaxZmen) (A je CNF formule) for i := 1 to MaxPokusu do 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do i f A je splnitelná pomoci 0 then return 0 V := proměnná, jejíž změna hodnoty nejvice sniži počet nesplněných klauzuli 0 : = přiřazeni, které se liši od 0 změnou hodnoty V return nejlepši 0 Hana Rudová, Omezující podmínky, 25. listopadu 2019 17 Lokální prohledávání Algoritmus GSAT proceduře GSAT(A,MaxPokusu,MaxZmen) (A je CNF formule) for i := 1 to MaxPokusu do 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do i f A je splnitelná pomoci 0 then return 0 V := proměnná, jejíž změna hodnoty nejvíce sníží počet nesplněných klauzuli 0 : = přiřazeni, které se liši od 0 změnou hodnoty V return nejlepši 0 M Příklad: {-.C, -A v v C, -AvDvf, v --C} 3 iniciální přiřazení (všechny proměnné mají hodnotu 1) nesplňuje první a poslední klauzuli M změna A, D, £ Hana Rudová, Omezující podmínky, 25. listopadu 2019 17 Lokální prohledávání Algoritmus GSAT proceduře GSAT(A,MaxPokusu,MaxZmen) (A je CNF formule) for i := 1 to MaxPokusu do 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do i f A je splnitelná pomoci 0 then return 0 V := proměnná, jejíž změna hodnoty nejvice sniži počet nesplněných klauzuli 0 : = přiřazeni, které se liši od 0 změnou hodnoty V return nejlepši 0 M Příklad: {-.C, -A v v C, -AvDvf, v --C} 3 iniciální přiřazení (všechny proměnné mají hodnotu 1) nesplňuje první a poslední klauzuli změna A,D,E nemá vliv na počet nesplněných klauzulí 3 změna C na 0 Hana Rudová, Omezující podmínky, 25. listopadu 2019 17 Lokální prohledávání Algoritmus GSAT procedúre GSAT(A,MaxPokusu,MaxZmen) (A je CNF formule) for i := 1 to MaxPokusu do 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do i f A je splnitelná pomoci 0 then return 0 V := proměnná, jejíž změna hodnoty nejvíce sníží počet nesplněných klauzuli 0 : = přiřazeni, které se liši od 0 změnou hodnoty V return nejlepši 0 M Příklad: {-.C, -A v v C, -AvDvf, v --C} 3 iniciální přiřazení (všechny proměnné mají hodnotu 1) nesplňuje první a poslední klauzuli změna A,D,E nemá vliv na počet nesplněných klauzulí změna C na 0 splní první i poslední klauzuli ale nesplní —>A v ~*B v C (evaluace=l) 3 změna B Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 17 Lokální prohledávání Algoritmus GSAT proceduře GSAT(A,MaxPokusu,MaxZmen) (A je CNF formule) for i := 1 to MaxPokusu do 0 : = náhodné ohodnoceni proměnných for j := 1 to MaxZmen do i f A je splnitelná pomoci 0 then return 0 V := proměnná, jejíž změna hodnoty nejvíce sníží počet nesplněných klauzuli 0 : = přiřazeni, které se liši od 0 změnou hodnoty V return nejlepši 0 M Příklad: {-.C, -A v v C, -AvDvf, v --C} 3 iniciální přiřazení (všechny proměnné mají hodnotu 1) nesplňuje první a poslední klauzuli změna A,D,E nemá vliv na počet nesplněných klauzulí změna C na 0 splní první i poslední klauzuli ale nesplní —>A v ~*B v C (evaluace=l) M změna B má evaluaci 1 také, pokud ale změníme C a pak B, pak dostáváme evaluaci 0 Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 17 Lokální prohledávání Heuristiky pro GSAT GSAT lze kombinovat s různými heuristikami, které zvyšují jeho efektivitu M obzvláště při řešení strukturovaných problémů Použití náhodné procházky spolu s minimalizací konfliktů Vážení klauzulí 3 některé klauzule zůstávají po řadu iterací nesplněné, klauzule tedy mají různou důležitost splnění „těžké" klauzule lze preferovat přidáním váhy 3 váhu může systém odvodit ±> na začátku mají všechny klauzule stejnou váhu ±> po každém pokusu zvyšujeme váhu u nesplněných klauzulí Hana Rudová, Omezující podmínky, 25. listopadu 2019 18 Lokální prohledávání Heuristiky pro GSAT GSAT lze kombinovat s různými heuristikami, které zvyšují jeho efektivitu M obzvláště při řešení strukturovaných problémů Použití náhodné procházky spolu s minimalizací konfliktů Vážení klauzulí * některé klauzule zůstávají po řadu iterací nesplněné, klauzule tedy mají různou důležitost splnění „těžké" klauzule lze preferovat přidáním váhy 3 váhu může systém odvodit ±> na začátku mají všechny klauzule stejnou váhu ±> po každém pokusu zvyšujeme váhu u nesplněných klauzulí 3 Průměrování řešení M standardně každý pokus začíná z náhodného řešení 3 společné části předchozích řešení lze zachovat ±> restartovací stav se vypočte ze dvou posledních výsledků bitovým srovnáním stejné bity zachovány, ostatní nastaveny náhodně Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 18 Lokální prohledávání Hybridní prohledávání 3 Příklady kombinace lokálního prohledávání prohledává úplná nekonzistentní přiřazení a stromového prohledávání rozšiřuje částečné konzistentní přiřazení Hana Rudová, Omezující podmínky, 25. listopadu 2019 19 Lokální prohledávání Hybridní prohledávání 3 Příklady kombinace lokálního prohledávání prohledává úplná nekonzistentní přiřazení a stromového prohledávání rozšiřuje částečné konzistentní přiřazení 1. Lokální prohledávání před nebo po stromovém prohledávání např: M před: Hana Rudová, Omezující podmínky, 25. listopadu 2019 19 Lokální prohledávání Hybridní prohledávání 3 Příklady kombinace lokálního prohledávání prohledává úplná nekonzistentní přiřazení a stromového prohledávání rozšiřuje částečné konzistentní přiřazení 1. Lokální prohledávání před nebo po stromovém prohledávání např: před: lokální prohledávání nám poskytne heuristiku na uspořádání hodnot M po: Hana Rudová, Omezující podmínky, 25. listopadu 2019 19 Lokální prohledávání Hybridní prohledávání 3 Příklady kombinace lokálního prohledávání prohledává úplná nekonzistentní přiřazení a stromového prohledávání rozšiřuje částečné konzistentní přiřazení 1. Lokální prohledávání před nebo po stromovém prohledávání např: před: lokální prohledávání nám poskytne heuristiku na uspořádání hodnot M po: lokálním prohledáváním se snažíme lokálně vylepšit spočítané řešení (optimalizace) 2. Stromové prohledávání je doplněno lokálním prohledávání v listech prohledávacího stromu i v jeho uzlech např. lokální prohledávání pro výběr hodnoty nebo vylepšení spočítaného řešení 3. Lokální prohledávání je doplněno stromovým prohledáváním pro výběr souseda z okolí a nebo pro prořezávání stavového prostoru Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 19 Lokální prohledávání Iterativní dopředně prohledávání Iterative Forward Search (IFS) 3 Hybridní prohledávání: konstruktivní nesystematický algoritmus pracuje nad modelem s pevnými a měkkými omezujícími podmínkami M pevné podmínky: musí být splněny 3 měkké podmínky: reprezentují účelové funkce, jejichž vážený součet je minimalizován Pracuje s konzistentními přiřazeními Základní myšlenky (blízký dynamickému backtrackingu) začíná s prázdným přiřazením M vybere novou proměnnou k přiřazení 3 pokud nalezne konflikt, zruší přiřazení všech proměnných v konfliktu s vybranou proměnnou M výběr hodnot pomocí konfliktní statistiky výběr proměnných není pro algoritmus kritický, protože lze proměnné přiřadit opakovaně Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 20 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution ■ Unassigned variables Hana Rudová, Omezující podmínky, 25. listopadu 2019 21 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution < m £- o ■ Unassigned variables Hana Rudová, Omezující podmínky, 25. listopadu 2019 22 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution Select a value < m £- o □ 1? 1? U 1? T Unassigned variables Hana Rudová, Omezující podmínky, 25. listopadu 2019 23 Lokální prohledávání Iterative Forward Search Algorithm A (partial) feasible solution Select a value < m £- o ■ Some variables can be unassigned Unassigned variables Hana Rudová, Omezující podmínky, 25. listopadu 2019 24 Lokální prohledávání IFS: algoritmus procedure IFS() iteration = 0; % čítač iterací current = 0; % aktuální řešení best = 0; % nejlepší řešení while canContinue (current, iteration) do iteration = iteration + 1; variable = selectVariable (current); value = selectValue (current, variable); unassign(current, conflictingVariables(current, variable, value)); assign(current, variable, value); if better (current, best) then best = current return best end IFS procedure conflictingVariables: kontroluje konzistenci tak, aby byla splněna omezení na přiřazených proměnných, a vrací konfliktní proměnné unassign: odstraní přiřazení konfliktních proměnných Hana Rudová, Omezující podmínky, 25. listopadu 2019 25 Lokální prohledávání IFS: konfliktní statistika Předpoklad: při výběru hodnoty a proměnné A je nutné zrušit přiřazení hodnoty b proměnné B, tj. [A = a — -> B = b] 3 V průběhu výpočtu si tedy lze pamatovat: A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a Hana Rudová, Omezující podmínky, 25. listopadu 2019 26 Lokální prohledávání IFS: konfliktní statistika Předpoklad: při výběru hodnoty a proměnné A je nutné zrušit přiřazení hodnoty b proměnné B, tj. [A = a — -> B = b] V průběhu výpočtu si tedy lze pamatovat: A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a M Při výběru hodnoty vybíráme hodnoty s nejnižším počtem konfliktů vážených jejich frekvencí ±> konflikt započítáme pouze tehdy, pokud to vede k odstranění přiřazení J př. A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a A = b => 1x^5 = a, 3x^ B = b, 2 x ^ C = a Máme přiřazení B = c,C = a,D = b a vybíráme hodnotu pro A: ± nechť Aja vede ke konfliktu s B je: Hana Rudová, Omezující podmínky, 25. listopadu 2019 26 Lokální prohledávání IFS: konfliktní statistika Předpoklad: při výběru hodnoty a proměnné A je nutné zrušit přiřazení hodnoty b proměnné B, tj. [A = a — -> B = b] V průběhu výpočtu si tedy lze pamatovat: A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a M Při výběru hodnoty vybíráme hodnoty s nejnižším počtem konfliktů vážených jejich frekvencí ±> konflikt započítáme pouze tehdy, pokud to vede k odstranění přiřazení J př. A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a A = b => 1x^5 = a, 3x^ B = b, 2 x ^ C = a Máme přiřazení B = c,C = a,D = b a vybíráme hodnotu pro A: nechť AIa vede ke konfliktu s BI c: vyhodnoceno jako 4 • není konflikt s C/a, tak se nezapočítává M nechť Alb vede ke konfliktu s C/a: Hana Rudová, Omezující podmínky, 25. listopadu 2019 26 Lokální prohledávání IFS: konfliktní statistika Předpoklad: při výběru hodnoty a proměnné A je nutné zrušit přiřazení hodnoty b proměnné B, tj. [A = a — -> B = b] V průběhu výpočtu si tedy lze pamatovat: A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a M Při výběru hodnoty vybíráme hodnoty s nejnižším počtem konfliktů vážených jejich frekvencí ±> konflikt započítáme pouze tehdy, pokud to vede k odstranění přiřazení J př. A = a => 3x^B = b, 4x^B = c, 1 x ^ C = a, 120 x^D = a A = b => 1x^5 = a, 3x^ B = b, 2 x ^ C = a Máme přiřazení B = c,C = a,D = b a vybíráme hodnotu pro A: nechť AIa vede ke konfliktu s BI c: vyhodnoceno jako 4 • není konflikt s C/a, tak se nezapočítává ±* nechť Alb vede ke konfliktu s C/a: vyhodnoceno jako 2 -i* tj. vybereme hodnotu b pro proměnnou A Hana Rudová, Omezující podmínky, 2 5. listopadu 2019 26 Lokální prohledávání