Splňování omezujících podmínek: backtracking, propagace omezení a AC-3 na sudoku a mapě krajů

Proměnné, domény a podmínky, graf podmínek, backtracking, heuristiky MRV a LCV, dopředná kontrola, AC-3 a min-conflicts — na barvení krajů Česka, sudoku a osmi dámách.

15 minut Matěj Žalmánek 2026-10-15

Série Základy AI Díl 23 z 83

1. Mapa umělé inteligence: co je co a jak to do sebe zapadá
2. Stručná historie umělé inteligence: od Turinga po jazykové modely
3. Data, model, trénink, inference: základní pojmy na jednom příkladu
4. Jak číst matematický zápis: symboly, indexy, sumy a kvantifikátory
5. Množiny a relace: stavebnice, ze které se skládají definice v AI
6. Funkce a zobrazení: proč je každý model v AI funkce
7. Logika a důkazy: pravidla, podle kterých se v AI uvažuje
8. Grafy a stromy: struktura, na které stojí hledání i neuronové sítě
9. Lineární algebra pro strojové učení: vektory, matice a proč AI hlavně násobí
10. Derivace, gradient a řetízkové pravidlo: jak model zjistí, kterým směrem se učit
11. Gradientní sestup: jak se model učí
12. Co je pravděpodobnost: od hodu kostkou ke Kolmogorovovým axiomům
13. Podmíněná pravděpodobnost a Bayesova věta: jak změnit odhad, když se dozvíte něco nového
14. Náhodná veličina a distribuční funkce: jedna funkce, která o rozdělení řekne všechno
15. Funkce hustoty a pravděpodobnostní funkce: proč má spojitá veličina v bodě pravděpodobnost nula
16. Střední hodnota, rozptyl a kovariance: kde rozdělení leží, jak je široké a co s čím souvisí
17. Přehled pravděpodobnostních rozdělení: Bernoulli, binomické, Poisson, rovnoměrné, normální a exponenciální
18. Zákon velkých čísel a centrální limitní věta: proč se průměry chovají tak předvídatelně
19. Statistika a odhady parametrů: maximální věrohodnost, MAP a intervaly spolehlivosti
20. Teorie informace: entropie, křížová entropie a KL divergence — odkud se berou ztrátové funkce
21. Prohledávání stavového prostoru: BFS, DFS, UCS a A* s animacemi
22. Hry a protivník: minimax, alfa-beta ořezávání a Monte Carlo tree search
23. Splňování omezujících podmínek: backtracking, propagace omezení a AC-3 na sudoku a mapě krajů
24. Logika a znalostní systémy: dopředné a zpětné řetězení, rezoluce a expertní systémy
25. Plánování: STRIPS, svět kostek, heuristiky z relaxace a plánování v AI agentech
26. Lokální hledání a simulované žíhání: obchodní cestující přes krajská města
27. Genetické algoritmy: populace, křížení, mutace a výběr na batohu na výlet
28. Evoluční strategie a genetické programování: od pravidla jedné pětiny po Keplerův zákon
29. Optimalizace mravenčí kolonií: jak feromonová stopa najde krátkou cestu
30. Optimalizace hejnem částic: setrvačnost, vlastní zkušenost a zkušenost hejna
31. Neuroevoluce: evoluce vah i tvaru neuronových sítí a algoritmus NEAT
32. Fuzzy množiny a funkce příslušnosti: jak zapsat „trochu teplo“
33. Fuzzy logika a pravděpodobnost: proč „trochu teplo“ neznamená „pravděpodobně teplo“
34. Fuzzy logika: t-normy, implikace a pravidla KDYŽ–PAK
35. Fuzzy řízení: Mamdani a Sugeno od ventilátoru po kyvadlo na vozíku
36. Fuzzy shlukování: algoritmus fuzzy c-means a body mezi shluky
37. Neuro-fuzzy systémy (ANFIS): fuzzy pravidla, která se učí z dat
38. Markovovy řetězce: přechodová matice, stacionární rozdělení a PageRank
39. Skryté Markovovy modely: Viterbiho algoritmus a nepoctivé kasino
40. Bayesovské sítě: proč je tráva mokrá a co z toho plyne pro postřikovač
41. Kalmanův filtr: jak z nepřesných měření odhadnout, kde auto je a jak rychle jede
42. Druhy strojového učení: s učitelem, bez učitele, s částečným učitelem a další
43. Přeučení a regularizace: proč model, který zná data nazpaměť, selže
44. Vyhodnocení modelu: křížová validace, F1 a křivka ROC
45. Shlukování a snížení dimenze: k-means, PCA a t-SNE
46. Klasifikace a regrese: dvě úlohy učení s učitelem
47. Lineární regrese: nejmenší čtverce geometricky i maticově
48. Polynomiální a nelineární regrese: jak přímku ohnout
49. Logistická regrese: sigmoida, šance a křížová entropie
50. Vícetřídní klasifikace a softmax: od dvou tříd k mnoha
51. Naivní Bayesův klasifikátor: spamový filtr, který funguje lépe, než by měl
52. Ztrátové funkce: co přesně model minimalizuje
53. Rozhodovací stromy a k nejbližších sousedů: modely bez vzorců
54. Ansámbly: náhodný les a gradient boosting
55. SVM a jádrový trik: nejširší hranice a jak ji ohnout
56. Signál a vzorkování: proč platí Nyquistův teorém
57. Fourierova transformace: rozklad signálu na frekvence
58. Filtry a konvoluce: vyhlazení, hrany a odstranění šumu
59. Zvuk a řeč: spektrogram, melová škála a MFCC
60. Obraz jako signál: pixely, barvy, konvoluce a hrany
61. Perceptron a umělý neuron: nejjednodušší neuronová síť a co neumí
62. Neuronová síť od nuly: zpětné šíření chyby krok za krokem
63. Aktivace, inicializace a normalizace: drobnosti, na kterých hluboká síť stojí
64. Konvoluční sítě: jak síť poznává obrázky
65. Rekurentní sítě: paměť pro posloupnosti a mizející gradient
66. LSTM a GRU: brány, které rozhodují, co si síť zapamatuje
67. Autoenkodéry: síť, která se učí data stlačit a zase rozbalit
68. Embeddingy a word2vec: jak se slovo stane vektorem
69. Mechanismus pozornosti: jak se model naučí, kam se dívat
70. Transformery a velké jazykové modely: architektura krok za krokem
71. Tokenizace: jak se text rozseká na kousky pro model
72. Předtrénování a škálování: proč větší model a víc dat funguje
73. Doladění a RLHF: jak se z doplňovače textu stane asistent
74. Prompty, kontext a RAG: jak modelu dát správné informace
75. Variační autoenkodéry (VAE): nové obrázky ze spojitého latentního prostoru
76. Generativní adversariální sítě (GAN): padělatel proti detektivovi
77. Difúzní modely: jak se z čistého šumu stane obrázek
78. Markovovy rozhodovací procesy: stavy, akce, odměny a Bellmanovy rovnice
79. Q-learning a DQN: učení hodnoty akcí od tabulky po neuronovou síť
80. Policy gradient a PPO: učení přímo strategie
81. Jak funguje AI agent: jazykový model ve smyčce s nástroji
82. Programování s AI agenty: zadání, testy a kontrola
83. Vyhodnocení a bezpečnost AI systémů: jak měřit a jak hlídat

