Splňovanie obmedzujúcich podmienok: backtracking, propagácia obmedzení a AC-3 na sudoku a mape krajov

Premenné, domény a podmienky, graf podmienok, backtracking, heuristiky MRV a LCV, dopredná kontrola, AC-3 a min-conflicts — na farbení krajov Česka, sudoku a ôsmich dámach.

15 minút Matěj Žalmánek 2026-10-15

Séria Základy AI Diel 23 z 52

1. Mapa umelej inteligencie: čo je čo a ako to do seba zapadá
2. Stručná história umelej inteligencie: od Turinga po jazykové modely
3. Dáta, model, tréning, inferencia: základné pojmy na jednom príklade
4. Ako čítať matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relácie: stavebnica, z ktorej sa skladajú definície v AI
6. Funkcie a zobrazenia: prečo je každý model v AI funkcia
7. Logika a dôkazy: pravidlá, podľa ktorých sa v AI uvažuje
8. Grafy a stromy: štruktúra, na ktorej stojí hľadanie aj neurónové siete
9. Lineárna algebra pre strojové učenie: vektory, matice a prečo AI hlavne násobí
10. Derivácie, gradient a reťazové pravidlo: ako model zistí, ktorým smerom sa učiť
11. Gradientný zostup: ako sa model učí
12. Čo je pravdepodobnosť: od hodu kockou ku Kolmogorovovým axiómam
13. Podmienená pravdepodobnosť a Bayesova veta: ako zmeniť odhad, keď sa dozviete niečo nové
14. Náhodná premenná a distribučná funkcia: jedna funkcia, ktorá o rozdelení povie všetko
15. Funkcia hustoty a pravdepodobnostná funkcia: prečo má spojitá premenná v bode pravdepodobnosť nula
16. Stredná hodnota, rozptyl a kovariancia: kde rozdelenie leží, aké je široké a čo s čím súvisí
17. Prehľad pravdepodobnostných rozdelení: Bernoulliho, binomické, Poissonovo, rovnomerné, normálne a exponenciálne
18. Zákon veľkých čísel a centrálna limitná veta: prečo sa priemery správajú tak predvídateľne
19. Štatistika a odhady parametrov: maximálna vierohodnosť, MAP a intervaly spoľahlivosti
20. Teória informácie: entropia, krížová entropia a KL divergencia — odkiaľ sa berú stratové funkcie
21. Prehľadávanie stavového priestoru: BFS, DFS, UCS a A* s animáciami
22. Hry a protivník: minimax, alfa-beta orezávanie a Monte Carlo tree search
23. Splňovanie obmedzujúcich podmienok: backtracking, propagácia obmedzení a AC-3 na sudoku a mape krajov
24. Logika a znalostné systémy: dopredné a spätné reťazenie, rezolúcia a expertné systémy
25. Plánovanie: STRIPS, svet kociek, heuristiky z relaxácie a plánovanie v AI agentoch
26. Lokálne hľadanie a simulované žíhanie: obchodný cestujúci cez krajské mestá
27. Genetické algoritmy: populácia, kríženie, mutácia a výber na batohu na výlet
28. Evolučné stratégie a genetické programovanie: od pravidla jednej pätiny po Keplerov zákon
29. Optimalizácia mravčou kolóniou: ako feromónová stopa nájde krátku cestu
30. Optimalizácia rojom častíc: zotrvačnosť, vlastná skúsenosť a skúsenosť roja
31. Neuroevolúcia: evolúcia váh aj tvaru neurónových sietí a algoritmus NEAT
32. Fuzzy množiny a funkcie príslušnosti: ako zapísať „trochu teplo“
33. Fuzzy logika a pravdepodobnosť: prečo „trochu teplo“ neznamená „pravdepodobne teplo“
34. Fuzzy logika: t-normy, implikácie a pravidlá AK–TAK
35. Fuzzy riadenie: Mamdani a Sugeno od ventilátora po kyvadlo na vozíku
36. Fuzzy zhlukovanie: algoritmus fuzzy c-means a body medzi zhlukmi
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidlá, ktoré sa učia z dát
38. Markovove reťazce: prechodová matica, stacionárne rozdelenie a PageRank
39. Skryté Markovove modely: Viterbiho algoritmus a nepoctivé kasíno
40. Bayesovské siete: prečo je tráva mokrá a čo z toho vyplýva pre postrekovač
41. Kalmanov filter: ako z nepresných meraní odhadnúť, kde auto je a ako rýchlo ide
42. Druhy strojového učenia: s učiteľom, bez učiteľa, s čiastočným učiteľom a ďalšie
43. Prompty, kontext a RAG: ako modelu dať správne informácie
44. Variačné autoenkodéry (VAE): nové obrázky zo spojitého latentného priestoru
45. Generatívne adversariálne siete (GAN): falšovateľ proti detektívovi
46. Difúzne modely: ako sa z čistého šumu stane obrázok
47. Markovove rozhodovacie procesy: stavy, akcie, odmeny a Bellmanove rovnice
48. Q-learning a DQN: učenie hodnoty akcií od tabuľky po neurónovú sieť
49. Policy gradient a PPO: učenie priamo stratégie
50. Ako funguje AI agent: jazykový model v slučke s nástrojmi
51. Programovanie s AI agentmi: zadanie, testy a kontrola
52. Vyhodnocovanie a bezpečnosť AI systémov: ako merať a ako strážiť

