Lahat ng Kailangan Mong Malaman Tungkol sa Lawak ng Unang Algorithm sa Paghahanap

Ang mga pamamaraan ng Graph Traversal ay palaging nakakaakit sa akin. Mula sa pagsasagawa ng mabisang komunikasyon ng peer to peer hanggang sa paghahanap ng pinakamalapit na mga restawran at cafe gamit ang GPS, ang mga pamamaraang traversal ay may iba-ibang hanay ng mga aplikasyon sa senaryong totoong mundo. Sa blog na ito sa Breadth-First Search Algorithm, tatalakayin namin ang lohika sa likod ng mga pamamaraan ng graph traversal at gumamit ng mga halimbawa upang maunawaan ang pagtatrabaho ng Breadth-First Search algorithm.

Upang makakuha ng malalim na kaalaman sa Artipisyal na Katalinuhan at Pag-aaral ng Makina, maaari kang magpatala nang live ni Edureka na may suporta na 24/7 at habang-buhay na pag-access.

Narito ang isang listahan ng mga paksa saklaw sa blog na ito:

1. Panimula Sa Graph Traversal
2. Ano ang Breadth-First Search?
3. Pag-unawa sa algorithm ng Breadth-First Search na may isang halimbawa
4. Breadth-First Search Algorithm Pseudocode
5. Mga Aplikasyon Ng Breadth-First Search

Panimula Sa Graph Traversal

Ang proseso ng pagbisita at paggalugad ng isang graph para sa pagproseso ay tinatawag na graf traversal. Upang maging mas tiyak na ang lahat ay tungkol sa pagbisita at pagtuklas sa bawat tuktok at gilid sa isang graph na tulad ng lahat ng mga vertex ay ginalugad nang eksakto nang isang beses.

Parang simple yun! Ngunit mayroong isang catch.

Mayroong maraming mga diskarte sa traversal na grap tulad ng Breadth-First Search, Lalim na Unang Paghahanap at iba pa. Ang hamon ay ang paggamit ng isang grap pamamaraan ng traversal na pinakaangkop para sa paglutas ng isang partikular na problema. Dinadala tayo nito sa diskarteng Breadth-First Search.

Ano ang Algorithm ng Breadth-First Search?

Ang algorithm ng Breadth-First Search ay isang diskarteng dumadaan sa grap, kung saan pipiliin mo ang isang random na paunang node (pinagmulan o root node) at simulang daanan ang layer ng grap sa isang paraan na ang lahat ng mga node at kani-kanilang mga node ng bata ay binibisita at ginalugad.

Bago tayo lumipat nang higit pa at maunawaan ang Breadth-First Search na may isang halimbawa, pamilyar tayo sa dalawang mahahalagang term na nauugnay sa graf traversal:

1. Pagbisita sa isang node: Tulad ng iminumungkahi ng pangalan, ang pagbisita sa isang node ay nangangahulugang bisitahin o pumili ng isang node.
2. Paggalugad sa isang node: Pagtuklas sa mga katabing node (mga node ng bata) ng isang napiling node.

Sumangguni sa figure sa itaas upang mas maintindihan ito.

ano ang ginagawa ng bufferedreader sa java

Pag-unawa sa Breadth-First Search Algorithm na may isang halimbawa

Sinusundan ng Breadth-First Search algorithm ang isang simple, antas na batay sa diskarte upang malutas ang isang problema. Isaalang-alang ang ibabang puno ng binary (na kung saan ay isang grap). Ang aming hangarin ay upang daanan ang grap sa pamamagitan ng paggamit ng Breadth-First Search Algorithm.

Bago kami magsimula, dapat ay pamilyar ka sa pangunahing istraktura ng data na kasangkot sa Breadth-First Search algorithm.

Ang pila ay isang abstract na istraktura ng data na sumusunod sa pamamaraan ng First-In-First-Out (ang data na naipasok muna ay maa-access muna). Bukas ito sa magkabilang dulo, kung saan laging ginagamit ang isang dulo upang magsingit ng data (enqueue) at ang isa pa ay ginagamit upang alisin ang data (dequeue).

Tingnan natin ngayon ang mga hakbang na kasangkot sa pagtawid sa isang graph sa pamamagitan ng paggamit ng Breadth-First Search:

Hakbang 1: Kumuha ng isang Empty Queue.

Hakbang 2: Pumili ng isang panimulang node (pagbisita sa isang node) at ipasok ito sa Queue.

Hakbang 3: Sa kondisyon na ang pila ay hindi walang laman, kunin ang node mula sa Queue at ipasok ang mga node ng bata (paggalugad ng isang node) sa Queue.

Hakbang 4: I-print ang node na nakuha.

Huwag magalala kung nalilito ka, maiintindihan namin ito sa isang halimbawa.

Tingnan ang graph sa ibaba, gagamitin namin ang Breadth-First Search algorithm upang dumaan sa grap.

Sa aming kaso, magtatalaga kami ng node 'a' bilang root node at magsimulang dumaan pababa at sundin ang mga hakbang na nabanggit sa itaas.

Inilalarawan ng larawang nasa itaas ang end-to-end na proseso ng Breadth-First Search Algorithm. Hayaan mong ipaliwanag ko ito nang mas malalim.

Ang tutorial ng tutorial ay sunud-sunod