Celá osnova série 83 z 83 témat hotovo

Rozvrh hodin, ve kterém žádný učitel neučí dvě třídy naráz. Sudoku. Rozmístění součástek na desce, směny v nemocnici, přidělení letadel k branám. Všechny tyhle úlohy mají společné to, že nehledáme cestu, ale přiřazení: každé proměnné dát hodnotu tak, aby platila všechna pravidla najednou. Takové úloze se říká úloha s omezujícími podmínkami a na rozdíl od obecného prohledávání má jednu velkou výhodu — pravidla jsou vidět, takže z nich algoritmus může usuzovat, ne jen zkoušet.

Navazuje na díly Prohledávání stavového prostoru a Grafy a stromy.

1. Co je úloha s omezujícími podmínkami

Definice — CSP

Nechť n ∈ ℕ, n ≥ 1. Úloha s omezujícími podmínkami (constraint satisfaction problem, CSP) je trojice (X, D, C), kde

1. X = {X₁, …, X_n} je množina n různých proměnných;
2. D = (D₁, …, D_n), kde pro každé i = 1, …, n je D_i neprázdná množina — doména proměnné X_i, tj. množina hodnot, kterých smí X_i nabývat (v tomto dílu jsou všechny domény konečné);
3. C je konečná množina podmínek. Každá podmínka je dvojice (S, R), kde rozsah S = (X_i1, …, X_ir) je r-tice navzájem různých proměnných z X (r ≥ 1) a relace R ⊆ D_i1 × … × D_ir je množina povolených kombinací jejich hodnot.