Celá osnova série Hotovo: 52 z 83 tém

Rozvrh hodín, v ktorom žiadny učiteľ neučí dve triedy naraz. Sudoku. Rozmiestnenie súčiastok na doske, zmeny v nemocnici, pridelenie lietadiel k bránam. Všetky tieto úlohy majú spoločné to, že nehľadáme cestu, ale priradenie: každej premennej dať hodnotu tak, aby platili všetky pravidlá naraz. Takej úlohe sa hovorí úloha s obmedzujúcimi podmienkami a na rozdiel od všeobecného prehľadávania má jednu veľkú výhodu — pravidlá sú vidieť, takže z nich algoritmus môže usudzovať, nie len skúšať.

Nadväzuje na diely Prehľadávanie stavového priestoru a Grafy a stromy.

1. Čo je úloha s obmedzujúcimi podmienkami

Definícia — CSP

Nech n ∈ ℕ, n ≥ 1. Úloha s obmedzujúcimi podmienkami (constraint satisfaction problem, CSP) je trojica (X, D, C), kde

1. X = {X₁, …, X_n} je množina n rôznych premenných;
2. D = (D₁, …, D_n), kde pre každé i = 1, …, n je D_i neprázdna množina — doména premennej X_i, t. j. množina hodnôt, ktoré smie X_i nadobúdať (v tomto diele sú všetky domény konečné);
3. C je konečná množina podmienok. Každá podmienka je dvojica (S, R), kde rozsah S = (X_i1, …, X_ir) je r-tica navzájom rôznych premenných z X (r ≥ 1) a relácia R ⊆ D_i1 × … × D_ir je množina povolených kombinácií ich hodnôt.

Číslo r je arita podmienky. Podmienka s r = 2 je binárna, napríklad podmienka X₁ ≠ X₂ je dvojica ((X₁, X₂), {(x, y) ∈ D₁ × D₂ : x ≠ y}). CSP je binárny práve vtedy, keď sú všetky jeho podmienky binárne. Rozsah S budeme podľa potreby chápať aj ako množinu svojich premenných (S ⊆ X).

Slovami: CSP tvorí konečne veľa premenných, ku každej množina prípustných hodnôt a zoznam pravidiel, z ktorých každé vymenúva povolené kombinácie hodnôt niekoľkých premenných.

Definícia — priradenie a riešenie

Nech (X, D, C) je CSP. Priradenie je funkcia a : dom(a) → D₁ ∪ … ∪ D_n, kde dom(a) ⊆ X, taká, že

a(X_i) ∈ D_i pre každé X_i ∈ dom(a).

Pre podmienku (S, R) ∈ C s rozsahom S = (X_i1, …, X_ir) ⊆ dom(a) označme a|_S = (a(X_i1), …, a(X_ir)) hodnoty premenných rozsahu. Priradenie a je

1. konzistentné práve vtedy, keď pre každú podmienku (S, R) ∈ C s S ⊆ dom(a) platí a|_S ∈ R;
2. úplné práve vtedy, keď dom(a) = X.

Riešenie CSP je priradenie, ktoré je úplné a konzistentné. Slovami: riešenie dá hodnotu každej premennej a neporuší žiadnu podmienku; konzistentné priradenie neporuší žiadnu podmienku, ktorej premenné už všetky majú hodnotu.

Priradenie a je teda funkcia z množiny premenných dom(a) ⊆ X do ich domén. Podmienku konzistencie z definície možno zapísať jediným výrazom:

a je konzistentné ⇔ ∀(S, R) ∈ C : S ⊆ dom(a) ⇒ a|_S ∈ R

∀(S, R) ∈ C

prejdeme každú podmienku — rozsah S a reláciu R; stačí jediná porušená a priradenie je zlé

S ⊆ dom(a)

posudzujeme len podmienky, ktorých premenné už všetky majú hodnotu; o podmienke s voľnou premennou zatiaľ rozhodnúť nemožno, a preto ju rozpracované priradenie nemôže porušiť

a|_S ∈ R

hodnoty premenných z rozsahu (zúženie a na S) musia tvoriť kombináciu, ktorú relácia povoľuje

Príklad — farbenie krajov ako CSP

X = {KVK, ULK, …, MSK} je 14 krajov, každý má doménu D_i = {1, 2, 3, 4} (čísla farieb) a C obsahuje pre každú z 26 spoločných hraníc jednu podmienku ((X_i, X_j), ≠), teda reláciu {(x, y) : x ≠ y} s dvanástimi povolenými dvojicami zo 16.

