L6.2 Kapitola K6 — CSP / Arc Consistency (Slot 6) · [MUST]

REVISE a redukce domén

Jedna nová věc Procedura REVISE: pro orientovanou hranu $(x_i, x_j)$ smaže z domény $D_i$ každou hodnotu, která nemá v $D_j$ podporu — a vrátí příznak deleted, jestli se vůbec něco mazalo.

V [L6.1] CSP a arc consistency umíš hranu diagnostikovat: $(x_i, x_j)$ je AC ⟺ každá hodnota $a \in D_i$ má v $D_j$ podporu. Zkouškové zadání ale neříká „rozhodni“, říká „reduce the domains to be arc consistent“ — chce zákrok, ne diagnózu. Dnes se naučíš ten zákrok pro jednu hranu; jak hrany správně řadit do fronty (celý AC-3) přijde v [L6.3].

Od diagnózy k zákroku

Zkus sám: v [L6.1] jsi u instance z přednášky ($D_2 = D_3 = \{1,2,3\}$, omezení $x_2 + 1 = x_3$) zjistil, že hrana $(x_2, x_3)$ není AC — hodnota $3 \in D_2$ nemá podporu. Co s tou hodnotou udělat, aby hrana AC byla? A smíš to udělat bezpečně — nepřijdeš o nějaké řešení CSP?

Smazat ji z $D_2$. Bezpečné to je: hodnota bez podpory nemůže být v žádném řešení (řešení musí splnit všechna omezení, tedy i pro $x_3$ by musel existovat partner — a ten neexistuje). Mazáním hodnot bez podpory se množina řešení nemění; zmenšuje se jen prostor, který bude muset prohledávat search. Přesně tohle dělá procedura REVISE — projde všechny hodnoty $a \in D_i$ a ty bez podpory škrtne.

REVISE Procedure (slide 26, EN 1:1)

“This procedure deletes every value $a$ from domain $D_i$, if the value is not consistent with domain $D_j$.”

procedure REVISE
Input:  Domain D_i to be revised. Domain D_j. Set of constraints C.
Output: Binary variable deleted indicating deletion of some value
        from D_i. Revised domain D_i.

deleted := 0;
for a ∈ D_i do
    if there is no b ∈ D_j ; x_i = a, x_j = b satisfies all x_i, x_j constraints
      then
        D_i := D_i \ a;          // delete a from D_i
        deleted := 1;
    end
end

Čtení po řádcích: REVISE dostane doménu počátku $D_i$ (tail — ta, která se bude revidovat), doménu konce $D_j$ (head — ta jen dodává podpory) a omezení. Projde každé $a \in D_i$; když pro něj neexistuje podpora $b \in D_j$ splňující všechna omezení dvojice $x_i, x_j$ najednou, hodnotu smaže a nastaví deleted := 1. Po doběhnutí je hrana $(x_i, x_j)$ zaručeně AC — a příznak deleted říká, jestli se doména vůbec změnila (k čemu je dobrý, uvidíš za chvíli). Jedno volání REVISE = oprava jedné orientované hrany; $D_j$ se nedotkne.

REVISE v akci: instance ze slidu 27

Vezmi instanci, kterou jsi v [L6.1] úloze T01 diagnostikoval: $x_1 \in \{1,2,3\}$, $x_2 \in \{1,2,3\}$, $x_3 \in \{2,3\}$, omezení $x_1 > x_2$, $x_2 \ne x_3$, $x_2 + x_3 > 4$. Tři hrany ze čtyř vyšly non-AC. Slide 27 teď hrany reviduje jednu po druhé v pořadí $(x_1, x_2), (x_2, x_1), (x_2, x_3), (x_3, x_2)$ — krokuj a u každého kroku si nejdřív sám rozmysli, co REVISE smaže:

Slide 27 si o průchodu vede účetnictví — tabulku revizí: kterou hranu revidujeme, co se smazalo, jak vypadá zmenšená doména a které hrany jsou po tomto kroku AC (tabulka 1:1 dle slidu, horní indexy $^{1)}$–$^{4)}$ číslují škrtnutí):