Číslo r je arita podmínky. Podmínka s r = 2 je binární, například podmínka X₁ ≠ X₂ je dvojice ((X₁, X₂), {(x, y) ∈ D₁ × D₂ : x ≠ y}). CSP je binární, právě když jsou všechny jeho podmínky binární. Rozsah S budeme podle potřeby chápat i jako množinu svých proměnných (S ⊆ X).

Slovy: CSP tvoří konečně mnoho proměnných, ke každé množina přípustných hodnot a seznam pravidel, z nichž každé vyjmenovává povolené kombinace hodnot několika proměnných.

Definice — přiřazení a řešení

Nechť (X, D, C) je CSP. Přiřazení je funkce a : dom(a) → D₁ ∪ … ∪ D_n, kde dom(a) ⊆ X, taková, že

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

Pro podmínku (S, R) ∈ C s rozsahem S = (X_i1, …, X_ir) ⊆ dom(a) označme a|_S = (a(X_i1), …, a(X_ir)) hodnoty proměnných rozsahu. Přiřazení a je

1. konzistentní, právě když pro každou podmínku (S, R) ∈ C s S ⊆ dom(a) platí a|_S ∈ R;
2. úplné, právě když dom(a) = X.

Řešení CSP je přiřazení, které je úplné a konzistentní. Slovy: řešení dá hodnotu každé proměnné a neporuší žádnou podmínku; konzistentní přiřazení neporuší žádnou podmínku, jejíž proměnné už všechny hodnotu mají.

Přiřazení a je tedy funkce z množiny proměnných dom(a) ⊆ X do jejich domén. Podmínku konzistence z definice lze zapsat jediným výrazem:

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

∀(S, R) ∈ C

projdeme každou podmínku — rozsah S a relaci R; stačí jediná porušená a přiřazení je špatně

S ⊆ dom(a)

soudíme jen podmínky, jejichž proměnné už všechny mají hodnotu; o podmínce s volnou proměnnou zatím rozhodnout nelze, a proto ji rozpracované přiřazení nemůže porušit

a|_S ∈ R

hodnoty proměnných z rozsahu (zúžení a na S) musí tvořit kombinaci, kterou relace povoluje

Příklad — barvení krajů jako CSP

X = {KVK, ULK, …, MSK} je 14 krajů, každý má doménu D_i = {1, 2, 3, 4} (čísla barev) a C obsahuje pro každou z 26 společných hranic jednu podmínku ((X_i, X_j), ≠), tedy relaci {(x, y) : x ≠ y} s dvanácti povolenými dvojicemi z 16.

Úplných přiřazení je |D₁| · |D₂| · … · |D₁₄| = 4¹⁴ = 268 435 456. Hledáme mezi nimi ta, která splní všech 26 podmínek.

Proč to nepojmout jako obyčejné prohledávání? Šlo by to — stav je rozpracované přiřazení, akce je „dej další proměnné hodnotu“. Jenže prohledávání by se na stav dívalo jako na černou skříňku. CSP do skříňky vidí: ví, která pravidla platí a kterých proměnných se týkají. Na tom stojí všechny triky v tomhle dílu.

2. Graf podmínek: barvení mapy krajů

Klasická úloha: obarvit mapu tak, aby žádné dva sousední státy neměly stejnou barvu. Vezmeme čtrnáct krajů Česka. Proměnné jsou kraje, doména je sada barev a pro každou společnou hranici je podmínka „různé barvy“.

Definice — graf podmínek

Nechť (X, D, C) je binární CSP s proměnnými X = {X₁, …, X_n}. Jeho graf podmínek 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}.

Proměnné X_i a X_j jsou tedy spojeny hranou, právě když existuje podmínka, jejíž rozsah tvoří právě tyto dvě proměnné (v libovolném pořadí — proto stačí i, j projít oběma směry). Sousedy proměnné X_i v tomto grafu značíme N(X_i) = {X_j : {X_i, X_j} ∈ E}.

Se čtyřmi barvami to jde hladce. Se třemi to nejde vůbec — a graf ukáže proč. Středočeský kraj sousedí s Prahou a se sedmi kraji, které kolem něj tvoří uzavřený kruh. Kruh o lichém počtu vrcholů potřebuje sám o sobě tři barvy (dvě by se musely pravidelně střídat, a to u lichého počtu nevyjde). Středočeský kraj sousedí se všemi sedmi, takže na něj čtvrtá barva zbýt musí:

Věta — tři barvy na kraje nestačí

Nechť G = (V, E) je konečný neorientovaný graf a k ∈ ℕ, k ≥ 1. Obarvení grafu G k barvami je funkce c : V → {1, …, k} taková, že

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

Chromatické číslo grafu G je

