Alt du trenger å vite om bredden første søkealgoritmen



I denne bloggen på Breadth-First Search Algorithm, vil vi diskutere logikken bak grafgjennomgangsmetoder og forstå hvordan den fungerer.

Metoder for grafovergang har alltid ganske fascinert meg. Fra å utføre effektiv peer-to-peer-kommunikasjon til å finne de nærmeste restaurantene og kafeene ved hjelp av GPS, har traversal-metoder et variert sett med applikasjoner i den virkelige situasjonen. I denne bloggen på Breadth-First Search Algorithm, vil vi diskutere logikken bak grafgjennomgangsmetoder og bruke eksempler for å forstå hvordan Breadth-First Search-algoritmen fungerer.

For å få inngående kunnskap om kunstig intelligens og maskinlæring, kan du registrere deg for live av Edureka med 24/7 support og levetidstilgang.





Her er en liste over emner som blir dekket i denne bloggen:

  1. Introduksjon til grafgjennomgang
  2. Hva er Breadth-First Search?
  3. Forstå Breadth-First Search-algoritmen med et eksempel
  4. Bredde-første søkealgoritme Pseudokode
  5. Anvendelser av bredde-første søk

Introduksjon til grafgjennomgang

Prosessen med å besøke og utforske en graf for behandling kalles graph traversal. For å være mer spesifikk handler det om å besøke og utforske hvert toppunkt og kant i en graf slik at alle toppunktene blir utforsket nøyaktig en gang.



Det høres enkelt ut! Men det er en fangst.

Det er flere grafkjøringsteknikker som Breadth-First Search, Depth First Search og så videre. Utfordringen er å bruke en graf traversal teknikk som er best egnet for å løse et bestemt problem. Dette bringer oss til teknikken Breadth-First Search.

Hva er algoritmen for bredeste søk?

Breadth-First Search-algoritmen er en grafkjøringsteknikk, hvor du velger en tilfeldig startnode (kilde eller rotnode) og begynner å krysse grafen lagvis på en slik måte at alle noder og deres respektive barn-noder blir besøkt og utforsket.



hvordan konvertere fra dobbelt til int java

Før vi går videre og forstår Breadth-First Search med et eksempel, la oss bli kjent med to viktige begreper relatert til grafgjennomgang:

Grafgjennomgang - Algoritme for første søk i bredde - Edureka

  1. Å besøke en node: Akkurat som navnet antyder, betyr å besøke en node å besøke eller velge en node.
  2. Utforske en node: Utforske tilstøtende noder (undernoder) til en valgt node.

Se figuren ovenfor for bedre å forstå dette.

Forstå bredden-første søkealgoritmen med et eksempel

Breadth-First Search-algoritmen følger en enkel, nivåbasert tilnærming for å løse et problem. Tenk på det binære treet nedenfor (som er en graf). Målet vårt er å krysse grafen ved hjelp av Breadth-First Search Algorithm.

Før vi kommer i gang, må du være kjent med hoveddatastrukturen som er involvert i Breadth-First Search-algoritmen.

En kø er en abstrakt datastruktur som følger First-In-First-Out-metoden (data som settes inn først, får du tilgang til først). Den er åpen i begge ender, hvor den ene enden alltid brukes til å sette inn data (enqueue) og den andre brukes til å fjerne data (dequeue).

La oss nå se på trinnene som er involvert i å krysse en graf ved hjelp av Breadth-First Search:

Trinn 1: Ta en tom kø.

Steg 2: Velg en startnode (besøker en node) og sett den inn i køen.

Trinn 3: Forutsatt at køen ikke er tom, trekk ut noden fra køen og sett inn undernodene (utforsker en node) i køen.

Trinn 4: Skriv ut den ekstraherte noden.

Ikke bekymre deg hvis du er forvirret, vi vil forstå dette med et eksempel.

Ta en titt på grafen nedenfor, vi bruker Breadth-First Search-algoritmen til å krysse gjennom grafen.

I vårt tilfelle tildeler vi node ‘a’ som rotnode og begynner å krysse nedover og følge trinnene nevnt ovenfor.

