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. Kliknutím a tažením myši nakreslíš zdi. 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á výrazně méně možností — na volné ploše i řádově. 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 far fewer options — on open ground even by an order of magnitude. 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 na políčko, které 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í vzdálenosti (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á výrazně méně polí — chytrá heuristika tedy zmenší prohledávaný prostor. Na volné ploše (zkus „Smazat zdi“) je to i řádově méně; zdi, které heuristiku „oklamou“, náskok zmenšují. Hladový postup je nejúspornější, ale za cenu toho, že cesta nemusí být nejkratší. The point: both BFS and A* find an equally long (shortest) path, but A* explores far fewer cells — a smart heuristic shrinks the search space. On open ground (try "Clear walls") it's even an order of magnitude fewer; walls that "fool" the heuristic shrink the lead. Greedy is the most economical, but at the cost that its path may not be the shortest.