Procházení stromu

Technology
12 hours ago
8
4
2
Avatar
Author
Albert Flores

Procházení stromu (také prohledávání stromu) je úloha z oblasti algoritmů, jejíž podstatou je postupné „navštívení“ všech položek datového stromu. Protože na tento strom může být nahlíženo jako na graf, jedná se zároveň o úlohu z teorie grafů.

Různé přístupy k procházení stromu jsou obvykle ilustrovány na binárních stromech, neboť rozšíření na další stromy bývá poměrně přímočaré.

Dva základní přístupy k procházení stromu jsou prohledávání do hloubky a prohledávání do šířky, přičemž oba mají různé podvarianty (zleva, zprava, …). Kromě pořadí, v kterém jsou vrcholy navštíveny, se také liší použitím různých pomocných datových struktur. +more Prohledávání do hloubky je přirozeně rekurzivní proces, při kterém je přirozené použití zásobníku, ať už definovaném v programu explicitně, nebo implicitním využitím zásobníku volání. Naopak při prohledávání do šířky je typicky využívána fronta.

Pokud není cílem projít celý strom, ale jen najít určitou hodnotu, může být strom předem sestaven speciálním způsobem jako vyhledávací strom (nejčastěji binární vyhledávací strom) - v něm se pak jako efektivní uplatňují speciální varianty algoritmů. Jiné speciální varianty algoritmů se uplatňují při prohledávání stavového prostoru (stavový prostor mívá rovněž charakter stromu). +more V oblasti umělé inteligence v počítačových hrách jsou úspěšné heuristické algoritmy, například prohledávání stromu metodou Monte Carlo odvozené od obecné myšlenky metody Monte Carlo.

5 min read
Share this post:
Like it 8

Leave a Comment

Please, enter your name.
Please, provide a valid email address.
Please, enter your comment.
Enjoy this post? Join Cesko.wiki
Don’t forget to share it
Top