χ(G) = min {k ∈ ℕ, k ≥ 1 : existuje obarvení G k barvami},

tedy nejmenší počet barev, kterými jdou vrcholy obarvit tak, aby každé dva sousední vrcholy měly různé barvy (pro konečný graf minimum existuje, |V| barev stačí vždy).

Lemma. Nechť G = (V, E) je graf, m ≥ 3 liché a v₁, …, v_m ∈ V vrcholy tvořící cyklus, tj. {v_i, v_i+1} ∈ E pro i = 1, …, m − 1 a {v_m, v₁} ∈ E. Pak neexistuje funkce c : {v₁, …, v_m} → {1, 2}, která by na těchto hranách dávala sousedům různé barvy. Důkaz: se dvěma barvami se podél cyklu barvy musí střídat; má-li v₁ barvu 1, pak v_i má barvu 1 právě pro lichá i. Pak má v_m (liché m) barvu 1 stejně jako jeho soused v₁. Spor. ∎

Věta. Nechť G je graf krajů: vrcholy jsou kraje Česka (14 vrcholů) a {u, v} ∈ E, právě když kraje u a v mají společnou hranici. Pak χ(G) = 4. Důkaz: obarvení čtyřmi barvami existuje (obrázek výše), takže χ(G) ≤ 4. Nechť by existovalo obarvení c třemi barvami. Prstenec 7 krajů kolem Středočeského je cyklus liché délky, takže podle lemmatu na něm c nevystačí s méně než třemi barvami — použije všechny tři. Středočeský kraj sousedí s každým krajem prstence, a c(STČ) se proto liší od všech tří barev, což v {1, 2, 3} nejde. Spor, tedy χ(G) ≥ 4. ∎

Že čtyři barvy stačí na každou mapu, je slavná věta o čtyřech barvách. Dokázali ji Appel a Haken v roce 1976 — jako první velkou matematickou větu s pomocí počítače, který prověřil skoro dva tisíce případů.

3. Backtracking

Definice — backtracking

Backtracking je prohledávání do hloubky, které v každém kroku přiřadí hodnotu jedné další proměnné. Pro přiřazení a, proměnnou X_i ∉ dom(a) a hodnotu v ∈ D_i značíme a ∪ {X_i ↦ v} přiřazení a rozšířené o hodnotu v proměnné X_i.

Vstup: CSP (X, D, C) s konečnými doménami a konzistentní přiřazení a (na začátku prázdné, dom(a) = ∅).
Výstup: řešení CSP, které rozšiřuje a, nebo „neúspěch“, pokud takové řešení neexistuje.

Procedura BT(a):

1. Je-li dom(a) = X, vrať a (úplné konzistentní přiřazení je řešení).
2. Vyber proměnnou X_i ∈ X ∖ dom(a).
3. Pro každou hodnotu v ∈ D_i (v pevném pořadí): je-li a ∪ {X_i ↦ v} konzistentní, zavolej BT(a ∪ {X_i ↦ v}); vrátí-li toto volání řešení, vrať ho. Nekonzistentní hodnotu vůbec nezkoušej.
4. Nevedla-li k řešení žádná hodnota, vrať „neúspěch“ — volající se tím vrátí k předchozí proměnné a zkusí její další hodnotu.

Zastavení: každé vnořené volání má o jednu přiřazenou proměnnou víc, takže hloubka rekurze je nejvýš n = |X|, a každé volání zkusí nejvýš |D_i| hodnot. Strom volání je proto konečný a algoritmus vždy skončí.

Nechť d = max_i |D_i|. V nejhorším případě projde backtracking O(dⁿ) přiřazení. Obecný CSP je NP-těžký, takže v nejhorším případě lépe neumíme.

def backtracking(prirazeni, csp):
    if len(prirazeni) == len(csp.promenne):
        return prirazeni                      # všechno má hodnotu: řešení
    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: vrať se
    return None

Proč „jedna proměnná na patro“ dělá obrovský rozdíl? Obecné prohledávání by v každém stavu nabízelo všechny dvojice (nepřiřazená proměnná, hodnota). Totéž úplné přiřazení by pak šlo poskládat ve všech možných pořadích a strom by měl

n! · dⁿ listů místo dⁿ

n!

počet pořadí, ve kterých lze n proměnných přiřadit; na pořadí výsledek nezávisí (přiřazení je množina dvojic), takže všechna kromě jednoho jsou zbytečné kopie téže práce — backtracking je zahodí tím, že na každém patře rozhoduje o jediné proměnné

dⁿ

