Стратегії пошуку у просторі станів

📌 Про що ця тема

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

📖 Головне

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

• Вузол — стан; ребро — застосування оператора (може мати вартість/ціну переходу).

• Задача пошуку: знайти шлях від початкового стану до цільового (послідовність дій).

• Стратегії ділять на дві групи: неінформовані (сліпі) та інформовані (евристичні).

• Пошук у ширину (BFS): переглядає всі вузли рівня, потім наступний рівень. Використовує чергу (FIFO). Гарантує найкоротший шлях за кількістю кроків, але потребує багато памʼяті.

• Пошук у глибину (DFS): йде вглиб однією гілкою до кінця, потім повертається (backtracking). Використовує стек (LIFO). Економить памʼять, але може зациклитися й не дає оптимального шляху.

• Пошук із обмеженням глибини — DFS, що не спускається глибше заданого рівня.

• Ітеративне заглиблення — поєднує переваги BFS і DFS: повторює пошук із глибини, поступово збільшуючи ліміт.

• Інформований пошук використовує евристику h(n) — оцінку «наскільки близько» стан до мети.

• Жадібний пошук (greedy best-first): обирає вузол із найменшою h(n). Швидкий, але не завжди оптимальний.

• Алгоритм A*: оцінює вузли функцією f(n) = g(n) + h(n), де g(n) — вартість шляху від старту, h(n) — евристика до мети. За коректної евристики дає оптимальний шлях.

• Критерії оцінки стратегії: повнота (чи знайде рішення, якщо воно є), оптимальність (чи знайде найкраще), часова й просторова складність.

🔢 Як це працює на прикладі

Задача: з міста A дістатися в D. Переходи: A→B, A→C, B→D, C→D.

• BFS: з A перевіряє сусідів B і C (рівень 1), потім їхніх сусідів — знаходить D. Шлях у 2 кроки.

• DFS: з A йде в B, з B — у D. Знаходить D, не оглядаючи гілку C.

• A*: якщо вартості A→B=1, B→D=5, A→C=2, C→D=1, то g через B = 6, через C = 3. A* обере шлях A→C→D як дешевший.

⚠️ Типові помилки

• Плутають BFS і DFS за структурою даних: BFS — черга, DFS — стек.

• Вважають, що DFS завжди знаходить найкоротший шлях — ні, це робить BFS (за кроками) чи A* (за вартістю).

• Плутають g(n) і h(n): g — уже пройдений шлях, h — прогноз до мети.

• Думають, що жадібний пошук і A* — одне й те саме; A* враховує ще й пройдений шлях.

• Забувають про перевірку відвіданих станів — через це DFS зациклюється.

🎯 Що завчити напамʼять

• BFS — черга (FIFO), по рівнях, найкоротший за кроками.

• DFS — стек (LIFO), вглиб, економний за памʼяттю.

• A*: f(n) = g(n) + h(n).

• g(n) — вартість пройденого шляху, h(n) — евристична оцінка до мети.

• Критерії: повнота, оптимальність, часова і просторова складність.

🧠 Перевір себе

1. Яку структуру даних використовує пошук у ширину?

2. Чим відрізняється жадібний пошук від A*?

3. Що означає функція g(n) в алгоритмі A*?

4. Яка стратегія ризикує зациклитися і чому?

Відповіді: 1 — чергу (FIFO), переглядає стани по рівнях; 2 — жадібний враховує лише h(n), а A* — суму g(n)+h(n), тому A* оптимальніший; 3 — вартість шляху, вже пройденого від початкового стану до вузла n; 4 — пошук у глибину (DFS), бо може нескінченно йти однією гілкою без перевірки відвіданих станів.