Využití principů, ale vlastní naprogramování řešících

Využití CSP

Cvičení 1

Programování

s omezujícími podmínkami

Využití principů, ale vlastní naprogramování řešících algoritmů.

flexibilita (možnost plně přizpůsobit vlastním potřebám) rychlost (pro daný problém) náročné na počáteční vývoji i údržbu

Použití existujícího j řešiče p podmínek.

zpravidla integrovaný formou knihovny do hostitelského jazyka naprogramované řešící algoritmy soustředění na modelování problému nelze zasahovat do nízko-úrovňových struktur (definice domén,…) někdy možnost definovat vlastní podmínky často možnost definovat vlastní prohledávání

Roman Barták Katedra teoretické informatiky a matematické logiky [email protected] http://ktiml.mff.cuni.cz/~bartak

Programování s omezujícími podmínkami, Roman Barták

Řešiče podmínek

SICStus Prolog http://www.sics.se/sicstus

http://ktiml.mff.cuni.cz/~bartak/constraints/systems.html

Poskytované služby:

implementace datových struktur pro modelování domén proměnných a pro podmínky základní rámec propagace podmínek filtrační algoritmy pro řadu podmínek (včetně globálních podmínek) základní prohledávací strategie včetně heuristik pro výběr proměnných a hodnot rozhraní pro definici vlastních podmínek

Klasifikace:

Minion

vlastní programovací/modelovací jazyk

M Mozart, t OPL, OPL Comet, C t CHR

Vlastnosti

Prolog: ECLiPSe, SICStus Prolog C/C++: ILOG Solver, Solver Gecode Java: Choco, JaCoP Programování s omezujícími podmínkami, Roman Barták

podpora ISO standardu Prologu podpora řady počítačových platforem (Win, MacOS X, Linux, Solaris) vývojové prostředí GNU Emacs řada knihoven včetně clpfd možnost ž t ttvorby b samostatných t t ý h ((stand-alone) t d l ) i vestavěných t ě ý h (embedded) aplikací

Proč Prolog?

hostitelský jazyk

Komerční č í systém, é 30-denníí zkušební š í licence

samostatné é řřešiče šč

jednoduchá syntax krátký program hodně umí přímočará integrace omezujících podmínek prohledávání je součástí řešícího systému


Základní koncept Prologu Prolog je deduktivní systém, který hledá odpovědi na otázky použitím báze znalostí skládající se z faktů a odvozovacích pravidel.

Archite rchitek ktur tura a Prologu

Zdrojové soubory *.pl

Prologvská databáze

Kde jje programování? p g databáze faktů a pravidel Prolog automaticky odvozuje odpovědi ª deklarativní programování

SICStus 3.11.0 (x86-win32-nt-4): Mon Oct 20 00:38:10 WEDT 2003 Licensed to visopt.com | ?-

tvorba

Dotazy



Prologovské fakty Prologovské P l ké fakty f kt popisují i jí základní ákl d í údaje o řešeném problému.

Přímé dotazy Je možné klást dotazy na fakty uložené v bázi znalostí Prologu: Prolog prompt

node(a). node(a) node(b). node(c) node(c). node(d). node(e) node(e). jméno

argument a gu e

b d

a c

e

arc(a,b). arc(a b) arc(a,c). arc(b c) arc(b,c). arc(b,d). arc(c d) arc(c,d). arc(d,e). více argumentů se j čárkami odděluje


arc(a,b). arc(a,c). member(X,[X|_]). arc(b,c). member(X,[_|T]):- arc(c,d). member(X,T). arc(d,e). arc(b,e). delete([],_X,[]). delete([X|T],X,T).edge(X,Y):-arc(X,Y). delete([Y|T],X,[Y|NewT]):edge(X,Y):-arc(Y,X). X\=Y, \ , delete(T,X,NewT). path(X,Y):-arc(X,Y). path(X,Y):-arc(X,Z),path(Z,Y).

dotaz

?- node(a). odpověď yes ? node(bla). ?d (bl ) no ? arc(a,c). ?arc(a c) yes ?- arc(a,d). ? arc(a d) no ?- path(a,d). ? no

node(a). node(b). node(c). node(d). node(e). arc(a,b). arc(a,c). arc(b,c). arc(b d) arc(b,d). arc(c,d). arc(d,e).


Otevřené dotazy Dotaz může obsahovat proměnné, jejichž hodnoty budou nalezeny v bázi znalostí: ?-node(X). X X=a ; požadavek na X=b ; alternativní odpověď X=c X c ; X=d ; X=e ; žád é d žádné další lší odpovědi d ědi no ?-arc(a,X). ( , ) X=b ; X=c ; no