počet různých úplných přiřazení: každá z n proměnných nezávisle jednu z d hodnot; tolik listů zbude, i kdyby backtracking nic neořezával

Na krajích se čtyřmi barvami udělá backtracking 14 přiřazení, jedno na kraj, a ani jednou se nevrací. Se třemi barvami musí dokázat, že řešení neexistuje — a to znamená vyzkoušet všechno: 93 přiřazení, než to vzdá. Začátek jeho běhu (odsazení je hloubka ve stromu, barvy jsou čísla 1–3, ✗ znamená, že pro kraj nezbyla žádná barva):

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
…

Hned první slepá ulička je poučná: Středočeskému kraji vzaly všechny tři barvy Ústecký, Plzeňský a Praha. Backtracking se ale vrací jen k poslední proměnné — k Praze — a přebarvuje ji, i když skutečná potíž je v lichém prstenci. Praha se tak v běhu přebarvuje znovu a znovu. Tomuhle bezradnému přešlapování se říká thrashing a chytřejší volba proměnných ho výrazně omezí.

4. Kterou proměnnou a kterou hodnotu

Kostra backtrackingu nechává otevřené dvě otázky: kterou proměnnou vzít jako další a v jakém pořadí zkoušet její hodnoty. Na odpovědi záleží víc, než by se zdálo.

Definice — MRV, stupeň, LCV

Nechť (X, D, C) je binární CSP s grafem podmínek G a sousedy N(·), a je konzistentní přiřazení a U = X ∖ dom(a) ≠ ∅ množina nepřiřazených proměnných. Pro X_i ∈ U označme zbylé hodnoty

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

1. MRV (minimum remaining values) vybere jako další proměnnou některou z M = {X_i ∈ U : |D′_i| = min_{Xk ∈ U} |D′_k|}, tj. proměnnou s nejmenším počtem hodnot, které ještě nejsou v konfliktu s přiřazením.
2. Stupňová heuristika rozhodne shodu: z M vybere proměnnou X_i s největším |N(X_i) ∩ U|, tj. s nejvíce podmínkami s dosud nepřiřazenými proměnnými.
3. LCV (least constraining value): pro vybranou 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 ztráta(v) = ∑_{Xj ∈ N(Xi) ∩ U} |D′_j ∖ D″_j(v)|. LCV zkouší hodnoty v ∈ D′_i vzestupně podle ztráty(v).

Slovy: MRV bere proměnnou, které zbývá nejméně možností, stupňová heuristika při shodě tu, která nejvíc omezuje ostatní, a LCV zkouší nejdřív hodnotu, která sousedům vyškrtne nejméně možností. U podmínky ≠ je D′_j ∖ D″_j(v) = {v} ∩ D′_j, takže ztráta je prostě počet nepřiřazených sousedů, kterým v ještě zbývá.

U tří barev na krajích sníží MRV spolu s dopřednou kontrolou z další kapitoly počet přiřazení z 93 na 45 — začne u kraje, kterému zbývá nejméně barev, a spor najde dvakrát rychleji.

Na prázdné mapě mají všechny kraje po třech barvách a MRV nerozhodne. Stupňová heuristika by pak vzala Středočeský kraj, který má 8 sousedů — nejvíc ze všech; jeho barva hned omezí osm dalších krajů. Naše implementace při shodě bere prostě první kraj v pořadí od západu, tedy Karlovarský.

5. Dopředná kontrola

Definice — dopředná kontrola

Nechť (X, D, C) je binární CSP, ve kterém každé dvě proměnné spojuje nejvýš jedna podmínka (víc podmínek mezi touž dvojicí lze nahradit jednou s průnikem relací). Pro podmínku ((X_i, X_j), R) ∈ C značíme R_ij = R a R_ji = {(y, x) : (x, y) ∈ R}.

Nechť a je konzistentní přiřazení, D₁, …, D_n aktuální (případně už zúžené) domény, X_i ∉ dom(a) a v ∈ D_i. Dopředná kontrola po přiřazení X_i ↦ v nastaví D_i ← {v} a pro každou proměnnou X_j ∈ N(X_i) ∖ dom(a)

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

ostatní domény nemění. Je-li po zúžení D_j = ∅ pro některé j, přiřazení X_i ↦ v se okamžitě odvolá — nelze ho rozšířit na řešení, protože X_j by neměla žádnou přípustnou hodnotu.

Slovy: po každém přiřazení se ze všech nepřiřazených sousedů vyškrtnou hodnoty, které s přiřazenou hodnotou nejsou slučitelné, a prázdná 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                       # sousedovi nic nezbylo: p = h odvolat
    return nove

