Vše, co potřebujete vědět o algoritmu pro vyhledávání prvního šíře

Metody procházení grafů mě vždy docela fascinovaly. Od efektivní komunikace typu peer to peer až po hledání nejbližších restaurací a kaváren pomocí GPS - metody procházení mají v reálném scénáři pestrou sadu aplikací. V tomto blogu o algoritmu vyhledávání v první šíři probereme logiku metod procházení grafů a na příkladech pochopíme fungování algoritmu vyhledávání v první šíři.

Chcete-li získat podrobné znalosti o umělé inteligenci a strojovém učení, můžete se zaregistrovat naživo od společnosti Edureka s nepřetržitou podporou a doživotním přístupem.

Zde je seznam témat, která budou v tomto blogu:

1. Úvod do grafu Traversal
2. Co je vyhledávání na šířku?
3. Pochopení algoritmu prohledávání do šířky s příkladem
4. Šířka prvního vyhledávacího algoritmu Pseudokód
5. Aplikace vyhledávání na šířku

Úvod do grafu Traversal

Proces návštěvy a zkoumání grafu pro zpracování se nazývá procházení grafu. Přesněji řečeno, jde o návštěvu a zkoumání každého vrcholu a hrany v grafu, takže všechny vrcholy jsou prozkoumány přesně jednou.

To zní jednoduše! Ale má to háček.

Existuje několik technik procházení grafů, jako je Breadth-First Search, Depth First Search a tak dále. Úkolem je použít graf traverzová technika, která je nejvhodnější pro řešení konkrétního problému. Tím se dostáváme k technice vyhledávání na šířku.

Co je algoritmus vyhledávání první šířky?

Algoritmus Breadth-First Search je technika procházení grafů, při které vyberete náhodný počáteční uzel (zdrojový nebo kořenový uzel) a začnete procházet po vrstvě grafu takovým způsobem, aby byly navštíveny a prozkoumány všechny uzly a jejich příslušné podřízené uzly.

Než se přesuneme dále a pochopíme Breadth-First Search na příkladu, pojďme se seznámit se dvěma důležitými pojmy souvisejícími s procházením grafu:

1. Návštěva uzlu: Stejně jako název napovídá, návštěva uzlu znamená návštěvu nebo výběr uzlu.
2. Prozkoumání uzlu: Prozkoumejte sousední uzly (podřízené uzly) vybraného uzlu.

Viz výše uvedený obrázek, abyste tomu lépe porozuměli.

Porozumění algoritmu pro vyhledávání v první šíři s příkladem

Algoritmus vyhledávání první šířky se při řešení problému řídí jednoduchým přístupem založeným na úrovních. Zvažte níže uvedený binární strom (což je graf). Naším cílem je procházet graf pomocí algoritmu pro vyhledávání první šířky.

Než začneme, musíte být obeznámeni s hlavní datovou strukturou zapojenou do algoritmu Breadth-First Search.

Fronta je abstraktní datová struktura, která se řídí metodikou First-In-First-Out (k datům vloženým jako první se přistupuje jako první). Je otevřený na obou koncích, kde jeden konec se vždy používá k vložení dat (zařazení do fronty) a druhý se používá k odebrání dat (zařazení do fronty).

Pojďme se nyní podívat na kroky při procházení grafu pomocí vyhledávání na šířku:

Krok 1: Vezměte prázdnou frontu.

Krok 2: Vyberte počáteční uzel (návštěva uzlu) a vložte jej do fronty.

Krok 3: Za předpokladu, že fronta není prázdná, extrahujte uzel z fronty a vložte její podřízené uzly (zkoumající uzel) do fronty.

Krok 4: Vytiskněte extrahovaný uzel.

Nebojte se, pokud jste zmatení, pochopíme to na příkladu.

Podívejte se na níže uvedený graf, k procházení grafem použijeme algoritmus Breadth-First Search.

jak spustit python atomu

V našem případě přiřadíme uzel „a“ jako kořenový uzel a začneme procházet dolů a postupujte podle výše uvedených kroků.

Výše uvedený obrázek zobrazuje proces end-to-end algoritmu pro vyhledávání v první šíři. Dovolte mi to vysvětlit podrobněji.

