{{Predmet|Programování s omezujícími podmínkami|Roman Barták|OPT042}}
== Základní informace ==
Přednáška podává přehled o technikách programování s omezujícími podmínkami. Zaměřena je na algoritmy splňování podmínek a na problematiku řešení příliš omezených systémů podmínek. Zabývá se také praktickým využitím omezujících podmínek při řešení reálných problémů.
[[Wikipedia:Constraint satisfaction problem]]
== Podrobnosti ==
* CSP – problém popsaný pomocí (hyper)grafu; vrcholy = proměnné, hrany = podmínky
* binární CSP – všechny podmínky jsou binární
** unární se dají kódovat v doménách proměnných
** víc-ární se dají řešit prohozením podmínek a proměnných nebo přidáním skrytých proměnných
=== splňování podmínek prohledáváním ===
;systematické
* generuj a testuj – úplně tupé
* [[wen:backtracking|backtracking]]
** [[wen:backjumping|backjumping]] – skáče více dozadu na proměnné, které způsobily konflikt
** dynamický backtracking – přenáší důvod konfliktu, mění pořadí proměnných
** [[wen:backmarking|backmarking]] – testuje konzistenci je u podmínek, které se změnily, a pamatuje si nejvzdálenější úroveň konfliktu, čímž odstraňuje zbytečné testy
;nesystematické
*neúplná stromová prohledávání, nějak se omezují (cutoff) a když to nevyjde, omezí se méně (restart)
** bounded backtrack search (BBS) – omezen počet slepých uliček, když to nevyjde zkusí o jednu více
** iterative broadening (IB) – omezený počet alternativ k vyzkoušení v každém uzlu
** depth bounded search (DBS) – do dané hloubky projíždí všechno, pod tím už jen něco neúplného; v případě neúspěchu jde s úplností hlouběji
** credit search (CS) – daný kredit na větvení, když dojdou ve větvi peníze jde vždy jen jednou cestou
* s heuristikami; diskrepance = porušení heuristiky
** limited discrepancy search (LDS) – daný maximální počet diskrepancí v každé cestě
** improved limited discrepancy search (ILDS) – daný přesný počet diskrepancí, takže se při restartu nemusí procházet už prolezlé
** depth-bounded discrepancy search (DDS) – diskrepance povoleny jen do dané hloubky (v níž je diskrepance povinná – tak se nebudou opakovat slepé uličky z přechozí iterace – ta tam šla podle heuristiky)
;lokální
* hill climbing (HC) – začne na náhodném místě a v každém kroku udělá nejlepší možnou změnu jedné proměnné, když už to nejde zase skočí na náhodné místo, aby se vyhnul lokálnímu optimu
* minimalizace konfliktů (MC) – v každém kroku vezme konfliktní proměnou a minimalizuje u ní počet konfliktů; neumí vyskočit z lokálního optima
* náhodná procházka – v každém kroku hodím kostkou a buď jdu podle nějakého normálního algoritmu, nebo náhodně
** tabu seznam – brání trčení v lokálních optimech a cyklům (do urité délky) obecně
* GSAT – řeší SAT náhodným ohodnocením a postupným překlápěním těch proměnných, kde mu to nejvíc pomůže (heuristiky: random walk, zvyšování váhy těch co jsou dlouho nesplněné, průměrování dosavadních řešení)
* GENET – neuronová síť, neurony se navzájem potlačují tam kde by spolu neměly být aktivní; dobře je to vysvětleno v asi původním článku, viz. [http://sherry.ifi.unizh.ch/tsang92generic.html A Generic Neural Network Approach For Constraint Satisfaction Problems]
* simulované žíhání – na začátku jsme teplí a hodnoty náhodně skáčou, s klesající teplotou pak i jednotlivých hopsajícím proměnným klesá ochota přejít do horšího ohodnocení a celé se to stabilizuje
=== konzistenční techniky ===
== Zkoušky ==
=== 17.5.2006 ===
Zkouška probíhala ústně. Otázky byly zaměřeny zpravidla na popis různých algoritmů. Jedna otázka zahrnovala přibližně obsah jedné přednášky
Otázky:
*Backtracking, backjumping a spol.
*Konzistenční techniky - hranová k., k. po cestě a další
*Prohledávání s heuristikami
*Lokální prohledávání
*pak ještě jedna, ale tu jsem nezaslechl :)
== Odkazy ==
*Propracované [http://kti.ms.mff.cuni.cz/~bartak/podminky/prednaska.html slajdy z přednášky] (na homepage přednášky).
*[http://kti.ms.mff.cuni.cz/~bartak/constraints/ ON-LINE GUIDE TO CONSTRAINT PROGRAMMING] od Dr. Bartáka
[[category:Informatika]]