Backtracking pak místo původních domén předává do rekurze zúžené nove a MRV už jen porovnává jejich délky. Takhle vypadá začátek běhu s dopřednou kontrolou a MRV na krajích se třemi barvami. Ve sloupci vpravo jsou nepřiřazené kraje s nejmenší doménou — z nich MRV vybere ten první:

Po prvních třech krocích zbyla Středočeskému kraji jediná barva, a tak přijde na řadu dřív než Praha. Každý další vybraný kraj má už jen jednu možnost a v osmém kroku dopředná kontrola zjistí, že Pardubickému kraji nezůstalo nic — spor je odhalen, aniž by se Pardubický kraj vůbec zkoušel barvit. Celý prstenec se tak vynutí sám od sebe; volné rozhodnutí padlo jen u prvních dvou krajů.

Rozdíl je vidět na sudoku níže. Prostý backtracking políčka po řádcích potřebuje přes 14 milionů přiřazení. S dopřednou kontrolou jich je 11 400. A když k ní přidáme MRV, spadne to na 81 — 30 zadaných čísel a 51 doplněných, bez jediného návratu.

6. Hranová konzistence a AC-3

Dopředná kontrola se dívá jen o krok dál: na sousedy proměnné, kterou jsme právě přiřadili. Jde to důkladněji — vyškrtávat i mezi proměnnými, které ještě hodnotu nemají.

Definice — hranová konzistence

Nechť (X, D, C) je binární CSP se značením R_ij z definice dopředné kontroly a nechť X_i, X_j ∈ X jsou proměnné spojené podmínkou, tj. {X_i, X_j} ∈ E. Proměnná X_i je hranově konzistentní vzhledem k X_j, právě když

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

Uspořádaná dvojice (X_i, X_j) s {X_i, X_j} ∈ E se nazývá orientovaná hrana; každá hrana grafu podmínek dává dvě. CSP je hranově konzistentní, právě když je X_i hranově konzistentní vzhledem k X_j pro každou orientovanou hranu (X_i, X_j). Slovy: každá hodnota v doméně každé proměnné má u každého souseda aspoň jednu hodnotu, se kterou podmínku splní.

Zkonzistentnit jednu orientovanou hranu (operace zuz v kódu níže) znamená ponechat jen hodnoty s partnerem:

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

D_i ←

doménu přepisujeme na místě; zmenšuje se jen doména X_i, hrana je orientovaná — opačný směr (X_j, X_i) je samostatná položka fronty

x ∈ D_i

každou hodnotu soudíme zvlášť; nic nového nepřidáváme, takže doména může jen ubývat — proto AC-3 skončí

∃y ∈ D_j

stačí jeden partner v aktuální doméně souseda; ptáme se, jestli x může přežít, ne jak

(x, y) ∈ R_ij

dvojice musí podmínku mezi X_i a X_j splňovat — u barvení mapy prostě x ≠ y

Algoritmus — AC-3

Vstup: binární CSP (X, D, C) s konečnými doménami a grafem podmínek G = (X, E).
Výstup: „nepravda“, pokud některá doména zůstala prázdná (CSP pak nemá řešení); jinak „pravda“ a domény zúžené tak, že CSP je hranově konzistentní a má stejnou množinu řešení jako na vstupu.

1. Vlož do fronty Q všechny orientované hrany (X_i, X_j), {X_i, X_j} ∈ E.
2. Je-li Q prázdná, skonči s výsledkem „pravda“.
3. Vyjmi z Q hranu (X_i, X_j) a proveď D_i ← {x ∈ D_i : ∃y ∈ D_j : (x, y) ∈ R_ij} (rozbor výše).
4. Pokud se D_i zmenšila: je-li D_i = ∅, skonči s výsledkem „nepravda“; jinak vlož do Q všechny hrany (X_k, X_i) pro X_k ∈ N(X_i), X_k ≠ X_j — jejich hodnoty mohly právě přijít o partnera.
5. Pokračuj krokem 2.

Zastavení: hrany se do fronty vracejí jen tehdy, když některá doména ubude; domény jsou konečné a nikdy nerostou, takže po konečně mnoha krocích je fronta prázdná.

Pro c binárních podmínek a domény velikosti nejvýš 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ázdná doména: řešení 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 krokem

Tři proměnné X, Y, Z, každé dvě musí být různé, a domény D_X = {1}, D_Y = {1, 2}, D_Z = {1, 2, 3}. Fronta začíná šesti orientovanými hranami; řádek tabulky je jedno vyjmutí z fronty a jedno zúžení D_i ← podle vzorce výše (sloupec „doména po“ má barvu stejného členu):