1. Přiřaďte jako kořenový uzel „a“ a vložte jej do fronty.
2. Extrahujte uzel „a“ z fronty a vložte podřízené uzly „a“, tj. „B“ a „c“.
3. Tisk uzlu „a“.
4. Fronta není prázdná a má uzel „b“ a „c“. Protože „b“ je první uzel ve frontě, extrahujeme jej a vložme podřízené uzly „b“, tj. Uzel „d“ a „e“.
5. Tyto kroky opakujte, dokud se fronta nevyprázdní. Všimněte si, že uzly, které jsou již navštíveny, by neměly být přidány do fronty znovu.

Nyní se podívejme na pseudokód algoritmu Breadth-First Search.

Šířka prvního vyhledávacího algoritmu Pseudokód

Zde je pseudokód pro implementaci algoritmu pro vyhledávání v první šíři:

Vstup: s jako zdrojový uzel BFS (G, s) umožňuje Q být ve frontě. Q.enqueue (s) označí jako navštívené, zatímco (Q není prázdné) v = Q.dequeue () pro všechny sousedy w v v v grafu G, pokud w není navštíveno Q.enqueue (w) označí w jako navštívené

Ve výše uvedeném kódu jsou provedeny následující kroky:

1. (G, s) je vstup, zde G je graf a s je kořenový uzel
2. Vytvoří se fronta „Q“ a inicializuje se zdrojovým uzlem „s“
3. Všechny podřízené uzly „s“ jsou označeny
4. Extrahujte čísla z fronty a navštivte podřízené uzly
5. Zpracujte všechny podřízené uzly v
6. Uloží w (podřízené uzly) v Q k další návštěvě jeho podřízených uzlů
7. Pokračujte, dokud nebude „Q“ prázdný

Než blog uzavřeme, podívejme se na některé aplikace algoritmu Breadth-First Search.

Aplikace algoritmu pro vyhledávání první šířky

Šířka první vyhledávání je jednoduchá metoda procházení grafů, která má překvapivou škálu aplikací. Zde je několik zajímavých způsobů, jak se používá vyhledávání chleba:

Prohledávače ve vyhledávačích: Šířka-první vyhledávání je jedním z hlavních algoritmů používaných pro indexování webových stránek. Algoritmus začíná procházet ze zdrojové stránky a sleduje všechny odkazy spojené se stránkou. Zde bude každá webová stránka považována za uzel v grafu.

GPS navigační systémy: Breadth-First Search je jedním z nejlepších algoritmů používaných k vyhledání sousedních míst pomocí systému GPS.

Najděte nejkratší cestu a minimální rozpětí stromu pro nevážený graf: Pokud jde o nevážený graf, výpočet nejkratší cesty je docela jednoduchý, protože myšlenkou nejkratší cesty je vybrat cestu s nejmenším počtem hran. Šířka-první vyhledávání to může umožnit procházením minimálního počtu uzlů počínaje od zdrojového uzlu. Podobně pro překlenovací strom můžeme k vyhledání překlenovacího stromu použít jednu ze dvou metod prohledávání Breadth-First Search nebo Depth-first Traversal.

Vysílání: Síť využívá pro komunikaci to, co nazýváme pakety. Tyto pakety používají metodu procházení k dosažení různých síťových uzlů. Jednou z nejčastěji používaných metod procházení je Breadth-First Search. Používá se jako algoritmus, který se používá ke komunikaci vysílaných paketů napříč všemi uzly v síti.

Síť peer to peer: Breadth-First Search lze použít jako metodu procházení k vyhledání všech sousedních uzlů v síti Peer to Peer. Například BitTorrent používá Breadth-First Search pro komunikaci peer to peer.

Takže to bylo všechno o fungování algoritmu Breadth-First Search. Nyní, když víte, jak procházet grafy, jsem si jistý, že se chcete dozvědět více. Zde je několik relevantních blogů, které vás zaujmou:

3. Úvod do Markovových řetězců s příklady - Markovovy řetězce s Pythonem

Tímto se dostáváme na konec tohoto blogu. Máte-li jakékoli dotazy týkající se tohoto tématu, zanechte prosím níže uvedený komentář a my se vám ozveme.

Pokud se chcete zaregistrovat na kompletní kurz umělé inteligence a strojového učení, Edureka má speciálně připravený kurz díky nimž zvládnete techniky, jako je supervidované učení, nekontrolované učení a zpracování přirozeného jazyka. Zahrnuje školení o nejnovějších pokrokech a technických přístupech v oblasti umělé inteligence a strojového učení, jako je Deep Learning, Graphical Models a Reinforcement Learning.