Všetko, čo potrebujete vedieť o algoritme vyhľadávania prvého rozsahu



V tomto blogu o algoritme vyhľadávania prvého šírenia sa budeme zaoberať logikou metód prechádzania grafov a porozumieme ich fungovaniu.

Metódy prechodu grafu ma vždy dosť fascinovali. Metódy prechodu majú od skutočnej rovnocennej komunikácie až po hľadanie najbližších reštaurácií a kaviarní pomocou GPS pestrú škálu aplikácií v scenári reálneho sveta. V tomto blogu o Algoritme hľadania prvého šírky sa budeme zaoberať logikou metód prechádzania grafov a pomocou príkladov pochopíme fungovanie algoritmu vyhľadávania Šírka prvého vyhľadávania.

Ak chcete získať podrobné informácie o umelej inteligencii a strojovom učení, môžete sa zaregistrovať naživo od spoločnosti Edureka s nepretržitou podporou a doživotným prístupom.





Tu je zoznam tém, ktoré budú v tomto blogu:

  1. Úvod do grafu Traversal
  2. Čo je hľadanie na šírku?
  3. Pochopenie algoritmu vyhľadávania na šírku s príkladom
  4. Šírka prvého vyhľadávacieho algoritmu pseudokód
  5. Aplikácie vyhľadávania na šírku

Úvod do grafu Traversal

Proces návštevy a preskúmania grafu na spracovanie sa nazýva priechod grafu. Aby sme boli konkrétnejší, ide o to navštíviť a preskúmať každý vrchol a hranu v grafe tak, aby boli všetky vrcholy preskúmané presne raz.



To znie jednoducho! Má to však háčik.

Existuje niekoľko techník prechodu grafov, ako napríklad vyhľadávanie na šírku, vyhľadávanie na prvom mieste atď. Výzvou je použiť graf traverzová technika, ktorá je najvhodnejšia na riešenie konkrétneho problému. Týmto sa dostávame k technike vyhľadávania na šírku.

Čo je algoritmus vyhľadávania prvého šírky?

Algoritmus hľadania na šírku je technikou prechádzania grafu, pri ktorej vyberiete náhodný počiatočný uzol (zdrojový alebo koreňový uzol) a začnete prechádzať grafom po vrstvách tak, aby boli navštívené a preskúmané všetky uzly a ich príslušné podradené uzly.



Predtým, ako sa posunieme ďalej a porozumieme príkladu Breadth-First Search, oboznámme sa s dvoma dôležitými výrazmi súvisiacimi s prechodom grafu:

Traverz grafu - algoritmus prvého vyhľadávania šírky - Edureka

  1. Návšteva uzla: Ako naznačuje názov, návšteva uzla znamená navštíviť alebo vybrať uzol.
  2. Preskúmanie uzla: Skúmanie susedné uzly (dcérske uzly) vybraného uzla.

Pre lepšie pochopenie použite vyššie uvedený obrázok.

Pochopenie algoritmu vyhľadávania na šírku s príkladom

Algoritmus hľadania na šírku sleduje pri riešení problému jednoduchý prístup založený na úrovniach. Zvážte nižšie uvedený binárny strom (ktorý je grafom). Naším cieľom je prechádzať grafom pomocou algoritmu vyhľadávania na šírku ako prvý.

Predtým, ako začneme, musíte byť oboznámení s hlavnou dátovou štruktúrou zahrnutou do algoritmu Breadth-First Search.

Fronta je abstraktná dátová štruktúra, ktorá sa riadi metodikou First-In-First-Out (k najskôr vloženým údajom sa bude pristupovať najskôr). Je otvorený na oboch koncoch, kde jeden koniec sa vždy používa na vkladanie údajov (zaradenie do fronty) a druhý koniec sa používa na odstránenie údajov (zaradenie).

Teraz sa pozrime na kroky spojené s prechádzaním grafu pomocou vyhľadávania na šírku:

Krok 1: Zúčastnite sa prázdneho frontu.

Krok 2: Vyberte počiatočný uzol (návšteva uzla) a vložte ho do frontu.

Krok 3: Za predpokladu, že front nie je prázdny, vyberte uzol z frontu a vložte jeho podradené uzly (skúmajúce uzol) do frontu.

Krok 4: Vytlačte extrahovaný uzol.

Nerobte si starosti, ak budete zmätení, pochopíme to na príklade.

Pozrite sa na nasledujúci graf, na prechádzanie grafom použijeme algoritmus vyhľadávania v prvom rade.

čo je nemenný objekt v jave

V našom prípade priradíme uzol „a“ ako koreňový uzol a začneme prechádzať smerom nadol a vykonáme kroky uvedené vyššie.