node(a). node(b). node(c). node(d). node(e). arc(a,b). ( , ) arc(a,c). arc(b,c). arc(b d) arc(b,d). arc(c,d). arc(d,e).

Složené dotazy Seznam ffaktů S k ů je j vlastně l ě jednoduchá j d d há databáze. d bá Je možné zodpovědět otázku, jejíž odpověď není přímo uložena v databázi faktů, faktů ale kterou lze získat kombinací faktů? Ano je možné klást dotaz o kombinaci faktů z báze Ano, znalostí:


Syntaktická pauza

atom tomy y vs. p proměnné

Atomy slova

skládající se z písmen, čísel a podtržítek, která j malým ý písmenem p začínají

a, arc, john_123, …

slova v jednoduchých ´Edinburgh´, ´ ´ …

uvozovkách

slova

skládající se z písmen, čísel a podtržítek, která začínají velkým písmenem nebo podtržítkem

_

X Node X, Node, _noname, noname …

je tzv. anonymní proměnná

složené termy y

Složené termy vyjadřují strukturovanou informaci atomy y

ap proměnné jjsou jednoduché j termyy functor(arg1,…,argn) je složený term, kde functor jje atom a arg1, g , …,, argn g jjsou termyy arc(a,c) path(a,path(b,path(d,e))) tree(tree(a,tree(b,c)),tree(d,e)) arc(a,X) …

Proměnné

arc(a,b). ( , ) arc(a,c). arc(b,c). arc(b,d). arc(c,d). arc(d,e).


Syntatická pauza Data (a programy) jsou vyjádřeny formou termů.

node(a). node(b) node(b). node(c). node(d). node(e) node(e).

arc(a Y) arc(Y Z) ?-arc(a,Y),arc(Y,Z). ? Y=b Z=c ; variables be Proměnné jecan možné shared between sdílet mezi přímými Y=b simple open queries dotazy Z=d Z d ; Y=c Z=d ; no

různé výskyty _ jsou brány jako různé proměnné obsah proměnné není uživateli přístupný Programování s omezujícími podmínkami, Roman Barták

path a

•

• •

path b

•

path d

•

• e


Odvozovací pravidla

dotaz můžeme pojmenovat a uložit pro opakované použití

Jak to funguje? funguje? najdi

pravidlo, jehož název odpovídá dotazu a příslušným způsobem navaž proměnné

doubleArc(X Z):-arc(X doubleArc(X,Z): arc(X,Y),arc(Y,Z). Y) arc(Y Z) Takovému

dotazu se říká odvozovací pravidlo.

Po formulaci pravidla na něj můžeme klást dotazy stejně jako na fakta:

node(a). ( ) node(b). node(c). node(d). node(e). d ( )

?-doubleArc(b,W). W=d ; pouze proměnné z W=e ; názvu pravidla jsou vráceny uživateli no ?-doubleArc(a,W). ( , ) W=c ; W=d ; W=d ; no

arc(a,b). , arc(a,c). arc(b,c). arc(b,d). arc(c,d). arc(d e) arc(d,e).

doubleArc(b,W):-arc(b,Y),arc(Y,W). nahraď

dotaz definicí p pod-dotazu z p pravidla

?-arc(b,Y),arc(Y,W). najdi j

odpovídající p j fakt ((arc(b,c)), ( , )), dosaď p proměnné a odstraň z dotazu node(a).

opakuj

to samé se zbytkem (arc(c,d))

W=d ; zkus

alternativní fakta (arc(b,d),arc(d,e))

W=e ; no

edge(X,Y):-arc(X,Y). edge(X,Y):-arc(Y,X).

arc(a,b). arc(a,c). arc(b,c). arc(b,d). arc(c,d). arc(d,e).


Alternativní Alternativ ní pravidla Je možné také definovat alternativní pravidla (disjunkce dotazů)

node(b). node(c). node(d). node(e).

?-arc(c,W).


odvozovací p pravidla

? d bl A (b W) ?-doubleArc(b,W).

Jak to funguje? funguje?

alternativ lternativní ní pravidla p

Stejně jako předtím, pouze se zkouší i alternativní pravidla. g ( , ) ?-edge(W,b).

Najdi pravidlo, jehož název odpovídá dotazu, navaž proměnné a nahraď dotazem definicí dotazu z pravidla edge(W b):-arc(W b) edge(W,b):-arc(W,b).