Úplných priradení je |D₁| · |D₂| · … · |D₁₄| = 4¹⁴ = 268 435 456. Hľadáme medzi nimi tie, ktoré splnia všetkých 26 podmienok.

Prečo to nechápať ako obyčajné prehľadávanie? Išlo by to — stav je rozpracované priradenie, akcia je „daj ďalšej premennej hodnotu“. Lenže prehľadávanie by sa na stav pozeralo ako na čiernu skrinku. CSP do skrinky vidí: vie, ktoré pravidlá platia a ktorých premenných sa týkajú. Na tom stoja všetky triky v tomto diele.

2. Graf podmienok: farbenie mapy krajov

Klasická úloha: zafarbiť mapu tak, aby žiadne dva susedné štáty nemali rovnakú farbu. Vezmeme štrnásť krajov Česka. Premenné sú kraje, doména je sada farieb a pre každú spoločnú hranicu je podmienka „rôzne farby“.

Definícia — graf podmienok

Nech (X, D, C) je binárny CSP s premennými X = {X₁, …, X_n}. Jeho graf podmienok je neorientovaný graf (Grafy a stromy) G = (V, E), kde

V = X,   E = {{X_i, X_j} : i ≠ j ∧ ∃R : ((X_i, X_j), R) ∈ C}.

Premenné X_i a X_j sú teda spojené hranou práve vtedy, keď existuje podmienka, ktorej rozsah tvoria práve tieto dve premenné (v ľubovoľnom poradí — preto stačí i, j prejsť oboma smermi). Susedov premennej X_i v tomto grafe značíme N(X_i) = {X_j : {X_i, X_j} ∈ E}.

So štyrmi farbami to ide hladko. S tromi to nejde vôbec — a graf ukáže prečo. Stredočeský kraj susedí s Prahou a so siedmimi krajmi, ktoré okolo neho tvoria uzavretý kruh. Kruh s nepárnym počtom vrcholov potrebuje sám osebe tri farby (dve by sa museli pravidelne striedať, a to pri nepárnom počte nevyjde). Stredočeský kraj susedí so všetkými siedmimi, takže naň štvrtá farba zostať musí:

Veta — tri farby na kraje nestačia

Nech G = (V, E) je konečný neorientovaný graf a k ∈ ℕ, k ≥ 1. Zafarbenie grafu G k farbami je funkcia c : V → {1, …, k} taká, že

∀{u, v} ∈ E : c(u) ≠ c(v).

Chromatické číslo grafu G je

χ(G) = min {k ∈ ℕ, k ≥ 1 : existuje zafarbenie G k farbami},

teda najmenší počet farieb, ktorými sa dajú vrcholy zafarbiť tak, aby každé dva susedné vrcholy mali rôzne farby (pre konečný graf minimum existuje, |V| farieb stačí vždy).

Lema. Nech G = (V, E) je graf, m ≥ 3 nepárne a v₁, …, v_m ∈ V vrcholy tvoriace cyklus, t. j. {v_i, v_i+1} ∈ E pre i = 1, …, m − 1 a {v_m, v₁} ∈ E. Potom neexistuje funkcia c : {v₁, …, v_m} → {1, 2}, ktorá by na týchto hranách dávala susedom rôzne farby. Dôkaz: s dvoma farbami sa pozdĺž cyklu farby musia striedať; ak má v₁ farbu 1, potom v_i má farbu 1 práve pre nepárne i. Potom má v_m (nepárne m) farbu 1 rovnako ako jeho sused v₁. Spor. ∎

Veta. Nech G je graf krajov: vrcholy sú kraje Česka (14 vrcholov) a {u, v} ∈ E práve vtedy, keď kraje u a v majú spoločnú hranicu. Potom χ(G) = 4. Dôkaz: zafarbenie štyrmi farbami existuje (obrázok vyššie), takže χ(G) ≤ 4. Nech by existovalo zafarbenie c tromi farbami. Prstenec 7 krajov okolo Stredočeského je cyklus nepárnej dĺžky, takže podľa lemy na ňom c nevystačí s menej než tromi farbami — použije všetky tri. Stredočeský kraj susedí s každým krajom prstenca, a c(STČ) sa preto líši od všetkých troch farieb, čo v {1, 2, 3} nejde. Spor, teda χ(G) ≥ 4. ∎

To, že štyri farby stačia na každú mapu, je slávna veta o štyroch farbách. Dokázali ju Appel a Haken v roku 1976 — ako prvú veľkú matematickú vetu s pomocou počítača, ktorý preveril takmer dvetisíc prípadov.

3. Backtracking

Definícia — backtracking