Vyššie uvedený obrázok zobrazuje proces end-to-end vyhľadávacieho algoritmu šírky prvého. Dovoľte mi, aby som to vysvetlil hlbšie.

  1. Priraďte ako koreňový uzol písmeno „a“ a vložte ho do frontu.
  2. Extrahujte uzol „a“ z frontu a vložte podradené uzly znakov „a“, teda „b“ a „c“.
  3. Vytlačiť uzol „a“.
  4. Poradie nie je prázdne a má uzol „b“ a „c“. Pretože ‘b’ je prvý uzol vo fronte, rozoberme ho a vložme podradené uzly ‘b’, t. J. Uzol ‘d’ a ‘e’.
  5. Tieto kroky opakujte, kým sa front nevyprázdni. Upozorňujeme, že uzly, ktoré sú už navštívené, by sa nemali pridávať do poradia ešte raz.

Teraz sa pozrime na pseudokód algoritmu Breadth-First Search.

Šírka prvého vyhľadávacieho algoritmu pseudokód

Tu je pseudokód na implementáciu algoritmu vyhľadávania na šírku:

Vstup: s ako zdrojový uzol BFS (G, s) umožňuje Q zaradiť sa do frontu. Q.enqueue (s) označí s ako navštívené, zatiaľ čo (Q nie je prázdne) v = Q.dequeue () pre všetkých susedov w z v v grafe G, ak w nie je navštívené Q.enqueue (w) označí w ako navštívené

Vo vyššie uvedenom kóde sa vykonávajú nasledujúce kroky:

  1. (G, s) je vstup, tu G je graf a s je koreňový uzol
  2. Vytvorí sa fronta „Q“ a inicializuje sa so zdrojovým uzlom „s“
  3. Všetky podradené uzly „s“ sú označené
  4. Extrahujte „s“ z frontu a navštívte podradené uzly
  5. Spracujte všetky podradené uzly v
  6. Uloží w (podriadené uzly) v Q na ďalšiu návštevu jeho podriadených uzlov
  7. Pokračujte, kým nebude „Q“ prázdny

Predtým, ako blog uzavrieme, pozrime sa na niektoré aplikácie algoritmu Breadth-First Search.

Aplikácie algoritmu vyhľadávania na šírku

Vyhľadávanie na šírku je jednoduchá metóda prechodu grafu, ktorá má prekvapivú škálu aplikácií. Tu je niekoľko zaujímavých spôsobov, ako sa používa vyhľadávanie chleba:

Crawlers in search Engines: Vyhľadávanie na šírku je jedným z hlavných algoritmov používaných na indexovanie webových stránok. Algoritmus začne prechádzať zo zdrojovej stránky a sleduje všetky odkazy spojené so stránkou. Tu sa bude každá webová stránka považovať za uzol v grafe.

GPS navigačné systémy: Vyhľadávanie na šírku je jedným z najlepších algoritmov používaných na vyhľadanie susedných miest pomocou systému GPS.

Nájdite najkratšiu cestu a strom minimálneho rozsahu pre nevážený graf: Pokiaľ ide o nevážený graf, výpočet najkratšej cesty je dosť jednoduchý, pretože najkratšou cestou je zvoliť cestu s najmenším počtom hrán. Vyhľadávanie na šírku to môže umožniť prechodom minimálneho počtu uzlov počnúc od zdrojového uzla. Podobne pre spaning tree môžeme použiť jednu z dvoch metód Berseth-First Search alebo Depth-first traversal methods to find a spanning tree.

Vysielanie: Sieť využíva na komunikáciu to, čo nazývame pakety. Tieto pakety používajú metódu prechodu na dosiahnutie rôznych sieťových uzlov. Jednou z najbežnejšie používaných metód prechodu je Breadth-First Search. Používa sa ako algoritmus, ktorý sa používa na komunikáciu vysielaných paketov cez všetky uzly v sieti.

Sieť typu peer to peer: Vyhľadávanie šírky na prvom mieste je možné použiť ako metódu prechodu na vyhľadanie všetkých susedných uzlov v sieti Peer to Peer. Napríklad BitTorrent používa Breadth-First Search pre komunikáciu peer to peer.

Takže to bolo všetko o fungovaní algoritmu Breadth-First Search. Teraz, keď viete, ako prechádzať grafmi, som si istý, že by ste sa chceli dozvedieť viac. Tu je niekoľko relevantných blogov, ktoré vás zaujmú:

  1. Úvod do reťazcov Markov s príkladmi - reťazce Markov s Pythonom

Týmto sa dostávame na koniec tohto blogu. Ak máte akékoľvek otázky týkajúce sa tejto témy, zanechajte prosím komentár nižšie a my sa vám ozveme.

Ak sa chcete prihlásiť na úplný kurz umelej inteligencie a strojového učenia, má Edureka špeciálne kurátora vďaka čomu ovládate techniky, ako je supervidované učenie, nekontrolované učenie a spracovanie prirodzeného jazyka. Zahŕňa školenie o najnovších pokrokoch a technických prístupoch v oblasti umelej inteligencie a strojového učenia, ako sú napríklad Deep Learning, Graphical Models a Reinforcement Learning.