Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв

Змінні, домени та обмеження, граф обмежень, бектрекінг, евристики MRV і LCV, пряма перевірка, AC-3 і min-conflicts — на розфарбовуванні країв Чехії, судоку та восьми ферзях.

15 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 23 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

Розклад уроків, у якому жоден учитель не веде два класи водночас. Судоку. Розміщення компонентів на платі, зміни в лікарні, призначення літаків до виходів на посадку. Усі ці задачі мають спільне те, що ми шукаємо не шлях, а присвоєння: кожній змінній дати значення так, щоб усі правила виконувалися водночас. Таку задачу називають задачею задоволення обмежень, і на відміну від загального пошуку вона має одну велику перевагу, — правила видно, тож алгоритм може з них міркувати, а не лише пробувати.

Ця частина продовжує частини «Пошук у просторі станів» і «Графи й дерева».

1. Що таке задача задоволення обмежень

Означення — CSP

Задача задоволення обмежень (constraint satisfaction problem, CSP) — це трійка (X, D, C), де

• X = {X₁, …, X_n} — множина змінних,
• D = {D₁, …, D_n}, де D_i — домен, тобто множина значень, яких може набувати X_i,
• C — множина обмежень. Кожне обмеження — це пара (область, відношення): область — це список змінних, відношення каже, які комбінації їхніх значень дозволені.

Обмеження з двома змінними в області — бінарне, наприклад X₁ ≠ X₂.

Означення — присвоєння і розв’язок

Присвоєння дає значення з домену деяким змінним. Воно узгоджене, коли не порушує жодного обмеження, і повне, коли значення має кожна змінна.

Розв’язок CSP — це повне узгоджене присвоєння.

Чому б не розглядати це як звичайний пошук? Можна й так — стан є незавершеним присвоєнням, дія — «дай наступній змінній значення». Але пошук дивився б на стан як на чорну скриньку. CSP у скриньку бачить: знає, які правила діють і яких змінних вони стосуються. На цьому тримаються всі прийоми в цій частині.

2. Граф обмежень: розфарбовування мапи країв

Класична задача: розфарбувати мапу так, щоб жодні дві сусідні держави не мали однакового кольору. Візьмімо чотирнадцять країв Чехії. Змінні — це краї, домен — набір кольорів, а для кожного спільного кордону є обмеження «різні кольори».

Означення — граф обмежень

Граф обмежень бінарного CSP має вершинами змінні, а ребро між X_i і X_j — тоді й лише тоді, коли їх пов’язує якесь обмеження.

З чотирма кольорами все йде гладко. З трьома не виходить зовсім — і граф покаже чому. Середньочеський край сусідить із Прагою та із сімома краями, які утворюють навколо нього замкнене коло. Коло з непарною кількістю вершин саме по собі потребує трьох кольорів (два мусили б регулярно чергуватися, а за непарної кількості це не виходить). Середньочеський край сусідить з усіма сімома, тож для нього мусить залишитися четвертий колір:

Те, що чотирьох кольорів досить для будь-якої мапи, — знаменита теорема про чотири кольори. Довели її Аппель і Гакен 1976 року — як першу велику математичну теорему за допомогою комп’ютера, який перевірив майже дві тисячі випадків.

3. Бектрекінг

Означення — бектрекінг

Бектрекінг — це пошук у глибину, який на кожному кроці присвоює значення одній наступній змінній. Значення, що порушує обмеження з уже присвоєними змінними, він навіть не пробує. Коли для змінної не залишається жодного значення, він повертається до попередньої змінної і пробує її наступне значення.

У найгіршому випадку він переглядає O(dⁿ) присвоєнь, де d — розмір домену, а n — кількість змінних. Загальна задача CSP NP-складна, тож у найгіршому випадку краще ми не вміємо.

def backtracking(assignment, csp):
    if len(assignment) == len(csp.variables):
        return assignment                     # усе має значення: розв’язок
    p = select_variable(assignment, csp)
    for h in csp.domains[p]:
        if consistent(p, h, assignment, csp):
            assignment[p] = h
            result = backtracking(assignment, csp)
            if result:
                return result
            del assignment[p]                 # глухий кут: повернися
    return None

