Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями

Основи штучного інтелекту наочно: що таке простір станів, як працюють BFS, DFS, UCS, жадібний пошук і A*, що таке евристика і як із цим пов’язане машинне навчання.

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

Серія Основи ШІ Частина 21 з 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. Що таке простір станів

Перш ніж щось шукати, треба описати задачу так, щоб її зрозумів комп’ютер. Для цього слугує задача пошуку:

Означення — задача пошуку

Задача пошуку — це шістка P = (S, s₀, A, T, G, c), де

• S — множина станів,
• s₀ ∈ S — початковий стан,
• A(s) — множина дій, застосовних у стані s,
• T : S × A → S — функція переходу; стан s′ = T(s, a) — наступник стану s,
• G ⊆ S — множина цільових станів,
• c : S × A → ℝ⁺ — ціна дії, завжди додатна.

Означення — шлях, розв’язок, оптимум

Шлях довжини k — це послідовність s₀, a₁, s₁, …, a_k, s_k, де s_i = T(s_i−1, a_i).

Ціна шляху — це сума цін дій: g = ∑_i=1^k c(s_i−1, a_i).

Розв’язок — це шлях, що закінчується в цілі: s_k ∈ G. Оптимальний розв’язок — розв’язок із найменшою ціною; її позначають C*.

Стани, з’єднані діями, утворюють орієнтований граф: стани — це вершини, дії — ребра з вагою c. Шукати розв’язок означає знайти в графі шлях з s₀ до якоїсь вершини з G. Класичний приклад — головоломка 8: фішки 1–8 у рамці 3 × 3 і одна порожня клітинка. Стан — це розташування фішок, дія — зсув порожньої клітинки, а ціль — впорядковані фішки:

Виглядає невинно, але головоломка 8 має 181 440 досяжних станів, а її старша сестра, головоломка 15, — понад десять трильйонів. Тому граф ніколи не будують повністю наперед. Алгоритм відкриває його поступово — з функції переходу щоразу обчислює лише наступників стану, на якому саме стоїть.

2. Задача: шлях лабіринтом

Усі алгоритми покажемо на одній і тій самій задачі. Маємо лабіринт 9 × 14 клітинок і хочемо дістатися від старту до цілі якомога дешевше. Спершу — що означає кожна клітинка:

• Вільна клітинка — вхід на неї коштує 1
• Болото — пройти можна, але вхід коштує 5
• Стіна — на неї ступити не можна
• S Старт (start) — початковий стан, клітинка (0, 0)
• G Ціль (goal) — клітинка (8, 13)
• Досліджена клітинка — алгоритм її розгорнув
• Знайдений шлях — результат алгоритму

Формальна постановка

Клітинку записуємо як пару (r, s) — рядок r ∈ {0, …, 8}, стовпець s ∈ {0, …, 13}. Позначимо Z множину стін і B множину клітинок із болотом.

• Стани: S = {(r, s) : (r, s) ∉ Z} — усі клітинки, крім стін.
• Початковий стан: s₀ = (0, 0). Ціль: G = {(8, 13)}.
• Дії: A = {↑, →, ↓, ←}. Дія застосовна в стані, лише якщо веде на клітинку всередині сітки, яка не є стіною.
• Перехід: T((r, s), →) = (r, s + 1), аналогічно для інших напрямків.
• Ціна: c(x, a) = 5, якщо T(x, a) ∈ B, інакше 1 — платимо за клітинку, на яку ступаємо.
• Завдання: знайти розв’язок із найменшою ціною C*.

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

3. Спільний кістяк усіх алгоритмів

Усі алгоритми в статті мають однаковий кістяк. Відрізняються вони лише одним рішенням.

Означення — межа, закриті стани, розгортання

Межа (frontier) F ⊆ S — множина станів, які алгоритм уже відкрив, але ще не розгорнув.

Закриті стани E ⊆ S — стани, які вже розгорнуто.

Розгорнути стан s означає обчислити всіх його наступників {T(s, a) : a ∈ A(s)} і ті, яких немає в E, додати до F.

frontier = [start]
closed = {}
поки frontier не порожня:
    state = choose_from(frontier)  # ← саме тут алгоритми відрізняються
    якщо state — ціль: готово
    додати state до closed
    для кожного наступника state:
        якщо він ще не закритий: додати його до frontier

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

4. Пошук у ширину (BFS)

Означення — BFS

Межа F — це черга (FIFO): розгортається стан, який потрапив до F найраніше.