V kroku 3 přijde Y o jedničku, protože jediný možný partner u X je právě 1. Tím se do fronty vrátí hrana (Z, Y) — hodnota 2 v Z měla partnera právě v té vyškrtnuté jedničce. Hodnotu 2 ze Z ale škrtne už původní hrana (Z, Y) v kroku 6; vrácená kopie v kroku 7 nic nenajde. (Naše fronta není množina, takže v ní hrana může být dvakrát — na výsledku to nic nemění.) Po 9 krocích je fronta prázdná a domény jsou {1}, {2}, {3}: řešení bez jediného pokusu.

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

2c

každá binární podmínka dává dvě orientované hrany, každou je potřeba zkontrolovat

d

kolikrát nejvýš se hrana (X_k, X_i) vrátí do fronty: jen když D_i ubude, a to se stane nejvýš d-krát

d²

cena jedné kontroly hrany: pro každou z nejvýš d hodnot x hledáme partnera mezi nejvýš d hodnotami y

7. Sudoku: propagace v praxi

Sudoku je CSP jako z učebnice: 81 proměnných, domény {1, …, 9} a podmínka „různé hodnoty“ pro každou dvojici políček ve stejném řádku, sloupci nebo čtverci 3 × 3. Každé políčko tak má 20 sousedů v grafu podmínek.

Příklad — sudoku v číslech

Sousedé políčka: 8 dalších v řádku + 8 ve sloupci + 4 políčka čtverce 3 × 3, která neleží v jeho řádku ani sloupci (zbylá 4 už jsme započítali) = 20.

Podmínky: 81 · 20 = 1620 orientovaných hran, každá dvojice políček je v tom dvakrát, takže binárních podmínek je 1620/2 = 810.

Velikost domén na začátku: 30 zadaných políček s doménou {zadané číslo} a 51 prázdných s devíti hodnotami: 30 · 1 + 51 · 9 = 489 hodnot. Na konci má každé z 81 políček jednu hodnotu, takže AC-3 vyškrtlo 489 − 81 = 408 hodnot. Z fronty k tomu vzalo 9 372 hran.

Hrubá síla: vyzkoušet všechna doplnění prázdných políček znamená 9⁵¹ ≈ 4,6 · 10⁴⁸ přiřazení (dⁿ s d = 9 a n = 51 prázdných políček; barva podle vzorce v kapitole Backtracking). Backtracking jich díky kontrole konzistence udělá „jen“ čtrnáct milionů.

Spusťme na zadání s 30 čísly samotné AC-3, bez jediného přiřazení naslepo. Vyškrtá 408 hodnot — a každému z 51 prázdných políček zůstane právě jedna. Sudoku je vyřešené čistou úvahou:

U lehkých sudoku to tak chodí; u těžších propagace někde uvízne a nastoupí hledání — backtracking, který po každém přiřazení znovu pustí propagaci. Tahle kombinace (udržování hranové konzistence, MAC) je základ většiny skutečných řešičů. Pro srovnání na stejném zadání:

Od čtrnácti milionů k nule. Hrubá síla a chytrá úvaha řeší stejnou úlohu — jen jedna z nich čte pravidla.

8. Lokální hledání: min-conflicts

Úplně jiná strategie: nestavět řešení kousek po kousku, ale začít s úplným přiřazením, které porušuje spoustu podmínek, a postupně ho opravovat. Je to lokální hledání z dílu o prohledávání, jen účelová funkce je počet porušených podmínek.

Algoritmus — min-conflicts

Vstup: CSP (X, D, C) s konečnými doménami a největší počet kroků k_max ∈ ℕ.
Výstup: řešení CSP, nebo „neúspěch“.

Pro úplné přiřazení a, proměnnou X_i a hodnotu v ∈ D_i nechť konflikty(X_i, v) je počet podmínek (S, R) ∈ C s X_i ∈ S, které porušuje přiřazení vzniklé z a změnou hodnoty X_i na v. Proměnná X_i je v konfliktu, právě když konflikty(X_i, a(X_i)) > 0.

1. Zvol náhodné úplné přiřazení a (a(X_i) ∈ D_i pro všechna i).
2. Opakuj nejvýš k_max-krát: je-li a konzistentní (žádná proměnná není v konfliktu), vrať a. Jinak vyber náhodně proměnnou X_i v konfliktu a nastav a(X_i) ← v, kde v ∈ D_i má nejmenší konflikty(X_i, v) (při shodě náhodně) — tedy hodnotu, se kterou porušuje nejméně podmínek.
3. Po k_max krocích bez řešení vrať „neúspěch“.