1. Magtalaga ng 'a' bilang root node at ipasok ito sa Queue.
2. I-extract ang node 'a' mula sa pila at ipasok ang mga node ng bata ng 'a', ibig sabihin, 'b' at 'c'.
3. I-print ang node na 'a'.
4. Ang pila ay hindi walang laman at may node na 'b' at 'c'. Dahil ang 'b' ay ang unang node sa pila, kunin natin ito at ipasok ang mga node ng bata ng 'b', ibig sabihin, node 'd' at 'e'.
5. Ulitin ang mga hakbang na ito hanggang sa mawalan ng laman ang pila. Tandaan na ang mga node na nabisita ay hindi dapat idagdag sa pila muli

Tingnan natin ngayon ang pseudocode ng Breadth-First Search algorithm.

Breadth-First Search Algorithm Pseudocode

Narito ang pseudocode upang ipatupad ang Breadth-First Search Algorithm:

Input: s bilang pinagmulan node BFS (G, s) hayaan ang Q na maging pila. Q. (mga) marka ng s bilang binisita habang (ang Q ay walang laman) v = Q.dequeue () para sa lahat ng mga kapitbahay ng v sa Graph G kung hindi binisita ang Q.enqueue (w) markahan bilang binisita

Sa code sa itaas, ang mga sumusunod na hakbang ay naisagawa:

1. Ang (G, s) ay input, narito ang G ay ang grap at ang s ang root node
2. Ang isang pila na 'Q' ay nilikha at nasimulan sa pinagmulang node na 's'
3. Lahat ng mga node ng bata na 's' ay minarkahan
4. Mag-extract ng 's' mula sa pila at bisitahin ang mga node ng bata
5. Iproseso ang lahat ng mga node ng bata ng v
6. Ang mga tindahan w (mga node ng bata) sa Q upang higit pang bisitahin ang mga node ng bata
7. Magpatuloy hanggang sa 'Q' ay walang laman

Bago natin balutin ang blog, tingnan natin ang ilang mga application ng Breadth-First Search algorithm.

Mga Aplikasyon Ng Algorithm ng Breadth-First Search

Ang Breadth-first Search ay isang simpleng grapikong pamamaraan ng traversal na may nakakagulat na saklaw ng mga application. Narito ang ilang mga kagiliw-giliw na paraan kung saan ginagamit ang Bread-First Search:

Mga Crawler sa Mga Search Engine: Ang Breadth-First Search ay isa sa mga pangunahing algorithm na ginagamit para sa pag-index ng mga web page. Nagsisimula ang algorithm sa pagtawid mula sa pinagmulang pahina at sinusundan ang lahat ng mga link na nauugnay sa pahina. Dito ang bawat web page ay isasaalang-alang bilang isang node sa isang graph.

Mga sistema ng Navigation ng GPS: Ang Breadth-First Search ay isa sa mga pinakamahusay na algorithm na ginamit upang makahanap ng mga kalapit na lokasyon sa pamamagitan ng paggamit ng GPS system.

Hanapin ang Pinakamabilis na Landas at Minimum na Spanning Tree para sa isang walang timbang na grap: Pagdating sa isang walang timbang na grap, ang pagkalkula ng pinakamaikling landas ay medyo simple dahil ang ideya sa likod ng pinakamaikling landas ay ang pumili ng isang landas na may pinakamaliit na bilang ng mga gilid. Maaaring payagan ng Breadth-First Search na ito sa pamamagitan ng pagdaan sa isang minimum na bilang ng mga node na nagsisimula sa pinagmulang node. Katulad nito, para sa isang sumasaklaw na puno, maaari naming gamitin ang alinman sa dalawa, mga pamamaraan ng Breadth-First Search o Depth-first traversal upang makahanap ng isang sumasaklaw na puno.

Pag-broadcast: Ginagamit ng networking ang tinatawag naming mga packet para sa komunikasyon. Ang mga packet na ito ay sumusunod sa isang pamamaraang traversal upang maabot ang iba't ibang mga network node. Ang isa sa mga pinaka-karaniwang ginagamit na pamamaraang traversal ay ang Breadth-First Search. Ginagamit ito bilang isang algorithm na ginagamit upang makipag-usap sa mga naka-broadcast na packet sa lahat ng mga node sa isang network.

Peer to Peer Networking: Ang Breadth-First Search ay maaaring magamit bilang isang pamamaraang traversal upang mahanap ang lahat ng mga kalapit na node sa isang Peer to Peer Network. Halimbawa, gumagamit ang BitTorrent ng Breadth-First Search para sa komunikasyon ng peer to peer.

Kaya't iyon ang tungkol sa pagtatrabaho ng Breadth-First Search algorithm. Ngayong alam mo na kung paano dumaan sa mga graph, sigurado akong interesado kang malaman ang higit pa. Narito ang ilang mga nauugnay na blog upang mapanatili kang interesado:

3. Panimula Sa Mga Chain na Markov Na May Mga Halimbawa - Markov Chains Na May Python

Sa pamamagitan nito, natapos na kami sa blog na ito. Kung mayroon kang anumang mga query tungkol sa paksang ito, mangyaring mag-iwan ng komento sa ibaba at babalikan ka namin.

keyerror: 'a'

Kung nais mong magpatala para sa isang kumpletong kurso sa Artipisyal na Katalinuhan at Pag-aaral ng Makina, ang Edureka ay may espesyal na na-curate iyon ay magpapasikat sa iyo sa mga diskarteng tulad ng Pinangangasiwaang Pag-aaral, Hindi Pinapamahalaang Pag-aaral, at Pagproseso ng Likas na Wika. Kasama rito ang pagsasanay sa pinakabagong mga pagsulong at panteknikal na diskarte sa Artipisyal na Pag-intelektuwal at Pag-aaral ng Makina tulad ng Deep Learning, Mga Modelong Grapiko at Pag-aaral ng Patatag.