Backtracking je prehľadávanie do hĺbky, ktoré v každom kroku priradí hodnotu jednej ďalšej premennej. Pre priradenie a, premennú X_i ∉ dom(a) a hodnotu v ∈ D_i značíme a ∪ {X_i ↦ v} priradenie a rozšírené o hodnotu v premennej X_i.

Vstup: CSP (X, D, C) s konečnými doménami a konzistentné priradenie a (na začiatku prázdne, dom(a) = ∅).
Výstup: riešenie CSP, ktoré rozširuje a, alebo „neúspech“, ak také riešenie neexistuje.

Procedúra BT(a):

1. Ak je dom(a) = X, vráť a (úplné konzistentné priradenie je riešenie).
2. Vyber premennú X_i ∈ X ∖ dom(a).
3. Pre každú hodnotu v ∈ D_i (v pevnom poradí): ak je a ∪ {X_i ↦ v} konzistentné, zavolaj BT(a ∪ {X_i ↦ v}); ak toto volanie vráti riešenie, vráť ho. Nekonzistentnú hodnotu vôbec neskúšaj.
4. Ak k riešeniu neviedla žiadna hodnota, vráť „neúspech“ — volajúci sa tým vráti k predchádzajúcej premennej a skúsi jej ďalšiu hodnotu.

Zastavenie: každé vnorené volanie má o jednu priradenú premennú viac, takže hĺbka rekurzie je najviac n = |X|, a každé volanie skúsi najviac |D_i| hodnôt. Strom volaní je preto konečný a algoritmus vždy skončí.

Nech d = max_i |D_i|. V najhoršom prípade prejde backtracking O(dⁿ) priradení. Všeobecný CSP je NP-ťažký, takže v najhoršom prípade lepšie nevieme.

def backtracking(prirazeni, csp):
    if len(prirazeni) == len(csp.promenne):
        return prirazeni                      # všetko má hodnotu: riešenie
    p = vyber_promennou(prirazeni, csp)
    for h in csp.domena[p]:
        if konzistentni(p, h, prirazeni, csp):
            prirazeni[p] = h
            vysledek = backtracking(prirazeni, csp)
            if vysledek:
                return vysledek
            del prirazeni[p]                  # slepá ulička: vráť sa
    return None

Prečo „jedna premenná na poschodie“ robí obrovský rozdiel? Všeobecné prehľadávanie by v každom stave ponúkalo všetky dvojice (nepriradená premenná, hodnota). To isté úplné priradenie by sa potom dalo poskladať vo všetkých možných poradiach a strom by mal

n! · dⁿ listov namiesto dⁿ

n!

počet poradí, v ktorých možno n premenných priradiť; od poradia výsledok nezávisí (priradenie je množina dvojíc), takže všetky okrem jedného sú zbytočné kópie tej istej práce — backtracking ich zahodí tým, že na každom poschodí rozhoduje o jedinej premennej

dⁿ

počet rôznych úplných priradení: každá z n premenných nezávisle jednu z d hodnôt; toľko listov zostane, aj keby backtracking nič neorezával

Na krajoch so štyrmi farbami urobí backtracking 14 priradení, jedno na kraj, a ani raz sa nevracia. S tromi farbami musí dokázať, že riešenie neexistuje — a to znamená vyskúšať všetko: 93 priradení, kým to vzdá. Začiatok jeho behu (odsadenie je hĺbka v strome, farby sú čísla 1–3, ✗ znamená, že pre kraj nezostala žiadna farba):

KVK = 1
  ULK = 2
    PLK = 3
      PHA = 1
        STČ ✗
      PHA = 2
        STČ = 1
          LBK = 3
            JHČ = 2
              HKK = 2
                VYS = 3
                  PAK ✗
      PHA = 3
        STČ = 1
…

Hneď prvá slepá ulička je poučná: Stredočeskému kraju vzali všetky tri farby Ústecký, Plzenský kraj a Praha. Backtracking sa však vracia len k poslednej premennej — k Prahe — a prefarbuje ju, hoci skutočný problém je v nepárnom prstenci. Praha sa tak v behu prefarbuje znova a znova. Tomuto bezradnému prešľapovaniu sa hovorí thrashing a múdrejšia voľba premenných ho výrazne obmedzí.

4. Ktorú premennú a ktorú hodnotu

Kostra backtrackingu necháva otvorené dve otázky: ktorú premennú vziať ako ďalšiu a v akom poradí skúšať jej hodnoty. Na odpovediach záleží viac, než by sa zdalo.

Definícia — MRV, stupeň, LCV

Nech (X, D, C) je binárny CSP s grafom podmienok G a susedmi N(·), a je konzistentné priradenie a U = X ∖ dom(a) ≠ ∅ množina nepriradených premenných. Pre X_i ∈ U označme zvyšné hodnoty

D′_i = {v ∈ D_i : a ∪ {X_i ↦ v} je konzistentné}.