revised arcdeletedrevised domain$(x_1, x_2)$$(x_2, x_1)$$(x_2, x_3)$$(x_3, x_2)$
$(x_1, x_2)$$1^{1)}$$x_1 \in \{2, 3\}$ACnon-ACnon-ACAC
$(x_2, x_1)$$3^{2)}$$x_2 \in \{1, 2\}$ACACnon-ACnon-AC
$(x_2, x_3)$$1^{3)}$$x_2 \in \{2\}$non-ACACACnon-AC
$(x_3, x_2)$$2^{4)}$$x_3 \in \{3\}$non-ACACACAC
Zkus sám (než krokneš na 5. snímek): prošli jsme všechny čtyři hrany a každou jsme procedurou REVISE opravili. Jsou teď všechny hrany AC? Podívej se na poslední řádek tabulky.

Nejsou! Hrana $(x_1, x_2)$ — kterou jsme revidovali jako první a po revizi byla AC — je na konci průchodu zase non-AC. Mezitím se totiž doména $D_2$ zmenšila na $\{2\}$ a hodnota $2 \in D_1$ tím přišla o svou jedinou podporu ($b = 1$ už v $D_2$ není a $2 > 2$ neplatí). Oprava jedné hrany může rozbít hranu opravenou dříve.

Slide 27 (EN 1:1): “After revision, some of the arcs are still nonconsistent — the reason is that some of the domains have been reduced — continue in the revision until all the arc are consistent (but you have to do it without perpetual AC checking of all arcs — see AC-3 alg.).” Druhý průchod už je krátký:

revised arcdeletedrevised domain$(x_1, x_2)$$(x_2, x_1)$$(x_2, x_3)$$(x_3, x_2)$
$(x_1, x_2)$$2^{5)}$$x_1 \in \{3\}$ACACACAC

Výsledek: $D_1 = \{3\}$, $D_2 = \{2\}$, $D_3 = \{3\}$ — všechny hrany AC; tady dokonce zbylo jediné přiřazení $x_1 = 3$, $x_2 = 2$, $x_3 = 3$ (zkontroluj: $3 > 2$ ✓, $2 \ne 3$ ✓, $2 + 3 = 5 > 4$ ✓). Pozor ale, to je náhoda téhle instance — obecně AC dává jen zmenšené domény, ne řešení ([L6.1] takeaways: produkt domén je nadmnožina řešení).

Které hrany se mohly rozbít?

Opakovat slepě všechny průchody, dokud se nic nemaže, by fungovalo — ale je to plýtvání (slide tomu říká „perpetual AC checking“). Příznak deleted umožňuje chytřejší otázku:

Zkus sám: REVISE$(D_i, D_j)$ právě smazalo nějaké hodnoty z $D_i$. Kterým hranám grafu se tím mohla pokazit konzistence? Projdi si tři skupiny: hrany z $x_i$ ven, hrany do $x_i$, a hrany, kterých se $x_i$ vůbec netýká.

Hrany bez $x_i$ se nezměnily vůbec. Hrany ven z $x_i$, tj. $(x_i, x_k)$: jejich počátek se zmenšil — hodnoty, které zbyly, mají své podpory v $D_k$ pořád, takže AC se pokazit nemůže (ubyly jen „kontrolované“ hodnoty). Pokazit se mohly jen hrany do $x_i$, tj. $(x_k, x_i)$: doména $D_i$ je pro ně zásobárna podpor a ta se právě ztenčila — hodnota $c \in D_k$, jejíž jedinou podporou bylo smazané $a$, je teď bez podpory. Přesně to jsi viděl v příkladu: zmenšení $D_2$ rozbilo hranu $(x_1, x_2)$.

Jedna jemnost navíc (slide 28, EN 1:1): “The revision of $(x_k, x_m)$ does not change the arc consistency of $(x_m, x_k)$.” Proč? Hodnota $a$ smazaná z $D_k$ neměla v $D_m$ žádného partnera — takže nebyla podporou žádné hodnoty $b \in D_m$ a její zmizení hraně $(x_m, x_k)$ nic nevzalo. Protisměrnou hranu právě revidovaného omezení tedy znovu kontrolovat netřeba. Z těchhle dvou pozorování („po smazání z $D_i$ přezkoumej hrany do $x_i$“ + „protisměrku ne“) se v [L6.3] poskládá fronta algoritmu AC-3 — včetně přesného pravidla, které hrany do fronty vracet.