Наслідок: стани розгортаються в порядку глибини d(s) — кількості дій від s₀. Тому BFS знаходить розв’язок із найменшою кількістю дій.

Якщо b — коефіцієнт розгалуження (найбільша кількість наступників стану), а d — глибина найменш глибокого розв’язку, BFS згенерує щонайбільше b + b² + … + b^d = O(b^d) станів і стільки ж тримає в пам’яті.

У лабіринті хвилю добре видно — вона розтікається в усіх напрямках, доки не натрапить на ціль:

Але зверніть увагу, що шлях веде прямо через болото. BFS рахує дії, а не ціну — для нього крок болотом такий самий, як крок по сухому. Найкоротший шлях вийшов у 25 кроків, але з ціною 37. BFS оптимальний, лише коли всі дії мають однакову ціну.

from collections import deque

def bfs(start, goal, successors):
    frontier = deque([start])
    parent = {start: None}
    while frontier:
        state = frontier.popleft()          # черга: перший увійшов — перший вийшов
        if state == goal:
            return path(parent, goal)
        for nxt in successors(state):
            if nxt not in parent:
                parent[nxt] = state
                frontier.append(nxt)
    return None

def path(parent, state):
    result = []
    while state is not None:
        result.append(state)
        state = parent[state]
    return result[::-1]

5. Пошук у глибину (DFS)

Означення — DFS

Межа F — це стек (LIFO): розгортається стан, який потрапив до F останнім.

Якщо m — найбільша глибина простору станів, DFS тримає в пам’яті лише поточну гілку та її сусідні вузли: O(b · m) станів. Час у найгіршому випадку — O(b^m).

DFS не оптимальний, а в нескінченному просторі навіть не повний — він може спускатися до нескінченності.

У дереві це видно за порядком: A, B, D, H, I — і лише потім E. У лабіринті:

Тут DFS пощастило, і він дістався до цілі, не дослідивши багато клітинок. Але шлях зайво довгий — 31 крок замість 25 і ціна 59.

Означення — ітеративне поглиблення (IDDFS)

Для ℓ = 0, 1, 2, … запусти DFS, який не розгортає стани, глибші за ℓ. Зупинись на першому знайденому розв’язку.

Стани на глибині i генеруються (d − i + 1) разів, разом ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) — так само, як у BFS, але з пам’яттю лише O(b · d).

6. Пошук за ціною (UCS)

Означення — UCS

Для стану n позначимо g(n) ціну найдешевшого досі знайденого шляху з s₀ до n.

Межа — це черга з пріоритетом, упорядкована за g: розгортається стан із найменшим g(n).

Якщо всі ціни дій ≥ ε > 0, UCS розгортає стани в неспадному порядку g, тому він повний і оптимальний. Кількість розгорнутих станів — O(b^{1 + ⌊C*/ε⌋}).

UCS обійшов болото. Він знайшов шлях із такою самою кількістю кроків, як BFS, але з ціною 25 замість 37 — і він гарантовано найдешевший, тобто C* = 25. Платить за це тим, що шукає наосліп в усі боки: не знає, де ціль, тож поширюється і в протилежному напрямку.

7. Евристика: оцінка, куди йти до цілі

Алгоритми вище — неінформовані: про ціль вони знають лише те, що впізнають її, коли на неї ступлять. Інформовані алгоритми отримують на додачу оцінку, скільки ще лишилося.

Означення — евристика

Позначимо h*(n) ціну оптимального шляху зі стану n до найближчої цілі. Евристика — це функція h : S → ℝ_≥0, яка оцінює h*(n), причому h(n) = 0 для n ∈ G.

h допустима (admissible), якщо ніколи не переоцінює: ∀n ∈ S : h(n) ≤ h*(n).

h узгоджена (consistent), якщо для кожного стану n, дії a і наступника n′ = T(n, a) виконується h(n) ≤ c(n, a) + h(n′). Кожна узгоджена евристика допустима.

У нашому лабіринті напрошується манхеттенська відстань — кількість клітинок по горизонталі плюс по вертикалі, як коли ви йдете прямокутними вулицями Манхеттена:

8. Жадібний пошук

Означення — жадібний пошук

Межа — це черга з пріоритетом за f(n) = h(n): розгортається стан, який за оцінкою найближчий до цілі. Накопичену ціну g(n) не враховують.

Жадібний пошук не оптимальний; з контролем повторних станів він повний у скінченному просторі.