1. MRV (minimum remaining values) vyberie ako ďalšiu premennú niektorú z M = {X_i ∈ U : |D′_i| = min_{Xk ∈ U} |D′_k|}, t. j. premennú s najmenším počtom hodnôt, ktoré ešte nie sú v konflikte s priradením.
2. Stupňová heuristika rozhodne zhodu: z M vyberie premennú X_i s najväčším |N(X_i) ∩ U|, t. j. s najviac podmienkami s doteraz nepriradenými premennými.
3. LCV (least constraining value): pre vybranú X_i a v ∈ D′_i a každé X_j ∈ N(X_i) ∩ U označme D″_j(v) = {w ∈ D′_j : a ∪ {X_i ↦ v, X_j ↦ w} je konzistentné} a strata(v) = ∑_{Xj ∈ N(Xi) ∩ U} |D′_j ∖ D″_j(v)|. LCV skúša hodnoty v ∈ D′_i vzostupne podľa straty(v).

Slovami: MRV berie premennú, ktorej zostáva najmenej možností, stupňová heuristika pri zhode tú, ktorá najviac obmedzuje ostatné, a LCV skúša najprv hodnotu, ktorá susedom vyškrtne najmenej možností. Pri podmienke ≠ je D′_j ∖ D″_j(v) = {v} ∩ D′_j, takže strata je jednoducho počet nepriradených susedov, ktorým v ešte zostáva.

Pri troch farbách na krajoch zníži MRV spolu s doprednou kontrolou z ďalšej kapitoly počet priradení z 93 na 45 — začne pri kraji, ktorému zostáva najmenej farieb, a spor nájde dvakrát rýchlejšie.

Na prázdnej mape majú všetky kraje po tri farby a MRV nerozhodne. Stupňová heuristika by potom vzala Stredočeský kraj, ktorý má 8 susedov — najviac zo všetkých; jeho farba hneď obmedzí osem ďalších krajov. Naša implementácia pri zhode berie jednoducho prvý kraj v poradí od západu, teda Karlovarský.

5. Dopredná kontrola

Definícia — dopredná kontrola

Nech (X, D, C) je binárny CSP, v ktorom každé dve premenné spája najviac jedna podmienka (viac podmienok medzi tou istou dvojicou možno nahradiť jednou s prienikom relácií). Pre podmienku ((X_i, X_j), R) ∈ C značíme R_ij = R a R_ji = {(y, x) : (x, y) ∈ R}.

Nech a je konzistentné priradenie, D₁, …, D_n aktuálne (prípadne už zúžené) domény, X_i ∉ dom(a) a v ∈ D_i. Dopredná kontrola po priradení X_i ↦ v nastaví D_i ← {v} a pre každú premennú X_j ∈ N(X_i) ∖ dom(a)

D_j ← {w ∈ D_j : (v, w) ∈ R_ij};

ostatné domény nemení. Ak je po zúžení D_j = ∅ pre niektoré j, priradenie X_i ↦ v sa okamžite odvolá — nemožno ho rozšíriť na riešenie, pretože X_j by nemala žiadnu prípustnú hodnotu.

Slovami: po každom priradení sa zo všetkých nepriradených susedov vyškrtnú hodnoty, ktoré s priradenou hodnotou nie sú zlučiteľné, a prázdna doména znamená okamžitý návrat.

def dopredna(csp, domeny, prirazeni, p, h):
    nove = dict(domeny)
    nove[p] = [h]
    for s in csp.sousede[p]:
        if s in prirazeni:
            continue
        nove[s] = [x for x in nove[s] if csp.povoleno(p, h, s, x)]
        if not nove[s]:
            return None                       # susedovi nič nezostalo: p = h odvolať
    return nove

Backtracking potom namiesto pôvodných domén odovzdáva do rekurzie zúžené nove a MRV už len porovnáva ich dĺžky. Takto vyzerá začiatok behu s doprednou kontrolou a MRV na krajoch s tromi farbami. V stĺpci vpravo sú nepriradené kraje s najmenšou doménou — z nich MRV vyberie ten prvý:

Po prvých troch krokoch zostala Stredočeskému kraju jediná farba, a tak príde na rad skôr než Praha. Každý ďalší vybraný kraj má už len jednu možnosť a v ôsmom kroku dopredná kontrola zistí, že Pardubickému kraju nezostalo nič — spor je odhalený bez toho, aby sa Pardubický kraj vôbec skúšal farbiť. Celý prstenec sa tak vynúti sám od seba; voľné rozhodnutie padlo len pri prvých dvoch krajoch.

Rozdiel je vidieť na sudoku nižšie. Prostý backtracking políčok po riadkoch potrebuje vyše 14 miliónov priradení. S doprednou kontrolou ich je 11 400. A keď k nej pridáme MRV, klesne to na 81 — 30 zadaných čísel a 51 doplnených, bez jediného návratu.

6. Hranová konzistencia a AC-3