Pozor: tři klasické chyby u REVISE
Key takeaways — L6.2
T01 Zkoušková instance: průchod procedurou REVISE zdroj: zkouška KO 02.06.2021 = banka #41 (zadání 1:1); dnešní instrukce vlastní
Assignment (original, EN)

“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).”

Dnešní (vlastní) instrukce — záznam fronty si necháme do [L6.3], dnes proveď redukci ve stylu slidu 27: apply REVISE to the arcs in the order $(x_1, x_2), (x_2, x_1), (x_2, x_3), (x_3, x_2)$; for each call record the deleted value(s) and the revised domain. Then decide which arcs may have become inconsistent again, finish the revision, and state the final arc-consistent domains.

a) Co je v zadání?

Zkoušková instance Slotu 6 (v [L6.1] T02 už máš její graf a diagnózu: non-AC jsou $(x_2, x_3)$ a $(x_3, x_2)$). Dnes domény skutečně zredukovat: čtyři volání REVISE v pevném pořadí + dokončení druhým kolem tam, kde se něco rozbilo.

b) Co k tomu budeme potřebovat?

  • Tato lekce — procedura REVISE, „mění se jen počátek“, které hrany se mohly rozbít.
  • [L6.1] CSP a arc consistency — graf omezení, vzorce podpor pro $x_2 = x_3 + 1$.

c) Jak nad úlohou uvažovat?

U každého volání si nejdřív napiš vzorec podpory: pro $x_1 = x_2$ je to $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$. Pak mechanicky škrtej. Po průchodu se ptej: které domény se zmenšily a které hrany do nich vedou? Ty zkontroluj znovu.

d) Úplné řešení

Krokuj běh (snímky = stavy po jednotlivých voláních REVISE):

  1. REVISE$(D_1, D_2)$ pro $x_1 = x_2$: $a{=}1 \to b{=}1$ ✓, $a{=}2 \to b{=}2$ ✓ → nic se nemaže, deleted $= 0$.
  2. REVISE$(D_2, D_1)$: symetricky nic, deleted $= 0$.
  3. REVISE$(D_2, D_3)$ pro $x_2 = x_3 + 1$ (podpora $b = a - 1$): $a{=}1$ potřebuje $b = 0 \notin D_3$ ✗ smazat; $a{=}2 \to b{=}1$ ✓ → $D_2 = \{2\}$, deleted $= 1$.
  4. REVISE$(D_3, D_2)$ (podpora $b = a + 1$, už proti $D_2 = \{2\}$): $a{=}1 \to b{=}2$ ✓; $a{=}2$ potřebuje $b = 3 \notin D_2$ ✗ smazat → $D_3 = \{1\}$, deleted $= 1$.

Co se mohlo rozbít? Zmenšily se $D_2$ (krok 3) a $D_3$ (krok 4). Do $x_2$ vedou hrany $(x_1, x_2)$ a $(x_3, x_2)$ — druhá se revidovala až po zmenšení $D_2$, takže stačí znovu $(x_1, x_2)$. Do $x_3$ vede jen $(x_2, x_3)$, což je protisměrka hrany revidované v kroku 4 — dle slidu 28 se rozbít nemohla (a vskutku: $a{=}2 \to b{=}1 \in D_3$ ✓).

  1. REVISE$(D_1, D_2)$ podruhé ($D_2 = \{2\}$): $a{=}1$ bez podpory ✗ smazat; $a{=}2 \to b{=}2$ ✓ → $D_1 = \{2\}$, deleted $= 1$. Teď jsou všechny čtyři hrany AC.

Výsledek: $D_1 = \{2\}$, $D_2 = \{2\}$, $D_3 = \{1\}$ — odpovídá jedinému přiřazení $x_1 = 2$, $x_2 = 2$, $x_3 = 1$ (kontrola: $2 = 2$ ✓, $2 = 1 + 1$ ✓). Stejné domény dává i vzorový průběh AC-3 v bance #41 — v [L6.3] tenhle běh zopakuješ i se záznamem fronty před každou revizí, přesně jak chce zadání.

Poznámka: dochované ruční řešení zkoušky škrtá zrcadlové hodnoty (čte $x_3 = x_2 + 1$) — rozpor je rozebraný v [L6.1] T02; tady počítáme doslovně dle tištěného $x_2 = x_3 + 1$.

