Viss, kas jums jāzina par Platuma pirmās meklēšanas algoritmu

Diagrammu šķērsošanas metodes mani vienmēr ir diezgan fascinējušas. Sākot no efektīvas vienaudžu komunikācijas līdz tuvāko restorānu un kafejnīcu atrašanai, izmantojot GPS, reālās pasaules scenārijā šķērsošanas metodēm ir daudz dažādu lietojumprogrammu. Šajā emuārā par meklēšanas platuma pirmās meklēšanas algoritmu mēs apspriedīsim grafiku šķērsošanas metožu loģiku un izmantosim piemērus, lai izprastu algoritma Breadth-First Search darbību.

Lai iegūtu padziļinātas zināšanas par mākslīgo intelektu un mašīnmācīšanos, varat reģistrēties tiešraidē autors Edureka ar diennakts atbalstu un piekļuvi mūža garumā.

Šeit būs saraksts ar tēmām, kas būs apskatīts šajā emuārā:

1. Ievads grafiku šķērsošanā
2. Kas ir pirmais platuma meklējums?
3. Izpratne par platuma pirmās meklēšanas algoritmu ar piemēru
4. Pirmās platuma meklēšanas algoritma pseidokods
5. Pirmās platuma meklēšanas lietojumi

Ievads grafiku šķērsošanā

Grafa apmeklēšanas un izpētes procesu apstrādei sauc par grafa šķērsošanu. Konkrētāk, tas ir par katra virsotnes un malas apmeklēšanu un izpēti diagrammā tā, lai visas virsotnes tiktu izpētītas tieši vienu reizi.

Tas izklausās vienkārši! Bet tur ir nozveja.

Ir vairākas grafiku šķērsošanas metodes, piemēram, meklēšana pēc platuma-pirmā, dziļuma pirmā meklēšana un tā tālāk. Uzdevums ir izmantot grafiku šķērsošanas tehnika, kas ir vispiemērotākā konkrētas problēmas risināšanai. Tas mūs noved pie Breadth-First Search tehnikas.

Kas ir platuma pirmās meklēšanas algoritms?

Platuma pirmās meklēšanas algoritms ir grafika šķērsošanas paņēmiens, kurā atlasāt nejaušu sākotnējo mezglu (avota vai saknes mezglu) un sākat šķērsot grafiku pa slāni tādā veidā, lai visi mezgli un viņu attiecīgie bērnu mezgli tiktu apmeklēti un izpētīti.

Pirms mēs virzāmies tālāk un saprotam “Breadth-First Search” piemēru, iepazīsimies ar diviem svarīgiem terminiem, kas saistīti ar diagrammu šķērsošanu:

1. Apmeklējot mezglu: Tāpat kā norāda nosaukums, mezgla apmeklēšana nozīmē mezgla apmeklēšanu vai atlasīšanu.
2. Mezgla izpēte: Izpētīt blakus esošie mezgli (bērnu mezgli) no izvēlētā mezgla.

Skatiet iepriekšējo attēlu, lai to labāk izprastu.

Izpratne par platuma pirmās meklēšanas algoritmu ar piemēru

Sākotnējās meklēšanas algoritms problēmas risināšanai izmanto vienkāršu, uz līmeni balstītu pieeju. Apsveriet zemāk esošo bināro koku (kas ir grafiks). Mūsu mērķis ir šķērsot grafiku, izmantojot Breadth-First Search algoritmu.

Pirms sākam darbu, jums jāpārzina galvenā datu struktūra, kas iesaistīta algoritmā Breadth-First Search.

kas ir jit kompilators java

Rinda ir abstrakta datu struktūra, kas atbilst metodei First-In-First-Out (vispirms tiks iekļauti vispirms ievietotie dati). Tas ir atvērts abos galos, kur vienu galu vienmēr izmanto datu ievietošanai (enqueue), bet otru - datu noņemšanai (dequeue).

Tagad aplūkosim soļus, kas saistīti ar diagrammas šķērsošanu, izmantojot meklēšanu “Platums-pirmais”:

1. darbība: Izvēlieties tukšu rindu.

2. darbība: Atlasiet sākuma mezglu (apmeklējot mezglu) un ievietojiet to rindā.

3. solis: Ja rinda nav tukša, izvelciet mezglu no rindas un ievietojiet tās pakārtotos mezglus (izpētot mezglu) rindā.

4. solis: Izdrukājiet izvilkto mezglu.

Neuztraucieties, ja esat neskaidrs, mēs to sapratīsim ar piemēru.

Apskatiet zemāk redzamo diagrammu, lai pārvietotos pa diagrammu, mēs izmantosim meklēšanas platuma pirmās meklēšanas algoritmu.

Mūsu gadījumā kā saknes mezglu piešķirsim mezglu ‘a’, sāksim virzīties uz leju un izpildīsim iepriekš minētās darbības.

c ++ kā izmantot nosaukumvietas

Iepriekš redzamajā attēlā ir attēlots “Breadth-First Search Algorithm” process no sākuma līdz beigām. Ļaujiet man to izskaidrot dziļāk.