Dopredná kontrola sa pozerá len o krok ďalej: na susedov premennej, ktorú sme práve priradili. Ide to dôkladnejšie — vyškrtávať aj medzi premennými, ktoré ešte hodnotu nemajú.

Definícia — hranová konzistencia

Nech (X, D, C) je binárny CSP so značením R_ij z definície doprednej kontroly a nech X_i, X_j ∈ X sú premenné spojené podmienkou, t. j. {X_i, X_j} ∈ E. Premenná X_i je hranovo konzistentná vzhľadom na X_j práve vtedy, keď

∀x ∈ D_i ∃y ∈ D_j : (x, y) ∈ R_ij.

Usporiadaná dvojica (X_i, X_j) s {X_i, X_j} ∈ E sa nazýva orientovaná hrana; každá hrana grafu podmienok dáva dve. CSP je hranovo konzistentný práve vtedy, keď je X_i hranovo konzistentná vzhľadom na X_j pre každú orientovanú hranu (X_i, X_j). Slovami: každá hodnota v doméne každej premennej má pri každom susedovi aspoň jednu hodnotu, s ktorou podmienku splní.

Skonzistentniť jednu orientovanú hranu (operácia zuz v kóde nižšie) znamená ponechať len hodnoty s partnerom:

D_i ← { x ∈ D_i : ∃y ∈ D_j : (x, y) ∈ R_ij }

D_i ←

doménu prepisujeme na mieste; zmenšuje sa len doména X_i, hrana je orientovaná — opačný smer (X_j, X_i) je samostatná položka frontu

x ∈ D_i

každú hodnotu posudzujeme zvlášť; nič nové nepridávame, takže doména môže len ubúdať — preto AC-3 skončí

∃y ∈ D_j

stačí jeden partner v aktuálnej doméne suseda; pýtame sa, či x môže prežiť, nie ako

(x, y) ∈ R_ij

dvojica musí podmienku medzi X_i a X_j spĺňať — pri farbení mapy jednoducho x ≠ y

Algoritmus — AC-3

Vstup: binárny CSP (X, D, C) s konečnými doménami a grafom podmienok G = (X, E).
Výstup: „nepravda“, ak niektorá doména zostala prázdna (CSP potom nemá riešenie); inak „pravda“ a domény zúžené tak, že CSP je hranovo konzistentný a má rovnakú množinu riešení ako na vstupe.

1. Vlož do frontu Q všetky orientované hrany (X_i, X_j), {X_i, X_j} ∈ E.
2. Ak je Q prázdny, skonči s výsledkom „pravda“.
3. Vyber z Q hranu (X_i, X_j) a vykonaj D_i ← {x ∈ D_i : ∃y ∈ D_j : (x, y) ∈ R_ij} (rozbor vyššie).
4. Ak sa D_i zmenšila: ak je D_i = ∅, skonči s výsledkom „nepravda“; inak vlož do Q všetky hrany (X_k, X_i) pre X_k ∈ N(X_i), X_k ≠ X_j — ich hodnoty mohli práve prísť o partnera.
5. Pokračuj krokom 2.

Zastavenie: hrany sa do frontu vracajú len vtedy, keď niektorá doména ubudne; domény sú konečné a nikdy nerastú, takže po konečne mnohých krokoch je front prázdny.

Pre c binárnych podmienok a domény veľkosti najviac d trvá AC-3 O(c · d³).

from collections import deque

def ac3(csp):
    fronta = deque((xi, xj) for xi in csp.promenne for xj in csp.sousede[xi])
    while fronta:
        xi, xj = fronta.popleft()
        if zuz(csp, xi, xj):
            if not csp.domena[xi]:
                return False                  # prázdna doména: riešenie neexistuje
            for xk in csp.sousede[xi]:
                if xk != xj:
                    fronta.append((xk, xi))
    return True

def zuz(csp, xi, xj):
    puvodne = len(csp.domena[xi])
    csp.domena[xi] = [x for x in csp.domena[xi]
                      if any(csp.povoleno(xi, x, xj, y) for y in csp.domena[xj])]
    return len(csp.domena[xi]) < puvodne

AC-3 krok za krokom

Tri premenné X, Y, Z, každé dve musia byť rôzne, a domény D_X = {1}, D_Y = {1, 2}, D_Z = {1, 2, 3}. Front začína šiestimi orientovanými hranami; riadok tabuľky je jedno vybratie z frontu a jedno zúženie D_i ← podľa vzorca vyššie (stĺpec „doména po“ má farbu rovnakého člena):

V kroku 3 príde Y o jednotku, pretože jediný možný partner pri X je práve 1. Tým sa do frontu vráti hrana (Z, Y) — hodnota 2 v Z mala partnera práve v tej vyškrtnutej jednotke. Hodnotu 2 zo Z však škrtne už pôvodná hrana (Z, Y) v kroku 6; vrátená kópia v kroku 7 nič nenájde. (Náš front nie je množina, takže v ňom hrana môže byť dvakrát — na výsledku to nič nemení.) Po 9 krokoch je front prázdny a domény sú {1}, {2}, {3}: riešenie bez jediného pokusu.

