Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami

Podstawy sztucznej inteligencji w przystępnej formie: czym jest przestrzeń stanów, jak działają BFS, DFS, UCS, przeszukiwanie zachłanne i A*, czym jest heurystyka i jak to się łączy z uczeniem maszynowym.

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

Seria Podstawy AI Część 21 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Kiedy dziś mówi się o sztucznej inteligencji, większość ludzi myśli o sieciach neuronowych i dużych modelach językowych. Jednak na długo przedtem, zanim maszyny zaczęły uczyć się z danych, potrafiły szukać. Nawigacja na mapie, ruch w szachach, plan robota w magazynie — wszystko to jest szukaniem drogi w przestrzeni możliwości. Przeszukiwanie przestrzeni stanów to pierwszy rozdział każdego podręcznika sztucznej inteligencji, a jego idee spotkasz też w uczeniu maszynowym: heurystyki, optymalizację, szukanie najlepszego rozwiązania.

Każde pojęcie znajdziesz tu dwa razy: najpierw ścisłą definicję matematyczną, a tuż pod nią to samo ludzkim językiem. Wszystkie animacje to prawdziwe działanie algorytmu — nic z tego nie jest rysowane ręcznie.

1. Czym jest przestrzeń stanów

Zanim zaczniemy czegokolwiek szukać, musimy opisać problem tak, żeby zrozumiał go komputer. Do tego służy problem przeszukiwania:

Definicja — problem przeszukiwania

Problem przeszukiwania to szóstka P = (S, s₀, A, T, G, c), gdzie

• S jest zbiorem stanów,
• s₀ ∈ S jest stanem początkowym,
• A(s) jest zbiorem akcji dostępnych w stanie s,
• T : S × A → S jest funkcją przejścia; stan s′ = T(s, a) jest następnikiem stanu s,
• G ⊆ S jest zbiorem stanów docelowych,
• c : S × A → ℝ⁺ jest kosztem akcji, zawsze dodatnim.

Definicja — ścieżka, rozwiązanie, optimum

Ścieżka długości k to ciąg s₀, a₁, s₁, …, a_k, s_k, gdzie s_i = T(s_i−1, a_i).

Koszt ścieżki to suma kosztów akcji: g = ∑_i=1^k c(s_i−1, a_i).

Rozwiązanie to ścieżka, która kończy się w celu: s_k ∈ G. Rozwiązanie optymalne to rozwiązanie o najmniejszym koszcie; ten koszt oznaczamy C*.

Stany połączone akcjami tworzą graf skierowany: stany są wierzchołkami, akcje krawędziami o wadze c. Szukać rozwiązania znaczy więc znaleźć w grafie ścieżkę z s₀ do któregoś wierzchołka z G. Klasyczny przykład to łamigłówka 8 (ósemka): klocki 1–8 w ramce 3 × 3 i jedno puste miejsce. Stan to układ klocków, akcja to przesunięcie pustego miejsca, a cel to uporządkowane klocki:

Wygląda to niewinnie, ale łamigłówka 8 ma 181 440 osiągalnych stanów, a jej starszy brat, łamigłówka 15 (piętnastka), ponad dziesięć bilionów. Dlatego nigdy nie budujemy całego grafu z góry. Algorytm odkrywa go stopniowo — z funkcji przejścia oblicza zawsze tylko następników stanu, na którym akurat stoi.

2. Zadanie: droga przez labirynt

Wszystkie algorytmy pokażemy na tym samym zadaniu. Mamy labirynt 9 × 14 pól i chcemy dostać się ze startu do celu jak najtaniej. Najpierw, co oznacza które pole:

• Wolne pole — wejście na nie kosztuje 1
• Błoto — da się przez nie przejść, ale wejście kosztuje 5
• Ściana — nie można na nią wejść
• S Start — stan początkowy, pole (0, 0)
• G Cel (goal) — pole (8, 13)
• Zbadane pole — algorytm je rozwinął
• Znaleziona ścieżka — wynik algorytmu

Formalne sformułowanie zadania

Pole zapisujemy jako parę (r, s) — wiersz r ∈ {0, …, 8}, kolumna s ∈ {0, …, 13}. Niech Z oznacza zbiór ścian, a B zbiór pól z błotem.