Жадібний пошук досліджує мало клітинок, але йде туди, де здається ближче, і опиняється на довгому й дорогому шляху — 31 крок, ціна 59.

9. A*: найкраще з обох світів

Означення — A*

Межа — це черга з пріоритетом за f(n) = g(n) + h(n) — оцінкою ціни всього шляху від старту через n до цілі.

Теорема. Якщо h узгоджена, значення f уздовж кожного шляху не спадають, A* розгортає стани в неспадному порядку f, і перший розгорнутий цільовий стан лежить на оптимальному шляху з ціною C*. При цьому він розгортає кожен стан із f(n) < C* і жодного з f(n) > C*.

Для h ≡ 0 A* — те саме, що UCS; без g це був би жадібний пошук.

Та сама ціна 25, що й в UCS, але A* дослідив 37 клітинок замість 49. У маленькому лабіринті це різниця в кілька клітинок; на мапі з мільйонами перехресть — різниця між миттєвою відповіддю і хвилиною очікування. Тому A* (і його варіанти) ви знайдете в навігаторах, в іграх і в плануванні руху роботів.

import heapq

def a_star(start, goal, successors, h):
    frontier = [(h(start), 0, start)]        # (f, g, стан)
    g = {start: 0}
    parent = {start: None}
    while frontier:
        _, cost, state = heapq.heappop(frontier)
        if state == goal:
            return path(parent, goal), cost
        if cost > g[state]:
            continue                       # застарілий запис, ми вже знаємо дешевший
        for nxt, step in successors(state):
            new = cost + step
            if new < g.get(nxt, float("inf")):
                g[nxt] = new
                parent[nxt] = state
                heapq.heappush(frontier, (new + h(nxt), new, nxt))
    return None

10. Порівняння алгоритмів

Означення — властивості алгоритму

Алгоритм повний, якщо для кожної задачі, що має розв’язок, він повертає якийсь розв’язок.

Алгоритм оптимальний, якщо повернений розв’язок має ціну C*.

b — коефіцієнт розгалуження, d — глибина найменш глибокого розв’язку, m — найбільша глибина простору. O(·) показує, як час або пам’ять зростають із цими параметрами.

* У скінченному просторі з контролем повторних станів розв’язок знаходять завжди. ** З узгодженою евристикою.

11. Локальний пошук: коли йдеться не про шлях

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

Означення — локальний пошук

Задано цільову функцію f : S → ℝ і окіл N(s) ⊆ S кожного стану. Шукаємо s* = argmax_{s ∈ S} f(s).

Стан s — локальний максимум, якщо f(s) ≥ f(s′) для всіх s′ ∈ N(s), і глобальний максимум, якщо це виконується для всіх s′ ∈ S.

Алгоритм сходження на пагорб: повторюй s ← argmax_{s′ ∈ N(s)} f(s′), доки f зростає.

Щоб не застрягти, використовують випадковий перезапуск (запускати альпініста з різних місць), генетичні алгоритми, які схрещують і мутують цілу популяцію розв’язків, або імітацію відпалу:

Імітація відпалу

Вибери випадкового сусіда s′ ∈ N(s) і обчисли Δ = f(s′) − f(s). Якщо Δ > 0, перейди до s′; інакше перейди з імовірністю e^Δ/T, де «температура» T поступово спадає до нуля.

І тут коло замикається з машинним навчанням. Навчання нейронної мережі — це локальний пошук у просторі її ваг θ: градієнтний спуск повторює θ ← θ − η ∇L(θ) — крок розміром η у тому напрямку, в якому функція помилки L спадає найшвидше. Це альпініст, перевернутий догори ногами, який замість найвищої вершини шукає найнижчу долину, — і він стикається з тими самими проблемами: локальними мінімумами та плато.

12. Підсумок

• Задача пошуку — це шістка (S, s₀, A, T, G, c). Розв’язок — це шлях у графі станів, оптимальний розв’язок — найдешевший із них.
• Алгоритми відрізняються лише тим, який стан вибирають із межі: черга (BFS), стек (DFS), найменше g (UCS), найменше h (жадібний), найменше g + h (A*).
• BFS знаходить найменше кроків, UCS — найнижчу ціну, A* — найнижчу ціну, досліджуючи при цьому найменше, якщо має узгоджену евристику.
• Коли йдеться не про шлях, а про результат, у гру вступає локальний пошук — а від нього лише крок до градієнтного спуску та машинного навчання.

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

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