O( 2c · d · d² ) = O(c · d³)

2c

každá binárna podmienka dáva dve orientované hrany, každú treba skontrolovať

d

koľkokrát najviac sa hrana (X_k, X_i) vráti do frontu: len keď D_i ubudne, a to sa stane najviac d-krát

d²

cena jednej kontroly hrany: pre každú z najviac d hodnôt x hľadáme partnera medzi najviac d hodnotami y

7. Sudoku: propagácia v praxi

Sudoku je CSP ako z učebnice: 81 premenných, domény {1, …, 9} a podmienka „rôzne hodnoty“ pre každú dvojicu políčok v rovnakom riadku, stĺpci alebo štvorci 3 × 3. Každé políčko tak má 20 susedov v grafe podmienok.

Príklad — sudoku v číslach

Susedia políčka: 8 ďalších v riadku + 8 v stĺpci + 4 políčka štvorca 3 × 3, ktoré neležia v jeho riadku ani stĺpci (zvyšné 4 sme už započítali) = 20.

Podmienky: 81 · 20 = 1620 orientovaných hrán, každá dvojica políčok je v tom dvakrát, takže binárnych podmienok je 1620/2 = 810.

Veľkosť domén na začiatku: 30 zadaných políčok s doménou {zadané číslo} a 51 prázdnych s deviatimi hodnotami: 30 · 1 + 51 · 9 = 489 hodnôt. Na konci má každé z 81 políčok jednu hodnotu, takže AC-3 vyškrtlo 489 − 81 = 408 hodnôt. Z frontu na to vybralo 9 372 hrán.

Hrubá sila: vyskúšať všetky doplnenia prázdnych políčok znamená 9⁵¹ ≈ 4,6 · 10⁴⁸ priradení (dⁿ s d = 9 a n = 51 prázdnych políčok; farba podľa vzorca v kapitole Backtracking). Backtracking ich vďaka kontrole konzistencie urobí „len“ štrnásť miliónov.

Spustime na zadaní s 30 číslami samotné AC-3, bez jediného priradenia naslepo. Vyškrtá 408 hodnôt — a každému z 51 prázdnych políčok zostane práve jedna. Sudoku je vyriešené čistou úvahou:

Pri ľahkých sudoku to tak chodí; pri ťažších propagácia niekde uviazne a nastúpi hľadanie — backtracking, ktorý po každom priradení znova pustí propagáciu. Táto kombinácia (udržiavanie hranovej konzistencie, MAC) je základ väčšiny skutočných riešičov. Pre porovnanie na rovnakom zadaní:

Od štrnástich miliónov k nule. Hrubá sila a múdra úvaha riešia rovnakú úlohu — len jedna z nich číta pravidlá.

8. Lokálne hľadanie: min-conflicts

Úplne iná stratégia: nestavať riešenie kúsok po kúsku, ale začať s úplným priradením, ktoré porušuje kopu podmienok, a postupne ho opravovať. Je to lokálne hľadanie z dielu o prehľadávaní, len účelová funkcia je počet porušených podmienok.

Algoritmus — min-conflicts

Vstup: CSP (X, D, C) s konečnými doménami a najväčší počet krokov k_max ∈ ℕ.
Výstup: riešenie CSP, alebo „neúspech“.

Pre úplné priradenie a, premennú X_i a hodnotu v ∈ D_i nech konflikty(X_i, v) je počet podmienok (S, R) ∈ C s X_i ∈ S, ktoré porušuje priradenie vzniknuté z a zmenou hodnoty X_i na v. Premenná X_i je v konflikte práve vtedy, keď konflikty(X_i, a(X_i)) > 0.

1. Zvoľ náhodné úplné priradenie a (a(X_i) ∈ D_i pre všetky i).
2. Opakuj najviac k_max-krát: ak je a konzistentné (žiadna premenná nie je v konflikte), vráť a. Inak vyber náhodne premennú X_i v konflikte a nastav a(X_i) ← v, kde v ∈ D_i má najmenšie konflikty(X_i, v) (pri zhode náhodne) — teda hodnotu, s ktorou porušuje najmenej podmienok.
3. Po k_max krokoch bez riešenia vráť „neúspech“.

Zastavenie: najneskôr po k_max krokoch. Algoritmus nie je úplný: „neúspech“ neznamená, že riešenie neexistuje.

Klasická skúška je úloha n dám: rozostaviť n šachových dám na šachovnicu n × n tak, aby sa žiadne dve neohrozovali. Premenná je riadok dámy v každom stĺpci. Pre osem dám začal náš beh so šiestimi ohrozujúcimi sa dvojicami a skončil po 8 krokoch:

Čo presne algoritmus minimalizuje? Dáma v stĺpci i stojí v riadku r_i. Počet konfliktov, keby ju postavil do riadku v, je