• Stany: S = {(r, s) : (r, s) ∉ Z} — wszystkie pola oprócz ścian.
• Stan początkowy: s₀ = (0, 0). Cel: G = {(8, 13)}.
• Akcje: A = {↑, →, ↓, ←}. Akcja jest dostępna w danym stanie tylko wtedy, gdy prowadzi na pole wewnątrz siatki, które nie jest ścianą.
• Przejście: T((r, s), →) = (r, s + 1), analogicznie dla pozostałych kierunków.
• Koszt: c(x, a) = 5, jeśli T(x, a) ∈ B, w przeciwnym razie 1 — płaci się za pole, na które wchodzimy.
• Zadanie: znaleźć rozwiązanie o najmniejszym koszcie C*.

Błoto leży celowo na najprostszej trasie. Zobaczymy, że nie każdy algorytm je zauważy: niektóre liczą tylko kroki, inne rzeczywisty koszt.

3. Wspólny szkielet wszystkich algorytmów

Wszystkie algorytmy w tym artykule mają ten sam szkielet. Różnią się tylko jedną decyzją.

Definicja — brzeg, stany zamknięte, rozwinięcie

Brzeg (frontier) F ⊆ S to zbiór stanów, które algorytm już odkrył, ale jeszcze nie rozwinął.

Stany zamknięte E ⊆ S to stany już rozwinięte.

Rozwinąć stan s znaczy obliczyć wszystkich jego następników {T(s, a) : a ∈ A(s)} i tych, którzy nie są w E, dodać do F.

brzeg = [start]
zamkniete = {}
dopóki brzeg nie jest pusty:
    stan = wybierz_z(brzeg)        # ← tu algorytmy się różnią
    jeśli stan jest celem: koniec
    dodaj stan do zamkniete
    dla każdego następnika stanu:
        jeśli jeszcze nie jest zamknięty: dodaj go do brzegu

Cała różnica między algorytmami leży w jednej linijce: który stan z brzegu wybierzemy jako następny. Kolejka, stos albo kolejka priorytetowa według jakiejś liczby. Na tym opiera się cała reszta.

4. Przeszukiwanie wszerz (BFS)

Definicja — BFS

Brzeg F jest kolejką (FIFO): rozwija się stan, który trafił do F najwcześniej.

Wniosek: stany są rozwijane w kolejności głębokości d(s) — liczby akcji od s₀. BFS znajduje więc rozwiązanie z najmniejszą liczbą akcji.

Jeśli b jest współczynnikiem rozgałęzienia (największą liczbą następników stanu), a d głębokością najpłytszego rozwiązania, BFS wygeneruje co najwyżej b + b² + … + b^d = O(b^d) stanów i tyle samo trzyma w pamięci.

W labiryncie falę dobrze widać — rozlewa się we wszystkich kierunkach, aż natrafi na cel:

Zauważ jednak, że ścieżka prowadzi prosto przez błoto. BFS liczy akcje, nie koszt — dla niego krok w błoto jest taki sam jak krok po suchym. Najkrótsza ścieżka wyszła więc na 25 kroków, ale koszt 37. BFS jest optymalny tylko wtedy, gdy wszystkie akcje kosztują tyle samo.

from collections import deque

def bfs(start, goal, successors):
    frontier = deque([start])
    parent = {start: None}
    while frontier:
        state = frontier.popleft()      # kolejka: pierwszy wchodzi, pierwszy wychodzi
        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. Przeszukiwanie w głąb (DFS)

Definicja — DFS

Brzeg F jest stosem (LIFO): rozwija się stan, który trafił do F najpóźniej.

Jeśli m jest największą głębokością przestrzeni stanów, DFS trzyma w pamięci tylko bieżącą gałąź i jej rodzeństwo: O(b · m) stanów. Czas w najgorszym przypadku wynosi O(b^m).

DFS nie jest optymalny, a w nieskończonej przestrzeni nie jest nawet zupełny — może schodzić w dół w nieskończoność.

W drzewie widać to po kolejności: A, B, D, H, I — i dopiero potem E. W labiryncie:

Tutaj DFS miał szczęście i dotarł do celu, nie badając wielu pól. Ścieżka jest jednak niepotrzebnie długa — 31 kroków zamiast 25 i koszt 59.

Definicja — iteracyjne pogłębianie (IDDFS)

Dla ℓ = 0, 1, 2, … uruchom DFS, który nie rozwija stanów głębszych niż ℓ. Zakończ przy pierwszym znalezionym rozwiązaniu.

Stany na głębokości i są generowane (d − i + 1) razy, łącznie ∑_i=1^d (d − i + 1) · bⁱ = O(b^d) — tak samo jak BFS, ale z pamięcią tylko O(b · d).

6. Przeszukiwanie według kosztu (UCS)

Definicja — UCS

Dla stanu n oznaczmy przez g(n) koszt najtańszej dotąd znalezionej ścieżki z s₀ do n.

Brzeg jest kolejką priorytetową uporządkowaną według g: rozwija się stan o najmniejszym g(n).

Jeśli wszystkie koszty akcji są ≥ ε > 0, UCS rozwija stany w niemalejącej kolejności g, dlatego jest zupełny i optymalny. Liczba rozwiniętych stanów wynosi O(b^{1 + ⌊C*/ε⌋}).

UCS ominął błoto. Znalazł ścieżkę o tej samej liczbie kroków co BFS, ale z kosztem 25 zamiast 37 — i jest ona na pewno najtańsza, czyli C* = 25. Płaci za to tym, że przeszukuje na ślepo we wszystkich kierunkach: nie wie, gdzie leży cel, więc rozchodzi się także w stronę od niego.

7. Heurystyka: oszacowanie, którędy do celu

Powyższe algorytmy są niepoinformowane — o celu wiedzą tylko tyle, że go rozpoznają, kiedy na niego wejdą. Algorytmy poinformowane dostają dodatkowo oszacowanie, ile jeszcze zostało.

Definicja — heurystyka

Oznaczmy przez h*(n) koszt optymalnej ścieżki ze stanu n do najbliższego celu. Heurystyka to funkcja h : S → ℝ_≥0, która szacuje h*(n), przy czym h(n) = 0 dla n ∈ G.

h jest dopuszczalna (admissible), jeśli nigdy nie przeszacowuje: ∀n ∈ S : h(n) ≤ h*(n).

h jest spójna (konsystentna), jeśli dla każdego stanu n, akcji a i następnika n′ = T(n, a) zachodzi h(n) ≤ c(n, a) + h(n′). Każda spójna heurystyka jest dopuszczalna.

W naszym labiryncie nasuwa się odległość manhattańska — liczba pól w poziomie plus w pionie, jakbyś szedł prostopadłymi ulicami Manhattanu:

8. Przeszukiwanie zachłanne

Definicja — przeszukiwanie zachłanne

Brzeg jest kolejką priorytetową według f(n) = h(n): rozwija się stan, który jest według oszacowania najbliżej celu. Dotychczasowy koszt g(n) nie jest brany pod uwagę.

Przeszukiwanie zachłanne nie jest optymalne; z pilnowaniem powtórzonych stanów jest w skończonej przestrzeni zupełne.

Przeszukiwanie zachłanne bada mało pól, ale idzie tam, gdzie wygląda bliżej, i kończy na długiej i drogiej ścieżce — 31 kroków, koszt 59.

9. A*: to, co najlepsze z obu światów

Definicja — A*

Brzeg jest kolejką priorytetową według f(n) = g(n) + h(n) — oszacowania kosztu całej ścieżki od startu przez n do celu.

Twierdzenie. Jeśli h jest spójna, wartości f wzdłuż każdej ścieżki nie maleją, A* rozwija stany w niemalejącej kolejności f, a pierwszy rozwinięty stan docelowy leży na optymalnej ścieżce o koszcie C*. Rozwija przy tym każdy stan z f(n) < C* i żadnego z f(n) > C*.

Dla h ≡ 0 A* jest tym samym co UCS; bez g byłoby to przeszukiwanie zachłanne.