На краях із чотирма кольорами бектрекінг робить 14 присвоєнь, одне на край, і жодного разу не повертається. З трьома кольорами він мусить довести, що розв’язку не існує, — а це означає перепробувати все: 93 присвоєння, перш ніж здатися.

4. Яку змінну і яке значення

Кістяк бектрекінгу залишає відкритими два питання: яку змінну взяти наступною і в якому порядку пробувати її значення. Від відповідей залежить більше, ніж могло б здатися.

Означення — MRV, степінь, LCV

MRV (minimum remaining values): обери змінну з найменшою кількістю значень, які ще не конфліктують із присвоєнням.

Евристика степеня: за рівності обери змінну, яка має найбільше обмежень із ще не присвоєними змінними.

LCV (least constraining value): значення змінної пробуй, починаючи з того, яке викреслить сусідам найменше можливостей.

Для трьох кольорів на краях MRV разом із прямою перевіркою з наступного розділу зменшує кількість присвоєнь з 93 до 45 — починає з краю, якому залишилося найменше кольорів, і знаходить суперечність удвічі швидше.

5. Пряма перевірка

Означення — пряма перевірка

Після присвоєння X_i = v пройди кожну неприсвоєну змінну X_j, пов’язану з X_i обмеженням, і вилучи з D_j значення, несумісні з v. Якщо якийсь домен залишиться порожнім, негайно скасуй присвоєння.

Різницю видно на судоку нижче. Простий бектрекінг по клітинках рядок за рядком потребує понад 14 мільйонів присвоєнь. З прямою перевіркою їх 11 400. А коли до неї додамо MRV, кількість впаде до 81 — 30 заданих чисел і 51 доповнене, без жодного повернення.

6. Дугова узгодженість і AC-3

Пряма перевірка дивиться лише на крок уперед: на сусідів змінної, якій ми щойно присвоїли значення. Можна ретельніше — викреслювати й між змінними, які ще не мають значення.

Означення — дугова узгодженість

Змінна X_i дугово узгоджена щодо X_j, коли для кожного значення x ∈ D_i існує y ∈ D_j таке, що пара (x, y) задовольняє обмеження між ними. CSP дугово узгоджена, коли це виконується для кожного орієнтованого ребра (X_i, X_j) графа обмежень.

Алгоритм — AC-3

1. Додай до черги всі орієнтовані ребра (X_i, X_j).
2. Візьми ребро з черги і вилучи з D_i кожне значення, яке не має партнера в D_j.
3. Якщо D_i зменшився, поверни до черги всі ребра (X_k, X_i) для сусідів X_k ≠ X_j — їхні значення могли щойно втратити партнера. Якщо D_i порожній, CSP не має розв’язку.
4. Повторюй, доки черга не спорожніє.

Для c бінарних обмежень і доменів розміром щонайбільше d AC-3 триває O(c · d³).

from collections import deque

def ac3(csp):
    queue = deque((xi, xj) for xi in csp.variables for xj in csp.neighbors[xi])
    while queue:
        xi, xj = queue.popleft()
        if revise(csp, xi, xj):
            if not csp.domains[xi]:
                return False                  # порожній домен: розв’язку не існує
            for xk in csp.neighbors[xi]:
                if xk != xj:
                    queue.append((xk, xi))
    return True

def revise(csp, xi, xj):
    before = len(csp.domains[xi])
    csp.domains[xi] = [x for x in csp.domains[xi]
                       if any(csp.allowed(xi, x, xj, y) for y in csp.domains[xj])]
    return len(csp.domains[xi]) < before

7. Судоку: поширення обмежень на практиці

Судоку — це CSP як із підручника: 81 змінна, домени {1, …, 9} і обмеження «різні значення» для кожної пари клітинок в одному рядку, стовпці чи квадраті 3 × 3. Тож кожна клітинка має 20 сусідів у графі обмежень.

