Čtení: 35 minHodnotí se: test 3 (opakování), zkouška

2 Splňování podmínek (CSP)

Po přečtení umíš

zapsat úlohu jako CSP
spočítat hranovou konzistenci
vybrat proměnnou a hodnotu pomocí heuristik
vysvětlit backjumping a nogoody

2.1 Ukázka: sudoku

Každé políčko je proměnná, doména je 1 až 9 a podmínky říkají, že se v řádku, sloupci a čtverci nic neopakuje. Zapíšeš jen co musí platit a řešič dělá zbytek. To je smysl CSP.

Definice 2.2 (CSP)

Trojice $(X, D, C)$ : konečná množina proměnných, jejich domény a podmínky, tedy povolené kombinace hodnot. Řešení přiřadí každé proměnné hodnotu tak, aby platily všechny podmínky.

2.2 Hledání

Chronologický backtracking přiřazuje proměnné a při nemožnosti se vrátí k poslední. Dopředná kontrola po přiřazení vyškrtne z domén sousedů, co už nejde. Pokud se doména vyprázdní, hned se vrací.

Definice 2.3 (Hranová konzistence)

Hrana $(x_1, x_2)$ je konzistentní, pokud každá hodnota v $D(x_1)$ má podporu v $D(x_2)$ . Hodnota bez podpory se smaže. Opakuje se, dokud se domény mění. Složitost je $O(|X|^2 |D|^3)$ .

Příklad 2.4 (Hranová konzistence)

$X, Y, Z \in \{1, 2, 3\}$ , podmínky $X < Y$ a $Y < Z$ . Spočítej domény po AC.

Řešení

$X < Y$ : $X$ nemůže být 3 a $Y$ nemůže být 1.
$Y < Z$ : $Y$ nemůže být 3 a $Z$ nemůže být 1. Teď $Y = \{2\}$ .
Znovu $X < Y$ : $X = \{1\}$ . Znovu $Y < Z$ : $Z = \{3\}$ .

Výsledek $X = 1$ , $Y = 2$ , $Z = 3$ . Změna domény vyvolala novou kontrolu sousedních hran.

Varování 2.5 (AC nerozhoduje vždy)

Konzistentní síť nemusí mít řešení. Tři proměnné se dvěma barvami a nerovnostmi jsou hranově konzistentní, ale obarvit nejdou.

2.3 Heuristiky

Proměnná: nejvíce omezená (nejmenší doména), při shodě nejčastěji zapojená. Těžká rozhodnutí neodkládej.
Hodnota: nejméně omezující, ať má zbytek co nejvíc možností.

Zapamatuj si: proměnná se vybírá tak, aby se selhalo brzy, hodnota tak, aby se uspělo.

2.4 Skoky a učení

Backjumping se nevrací k poslední proměnné, ale k té, která konflikt skutečně způsobila. Nogood je zapamatovaná nerozšiřitelná kombinace hodnot. To je předobraz učení klauzulí v CDCL.

GAC rozšiřuje konzistenci na nebinární podmínky. Pro all-different existuje rychlá filtrace. Symetrie se rozbíjejí přidanými podmínkami.

2.5 Kvíz

Kvíz

1. Kterou proměnnou zvolíš jako první podle nejvíce omezené? S doménou velikosti 5 S doménou velikosti 2 S nejdelším názvem

2. Co je výsledkem, když se doména při AC vyprázdní? Instance nemá řešení Řešení je nalezeno Pokračuje se bez změny

3. Co platí? Může být správně více možností, ale také žádná. AC je silnější než dopředná kontrola AC vždy najde řešení Nogood zabrání opakování stejné chyby Hodnotu volíme nejméně omezující

4. V čem se liší backjumping od backtrackingu?

Ukázat řešení

Backtracking se vrací k poslední proměnné. Backjumping přeskočí proměnné, které s konfliktem nesouvisí, a vrátí se k poslední z konfliktní množiny.

2.6 Příklady na procvičení

Cvičení 2.6

Zapiš obarvení mapy tří sousedících zemí třemi barvami jako CSP.

Řešení

$X = \{A, B, C\}$ , $D = \{R, G, B\}$ , podmínky $A \ne B$ , $B \ne C$ , $A \ne C$ .

2.7 Tahák

Tahák

CSP $(X, D, C)$ .
Filtrace: dopředná kontrola < hranová konzistence < GAC.
Proměnná s nejmenší doménou, hodnota nejméně omezující.
AC $O(|X|^2|D|^3)$ , nerozhoduje řešitelnost.
Backjumping = skok ke konfliktu, nogood = naučený zákaz.

Kapitolu mám prostudovanou