AC-3 algoritmus + oditerování
Z [L6.2] REVISE a redukce domén víš dvě věci: jedno volání REVISE opraví jednu orientovanou hranu, ale jeden průchod všemi hranami nestačí — pozdější škrt může zpětně rozbít hranu opravenou dřív. Také už víš, které hrany se zmenšením $D_i$ mohly rozbít: jen hrany $(x_k, x_i)$ vedoucí do $x_i$ — a ani protisměrka právě revidovaného omezení ne. Dnes z toho poskládáme algoritmus AC-3 — a hlavně se naučíš jeho běh oditerovat na papír přesně ve formátu, který chce zkouškové zadání: „Record the steps of the algorithm (the queue content prior to the revision of each arc).“
Fronta místo věčných průchodů
Zkus sám: v [L6.2] jsi po průchodu hranami musel ručně přemýšlet, „co se mohlo rozbít“, a projít to znovu. Jak by sis tu práci zorganizoval, aby se nedalo na nic zapomenout — a zároveň aby se zbytečně nekontrolovaly hrany, kterých se žádný škrt netkl?
Veď si seznam úkolů — frontu hran čekajících na revizi. Na začátku do ní dej všechny hrany (každá si zaslouží aspoň jednu kontrolu). Pak opakuj: vyber hranu z fronty, zavolej na ni REVISE — a jen pokud se něco smazalo, přidej do fronty hrany, kterým se to mohlo pokazit (dle [L6.2]: hrany do právě zmenšené domény, kromě protisměrky). Hrany, kterých se škrt netýká, do fronty nikdy nespadnou — žádné „perpetual checking“. Až je fronta prázdná, je vše AC. Přesně tohle je AC-3.
AC-3 Algorithm (slide 28, EN 1:1)“Maintain a queue of arcs to be revised (the arc is put in the queue only if it's consistency could have been affected by the reduction of the domain).”
procedure AC-3
Input: X, D, C and graph G.
Output: Binary variable fail indicating no solution in this part of the
state space. The set of the revised domains D.
fail = 0; Q := E(G); // initialize Q by arcs of G
while Q ≠ ∅ do
select and remove arc (x_k, x_m) from Q;
(deleted, D_k) = REVISE(D_k, D_m, C);
if deleted then
if D_k = ∅ then fail = 1 and EXIT;
else Q := Q ∪ {(x_i, x_k) such that (x_i, x_k) ∈ E(G) and i ≠ m};
end
end“The revision of $(x_k, x_m)$ does not change the arc consistency of $(x_m, x_k)$.”
Čtení po řádcích: fronta $Q$ startuje jako všechny orientované hrany grafu omezení (z [L6.1] CSP a arc consistency: jedno binární omezení = dvě orientované hrany). V každé otočce smyčky se z fronty vybere a odebere hrana $(x_k, x_m)$ a zavolá se na ni [L6.2] REVISE$(D_k, D_m, C)$ — reviduje se tedy doména počátku $D_k$. Zajímavé to je, jen když REVISE něco smazalo (deleted $= 1$):
Zkus sám: proč se do fronty vrací právě hrany $(x_i, x_k)$ — tedy hrany do počátku $x_k$ — a proč se vynechává ta s $i = m$? Obojí jsi vlastně odvodil už v [L6.2].
Zmenšila se $D_k$ — a ta je zásobárnou podpor právě pro hrany $(x_i, x_k)$, které do $x_k$ vedou; jen ty se škrtem mohly pokazit ([L6.2] takeaways). Hrana $(x_m, x_k)$ — protisměrka právě revidovaného omezení — se ale pokazit nemohla: smazaná hodnota $a \in D_k$ neměla v $D_m$ žádného partnera, takže nebyla podporou ničeho v $D_m$ (poslední věta slidu 28). Proto podmínka $i \ne m$. A pozor na zápis $Q := Q \cup \{\dots\}$ — fronta je množina: hrana, která už ve frontě čeká, se podruhé nepřidává.
Zkus sám: k čemu je řádek „if $D_k = \emptyset$ then fail = 1 and EXIT“? Co prázdná doména znamená pro celý CSP?
Když REVISE smaže z $D_k$ úplně všechno, nezbyla pro $x_k$ žádná přípustná hodnota — a protože mazání hodnot bez podpory je bezpečné (množinu řešení nemění, [L6.2]), znamená to, že CSP nemá žádné řešení. Formulace „no solution in this part of the state space“ míří na použití AC-3 uvnitř prohledávání (search): po každém zkusmém přiřazení se propaguje AC-3, a fail $= 1$ říká „tahle větev je mrtvá, vrať se“. Pro samostatnou zkouškovou úlohu prostě: prázdná doména = okamžitý konec, nekonzistentní zadání.
Oditerování: instance z přednášky (slide 29)
Slide 29 krokuje AC-3 na instanci: $x_1 \in \{1,2,3\}$, $x_2 \in \{1,2,3\}$, $x_3 \in \{1,2,3\}$, omezení $x_1 = x_2$, $x_2 + 1 = x_3$. Inicializace fronty (pořadí dle slidu): $Q = ((x_1, x_2), (x_2, x_1), (x_2, x_3), (x_3, x_2))$. Vzorce podpor si napiš předem: pro $x_1 = x_2$ je podpora $b = a$ (oba směry); pro hranu $(x_2, x_3)$ je podpora hodnoty $a \in D_2$ rovna $b = a + 1$, pro $(x_3, x_2)$ je to $b = a - 1$. Krokuj — a u každého snímku si nejdřív sám rozmysli, co REVISE udělá a co se stane s frontou:
Zkus sám (kontrola kroku 3): revize $(x_2, x_3)$ právě smazala $3$ z $D_2$. Které hrany se podle pseudokódu přidají do fronty? Vypiš si kandidáty $(x_i, x_2)$ a aplikuj podmínku $i \ne m$.
Do $x_2$ vedou hrany $(x_1, x_2)$ a $(x_3, x_2)$. Revidovaná hrana byla $(x_2, x_3)$, takže $m = 3$ — hrana $(x_3, x_2)$ se nepřidává (protisměrka, $i = m$; navíc už stejně ve frontě čeká). Přidá se jen $(x_1, x_2)$: $Q = ((x_3, x_2), (x_1, x_2))$. Přesně to je na slidu 29.
A teď zkouškové účetnictví. Zadání chce „the queue content prior to the revision of each arc“ — tabulka má tedy jeden řádek na každé volání REVISE a fronta se zapisuje před ním (běh 1:1 dle slidu 29, horní indexy $^{1)}$–$^{3)}$ číslují škrty):
| # | $Q$ před revizí | revise | smazáno | domény po revizi | do $Q$ přidat |
|---|---|---|---|---|---|
| 1 | $(x_1{,}x_2), (x_2{,}x_1), (x_2{,}x_3), (x_3{,}x_2)$ | $(x_1, x_2)$ | — | $D_1 = \{1,2,3\}$, $D_2 = \{1,2,3\}$, $D_3 = \{1,2,3\}$ | nic |
| 2 | $(x_2{,}x_1), (x_2{,}x_3), (x_3{,}x_2)$ | $(x_2, x_1)$ | — | beze změny | nic |
| 3 | $(x_2{,}x_3), (x_3{,}x_2)$ | $(x_2, x_3)$ | $3^{1)}$ z $D_2$ | $D_2 = \{1, 2\}$ | $(x_1, x_2)$ |
| 4 | $(x_3{,}x_2), (x_1{,}x_2)$ | $(x_3, x_2)$ | $1^{2)}$ z $D_3$ | $D_3 = \{2, 3\}$ | nic ($i \ne m$ nic nedá) |
| 5 | $(x_1{,}x_2)$ | $(x_1, x_2)$ | $3^{3)}$ z $D_1$ | $D_1 = \{1, 2\}$ | nic |
| — | $Q = \emptyset$ | konec: $D_1 = \{1, 2\}$, $D_2 = \{1, 2\}$, $D_3 = \{2, 3\}$, fail $= 0$ | |||
Zkus sám: výsledné domény mají $2 \times 2 \times 2 = 8$ kombinací. Kolik z nich jsou skutečná řešení CSP? Co to říká o tom, „co AC-3 vrací“?
Jen dvě: $(1, 1, 2)$ a $(2, 2, 3)$ — zkontroluj $x_1 = x_2$ a $x_3 = x_2 + 1$. AC-3 tedy nevrací řešení, vrací zmenšené domény, jejichž produkt je nadmnožinou množiny řešení ([L6.1] takeaways). U zkouškové instance níže vyjde shodou okolností v každé doméně jediná hodnota — ale ani tehdy nezapomeň, že to je vlastnost té instance, ne algoritmu.
Recept na papír (zkouškový formát)- Nakresli graf omezení (2 orientované hrany na omezení) a ke každé hraně si napiš vzorec podpory ($b$ jako funkci $a$).
- Zapiš inicializaci fronty = všechny hrany (drž kanonické pořadí ze zadání/slidu).
- Pro každé volání REVISE jeden řádek: fronta PŘED revizí → revidovaná hrana → smazané hodnoty → nové domény → co se do fronty přidává (a proč nic: „jediný soused je $x_m$“).
- Skonči řádkem $Q = \emptyset$ a výslednými doménami (případně
fail$= 1$, pokud se nějaká doména vyprázdnila).
Pozor: čtyři klasické chyby u oditerování AC-3- Zapomenuté znovuzařazení. Po každém škrtu se ptej: které hrany vedou do právě zmenšené domény? Bez vrácení $(x_1, x_2)$ do fronty by v příkladu výše zůstala hodnota $3 \in D_1$ neškrtnutá — a hrany by AC nebyly.
- Přidání protisměrky. Hrana $(x_m, x_k)$ se po revizi $(x_k, x_m)$ do fronty nevrací ($i \ne m$, slide 28) — její konzistence se škrtem v $D_k$ nezměnila. Přidáš-li ji, výsledek nezkazíš, ale děláš práci navíc a examinátor vidí, že pravidlu nerozumíš.
- Fronta zapsaná po revizi místo před ní. Zadání výslovně chce „prior to the revision“ — první řádek tedy obsahuje všechny 4 hrany, ne 3.
- Konec po projití všech hran místo po vyprázdnění fronty. AC-3 končí, až když $Q = \emptyset$ — znovuzařazené hrany (5. revize výše) jsou plnohodnotná část běhu, ne „bonus“.
AC není úplná technika
Poslední věc, kterou o AC potřebuješ vědět — slide 30 dává trojúhelníkovou instanci: $x_1 \in \{1, 2\}$, $x_2 \in \{1, 2\}$, $x_3 \in \{1, 2\}$, omezení $x_1 \ne x_2$, $x_1 \ne x_3$, $x_2 \ne x_3$.
Zkus sám: (i) spustil bys AC-3 — smazala by se nějaká hodnota? (ii) Najdi řešení tohohle CSP.
(i) Nic se nesmaže. Každá hrana je AC: pro $a = 1$ je podporou $b = 2$ a naopak (omezení je vždy jen $\ne$). AC-3 projde inicializační frontu bez jediného škrtu a skončí. (ii) Řešení neexistuje: tři proměnné, navzájem různé, ale jen dvě hodnoty — dvě proměnné se vždy potkají (holubník). Slide 30 (EN 1:1): “It is not feasible, but it is AC.”
Hranová konzistence tedy není úplná (complete): CSP může být plně AC, mít neprázdné domény — a přesto nemít žádné řešení. AC je jen propagace: bezpečně zmenší domény, ale globální rozhodnutí „má/nemá řešení“ obecně nedá; na to se musí nasadit silnější konzistence (slide 30 zmiňuje path consistency) nebo prohledávání. Pro zkoušku: po doběhnutí AC-3 netvrď, že zbylé kombinace jsou řešení — pokud to zadání chce, řešení ověř dosazením (jako jsme to udělali u obou instancí výše).
Key takeaways — L6.3- AC-3: $Q := E(G)$ (všechny orientované hrany); dokud $Q \ne \emptyset$: vyber a odeber $(x_k, x_m)$, zavolej REVISE$(D_k, D_m, C)$; pokud se mazalo a $D_k = \emptyset$ →
fail$= 1$, konec; jinak po mazání přidej $Q := Q \cup \{(x_i, x_k) \mid (x_i, x_k) \in E(G),\ i \ne m\}$. - Znovuzařazují se jen hrany do zmenšené domény (ta je zásobárnou jejich podpor), protisměrka revidované hrany ne ($i \ne m$); $Q$ je množina — duplicitně se nepřidává.
- Zkouškový zápis: jeden řádek na revizi — fronta před revizí, smazané hodnoty, nové domény, co se přidává. Konec až při $Q = \emptyset$ (nebo
failpři vyprázdnění domény). - AC není úplná technika: instance může být AC s neprázdnými doménami, a přesto nemít řešení (trojúhelník $\ne$ nad $\{1,2\}$, slide 30). AC-3 vrací zmenšené domény = nadmnožinu řešení, ne řešení samo.
FOTO checkpoint
zdroj: zkouška KO 2. 6. 2021 = banka #41 (zadání EN 1:1); táž úloha doložena na termínu 1. 6. 2026
“Let us consider the CSP problem given by:
- variables $X = \{x_1, x_2, x_3\}$,
- constraints $x_1 = x_2$, $x_2 = x_3 + 1$,
- domains $D_1 = \{1, 2\}$, $D_2 = \{1, 2\}$, $D_3 = \{1, 2\}$.
Reduce the domains to be arc consistent. Record the steps of the algorithm (the queue content prior to the revision of each arc).”
a) Co je v zadání?
Slot 6 v plné kráse — a celá kapitola K6 vedla sem. V [L6.1] T02 jsi instanci diagnostikoval (non-AC jsou $(x_2, x_3)$ a $(x_3, x_2)$), v [L6.2] T01 jsi domény zredukoval procedurou REVISE bez fronty. Teď konečně to, co zadání doopravdy chce: celý běh AC-3 se záznamem fronty před každou revizí.
b) Co k tomu budeme potřebovat?
- Tato lekce — pseudokód AC-3, pravidlo znovuzařazení, zkouškový formát zápisu.
- [L6.2] REVISE a redukce domén — mechanika škrtání (mění se jen počátek).
- [L6.1] CSP a arc consistency — graf omezení (1 omezení = 2 hrany), vzorce podpor.
c) Jak nad úlohou uvažovat?
Postupuj přesně dle receptu výše: graf, vzorce podpor ($x_1 = x_2$: $b = a$ oběma směry; $(x_2, x_3)$: $b = a - 1$; $(x_3, x_2)$: $b = a + 1$ — čti rovnici doslovně, $x_2 = x_3 + 1$!), inicializace $Q$ ve čtecím pořadí $(x_1, x_2), (x_2, x_1), (x_2, x_3), (x_3, x_2)$, pak řádek po řádku. U každého škrtu se hned ptej: které hrany vedou do zmenšené domény a kterou vylučuje $i \ne m$? Hodnoty škrtů už znáš z [L6.2] T01 — dnes je hlavní disciplína fronta.
d) Úplné řešení
Krokuj běh (snímky = stavy po jednotlivých revizích; fronta v popisku je vždy stav před revizí):
Záznam ve zkouškovém formátu (shoduje se se vzorovým průběhem banky #41):
| # | $Q$ před revizí | revise | smazáno | domény po revizi | do $Q$ přidat |
|---|---|---|---|---|---|
| 1 | $(x_1{,}x_2), (x_2{,}x_1), (x_2{,}x_3), (x_3{,}x_2)$ | $(x_1, x_2)$ | — | $D_1 = \{1,2\}$, $D_2 = \{1,2\}$, $D_3 = \{1,2\}$ | nic |
| 2 | $(x_2{,}x_1), (x_2{,}x_3), (x_3{,}x_2)$ | $(x_2, x_1)$ | — | beze změny | nic |
| 3 | $(x_2{,}x_3), (x_3{,}x_2)$ | $(x_2, x_3)$ | $1$ z $D_2$ | $D_2 = \{2\}$ | $(x_1, x_2)$ |
| 4 | $(x_3{,}x_2), (x_1{,}x_2)$ | $(x_3, x_2)$ | $2$ z $D_3$ | $D_3 = \{1\}$ | nic (jediný soused $x_3$ je $x_2 = x_m$) |
| 5 | $(x_1{,}x_2)$ | $(x_1, x_2)$ | $1$ z $D_1$ | $D_1 = \{2\}$ | nic (do $x_1$ vede jen $(x_2, x_1)$, $i = m$) |
| — | $Q = \emptyset$ | konec: $\boxed{D_1 = \{2\},\ D_2 = \{2\},\ D_3 = \{1\}}$, fail $= 0$ | |||
Detaily škrtů: krok 3 — $a{=}1 \in D_2$ potřebuje $b = 0 \notin D_3$ ✗; krok 4 — $a{=}2 \in D_3$ potřebuje $b = 3 \notin D_2 = \{2\}$ ✗ (pozor, už proti zmenšené $D_2$!); krok 5 — $a{=}1 \in D_1$ nemá podporu v $D_2 = \{2\}$ ✗.
Zbylé domény tu odpovídají jedinému přiřazení $x_1 = 2$, $x_2 = 2$, $x_3 = 1$ — a ověření dosazením ($2 = 2$ ✓, $2 = 1 + 1$ ✓) potvrzuje, že to je řešení. To je ale vlastnost téhle instance, ne algoritmu (AC není úplná — viz výklad).
Poznámka k dochovanému ručnímu řešení zkoušky: sken škrtá zrcadlové hodnoty (vyjde $x_1 = x_2 = 1$, $x_3 = 2$), což odpovídá čtení $x_3 = x_2 + 1$ — rozpor rozebraný v [L6.1] T02. Rozhodnutí pro celou K6: počítáme doslovně dle tištěného $x_2 = x_3 + 1$; stejně to čte i vzorový průběh banky #41, se kterým se náš výsledek shoduje 1:1. Metoda (fronta, znovuzařazení) je v obou čteních identická, jen se prohodí role hodnot $1$ a $2$.
FOTO checkpointTuhle úlohu vyřeš celou na papír (graf omezení + tabulka s frontou před každou revizí + výsledné domény) bez koukání do řešení — a pošli mi fotku, zkontroluju ti ji a vytknu chyby. Je to nejmechaničtějších 6 bodů zkoušky; jediné, co tě o ně může připravit, je nepořádek v účetnictví fronty.
“For a binary CSP, define arc consistency and describe the AC-3 algorithm. Use the following source definitions.”
a) Co je v zadání?
Teoretická otázka (banka ji vede jako studijní úlohu ze slidů; AC-3 je i v seznamu témat dobrovolné ústní). Žádné počítání — souvislý výklad: definice AC, procedura REVISE, algoritmus AC-3 a jeho vlastnosti.
b) Co k tomu budeme potřebovat?
- [L6.1] CSP a arc consistency — definice CSP, graf omezení, definice AC.
- [L6.2] REVISE a redukce domén — pseudokód REVISE.
- Tato lekce — pseudokód AC-3 + neúplnost AC.
c) Jak nad úlohou uvažovat?
Stavěj odpověď jako pyramidu: pojem (AC hrany → AC celého CSP) → lokální zákrok (REVISE) → globální organizace (fronta AC-3). Ke každému patru měj po ruce jednu pointu „proč“: proč je mazání bezpečné, proč se znovu zařazují právě hrany $(x_i, x_k)$, proč $i \ne m$. A na závěr limitu metody (neúplnost) — tou u ústní uděláš dojem.
d) Úplné řešení (vzorová osnova odpovědi)
- Binární CSP a graf: CSP $= (X, D, C)$, kde každé omezení váže dvě proměnné; reprezentace digrafem $G$ — uzly = proměnné, omezení nad $x_i, x_j$ dává obě orientované hrany $(x_i, x_j)$ a $(x_j, x_i)$ ([L6.1]).
- Definice AC (EN, slide 25): “Arc $(x_i, x_j)$ is arc consistent iff for each value $a \in D_i$ there exists $b \in D_j$ such that the assignment $x_i = a$, $x_j = b$ meets all binary constraints for the variables $x_i, x_j$.” CSP je AC ⟺ všechny hrany jsou AC. AC je orientovaná: AC hrany $(x_i, x_j)$ neimplikuje AC hrany $(x_j, x_i)$.
- REVISE$(D_i, D_j, C)$: smaže z $D_i$ každou hodnotu bez podpory v $D_j$ a vrátí příznak
deleted(pseudokód v [L6.2]). Mazání je bezpečné — hodnota bez podpory nemůže být v žádném řešení, množina řešení se nemění. - AC-3: pseudokód viz box ve výkladu výše (slide 28). Klíčové věty: fronta startuje všemi hranami $E(G)$; hrana se do fronty vrací, jen pokud její konzistenci mohl rozbít škrt — tedy hrany $(x_i, x_k)$ do zmenšené $D_k$, s výjimkou $i = m$, protože revize $(x_k, x_m)$ konzistenci $(x_m, x_k)$ nemění; vyprázdnění $D_k$ ⟹
fail$= 1$ (v této části stavového prostoru není řešení). Konec při $Q = \emptyset$ ⟹ všechny hrany AC. - Neúplnost: AC je jen propagace — instance může být AC, a přesto nepřípustná (trojúhelník $x_1 \ne x_2 \ne x_3 \ne x_1$ nad doménami $\{1, 2\}$, slide 30). Výstup AC-3 = zmenšené domény (nadmnožina řešení), ne rozhodnutí o řešitelnosti; proto se AC kombinuje s prohledáváním, případně silnější konzistencí (path consistency).
(Osnova odpovědi je vlastní kompilace; definice a pseudokódy jsou EN 1:1 ze slidů 25, 26, 28 a 30 — viz [L6.1], [L6.2] a výklad této lekce.)