A grafikonjárási módszerek mindig is nagyon elbűvöltek. A hatékony társak közötti kommunikációtól kezdve a legközelebbi éttermek és kávézók GPS-ig történő megtalálásáig a bejárási módszerek változatos alkalmazásokkal rendelkeznek a valós helyzetben. Ebben a Breadth-First Search Algorithm blogban a gráfátjárási módszerek logikáját fogjuk megvitatni, és példák segítségével megértjük a Breadth-First Search algoritmus működését.
A mesterséges intelligencia és a gépi tanulás alapos ismereteinek megszerzéséhez regisztrálhat élőben által Edureka 24/7 támogatással és egész életen át tartó hozzáféréssel.
Itt van egy lista azokról a témákról, amelyek a következők lesznek ez a blog foglalkozik:
xml transzformáció az informatikában példával
- A grafikon bejárása
- Mi a Szélesség első keresése?
- A Szélesség-első keresés algoritmus megértése egy példával
- Szélesség-első keresési algoritmus álkód
- A szélesség első keresésének alkalmazásai
A grafikon bejárása
A gráf meglátogatásának és feldolgozásának felfedezésének folyamatát gráf bejárásának nevezzük. Pontosabban szólva, minden egyes csúcs és él meglátogatásáról és felkutatásáról van szó egy grafikonon úgy, hogy az összes csúcsot pontosan egyszer fedezze fel.
Ez egyszerűen hangzik! De van egy fogás.
Számos grafikon bejárási technika létezik, mint például Szélesség-Első keresés, Mélység-Első keresés és így tovább. A kihívás egy grafikon használata bejárási technika, amely a legmegfelelőbb egy adott probléma megoldására. Ez a Breadth-First Search technikához vezet.
Mi a Szélesség Első Keresési Algoritmus?
A Szélesség-Első keresés algoritmus egy gráfátjáró technika, ahol kiválaszt egy véletlenszerű kezdő csomópontot (forrás vagy gyökércsomópont), és rétegenként elkezdi haladni a gráfot úgy, hogy az összes csomópontot és a hozzájuk tartozó gyermek csomópontokat meglátogassa és feltárja.
Mielőtt továbblépnénk és megértenénk a Breadth-First Search példát, ismerkedjünk meg a grafikon bejárásával kapcsolatos két fontos kifejezéssel:
- Csomópont meglátogatása: Ahogy a neve is sugallja, egy csomópont meglátogatása azt jelenti, hogy meglátogatja vagy kiválasztja a csomópontot.
- Csomópont felfedezése: A. Feltárása a kiválasztott csomópont szomszédos csomópontjai (gyermekcsomópontjai).
Ennek jobb megértése érdekében olvassa el a fenti ábrát.
A Szélesség-első keresés algoritmus megértése példával
A Breadth-First Search algoritmus egyszerű, szintalapú megközelítést alkalmaz a probléma megoldására. Tekintsük az alábbi bináris fát (amely egy grafikon). Célunk a grafikon áthaladása a Szélesség-első keresés algoritmus használatával.
Mielőtt belekezdenénk, ismernie kell a Breadth-First Search algoritmusban részt vevő fő adatszerkezetet.
A várakozási sor egy elvont adatstruktúra, amely követi az Első-be-az első-kimenet módszertant (az elsőnek beillesztett adatokhoz először hozzáférnek). Mindkét végén nyitva van, ahol az egyik véget mindig az adatok beszúrására használják (enqueue), a másikat pedig az adatok (dequeue) eltávolítására használják.
Most nézzük meg a grafikon áthaladásának lépéseit a Breadth-First Search használatával:
1. lépés: Válasszon egy üres sort.
2. lépés: Válasszon kiinduló csomópontot (látogasson el egy csomópontot), és illessze be a várólistába.
3. lépés: Feltéve, hogy a várólista nem üres, vonja ki a csomópontot a várólistából, és helyezze be annak gyermekcsomópontjait (egy csomópont felfedezésével) a sorba.
4. lépés: Nyomtassa ki a kibontott csomópontot.
Ne aggódjon, ha összezavarodik, ezt megértjük egy példával.
Vessen egy pillantást az alábbi grafikonra, a Breadth-First Search algoritmust használjuk a grafikonon való áthaladáshoz.
Esetünkben az „a” csomópontot fogjuk kijelölni gyökércsomópontként, és elkezdjük lefelé haladni, és kövessük a fent említett lépéseket.
A fenti kép a szélesség-első keresés algoritmus végpontok közötti folyamatát ábrázolja. Hadd magyarázzam el ezt alaposabban.
- Rendeljen „a” -t gyökércsomópontként, és illessze be a várólistába.
- Bontsa ki az „a” csomópontot a sorból, és helyezze be az „a”, azaz „b” és „c” gyermek csomópontokat.
- „A” csomópont nyomtatása.
- A sor nem üres, és a „b” és a „c” csomópont van rajta. Mivel a „b” az első csomópont a sorban, bontsuk ki és helyezzük be a „b”, azaz a „d” és az „e” csomópontokat.
- Ismételje meg ezeket a lépéseket, amíg a sor kiürül. Ne feledje, hogy a már meglátogatott csomópontokat nem szabad felvenni a sorba újra.
Most nézzük meg a Breadth-First Search algoritmus álkódját.
Szélesség-első keresési algoritmus álkód
Itt van az álkód a Szélesség Első Keresési Algoritmus megvalósításához:
Bemenet: a forrás csomópontként a BFS (G, s) Q álljon sorba. Q.enqueue (s) megjelöli a látogatottakat, miközben (Q nem üres) v = Q.dequeue () minden v w szomszéd számára a G grafikonban, ha w nincs meglátogatva Q.enqueue (w) w
A fenti kódban a következő lépéseket hajtják végre:
- (G, s) van megadva, itt G a grafikon és s a gyökércsomópont
- A „Q” várólista létrehozása és inicializálása az „s” forráscsomóponttal történik
- Az ’s’ összes gyermekcsomópontja meg van jelölve
- Bontsa ki az „s” -t a sorból, és keresse fel a gyermek csomópontjait
- Feldolgozza a v összes gyermekcsomópontját
- A Q-ban tárolja a w (gyermekcsomópontokat), hogy tovább látogassa gyermekcsomópontjait
- Folytassa addig, amíg a „Q” van üres
Mielőtt összefoglalnánk a blogot, nézzük meg a Breadth-First Search algoritmus néhány alkalmazását.
A szélesség első keresési algoritmusának alkalmazásai
A Breadth-first Search egy egyszerű grafikonjárási módszer, amely meglepően sokféle alkalmazási lehetőséget kínál. Íme néhány érdekes módszer a Bread-First Search használatára:
Robotok a keresőmotorokban: A Breadth-First Search az egyik fő algoritmus, amelyet a weboldalak indexeléséhez használnak. Az algoritmus a forrásoldalról kezd bejárni, és követi az oldalhoz tartozó összes hivatkozást. Itt minden weboldal egy csomópontnak tekintendő egy grafikonon.
GPS navigációs rendszerek: A Breadth-First Search az egyik legjobb algoritmus, amelyet a szomszédos helyek megtalálásához használnak a GPS rendszer segítségével.
Keresse meg a legrövidebb útvonalat és a legkisebb átfutási fát egy súlyozatlan grafikonhoz: Ha egy súlyozatlan gráfról van szó, a legrövidebb út kiszámítása meglehetősen egyszerű, mivel a legrövidebb út mögött az az ötlet áll, hogy a legkevesebb éllel rendelkező utat válasszuk. A Szélesség első keresése lehetővé teheti ezt azáltal, hogy minimális számú csomópontot halad át a forrás csomóponttól kezdve. Hasonlóképpen, egy átívelő fához a két szélességi módszerrel, a Szélesség-Első keresés vagy a Mélység-az első bejárással bármelyik módszert felhasználhatjuk egy átfogó fa megkeresésére.
Műsorszolgáltatás: A hálózatépítés a kommunikáció csomagjainak nevezi. Ezek a csomagok bejárási módszert követnek a különböző hálózati csomópontok eléréséhez. Az egyik leggyakrabban használt bejárási módszer a Breadth-First Search. Algoritmusként használják, amelyet a sugárzott csomagok kommunikációjára használnak a hálózat összes csomópontján.
Peer to Peer hálózatépítés: A Szélesség-első keresés bejárási módszerként megtalálható a Peer to Peer hálózat összes szomszédos csomópontjának megtalálásához. Például a BitTorrent a Breadth-First Search funkciót használja a peer to peer kommunikációhoz.
Ez tehát a Szélesség-Első Kereső algoritmus működéséről szólt. Most, hogy tudod, hogyan kell áthaladni a grafikonokon, biztos vagyok benne, hogy kíváncsi vagy rá. Íme néhány releváns blog az érdeklődés fenntartására:
Ezzel a blog végére értünk. Ha bármilyen kérdése van ezzel a témával kapcsolatban, kérjük, hagyjon megjegyzést alább, és kapcsolatba lépünk Önnel.
Ha be akar jelentkezni a mesterséges intelligencia és a gépi tanulás teljes tanfolyamára, az Edureka speciálisan kurátora van amellyel jártas lesz az olyan technikákban, mint a felügyelt tanulás, a felügyelet nélküli tanulás és a természetes nyelv feldolgozása. Képzést tartalmaz a mesterséges intelligencia és a gépi tanulás legújabb fejleményeiről és technikai megközelítéseiről, például a mély tanulásról, a grafikus modellekről és a megerősítő tanulásról.