Ovenstående bilde skildrer end-to-end prosessen med Algoritme for bredde-første søk. La meg forklare dette nærmere.

  1. Tildel ‘a’ som rotnode og sett den inn i køen.
  2. Trekk ut node 'a' fra køen, og sett inn undernodene til 'a', dvs. 'b' og 'c'.
  3. Skriv ut node ‘a’.
  4. Køen er ikke tom og har node ‘b’ og ‘c’. Siden ‘b’ er den første noden i køen, la oss trekke den ut og sette inn undernodene til ‘b’, dvs. node ‘d’ og ‘e’.
  5. Gjenta disse trinnene til køen blir tom. Merk at nodene som allerede er besøkt ikke skal legges til køen en gang til.

La oss nå se på pseudokoden til algoritmen Breadth-First Search.

Bredde-første søkealgoritme Pseudokode

Her er pseudokoden for å implementere algoritmen for bredeste søk:

Inngang: s som kildenode BFS (G, s) lar Q stå i kø. Q.queque (s) merke s som besøkt mens (Q er ikke tom) v = Q.queque () for alle naboer w av v i graf G hvis w ikke besøkes Q.queque (w) mark w som besøkt

I koden ovenfor utføres følgende trinn:

  1. (G, s) er inngang, her er G grafen og s er rotnoden
  2. En kø 'Q' opprettes og initialiseres med kildenoden 's'
  3. Alle barn noder av ‘s’ er merket
  4. Trekk ut ‘s’ fra køen og besøk barnenodene
  5. Behandle alle barneknuter i v
  6. Lagrer w (barnekoder) i Q for å besøke barnekodene ytterligere
  7. Fortsett til 'Q' er tømme

Før vi avslutter bloggen, la oss se på noen applikasjoner av Breadth-First Search-algoritmen.

Anvendelser av bredde-første søkealgoritme

Breadth-first Search er en enkel graf-traversal-metode som har et overraskende utvalg av applikasjoner. Her er noen interessante måter Bread-First Search brukes på:

Crawlere i søkemotorer: Breadth-First Search er en av hovedalgoritmene som brukes til indeksering av websider. Algoritmen begynner å krysse fra kildesiden og følger alle koblingene som er tilknyttet siden. Her vil hver webside bli sett på som en node i en graf.

GPS-navigasjonssystemer: Breadth-First Search er en av de beste algoritmene som brukes til å finne nærliggende steder ved hjelp av GPS-systemet.

Finn den korteste stien og minimum spennende tre for en uvektet graf: Når det gjelder en uvektet graf, er det ganske enkelt å beregne den korteste banen, siden ideen bak den korteste banen er å velge en sti med minst antall kanter. Bredde-første søk kan tillate dette ved å krysse et minimum antall noder som starter fra kildenoden. På samme måte kan vi for et spennende tre bruke en av de to, Breadth-First Search eller Depth-first traversal metoder for å finne et spennende tre.

Kringkasting: Nettverk bruker det vi kaller som pakker for kommunikasjon. Disse pakkene følger en traversal metode for å nå forskjellige nettverksnoder. En av de mest brukte traversalmetodene er Breadth-First Search. Den blir brukt som en algoritme som brukes til å kommunisere kringkastede pakker over alle nodene i et nettverk.

Peer to Peer Networking: Breadth-First Search kan brukes som en traversal metode for å finne alle noder i et Peer to Peer-nettverk. For eksempel bruker BitTorrent Breadth-First Search for peer to peer-kommunikasjon.

Så alt handlet om hvordan Breadth-First Search-algoritmen fungerer. Nå som du vet hvordan du skal krysse grafer, er jeg sikker på at du er nysgjerrig på å lære mer. Her er noen relevante blogger for å holde deg interessert:

  1. Introduksjon til Markov-kjeder med eksempler - Markov-kjeder med python

Med dette kommer vi til slutten av denne bloggen. Hvis du har spørsmål angående dette emnet, kan du legge igjen en kommentar nedenfor, så kommer vi tilbake til deg.

Hvis du ønsker å melde deg på et komplett kurs om kunstig intelligens og maskinlæring, har Edureka en spesiell kurat som vil gjøre deg dyktig i teknikker som Supervised Learning, Unsupervised Learning, and Natural Language Processing. Det inkluderer opplæring i de siste fremskrittene og tekniske tilnærmingene innen kunstig intelligens og maskinlæring som dyp læring, grafiske modeller og forsterkningslæring.