Ten sam koszt 25 co UCS, ale A* zbadał 37 pól zamiast 49. W małym labiryncie to różnica kilku pól; na mapie z milionami skrzyżowań to różnica między natychmiastową odpowiedzią a minutą czekania. Dlatego A* (i jego warianty) znajdziesz w nawigacjach, w grach i w planowaniu ruchu robotów.

import heapq

def a_star(start, goal, successors, h):
    frontier = [(h(start), 0, start)]     # (f, g, stan)
    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                       # nieaktualny wpis, znamy już tańszy
        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. Porównanie algorytmów

Definicja — właściwości algorytmu

Algorytm jest zupełny, jeśli dla każdego problemu, który ma rozwiązanie, zwraca jakieś rozwiązanie.

Algorytm jest optymalny, jeśli zwrócone rozwiązanie ma koszt C*.

b — współczynnik rozgałęzienia, d — głębokość najpłytszego rozwiązania, m — największa głębokość przestrzeni. O(·) określa, jak czas lub pamięć rosną wraz z tymi parametrami.

* W skończonej przestrzeni z pilnowaniem powtórzonych stanów zawsze znajdą rozwiązanie. ** Ze spójną heurystyką.

11. Przeszukiwanie lokalne: kiedy nie chodzi o ścieżkę

W niektórych problemach ścieżka nas nie interesuje — chcemy tylko dobrego stanu końcowego. Planu lekcji, rozmieszczenia elementów na płytce, ustawienia parametrów.

Definicja — przeszukiwanie lokalne

Dana jest funkcja celu f : S → ℝ i sąsiedztwo N(s) ⊆ S każdego stanu. Szukamy s* = argmax_{s ∈ S} f(s).

Stan s jest maksimum lokalnym, jeśli f(s) ≥ f(s′) dla wszystkich s′ ∈ N(s), i maksimum globalnym, jeśli zachodzi to dla wszystkich s′ ∈ S.

Algorytm wspinaczkowy: powtarzaj s ← argmax_{s′ ∈ N(s)} f(s′), dopóki f rośnie.

Przeciw utknięciu stosuje się losowy restart (wypuszczenie wspinacza z różnych miejsc), algorytmy genetyczne, które krzyżują i mutują całą populację rozwiązań, albo symulowane wyżarzanie:

Symulowane wyżarzanie

Wybierz losowego sąsiada s′ ∈ N(s) i oblicz Δ = f(s′) − f(s). Jeśli Δ > 0, przejdź do s′; w przeciwnym razie przejdź z prawdopodobieństwem e^Δ/T, gdzie „temperatura” T stopniowo spada do zera.

I tu koło zamyka się z uczeniem maszynowym. Trenowanie sieci neuronowej to przeszukiwanie lokalne w przestrzeni jej wag θ: spadek gradientu powtarza θ ← θ − η ∇L(θ) — krok o wielkości η w tym kierunku, w którym funkcja straty L spada najszybciej. To wspinacz odwrócony do góry nogami, który zamiast najwyższego szczytu szuka najniższej doliny — i zmaga się z tymi samymi problemami: z minimami lokalnymi i płaskowyżami.

12. Podsumowanie

• Problem przeszukiwania to szóstka (S, s₀, A, T, G, c). Rozwiązanie to ścieżka w grafie stanów, rozwiązanie optymalne — najtańsze z nich.
• Algorytmy różnią się tylko tym, który stan wybierają z brzegu: kolejka (BFS), stos (DFS), najmniejsze g (UCS), najmniejsze h (zachłanne), najmniejsze g + h (A*).
• BFS znajduje najmniej kroków, UCS najniższy koszt, A* najniższy koszt, badając przy tym najmniej — o ile ma spójną heurystykę.
• Kiedy nie chodzi o ścieżkę, lecz o wynik, wkracza przeszukiwanie lokalne — a stąd już tylko krok do spadku gradientu i uczenia maszynowego.

Chcesz wypróbować algorytmy na własnej skórze? Poproś agenta AI o napisanie własnej wizualizacji — a potem poszukaj w kodzie tej jednej linijki, którą się od siebie różnią.

Masz inne zdanie? Napisz na support@coden-app.com.