1. Piešķiriet ‘a’ kā saknes mezglu un ievietojiet to rindā.
2. Izvelciet mezglu ‘a’ no rindas un ievietojiet bērna mezglus ‘a’, t.i., ‘b’ un ‘c’.
3. Drukas mezgls ‘a’.
4. Rinda nav tukša, un tajā ir mezgli “b” un “c”. Tā kā ‘b’ ir pirmais mezgls rindā, izvilksim to un ievietosim ‘b’ apakšmezglus, t.i., mezglus ‘d’ un ‘e’.
5. Atkārtojiet šīs darbības, līdz rinda kļūst tukša. Ņemiet vērā, ka mezglus, kas jau ir apmeklēti, nevajadzētu pievienot rindai atkal.

Tagad aplūkosim Breadth-First Search algoritma pseidokodu.

Pirmās platuma meklēšanas algoritma pseidokods

Lūk, pseidokods, lai ieviestu Breadth-First Search algoritmu:

Ievade: s kā avota mezgls BFS (G, s) ļauj Q būt rindā. Q.enqueue (s) atzīme (s) kā apmeklēta (Q nav tukša) v = Q.dequeue () visiem v kaimiņiem w no G grafikā G, ja w nav apmeklēts Q.enqueue (w) atzīme w kā apmeklēta

Iepriekš minētajā kodā tiek veiktas šādas darbības:

c ++ krātuves klase

1. (G, s) tiek ievadīts, šeit G ir grafiks un s ir saknes mezgls
2. Rinda “Q” tiek izveidota un inicializēta ar avota mezglu “s”
3. Visi “s” bērnu mezgli ir atzīmēti
4. Izvelciet ‘s’ no rindas un apmeklējiet bērna mezglus
5. Apstrādājiet visus v bērna mezglus
6. Veikali w (bērnu mezgli) Q, lai turpinātu apmeklēt tā bērnu mezglus
7. Turpiniet, līdz ‘Q’ ir tukšs

Pirms emuāra apkopošanas apskatīsim dažus Breadth-First Search algoritma lietojumus.

Pirmās platuma meklēšanas algoritma pielietojums

Meklēšana pēc platuma vispirms ir vienkārša diagrammas šķērsošanas metode, kurai ir pārsteidzošs lietojumu klāsts. Šeit ir daži interesanti veidi, kā tiek izmantota Bread-First meklēšana:

Rāpuļprogrammas meklētājprogrammās: Breadth-First Search ir viens no galvenajiem algoritmiem, ko izmanto tīmekļa lapu indeksēšanai. Algoritms sāk pārvietoties no avota lapas un seko visām ar lapu saistītajām saitēm. Šeit katra tīmekļa lapa tiks uzskatīta par mezglu diagrammā.

GPS navigācijas sistēmas: Breadth-First Search ir viens no labākajiem algoritmiem, ko izmanto, lai atrastu blakus esošās vietas, izmantojot GPS sistēmu.

Nesvērtajam grafikam atrodiet īsāko ceļu un minimālo aptverošo koku: Runājot par nesvērtu grafiku, īsākā ceļa aprēķināšana ir pavisam vienkārša, jo īsākā ceļa ideja ir izvēlēties ceļu ar vismazāko malu skaitu. Platuma pirmā meklēšana to var atļaut, šķērsojot minimālo mezglu skaitu, sākot no avota mezgla. Līdzīgi kā aptverošam kokam, lai atrastu aptverošu koku, mēs varam izmantot kādu no abām metodēm - pārvietošanās pa platumu vispirms un dziļumu vispirms.

Apraide: Tīklošana izmanto to, ko mēs saucam par saziņas paketēm. Šīs paketes izmanto šķērsošanas metodi, lai sasniegtu dažādus tīkla mezglus. Viena no visbiežāk izmantotajām šķērsošanas metodēm ir Breadth-First Search. To lieto kā algoritmu, ko izmanto, lai sazinātos ar apraidītajām paketēm visos tīkla mezglos.

Vienādranga tīklošana: Visuma meklēšanu var izmantot kā šķērsošanas metodi, lai atrastu visus blakus esošo mezglu vienādranga tīklā. Piemēram, BitTorrent izmanto vienādranga saziņai Breadth-First Search.

Tātad tas viss bija par algoritma Breadth-First Search darbību. Tagad, kad jūs zināt, kā šķērsot diagrammas, esmu pārliecināts, ka vēlaties uzzināt vairāk. Šeit ir daži attiecīgie emuāri, lai jūs ieinteresētu:

3. Ievads Markova ķēdēs ar piemēriem - Markova ķēdes ar Python

Ar to mēs esam nonākuši pie šī emuāra beigām. Ja jums ir kādi jautājumi par šo tēmu, lūdzu, atstājiet komentāru zemāk, un mēs ar jums sazināsimies.

Ja vēlaties iestāties pilnīgā mākslīgā intelekta un mašīnmācīšanās kursā, Edureka piedāvā īpaši kuratoru kas ļaus jums pārzināt tādas metodes kā uzraudzīta mācīšanās, bez uzraudzības un dabiskās valodas apstrāde. Tas ietver apmācību par jaunākajiem sasniegumiem un tehniskajām pieejām mākslīgā intelekta un mašīnmācīšanās jomā, piemēram, padziļināta mācīšanās, grafiskie modeļi un mācīšanās pastiprināšana.