V prvním příkladu jsme viděli, že projít všechny možnosti nejde. Tady ukazujeme, jak se v obřím prostoru hledá chytře. Stejná mřížka, stejný cíl — ale podívej se, kolik políček musí každý postup prozkoumat. Klikni a táhni myší pro kreslení zdí. In the first example we saw that going through every possibility is impossible. Here we show how to search a huge space cleverly. Same grid, same goal — but look how many cells each method has to explore. Click and drag the mouse to draw walls.
Co to jeWhat it is Bludiště na mřížce a čtyři způsoby, jak v něm najít cestu: náhodné tápání, hladový postup, BFS a A*. Stejný cíl, ale každý prohledá jiný počet políček.A grid maze and four ways to find a path through it: random wandering, a greedy approach, BFS and A*. Same goal, but each explores a different number of cells.
Co zkusitWhat to try Myší nakresli zdi a spusť postupně všechny čtyři postupy. Sleduj, kolik políček každý obarví (= musí prozkoumat), a srovnej čísla v tabulce dole.Draw walls with the mouse and run all four methods in turn. Watch how many cells each one colors in (= has to explore), and compare the numbers in the table below.
Proč je to důležitéWhy it matters V příkladu 1 jsme viděli, že „zkusit všechno" nejde. Tady je řešení: chytré hledání s heuristikou (odhadem směru k cíli) prozkoumá řádově méně možností. Tak se hrubá síla nahrazuje rozumem.Example 1 showed that “trying everything” is impossible. Here is the fix: smart search with a heuristic (a guess of the direction toward the goal) explores orders of magnitude fewer options. This is how brute force gives way to reasoning.
| PostupMethod | Prozkoumáno políCells explored | Délka cestyPath length |
|---|
U prohledávání nás zajímají tři věci: úplnost (najde cestu, pokud existuje?), optimalita (je cesta nejkratší?) a cena (kolik polí musel prozkoumat). V tom se postupy liší — porovnej je s čísly v tabulce výše. In search we care about three things: completeness (does it find a path if one exists?), optimality (is the path the shortest?) and cost (how many cells it had to explore). The methods differ in these — compare them with the numbers in the table above.
Z aktuálního políčka skočí na náhodného souseda. Nemá paměť ani cíl — jen bloudí. Obdoba „hrubé síly" z prvního příkladu. From the current cell it jumps to a random neighbor. It has no memory and no goal — it just wanders. Like the "brute force" of the first example.
Vždy jde tam, co se zdá nejblíž cíli (vzdušná vzdálenost). Řídí se jen odhadem, kolik zbývá — vůbec ho nezajímá, kolik už ušel. It always goes where it seems closest to the goal (straight-line distance). It's guided only by the estimate of what remains — it doesn't care how far it has already come.
Prohledává systematicky po vrstvách — nejdřív všechny sousedy, pak jejich sousedy… Postupuje rovnoměrně do všech stran. It searches systematically in layers — first all neighbors, then their neighbors… It spreads evenly in all directions.
Spojí to nejlepší z obou: sečte ušlou vzdálenost a odhad zbývající (heuristiku). Míří k cíli, ale nezapomíná hlídat délku cesty. It combines the best of both: it adds the distance travelled and the estimate of what remains (the heuristic). It heads for the goal but keeps an eye on path length.
Pointa: BFS i A* najdou stejně dlouhou (nejkratší) cestu, ale A* k tomu prozkoumá řádově méně polí — chytrá heuristika tedy dramaticky zmenší prohledávaný prostor. Hladový je nejúspornější, ale za cenu, že cesta nemusí být nejkratší. The point: both BFS and A* find an equally long (shortest) path, but A* explores an order of magnitude fewer cells — a smart heuristic dramatically shrinks the search space. Greedy is the most economical, but at the cost that its path may not be the shortest.