konflikty(i, v) = ∑_{j ≠ i} [ r_j = v ∨ |r_j − v| = |j − i| ]

konflikty(i, v)

cena ťahu „dámu zo stĺpca i do riadku v“; min-conflicts vyberie v, pre ktoré je najmenšia

∑_{j ≠ i} [ … ]

sčítame cez všetky ostatné dámy; hranatá zátvorka je 1, keď podmienka platí, inak 0 — počítame porušené podmienky

r_j = v

dáma j stojí v rovnakom riadku; stĺpec zdieľať nemôže, to vylučuje už voľba premenných (jedna dáma na stĺpec)

|r_j − v| = |j − i|

dámy ležia na rovnakej uhlopriečke: posun v riadkoch sa rovná posunu v stĺpcoch

def min_conflicts(csp, kroku_max):
    a = nahodne_uplne_prirazeni(csp)
    for _ in range(kroku_max):
        v_konfliktu = [x for x in csp.promenne if konflikty(csp, a, x, a[x]) > 0]
        if not v_konfliktu:
            return a                          # nič nedrhne: riešenie
        x = random.choice(v_konfliktu)
        ceny = {v: konflikty(csp, a, x, v) for v in csp.domena[x]}
        nejmene = min(ceny.values())
        a[x] = random.choice([v for v in ceny if ceny[v] == nejmene])
    return None                               # došla trpezlivosť

Náš beh ťah po ťahu. Stĺpce aj riadky číslujeme 1–8 (riadok 1 hore); „ceny“ sú hodnoty konflikty(i, v) pre v = 1, …, 8 a tučne je najmenšia z nich (farbou zodpovedajú členu konflikty(i, v) vo vzorci vyššie). Na začiatku stáli dámy v riadkoch 5 1 6 2 5 1 1 8.

V kroku 6 si algoritmus z dvoch rovnako dobrých riadkov vylosoval ten, v ktorom dáma už stála — ťah nič nezmenil. V krokoch 4 až 7 je najmenšia cena 1, až v ôsmom sa vo vylosovanom stĺpci nájde riadok s nulou.

Všimnite si prostredné kroky: počet konfliktov sa štyri kroky drží na jednom — algoritmus presúva dámy „do strany“ po plošine, kým nenájde ťah, ktorý spor odstráni. Prekvapivé je, ako dobre to škáluje: milión dám vyrieši min-conflicts v priemere zhruba na päťdesiat krokov. Rovnakým postupom sa plánovali pozorovania Hubblovho vesmírneho ďalekohľadu (oboje opisujú Minton, Johnston, Philips a Laird, 1992).

9. Obmedzujúce podmienky v praxi

• Rozvrhy a plánovanie. Školské rozvrhy, zmeny, prideľovanie učební aj výrobné plány sa zadávajú ako premenné, domény a podmienky. Riešiče ako Google OR-Tools kombinujú propagáciu, hľadanie a lokálne vylepšovanie.
• SAT riešiče riešia CSP, kde je každá premenná pravda/nepravda. Overujú návrhy čipov, hľadajú chyby v softvéri a správcovia balíčkov (napríklad v Linuxe) nimi skladajú verzie knižníc, ktoré spolu fungujú.
• Prekladače prideľujú premenné programu do registrov procesora farbením grafu: dve premenné, ktoré žijú zároveň, nesmú zdieľať register — presne ako susedné kraje farbu.
• Konfigurátory v e-shopoch a výrobe strážia, aby vybrané súčiastky išli dokopy.
• AI agenti a jazykové modely v CSP často nevynikajú: na sudoku alebo rozvrh sa spoľahlivejšie hodí riešič. Dobrý agent preto úlohu nepremýšľa „z hlavy“ — preloží ju na premenné a podmienky a zavolá na ňu nástroj.

10. Zhrnutie

• CSP je trojica (X, D, C): premenné, domény a podmienky. Riešenie je úplné priradenie, ktoré neporušuje žiadnu podmienku.
• Backtracking priraďuje premenné jednu po druhej a vracia sa zo slepých uličiek; v najhoršom prípade je exponenciálny.
• Heuristiky MRV a LCV volia najťažšiu premennú a najvstretlivejšiu hodnotu; dopredná kontrola odhalí slepú uličku o krok skôr.
• AC-3 šíri škrtanie po grafe podmienok, kým každá hodnota nemá partnera; ľahké sudoku vyrieši úplne bez hľadania.
• Min-conflicts opravuje úplné priradenie a zvládne aj obrovské úlohy, ako je milión dám.

Chcete si to vyskúšať? Nechajte AI agenta napísať riešič sudoku s backtrackingom a potom doň pridávajte doprednú kontrolu, MRV a AC-3 — a počítajte, koľko priradení ubudne.

Máte na to iný názor? Napíšte na support@coden-app.com.