Algoritmy pro CSP (pokračování) Prohledávání do hloubky Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky (depth first search) Dvě fáze prohledávání s navracením ■ dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistení hodnoty (pokud existuje) další proměnné ■ po vybrání hodnoty testujeme konzistenci ■ zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě Proměnné dělíme na ■ minulé - proměnné, které už byly vybrány (a mají přiřazenu hodnotu) ■ aktuální - proměnná, která je právě vybrána a je jí přiřazována hodnota ■ budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Logické programování I, 18. května 2009 3 Algoritmy pro CSP Prohledávání + konzistence ■ Splňování podmínek prohledáváním prostoru řešení ■ podmínky jsou užívány pasivně jako test ■ přiřazuji hodnoty proměnných a zkouším co se stane ■ vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj ■ úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) ■ zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení ■ Konzistenční (propagační) techniky ■ umožňují odstranění nekonzistentních hodnot z domény proměnných ■ neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) ■ relativně rychlé (polynomiální) ■ Používá se kombinace obou metod ■ postupné přiřazování hodnot proměnným ■ po přiřazení hodnoty odstranění nekonzistentních hodnot konzistenčními technikami Hana Rudová, Logické programování I, 18. května 2009 2 Algoritmy pro CSP Základní algoritmus prohledávání do hloubky ■ Pro jednoduchost proměnné očíslujeme a ohodnocujeme je v daném pořadí ■ Na začátku voláno jako 1 abel i ng (C, 1) proceduře labeling(G,a) if a > |uzly(G)| then return uzly(G) for V x e Da do if consistent(G,a) then % consistent(G,a) je nahrazeno FC(G,a), LA(G,a R := Tabel ing(G,a +1) if R ŕ fail then return R return fail end labeling Po přiřazení všech proměnných vrátíme jejich ohodnocení ■ Procedury consistent uvedeme pouze pro binární podmínky Hana Rudová, Logické programování I, 18. května 2009 4 Algoritmy pro CSP Backtracking (BT) Príklad: backtracking Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné Backtracking tedy zajišťuje konzistenci podmínek ■ na všech minulých proměnných ■ na podmínkách mezi minulými proměnnými a aktuální proměnnou proceduře BT(G,a) Q:={(Ví, V a) e hranyCO , i < a] % hrany vedoucí z minulých proměnných do aktuální Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (VJt,Vm) z Q Consistent := not reviseiV^, Vm) % pokud vyradíme prvek, bude doména prázdná return Consistent end BT Hana Rudová, Logické programování I, 18. května 2009 5 Algoritmy pro CSP Kontrola dopředu (FC - forward checking) FCje rozšíření backtrackingu FC navíc zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami procedure FC(G,a) Q:={(Ví, V a) e h rany (C) , í > a] % přidání hran z budoucích do aktuální proměnné Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (VJt,Vm) z Q if revi se((VJt, Vm)) then Consistent := (|Djt|>0) % vyprázdnění domény znamená nekonzistenci return Consistent end FC Hrany z minulých proměnných do aktuální proměnné není nutno testovat ■ Omezení: Vu V2, V3 in 1... 3, V1# = 3xV3 ■ Stavový prostor: 4 ■ červené čtverečky: chybný pokus o instanciaci, řešení neexistuje ■ nevyplněná kolečka: nalezeno řešení ■ černá kolečka: vnitřní uzel, máme pouze částečné přiřazení Hana Rudová, Logické programování I, 18. května 2009 6 Příklad: kontrola dopředu ■ Omezení: Vlt V2, V3 in 1... 3, c:V1#=3x V3 ■ Stavový prostor: C => fail C => fail Hana Rudová, Logické programování I, 18. května 2009 7 Algoritmy pro CSP Hana Rudová, Logické programování I, 18. května 2009 Pohled dopředu (LA - looking aheacl) LAje rozšíření FC, navíc ověřuje konzistenci hran mezi budoucími proměnnými % začínáme s hranami do a proceduře LA(G,a) Q := {(VuVa) e h rany (C), í > a] Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vk,Vm) z Q if revi seC(Vk, Vm)) then Q := Q u {(VuVk)\(VuVk) e hrany(G), í + k, í + m, í > a] Consistent := (\Dk\ > 0) return Consistent end LA ■ Hrany z minulých proměnných do aktuální proměnné opět netestujeme ■ Tato LA procedura je založena naAC-3, lze použít i jiné AC algoritmy LA udržuje hranovou konzistenci: protože ale LA(G,a) používá AC-3, musíme zajistit iniciální konzistenci pomocí AC-3 ještě před startem prohledávání Hana Rudová, Logické programování I, 18. května 2009 Algoritmy pro CSP Příklad: pohled dopředu pomocí AC-1 Omezení: V1.y2.V3 in 1...4, cl:V1#>V2, c2 : V2# = 3 x V3 Stavový prostor, pokud bychom použili místo AC-3 algoritmus AC-1 ■ iniciální konzistence se před startem prohledávání nespouští ■ algorimus AC-1 opakuje revize všech hran, dokud se změnila doména alespoň jedné proměnné => AC-1 vynutí hranovou konzistenci, jakmile je přiřazena hodnota aktuální proměnné Ví d => fail c1 => V2=1 c1=>V2=1..2 c2 => fail c2 => fail Vo 3 Vo d => V2=1..3 c2 => V2=3 V3=1 Hana Rudová, Logické programování I, 18. května 2009 Algoritmy pro CSP Příklad: pohled dopředu (pomocí AC-3) Omezení: Vi,V2,V3 in 1...4, cl : Vi# > V2, c2 : V2# = 3 x V3 Stavový prostor (spouští se iniciální konzistence se před startem prohledávání) ^ d => V1 in 2..4 V2in 1..3 C2 => V2=3 V3= 1 d => V1= 4 V. 41 V2 3, Vo 1j v3 o Hana Rudová, Logické programování I, 18. května 2009 Algoritmy pro CSP Přehled algoritmů proměnné BT Backtracking (BT) kontroluje v kroku a podmínky c(Vi,Vfl),...,c(Vfl-i,Vfl) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky \^ c(V«+i,V«),...,c(V„,Vfl) a — z budoucích proměnných do aktuální proměnné Pohled dopředu (LA) kontroluje v kroku a podmínky ^ /I Vi(a < l < n), Vfe(a 1 0. 2. Ukažte, jak je dosaženo hranové konzistence v následujícím příkladu: domain([X,Y,Z],l ,5]), X #< Y, Z#= Y+l . Hana Rudová, Logické programování I, 18. května 2009 Algoritmy pro CSP Hana Rudová, Logické programování I, 1 8. května 2009 1 4 Algoritmy pro CSP Implementace Prologu Literatura: Matýska L, Toman D.: Implementační techniky Prologu , Informační systémy, (1 990), 21-59. http://www.ics.muni.cz/people/matyska/vyuka/Jp/Jp.hl Opakování: základní pojmy Konečná množina klauzulí Hlava :- Tělo tvoří program P. Hlava je literál Tělo je (eventuálně prázdná) konjunkce literálů Ti,... Ta, a > 0 Literál je tvořen m-árním predikátovým symbolem (m/p) a m termy (argumenty) Term je konstanta, proměnná nebo složený term. Složený term a n termy na místě argumentů Dotaz (cíl) je neprázdná množina literálů. Hana Rudová, Logické programování I, 18. května 2009 16 Implementace Prologu Interpretace Abstraktní interpret Deklarativní sémantika: Hlava platí, platí-1i jednotlivé literály těla. Procedurální (imperativní) sémantika: Entry: Hlava:: { call Ti call Ta } Volání procedury s názvem Hlava uspěje, pokud uspěje volání všech procedur (literálů) v těle. Procedurální sémantika = podklad pro implementaci Hana Rudová, Logické programování I, 18. května 2009 17 Implementace Prologu Abstraktní interpret - pokračování Kroky (3) až (5) představují redukci (logickou inferenci) cíle A. Počet redukcí za sekundu (LIPS) == indikátor výkonu implementace Věta Existuje-li instance C dotazu C, odvoditelná z programu P v konečném počtu kroků, pak bude tímto interpretem nalezena. Hana Rudová, Logické programování I, 18. května 2009 19 Implementace Prologu Vstup: Logický program P a dotaz C. 1. Inicializuj množinu cílů S literály z dotazu C; S:=C 2. while ( S != empty ) do 3. Vyber AeS a dále vyber klauzuli A' : -Bi, . . . , B„ (n > 0) z programu P takovou, že 3a : Aer = A' cr; cr je nejobecnější unifikátor. Pokud neexistuje A' nebo cr, ukonči cyklus. 4. Nahraď A v S cíli Bi až B„. 5. Aplikuj a na C a S. 6. end while 7. Pokud S==empty, pak výpočet úspěšně skončil a výstupem je C se všemi aplikovanými substitucemi. Pokud S!=empty, výpočet končí neúspěchem. Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Nedeterminismus interpetu 1. Selekční pravidlo: výběr cíle A z množiny cílů S ■ neovlivňuje výrazně výsledek chování interpretu 2. Způsob prohledávání stromu výpočtu: výběr klauzule A' z programu P ■ je velmi důležitý, všechny klauzule totiž nevedou k úspěšnému řešení Vztah k úplnosti: 1. Selekční pravidlo neovlivňuje úplnost ■ možno zvolit libovolné v rámci SLD rezoluce 2. Prohledávání stromu výpočtu do šířky nebo do hloubky „Prozření" - automatický výběr správné klauzule ■ vlastnost abstraktního interpretu, kterou ale reálné interprety nemají Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Prohledávání do šířky 1. Vybereme všechny klauzule Ar, které je možno unifikovat s literálem A ■ nechť je těchto klauzulí q 2. Vytvoříme q kopií množiny S 3. V každé kopii redukujeme A jednou z klauzulí Ar. ■ aplikujeme příslušný nejobecnější unifikátor 4. V následujících krocích redukujeme všechny množiny Si současně. 5. Výpočet ukončíme úspěchem, pokud se alespoň jedna z množin Si stane prázdnou. ■ Ekvivalence s abstraktnímu interpretem ■ pokud jeden interpret neuspěje, pak neuspěje i druhý ■ pokud jeden interpret uspěje, pak uspěje i druhý Hana Rudová, Logické programování I, 18. května 2009 21 Implementace Prologu Reprezentace objektů ■ Beztypový jazyk ■ Kontrola „typů" za běhu výpočtu ■ Informace o struktuře součástí objektu Typy objektů ■ Primitivní objekty: ■ konstanta ■ číslo ■ volná proměnná ■ odkaz (reference) ■ Složené (strukturované) objekty: ■ struktura ■ seznam Hana Rudová, Logické programování I, 18. května 2009 í Implementace Prologu Prohledávání do hloubky 1. Vybereme všechny klauzule A' i, které je možno unifikovat s literálem A. 2. Všechny tyto klauzule zapíšeme na zásobník. 3. Redukci provedeme s klauzulí na vrcholu zásobníku. 4. Pokud v nějakém kroku nenajdeme vhodnou klauzuli A', vrátíme se k předchozímu stavu (tedy anulujeme aplikace posledního unifikátoru cr) a vybereme ze zásobníku další klauzuli. 5. Pokud je zásobník prázdný, končí výpočet neúspěchem. 6. Pokud naopak zredukujeme všechny literály v S, výpočet končí úspěchem. ■ Není úplné, tj. nemusí najít všechna řešení ■ Nižší paměťová náročnost než prohledávání do šířky ■ Používá se v Prologu Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Reprezentace objektů II Příznaky (tags): Objekt Příznak volná proměnná FREE konstanta CONST celé číslo INT odkaz REF složený term FUNCT Obsah adresovatelného slova: hodnota a příznak. Primitivní objekty uloženy přímo ve slově Složené objekty ■ jsou instance termu ve zdrojovém textu, tzv. zdrojového termu ■ zdrojový term bez proměnných => každá instanciace ekvivalentní zdrojovému termu ■ zdrojový term s proměnnými => dvě instance se mohou lišit aktuálními hodnotami proměnných, jedinečnost zajišťuje kopírování struktur nebo sdílení struktur Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Kopírování struktur Kopírování struktur II Příklad: a(b(X),c(X,Y),d), FUNCT a/3 REF REF CONST d FUNCT c/2 REF FREE Y FUNCT b/1 FREE X Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Sdílení struktur Vychází z myšlenky, že při reprezentaci je třeba řešit přítomnost proměnných Instance termu < kostra_termu; rámec > ■ kostra_termu je zdrojový term s očíslovanými proměnnými ■ rámec je vektor aktuálních hodnot těchto proměnných ■ i-tá položka nese hodnotu i-té proměnné v původním termu Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Term F s aritou A reprezentován A+l slovy: ■ funktor a arita v prvním slově ■ 2. slovo nese první argument (resp. odkaz na jeho hodnotu) ■ ■ A+l slovo nese hodnotu A-tého argumentu Reprezentace vychází z orientovaných acyklických grafů: a/3 c/2 b/l X Vykopírována každá instance => kopírování struktur Termy ukládány na globální zásobník Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Sdílení struktur II Příklad: a(b(X),c(X,Y),d) reprezentuje < a(b($l),c($l,$2),d) ; [FREE, FREE] > kde symbolem $i označujeme i-tou proměnnou. Implementace: < &kostra_termu ; &rámec > (& vrací adresu objektu) Všechny instance sdílí společnou kostru_termu => sdílení struktur Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Srovnání: příklad Naivní srovnání: sdílení paměťově méně náročné Platí ale pouze pro rozsáhlé termy přítomné ve zdrojovém kódu Postupná tvorba termů: A = a(K,L,M), K = b(X), L = c(X,Y), M = d ■ Sdílení termů: kostra_a M:d kostra_b kostra_c Hana Rudová, Logické programování I, 18. května 2009 Implementace Prologu Srovnání II Složitost algoritmů pro přístup k jednotlivým argumentům ■ sdílení struktur: nutná víceúrovňová nepřímá adresace ■ kopírování struktur: bez problémů ■ jednodušší algoritmy usnadňují i optimalizace Lokalita přístupů do paměti ■ sdílení struktur: přístupy rozptýleny po paměti ■ kopírování struktur: lokalizované přístupy ■ při stránkování paměti - rozptýlení vyžaduje přístup k více stránkám Z praktického hlediska neexistuje mezi těmito přístupy zásadní rozdíl Srovnání: příklad - pokračování Kopírování struktur: A = a(K,L,M),K = b(X), L = c(X,Y), M = d FUNCT a/3 REF REF -CONST d FUNCT c/2 REF FREE Y FUNCT b/1 FREE X tj. identické jako přímé vytvoření termu a(b(X) ,c(X,Y) ,d) Hana Rudová, Logické programování I, 18. května 2009 30 Implementace Prologu Řízení výpočtu Dopředný výpočet ■ po úspěchu (úspěšná redukce) ■ jednotlivá volání procedur skončí úspěchem ■ klasické volání rekurzivních procedur Zpětný výpočet (backtracking) ■ po neúspěchu vyhodnocení literálu (neúspěšná redukce) ■ nepodaří se unifikace aktuálních a formálních parametrů hlavy ■ návrat do bodu, kde zůstala nevyzkoušená alternativa výpočtu ■ je nutná obnova původních hodnot jednotlivých proměnných ■ po nalezení místa s dosud nevyzkoušenou klauzulí pokračuje dále dopředný výpočet Hana Rudová, Logické programování I, 18. května 2009 31 Implementace Prologu Hana Rudová, Logické programování I, 18. května 2009 32 Implementace Prologu Aktivační záznam ■ Volání (=aktivace) procedury ■ Aktivace sdílí společný kód, liší se obsahem aktivačního záznamu ■ Aktivační záznam uložen na lokálním zásobníku ■ Dopředný výpočet ■ stav výpočtu v okamžiku volání procedury ■ aktuální parametry ■ lokální proměnné ■ pomocné proměnné ('a la registry) ■ Zpětný výpočet (backtracking) ■ hodnoty parametrů v okamžiku zavolání procedury ■ následující klauzule pro zpracování při neúspěchu Hana Rudová, Logické programování I, 18. května 2009 33 Implementace Prologu Okolí a bod volby Aktivační záznam úspěšně ukončené procedury nelze odstranit z lokálního zásobníku => rozdělení aktivačního záznamu: ■ okolí (environment) - informace nutné pro dopředný běh programu ■ bod volby (choice point) - informace nezbytné pro zotavení po neúspěchu ■ ukládány na lokální zásobník ■ samostatně provázány (odkaz na předchozí okolí resp. bod volby) Důsledky: ■ samostatná práce s každou částí aktivačního záznamu (optimalizace) ■ alokace pouze okolí pro deterministické procedury ■ možnost odstranění okolí po úspěšném vykonání (i nedeterministické) procedury (pokud okolí následuje po bodu volby dané procedury) ■ pokud je okolí na vrcholu zásobníku Hana Rudová, Logické programování I, 18. května 2009 35 Implementace Prologu Aktivační záznam a roll-back ■ Neúspěšná klauzule mohla nainstanciovat nelokální proměnné ■ a(X) :- X = b(c,Y), Y = d. ?- W = b(Z,e), a(W) . (viz instanciace Z) ■ Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných ■ Využijeme vlastností logických proměnných ■ instanciovat lze pouze volnou proměnnou ■ jakmile proměnná získá hodnotu, nelzeji změnit jinak než návratem výpočtu => původní hodnoty všech proměnných odpovídají volné proměnné ■ Stopa (trail): zásobník s adresami instanciovaných proměnných ■ ukazatel na aktuální vrchol zásobníku uchováván v aktivačním záznamu ■ při neúspěchu jsou hodnoty proměnných na stopě v úseku mezi aktuálním a uloženým vrcholem zásobníku změněny na „volná" ■ Globální zásobník: pro uložení složených termů ■ ukazatel na aktuální vrchol zásobníku uchováván v aktivačním záznamu ■ při neúspěchu vrchol zásobníku snížen podle uschované hodnoty v aktivačním záznamu Hana Rudová, Logické programování I, 18. května 2009 34 Implementace Prologu Řez ■ Prostředek pro ovlivnění běhu výpočtu programátorem ■ a(X) :- b(X), !, c(X). a(3). b(l). b(2). c(l). c(2). ■ Řez: neovlivňuje dopředný výpočet, má vliv pouze na zpětný výpočet ■ Odstranění alternativních větví výpočtu => odstranění odpovídajících bodů volby ■ tj. odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) => změna ukazatele na „nejmladší" bod volby => Vytváření deterministických procedur => Optimalizace využití zásobníku Hana Rudová, Logické programování I, 18. května 2009 36 Implementace Prologu