?-edge(W,b). odvozeno pomocí W W=a ; prvního pravidla W=c ; W=d ; odvozeno pomocí druhého pravidla no

node(a). node(b). node(c). node(d). node(e).

?-arc(W,b).

najdi j řešení dotazu p pomocí faktů

W=a ;

zkus alternativní pravidlo pro původní dotaz

node(a). node(b). node(c). node(d). node(e).

edge(W,b):-arc(b,W). d (W b) (b W) arc(a,b). arc(a,c). arc(b c) arc(b,c). arc(b,d). arc(c,d). arc(d e) arc(d,e).


?-arc(b,W).

najdi řešení dotazu pomocí faktů

W=c ; W=d ; no

arc(a,b). arc(a,c). arc(b c) arc(b,c). arc(b,d). arc(c,d). arc(d e) arc(d,e). Programování s omezujícími podmínkami, Roman Barták

Rek Re kurzivní urzivní pravidla

Je dokonce možné použít jméno pravidlo při ři definici d fi i i pod-dotazu, dd t tj tj. použít žít rekurzi k i path(X,Y):-arc(X,Y). path(X,Y):-arc(X,Z),path(Z,Y). ?-path(c,W). odvozeno prvním W d ; W=d pravidle a arc(c,d) W=e ; odvozeno druhým no

pravidlem a rekurzí

node(a). node(b). node(c). node(d). node(e). d ( ) arc(a,b). arc(a,c). arc(b,c). arc(b,d). arc(c,d). arc(d,e). (d )

Jak to funguje? funguje?

Stejně jako předtím, ale pravidlo může být použito vícekrát. vícekrát Každé užití pravidla y j čerstvou vyžaduje kopii proměnných (podobné jako volání procedury s lokálními proměnnými).

rekurzivní urzivní pravidla p

?-path(c,W) path(c,W):-arc(c,W).

?-arc(c,W)

Hlava jje (složený) ( ý) term Tělo je dotaz (konjunkce termů)

sémantika: p pokud jje Tělo p pravda p potom odvoď Hlavu

Tělo typicky obsahuje všechny proměnné z Hlavy

node(a). node(b). d (b) node(c). node(d). node(e).

?-arc(d,W)

Pro pravidla, kde Tělo=true, dotaz Q1 zmizí.

Opakuj dokud nezískáš prázdný dotaz. Opakuj, dotaz Programování s omezujícími podmínkami, Roman Barták

?-arc(d,Z2),path(Z2,W) arc(d,e).

arc(d,e).

W=e

?-path(e,W)

arc(a,b). arc(a,c). ( ) arc(b,c). arc(b,d). arc(c,d). arc(d,e). (d )

path(e,W):arc(e,Z3),path(Z3,W).

?-arc(e,W)

?-arc(e,Z3),path(Z3,W)

fail

fail

Technologie Prologu Prolog = Unifikace + Backtracking

Unifikace (matching) slouží pro výběr

vhodného pravidla (dle hlavy) vytvoření odpovědní substituce Jak?

Použij tělo pravidla, kterým v dotazu nahraď část Q1.

path(c,W):arc(c,Z2),path(Z2,W).


Dotaz je D j konjunkce k j k termů: ů Q = Q1,Q2,…,Qn. Q1 Q2 Q Najdi pravidlo, jehož hlava odpovídá dotazu Q1.

?-path(d,W)

path(d,W):-arc(d,W).

path(e,W):-arc(e,W).

Fakty jsou vlastně pravidla s prázdným tělem (true).

Pokud je takových pravidel více, více vytvoř „bod bod volby volby“ a použij první pravidlo. Pokud neexistuje žádné pravidlo, potom se vrať na poslední bod pravidlo. volbyy a zkus zde alternativní p

arc(c,d).

W=d

path(X,Y):-arc(X,Y). th(X Y) (X Y) path(X,Y):-arc(X,Z),path(Z,Y).

Prolog ve zkratce

?-arc(c,Z1),path(Z1,W)

arc(c,d).


Prologovský „program program“ se skládá z pravidel a faktů. faktů Každé pravidlo má strukturu Hlava:-Tělo.

path(c,W):-arc(c,Z1),path(Z1,W).

substitucí se snaží udělat termy syntakticky identické

Backtracking (prohledávání do hloubky) je pro prozkoumání

alternativ

Jak?

nejdříve j vyřeš y první p část (zleva) ( ) dotazu použij první pravidlo (shora) Programování s omezujícími podmínkami, Roman Barták

Využití principů, ale vlastní naprogramování řešících

Recommend Documents