Stromove CSP

Dotazy k přednášce

1. Vysvětlete algoritmus DAC.
2. Vysvětlete, jak funguje algoritmus DAC pro příklad z průsvitky 2.
3. Jak se liší směrová i-konzistence od k-konzistence?
4. Při řesení CSP problému můžeme postupně rozšiřovat částečné ohodnocení proměnných přidáváním ohodnocení jednotlivých proměnných z posloupnosti (x_1, x_2, ... x_n). Jaké má zpětné hrany proměnná x_i v této posloupnosti?
5. Dokážete vysvětlit souvislost mezi řešením CSP bez navracení, silnou směrovou i-konzistencí a počtem zpětných hran?
6. Co to je šířka vrcholu, šířka uspořádaného grafu a šířka grafu?
7. Jak spočítáte šířku grafu, ve kterém jsou tři proměnné a,b,c a hrany a=b a a=c?
8. Jak zkonstruujeme graf s minimální šířkou?
9. Proč má graf podmínek, který je stromem, šířku 1? Jak silnou směrovou i-konzistenci potřebujeme, aby měl stromový graf podmínek řešení bez navracení?
10. Jak spočítáte směrovou hranovou konzistenci pro stromový CSP?
11. Následující problém udělejte směrově hranově konzistentní
    • X1,X2,X3,X4 in 1..5,
    • X1=X2+1, X1<X3, X3<X4.
12. Jak silnou směrovou i-konzistenci potřebujeme, abychom dokázali vyřešit CSP problém bez navracení?
13. Jak funguje algoritmus adaptivní konzistence?
14. Je omezení A + B = C obecně hranově konzistentní, pokud jsou domény
    • A in {1,2}, B in {3,4,5}, C in {4,5,6,7} ?
    Změnilo by se něco, pokud by doména proměnné C byla {4,5,7} nebo {3,4,5,6,7}?
15. Jak se liší konzistence mezí od obecné hranové konzistence?
16. Jak bude aplikována konzistence mezí na příklad
    • A in {1,...,6,9,10}, B in {1,...,10},
    • A = B + 2 ?
    Co se stane, pokud následně přidáme omezení B>2?
17. Jaká jsou pravidla pro konzistenci mezí pro omezení A=<B?
18. Jaký je rozdíl mezi intervalovou podporou a doménovou podporou?