Zastavení: nejpozději po k_max krocích. Algoritmus není úplný: „neúspěch“ neznamená, že řešení neexistuje.

Klasická zkouška je úloha n dam: rozestavit n šachových dam na šachovnici n × n tak, aby se žádné dvě neohrožovaly. Proměnná je řádek dámy v každém sloupci. Pro osm dam začal náš běh se šesti ohrožujícími se dvojicemi a skončil po 8 krocích:

Co přesně algoritmus minimalizuje? Dáma ve sloupci i stojí v řádku r_i. Počet konfliktů, kdyby ji postavil do řádku v, je

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

konflikty(i, v)

cena tahu „dámu ze sloupce i do řádku v“; min-conflicts vybere v, pro které je nejmenší

∑_{j ≠ i} [ … ]

sečteme přes všechny ostatní dámy; hranatá závorka je 1, když podmínka platí, jinak 0 — počítáme porušené podmínky

r_j = v

dáma j stojí ve stejném řádku; sloupec sdílet nemůže, to vylučuje už volba proměnných (jedna dáma na sloupec)

|r_j − v| = |j − i|

dámy leží na stejné úhlopříčce: posun v řádcích se rovná posunu ve sloupcích

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                          # nic nedrhne: řešení
        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 trpělivost

Náš běh tah po tahu. Sloupce i řádky číslujeme 1–8 (řádek 1 nahoře); „ceny“ jsou hodnoty konflikty(i, v) pro v = 1, …, 8 a tučně je nejmenší z nich (barvou odpovídají členu konflikty(i, v) ve vzorci výše). Na začátku stály dámy v řádcích 5 1 6 2 5 1 1 8.

V kroku 6 si algoritmus ze dvou stejně dobrých řádků vylosoval ten, ve kterém dáma už stála — tah nic nezměnil. V krocích 4 až 7 je nejmenší cena 1, teprve v osmém se ve vylosovaném sloupci najde řádek s nulou.

Všimněte si prostředních kroků: počet konfliktů se čtyři kroky drží na jedné — algoritmus přesouvá dámy „do strany“ po plošině, než najde tah, který spor odstraní. Překvapivé je, jak dobře to škáluje: milion dam vyřeší min-conflicts v průměru zhruba na padesát kroků. Stejným postupem se plánovala pozorování Hubbleova vesmírného dalekohledu (obojí popisují Minton, Johnston, Philips a Laird, 1992).

9. Omezující podmínky v praxi

• Rozvrhy a plánování. Školní rozvrhy, směny, přidělování učeben i výrobní plány se zadávají jako proměnné, domény a podmínky. Řešiče jako Google OR-Tools kombinují propagaci, hledání a lokální vylepšování.
• SAT řešiče řeší CSP, kde je každá proměnná pravda/nepravda. Ověřují návrhy čipů, hledají chyby v softwaru a správci balíčků (například v Linuxu) jimi skládají verze knihoven, které spolu fungují.
• Překladače přidělují proměnné programu do registrů procesoru barvením grafu: dvě proměnné, které žijí zároveň, nesmějí sdílet registr — přesně jako sousední kraje barvu.
• Konfigurátory v e-shopech a výrobě hlídají, aby šly vybrané součástky dohromady.
• AI agenti a jazykové modely v CSP často nevynikají: na sudoku nebo rozvrh se spolehlivěji hodí řešič. Dobrý agent proto úlohu nepřemýšlí „z hlavy“ — přeloží ji na proměnné a podmínky a zavolá na ni nástroj.

10. Shrnutí

• CSP je trojice (X, D, C): proměnné, domény a podmínky. Řešení je úplné přiřazení, které neporušuje žádnou podmínku.
• Backtracking přiřazuje proměnné jednu po druhé a vrací se ze slepých uliček; v nejhorším případě je exponenciální.
• Heuristiky MRV a LCV volí nejtěžší proměnnou a nejvstřícnější hodnotu; dopředná kontrola odhalí slepou uličku o krok dřív.
• AC-3 šíří škrtání po grafu podmínek, dokud každá hodnota nemá partnera; lehké sudoku vyřeší úplně bez hledání.
• Min-conflicts opravuje úplné přiřazení a zvládne i obrovské úlohy, jako je milion dam.

Chcete si to osahat? Nechte AI agenta napsat řešič sudoku s backtrackingem a pak do něj přidávejte dopřednou kontrolu, MRV a AC-3 — a počítejte, kolik přiřazení ubude.

Máte na to jiný názor? Napište na support@coden-app.com.