# Przeszukiwanie heurystyczne (A*)

EN: **Heuristic search (A*)** · id `astar`

Path: [AI Atlas](https://aiatlasgraph.com/llms.txt) › [Fundamenty i rozumowanie](https://aiatlasgraph.com/t/foundations.md) › [Przeszukiwanie i planowanie](https://aiatlasgraph.com/t/search.md) › Przeszukiwanie heurystyczne (A*)

## Description

- PL: A* porządkuje węzły według sumy kosztu dotychczasowej drogi i heurystycznego kosztu do celu. Dopuszczalna heurystyka zapewnia optymalność w przeszukiwaniu drzewa; w przeszukiwaniu grafu trzeba dodatkowo poprawnie obsługiwać znalezione tańsze dojścia do wcześniej odwiedzonych stanów.
- EN: A* orders nodes by the sum of path cost so far and heuristic cost to the goal. An admissible heuristic guarantees optimality in tree search; graph search must additionally handle newly found cheaper paths to previously visited states correctly.

## In one sentence

- PL: To szukanie drogi przez sprawdzanie najpierw tras, które wydają się prowadzić do celu najmniejszym kosztem.
- EN: This searches for a route by first exploring paths that appear to reach the goal at the lowest cost.

## Problem it solves

- PL: Sprawdzanie każdej możliwej trasy zabiera dużo czasu, zwłaszcza gdy większość prowadzi w nieprzydatnym kierunku.
- EN: Checking every possible route takes time, especially when most head in unhelpful directions.

## What it does

- PL: Dodaje koszt przebytej części drogi do szacowanego kosztu pozostałej i według tej sumy wybiera kolejne warianty do sprawdzenia.
- EN: It adds the cost already incurred to the estimated remaining cost, then uses that sum to choose which paths to examine next.

## Everyday example

- PL: Postać w grze szuka drogi do drzwi, omijając ściany i wybierając kolejne kroki według przebytej drogi oraz szacowanej odległości.
- EN: A game character seeks a route to a door, avoiding walls and choosing paths using travelled distance and an estimate of what remains.

## This concerns you if you…

- PL: szukasz trasy wśród wielu możliwych przejść
- PL: potrafisz oszacować koszt pozostały do osiągnięcia celu
- EN: search for a route among many possible paths
- EN: can estimate the remaining cost of reaching the goal

## Keywords

admissible heuristics · consistent heuristics · greedy best-first search · weighted A* · priority queues

## How it works

- PL: Kolejka priorytetowa porządkuje stany według kosztu przebytej ścieżki i heurystycznego kosztu do celu. Po znalezieniu tańszej drogi aktualizuje się zapis, a odpowiednia heurystyka i obsługa powrotów pozwalają zachować optymalność.
- EN: A priority queue orders states by accumulated path cost plus estimated remaining cost. Cheaper paths update records, and suitable heuristics with correct reopening preserve optimality.

## Limits

- PL: Heurystyka zawyżająca koszt może utracić gwarancję optymalności. Niespójna wymaga poprawnej obsługi ponownych odwiedzin, a duży frontier zwiększa zużycie pamięci.
- EN: Overestimating heuristics can lose optimality guarantees. Inconsistent heuristics require correct reopening, while large frontiers increase memory use.

## Key terms

- PL: **heurystyka dopuszczalna**: Ocena pozostałego kosztu, która nie przekracza kosztu rzeczywistego.
- PL: **heurystyka spójna**: Ocena spełniająca lokalny warunek zgodności z kosztami przejść.
- EN: **admissible heuristic**: A remaining-cost estimate that never exceeds actual cost.
- EN: **consistent heuristic**: An estimate satisfying a local consistency condition with transition costs.

## Know first

- [Przeszukiwanie ślepe (BFS, DFS) (Uninformed search (BFS, DFS, uniform-cost))](https://aiatlasgraph.com/t/uninformedsearch.md)

## Examples

- PL: A* · heurystyka dopuszczalna · przeszukiwanie zachłanne · wyznaczanie tras
- EN: A* · admissible heuristic · greedy best-first · route finding

## Related topics

Untyped, symmetric "see also" links.

- [Klasyczne planowanie trajektorii (Classical trajectory planning)](https://aiatlasgraph.com/t/rulebasedplanning.md)
- [Siatki nawigacyjne i odnajdywanie drogi (Navigation meshes and pathfinding)](https://aiatlasgraph.com/t/navmesh.md)

## Sources

- [Berkeley CS188 · Introduction to Artificial Intelligence (Fall 2025)](<https://inst.eecs.berkeley.edu/~cs188/fa25/>) `cs188fa25` · by Emma Pierson, Peyrin Kao (prowadzący)
- [Russell & Norvig · Artificial Intelligence: A Modern Approach, 4th ed. — table of contents](<https://aima.cs.berkeley.edu/>) `aima4` · by Stuart Russell, Peter Norvig

---

AI Atlas revision 122 (2026-10-30) · HTML: https://aiatlasgraph.com/t/astar · index: https://aiatlasgraph.com/llms.txt · everything: https://aiatlasgraph.com/llms-full.txt · updated 2026-10-30