T02 Drill: záleží na pořadí revizí? instance: prezentace 08_CP_KO, slide 27 (1:1); obrácené pořadí a otázky vlastní
Assignment (EN; instance 1:1 ze slidu 27, pokyny vlastní)

“CSP with variables and domains: $x_1 \in \{1, 2, 3\},\ x_2 \in \{1, 2, 3\},\ x_3 \in \{2, 3\}$ and constraints $x_1 > x_2,\ x_2 \ne x_3,\ x_2 + x_3 > 4$.”

Apply REVISE to the arcs in the reversed order $(x_3, x_2), (x_2, x_3), (x_2, x_1), (x_1, x_2)$, then finish the revision wherever an arc may have become inconsistent again. Record the deleted values and the revised domains after each call. Do you obtain the same final domains as with the order used on slide 27?

a) Co je v zadání?

Stejná instance, jakou výklad propočítal v pořadí slidu 27 — teď hrany revidovat pozpátku. Otázka míří na to, co je na výsledku REVISE „náhoda pořadí“ a co ne.

b) Co k tomu budeme potřebovat?

  • Tato lekce — REVISE, podpora proti všem omezením najednou, které hrany rozbít šly.

c) Jak nad úlohou uvažovat?

Mechanika je stejná, jen jiné pořadí — pozor, že u dvojice $\{x_2, x_3\}$ musí podpora splnit obě omezení současně. Po průchodu zkontroluj hrany vedoucí do zmenšených domén. A než začneš počítat, tipni si: vyjde totéž?

d) Úplné řešení (vlastní — slide počítá jen původní pořadí)
  1. REVISE$(D_3, D_2)$: $a{=}2$: podpora $b \ne 2$, $b + 2 > 4$ → $b{=}3$ ✓; $a{=}3 \to b{=}2$ ✓ → nic, deleted $= 0$.
  2. REVISE$(D_2, D_3)$: $a{=}1$: $b{=}2$ dá součet $3$ ✗, $b{=}3$ dá $4 \not> 4$ ✗ → smazat; $a{=}2 \to b{=}3$ ✓; $a{=}3 \to b{=}2$ ✓ → $D_2 = \{2, 3\}$.
  3. REVISE$(D_2, D_1)$ pro $x_1 > x_2$ (podpora $b > a$): $a{=}2 \to b{=}3$ ✓; $a{=}3$ potřebuje $b > 3$ ✗ smazat → $D_2 = \{2\}$.
  4. REVISE$(D_1, D_2)$ (podpora $b < a$, $D_2 = \{2\}$): $a{=}1$ ✗ smazat, $a{=}2$ ✗ smazat (potřebuje $b < 2$), $a{=}3 \to b{=}2$ ✓ → $D_1 = \{3\}$ — jedno volání REVISE klidně smaže víc hodnot najednou.

Dokončení: zmenšily se $D_2$ (kroky 2, 3) a $D_1$ (krok 4). Do $x_1$ vede jen protisměrka $(x_2, x_1)$ → netřeba. Do $x_2$ vedou $(x_1, x_2)$ — revidována až po posledním zmenšení $D_2$ ✓ — a $(x_3, x_2)$, revidovaná ještě před škrty → znovu:

  1. REVISE$(D_3, D_2)$ podruhé ($D_2 = \{2\}$): $a{=}2$: jediný kandidát $b{=}2$ porušuje $x_2 \ne x_3$ ✗ smazat; $a{=}3 \to b{=}2$ ✓ ($5 > 4$) → $D_3 = \{3\}$. Do $x_3$ vede jen protisměrka $(x_2, x_3)$ → hotovo.

Výsledek: $D_1 = \{3\}$, $D_2 = \{2\}$, $D_3 = \{3\}$ — přesně totéž co v pořadí slidu 27, jen se hodnoty škrtaly v jiných krocích (a celkem to opět dalo 5 volání REVISE). Pořadí revizí mění průběh, ne výsledné domény — výsledné maximální arc-consistent domény jsou pro danou instanci jednoznačné (vlastní pozorování nad rámec slidů; u zkoušky se na pořadí fronty držte zadaného/kanonického pořadí, ať examinátor snadno kontroluje).

← Předchozí L6.1 · CSP a arc consistency