Grafikų perėjimo metodai mane visada žavėjo. Pradedant efektyviu tarpusavio bendravimu ir baigiant artimiausių restoranų ir kavinių paieška naudojant GPS, tikrojo pasaulio scenarijams keliavimo būdai turi įvairias programas. Šiame tinklaraštyje apie „Platumos pirmosios paieškos“ algoritmą aptarsime grafikų perėjimo metodų logiką ir naudosime pavyzdžius, kad suprastume „Platumo pirmosios paieškos“ algoritmo veikimą.
Norėdami gauti išsamių žinių apie dirbtinį intelektą ir mašininį mokymąsi, galite užsiregistruoti tiesiogiai sukūrė „Edureka“ su parą visą parą ir visą gyvenimą.
Čia pateikiamos temos, kurios bus aprašyta šiame tinklaraštyje:
- Grafikų perėjimo įvadas
- Kas yra „Pirmojo pločio“ paieška?
- Suprasti „Platumo pirmosios paieškos“ algoritmą su pavyzdžiu
- Pirmojo pločio paieškos algoritmo pseudokodas
- Pirmojo pločio paieškos programos
Grafikų perėjimo įvadas
Grafo lankymo ir tyrimo procesas apdorojimui vadinamas grafo perėjimu. Konkrečiau kalbant, viskas yra apie kiekvieno viršūnės ir krašto aplankymą ir tyrimą diagramoje taip, kad visos viršūnės būtų ištirtos tiksliai vieną kartą.
Tai skamba paprastai! Bet yra laimikis.
Yra keletas grafikų perėjimo būdų, tokių kaip „Pirmojo pločio paieška“, „Pirmojo gylio paieška“ ir pan. Užduotis yra naudoti grafiką perėjimo technika, kuri yra tinkamiausia tam tikrai problemai spręsti. Tai leidžia mums naudotis „Pirmojo platumo paieškos“ technika.
Kas yra „Pirmojo pločio paieškos“ algoritmas?
„Platumo pirmosios paieškos“ algoritmas yra grafiko perėjimo technika, kur jūs pasirenkate atsitiktinį pradinį mazgą (šaltinio arba šaknies mazgą) ir pradedate slinkti grafiku taip, kad visi mazgai ir jų atitinkami vaikų mazgai būtų aplankyti ir ištirti.
Prieš pereidami toliau ir suprasdami „Platumo pirmoji paieška“ pavyzdį, susipažinkime su dviem svarbiais terminais, susijusiais su grafiko perėjimu:
- Apsilankymas mazge: Kaip rodo pavadinimas, lankymasis mazge reiškia lankymąsi arba jo pasirinkimą.
- Naršymas po mazgą: Naršyti gretimi pasirinkto mazgo mazgai (vaikų mazgai).
Norėdami geriau tai suprasti, remkitės aukščiau esančiu paveikslu.
Pirmojo platumo paieškos algoritmo supratimas su pavyzdžiu
„Platumo pirmosios paieškos“ algoritmas sprendžia problemą naudodamas paprastą, lygiu pagrįstą metodą. Apsvarstykite toliau pateiktą dvejetainį medį (kuris yra grafikas). Mūsų tikslas yra perbraukti grafiką naudojant „Pirmojo pločio paieškos“ algoritmą.
Prieš pradėdami, turite būti susipažinę su pagrindine duomenų struktūra, susijusia su „Breadth-First Search“ algoritmu.
Eilė yra abstrakti duomenų struktūra, kuri vadovaujasi „First-in-first-out“ metodika (pirmiausia bus įtraukti duomenys, kurie įterpti pirmiausia). Jis yra atidarytas abiejuose galuose, kur vienas galas visada naudojamas duomenims įterpti (pritraukti), o kitas - duomenims pašalinti (dequeue).
Dabar pažvelkime į veiksmus, susijusius su diagramos perėjimu naudojant „Pirmojo platumo“ paiešką:
rasti didžiausią skaičių masyvo java
1 žingsnis: Paimkite tuščią eilę.
2 žingsnis: Pasirinkite pradinį mazgą (aplankydami mazgą) ir įdėkite jį į eilę.
3 žingsnis: Jei eilė nėra tuščia, ištraukite mazgą iš eilės ir įdėkite jo antrinius mazgus (tyrinėdami mazgą) į eilę.
4 žingsnis: Atspausdinkite ištrauktą mazgą.
Nesijaudinkite, jei nesuprantate, suprasime tai su pavyzdžiu.
Pažvelkite į žemiau pateiktą grafiką, norėdami pereiti per diagramą, naudosime „Breadth-First Search“ algoritmą.
Mūsų atveju priskirsime mazgą „a“ kaip šakninį mazgą, pradėsime judėti žemyn ir atliksime pirmiau minėtus veiksmus.
Aukščiau pateiktame paveikslėlyje pavaizduotas „Breadth-First Search“ algoritmo procesas nuo pabaigos. Leiskite man tai paaiškinti išsamiau.
- Priskirkite „a“ kaip šakninį mazgą ir įterpkite jį į eilę.
- Iš eilės ištraukite mazgą „a“ ir įterpkite „a“, t. Y., „B“ ir „c“, antrinius mazgus.
- Spausdinimo mazgas „a“.
- Eilė nėra tuščia, joje yra mazgai „b“ ir „c“. Kadangi „b“ yra pirmasis mazgas eilėje, išskirkime jį ir įterpkime „b“ antrinius mazgus, t. Y. Mazgus „d“ ir „e“.
- Pakartokite šiuos veiksmus, kol eilė bus tuščia. Atkreipkite dėmesį, kad mazgai, kurie jau aplankyti, neturėtų būti pridėti prie eilės vėl.
Dabar pažvelkime į „Breadth-First Search“ algoritmo pseudokodą.
Pirmojo pločio paieškos algoritmo pseudokodas
Štai pseudokodas, skirtas įdiegti „Pirmojo platumo“ paieškos algoritmą:
Įvestis: s kaip šaltinio mazgas BFS (G, s) leiskite Q būti eilėje. Q.enqueue (s) ženklas (-ai) kaip aplankytas (Q nėra tuščias) v = Q.dequeue () visiems kaimynams w iš v G grafike, jei w nėra aplankytas
Pirmiau pateiktame kode atliekami šie veiksmai:
- (G, s) yra įvestis, čia G yra grafikas, o s yra šaknies mazgas
- Eilė „Q“ sukuriama ir inicijuojama naudojant šaltinio mazgą „s“
- Pažymimi visi „s“ vaikų mazgai
- Ištraukite „s“ iš eilės ir aplankykite vaiko mazgus
- Apdorokite visus vaiko mazgus
- Parduotuvėse w (vaiko mazgai) Q yra toliau lankomi jos vaikų mazgai
- Tęskite, kol bus „Q“ tuščia
Prieš baigdami tinklaraštį, pažvelkime į kai kurias „Breadth-First Search“ algoritmo programas.
java kaip išeiti iš programos
Pirmojo pločio paieškos algoritmo taikymai
„Pirmojo pločio“ paieška yra paprastas grafikų perėjimo metodas, turintis stebėtiną programų spektrą. Štai keletas įdomių būdų, kaip naudojama „Bread-First Search“:
Tikrintuvai paieškos sistemose: „Platumo pirmoji“ paieška yra vienas iš pagrindinių algoritmų, naudojamų indeksuojant tinklalapius. Algoritmas pradeda judėti iš šaltinio puslapio ir seka visas su puslapiu susijusias nuorodas. Čia kiekvienas tinklalapis bus laikomas mazgu diagramoje.
GPS navigacijos sistemos: „Pirmojo pločio paieška“ yra vienas iš geriausių algoritmų, naudojamų norint rasti kaimynines vietas naudojant GPS sistemą.
Suraskite trumpiausią kelią ir minimalų nesuvertinto grafiko kelią: Kalbant apie nesvarstytą grafiką, apskaičiuoti trumpiausią kelią yra gana paprasta, nes trumpiausio kelio idėja yra pasirinkti kelią su mažiausiu kraštų skaičiumi. „Platumo pirmoji“ paieška tai gali leisti pereinant minimalų mazgų skaičių, pradedant nuo šaltinio mazgo. Panašiai, jei norite rasti besiplečiantį medį, mes galime naudoti bet kurį iš šių dviejų būdų: „Pirmojo pločio paieškos“ arba „Pirmojo gylio“ perėjimo metodai.
Transliacija: Tinklas naudoja tai, ką mes vadiname paketais bendravimui. Šie paketai naudojasi perėjimo metodu, kad pasiektų įvairius tinklo mazgus. Vienas dažniausiai naudojamų perėjimo būdų yra „Pirmojo pločio paieška“. Jis naudojamas kaip algoritmas, naudojamas transliuojamiems paketams perduoti visuose tinklo mazguose.
„Peer to Peer“ tinklas: „Platumo pirmoji“ paieška gali būti naudojama kaip perėjimo metodas, norint rasti visus kaimyninius mazgus tinkle „Peer to Peer“. Pvz., „BitTorrent“ naudoja „Breadth-First Search“ tarpusavio bendravimui.
Taigi viskas buvo apie „Breadth-First Search“ algoritmo veikimą. Dabar, kai mokate pereiti grafikus, esu tikra, kad norite sužinoti daugiau. Čia yra keli atitinkami tinklaraščiai, kurie jus domina:
Tuo mes einame į šio tinklaraščio pabaigą. Jei turite klausimų dėl šios temos, palikite komentarą žemiau ir mes susisieksime su jumis.
Jei norite užsiregistruoti į visą dirbtinio intelekto ir mašininio mokymosi kursą, „Edureka“ turi specialiai kuruotą tai leis jums išmanyti tokias technikas kaip prižiūrimas mokymasis, neprižiūrimas mokymasis ir natūralios kalbos apdorojimas. Tai apima mokymus apie naujausius dirbtinio intelekto ir mašininio mokymosi pasiekimus ir techninius metodus, tokius kaip gilus mokymasis, grafiniai modeliai ir mokymasis sustiprinti.