Запустімо на умові з 30 числами саме лише AC-3, без жодного присвоєння навмання. Він викреслить 408 значень — і кожній із 51 порожньої клітинки залишиться рівно одне. Судоку розв’язане чистим міркуванням:

З легкими судоку так і буває; у складніших поширення десь застрягне і настає черга пошуку — бектрекінгу, який після кожного присвоєння знову запускає поширення. Це поєднання (підтримування дугової узгодженості, MAC) — основа більшості справжніх розв’язувачів. Для порівняння на тій самій умові:

Від чотирнадцяти мільйонів до нуля. Груба сила і розумне міркування розв’язують ту саму задачу — лише одна з них читає правила.

8. Локальний пошук: min-conflicts

Зовсім інша стратегія: не будувати розв’язок шматок за шматком, а почати з повного присвоєння, яке порушує купу обмежень, і поступово його виправляти. Це локальний пошук із частини про пошук, лише цільова функція — кількість порушених обмежень.

Алгоритм — min-conflicts

1. Почни з випадкового повного присвоєння.
2. Доки якесь обмеження не виконується: випадково обери змінну в конфлікті й дай їй значення, з яким вона порушує найменше обмежень (за рівності випадково).

Класичне випробування — задача n ферзів: розставити n шахових ферзів на шахівниці n × n так, щоб жодні два не загрожували один одному. Змінна — це рядок ферзя в кожному стовпці. Для восьми ферзів наш запуск почався із шести пар, що загрожують одна одній, і закінчився після 8 кроків:

Зверніть увагу на середні кроки: кількість конфліктів чотири кроки тримається на одиниці — алгоритм переставляє ферзів «убік» по плато, доки не знайде хід, який усуне суперечність. Дивує, як добре це масштабується: мільйон ферзів min-conflicts розв’язує в середньому приблизно за п’ятдесят кроків. Тим самим способом планували спостереження космічного телескопа «Габбл».

9. Обмеження на практиці

• Розклади та планування. Шкільні розклади, зміни, розподіл аудиторій і виробничі плани задають як змінні, домени та обмеження. Розв’язувачі на кшталт Google OR-Tools поєднують поширення обмежень, пошук і локальне вдосконалення.
• SAT-розв’язувачі розв’язують CSP, у яких кожна змінна — істина/хиба. Вони перевіряють проєкти чипів, шукають помилки в програмах, а менеджери пакетів (наприклад, у Linux) складають із їхньою допомогою версії бібліотек, які працюють разом.
• Компілятори розподіляють змінні програми по регістрах процесора розфарбовуванням графа: дві змінні, що живуть одночасно, не можуть ділити регістр — точнісінько як сусідні краї колір.
• Конфігуратори в інтернет-магазинах і на виробництві стежать, щоб вибрані компоненти пасували одне до одного.
• ШІ-агенти та мовні моделі у CSP часто не блищать: для судоку чи розкладу надійніше підходить розв’язувач. Тому добрий агент не обмірковує задачу «в голові» — він переводить її у змінні та обмеження і викликає для неї інструмент.

10. Підсумок

• CSP — це трійка (X, D, C): змінні, домени та обмеження. Розв’язок — повне присвоєння, яке не порушує жодного обмеження.
• Бектрекінг присвоює змінні одну за одною і повертається з глухих кутів; у найгіршому випадку він експоненційний.
• Евристики MRV і LCV обирають найважчу змінну та найпоступливіше значення; пряма перевірка виявляє глухий кут на крок раніше.
• AC-3 поширює викреслювання графом обмежень, доки кожне значення не матиме партнера; легке судоку він розв’язує взагалі без пошуку.
• Min-conflicts виправляє повне присвоєння і впорається навіть з величезними задачами, як-от мільйон ферзів.

Хочете спробувати самі? Попросіть ШІ-агента написати розв’язувач судоку з бектрекінгом, а тоді додавайте до нього пряму перевірку, MRV і AC-3 — і рахуйте, наскільки менше стане присвоєнь.

Маєте іншу думку? Напишіть на support@coden-app.com.