V informatike má vyhľadávanie na strome 2 spôsoby implementácie - do hĺbky a do šírky. Ale načo nám je?
Napríklad keď potrebujeme v tomto strome nájist číslo, vždy musíme nejaké použiť. Chcete praktickejšie využitie? Čo tak pri hľadaní potenciálnych obetí v uličkách mesta!
Ako funguje? Ukážeme si to na nasledujúcom príklade.
A tu ako vždy prichádzajú na radu zombíci! Ako aj tá rozumná časť populácie predpokladala
na pozemšťanov udrela zombie apokalypsa. Tí inteligentnejší mali už dávno pripravenú tašku s vodou a energickými tyčinkami, poprípade aj
niakú tú zbraň v podobe katany alebo mačety a samozrejmosťou je snáď aj únikový plán do bezpečných zón.
Kto sa smeje naposledy, toho zožere zombie...
Obyčajní neverníci ostali na pospas osudu a ako to býva karta sa obrátila a pripravení nerdi sa už v teplúčku a bezpečí smejú tým, ktorí ich
považovali za bláznov. Zombíci pojedli všetkých žívých ktorých našli pohybovať sa po vonku a najivná časť populácie ostala zamknutá doma s tým že sú predsa v bezpečí.
OMYL! Časom im začali dochádzať zásoby a už ani malý Jurko nechcel tretí deň po sebe jesť zavárané slivky, tak využili občania ešte pozostalej technológie a pomocou
mobilnej komunikácie sa dohodli že najváčšiu šancu prežiť majú, keď pôjdu spolu.
Panvicou už toho veľa nenarobíš
Skupinka ľudí, ktorím sa podarilo úspešne dostať na miesto stretnutia za pomoci provizórnych zbraní ako sú panvice
čoskoro zistila že stretnúť sa v meste nie je najlepší nápad vzhľadom na počet infikovaných premenených na zombie
(čo keby sa nad tým v minulosti aspoň na chvíľku zamysleli by dávno vedeli). Najlepší nápad samozrejme v tej chvíli padol
aby sa všetci rozutekali iným smerom a poschovávali sa v spletitých uličkách mesta. A tu prišli na radu ZOMBIE!
Nájdime si nejaké mäsko - vyhľadávanie do hĺbky
Predpokladajme na chvíľu absurdnú priam nepredstaviteľnú vec a to že zombie rozmýšľajú. Ja viem blboť, ale skúste si to predstaviť.
A naši zombie sa zhromaždia aby dohodli taktiku ako na ľudí. Keďže sú v meste môžeme predpokladať že ich je strááášne veľa. Ale ako čo najrýchlejšie tých ľudí pochytať?
Jeden zombie dostal nápad. Čo ak pôjdem vždy doľava a keď sa dostanem do slepej uličky vrárim sa o 1 späť a ak sa bude dať ísť doprava prezrem to tam rovnakým systémom,
ak sa nebude dať vrátim sa ešte o jedno späť a znova skontrolujem cestu doprava. Pôjdem vlastne vždy do najvačšej hĺbky uličiek ako to pôjde, preskúmam každú a vrátim sa.
Na obrázku môže čitateľ vidieť názorný príklad hľadania do hĺbky, kde farba číslice je v súlade s pohybom zombíka.
Poďme naraz, najeme sa viacerí a bude to rýchlejšie
Zombie kamarátom sa to však nepáčilo obzvlášť preto že by všetkých ľudí pojedol on sám a nič by im neostalo. Ale iný zombík mal lepší nápad! Je nás veľa.
Vždy keď bude viac možností kam ísť, rozdeľme sa na toľko skupín, koľko je možností kade ísť do šírky. Takto to prebehneme rýchlo a skoro kazdý z nás si pochutí.
Všetci zombie s tým súhlasili a vrhli sa hladní do uličiek. Požrali ľudí a zhodli sa na tom že vyhľadávanie do šírky bolo pre nich určite lepšie.
Pevne verím že z obrázku je krásne vidno ako algoritmus funguje.
Záver
Reálne naprogramovanie týchto algoritmov je asi najkrajšie a najjednoduchšie cez rekurziu, ale pre tých čo nemajú radi sami seba to môžu spraviť vyhľadávanie do hĺbky cez zásobník a
vyhľadávanie do šírky cez rad. Dúfam že čitateľ pochopil ako vyhľadávania fungujú a tiež že zombie apokalypsu netreba podceňovať, lebo budete zožraní!
Zdroje
Obrázky: Zdroj obrázkov bol » www.freepik.com
Informácie: moja hlava.
Blog
Komentuj
Komenty k blogu
Napíš svoj komentár