Els mètodes gràfics transversals sempre m’han fascinat força. Des de realitzar una comunicació efectiva entre iguals fins a trobar els restaurants i cafeteries més propers mitjançant GPS, els mètodes de recorregut tenen un conjunt variat d’aplicacions en l’escenari del món real. En aquest bloc sobre l'algorisme de cerca per amplada, analitzarem la lògica que hi ha darrere dels mètodes de recorregut de gràfics i utilitzarem exemples per entendre el funcionament de l'algorisme de cerca per amplada.
Per obtenir un coneixement en profunditat de la Intel·ligència Artificial i l’aprenentatge automàtic, podeu inscriure-us per viure per Edureka amb assistència les 24 hores del dia, els 7 dies de la setmana i accés permanent.
Aquí teniu una llista de temes que hi haurà tractat en aquest bloc:
implementació de pila màxima a Java
- Introducció a la transversal gràfica
- Què és la primera cerca per amplada?
- Descripció de l'algorisme Breadth-First Search amb un exemple
- Pseudocodi de l'algorisme de cerca per amplada-primera
- Aplicacions de la cerca per amplada
Introducció a la transversal gràfica
El procés de visitar i explorar un gràfic per processar-lo s’anomena recorregut de gràfics. Per ser més específics, es tracta de visitar i explorar cada vèrtex i vora en un gràfic de manera que tots els vèrtexs s’explorin exactament una vegada.
Sembla senzill. Però hi ha un problema.
Hi ha diverses tècniques de recorregut de gràfics, com ara Cerca per amplada-primer, Cerca per profunditat, etc. El repte és utilitzar un gràfic tècnica de travessia més adequada per resoldre un problema concret. Això ens porta a la tècnica Breadth-First Search.
Què és l'algorisme de cerca per amplada?
L’algorisme de cerca per amplada és una tècnica de recorregut de gràfics, en la qual seleccioneu un node inicial aleatori (node origen o arrel) i comenceu a recórrer el gràfic per capes de manera que tots els nodes i els seus respectius nodes fills siguin visitats i explorats.
Abans d’avançar-nos i entendre la cerca de amplada-primer amb un exemple, familiaritzem-nos amb dos termes importants relacionats amb el recorregut de gràfics:
- Visitar un node: Tal com indica el nom, visitar un node significa visitar o seleccionar un node.
- Exploració d'un node: Explorant el nodes adjacents (nodes fills) d'un node seleccionat.
Consulteu la figura anterior per entendre-ho millor.
Comprensió de l'algorisme de cerca per amplada-primer amb un exemple
L’algorisme de cerca de amplada primer segueix un enfocament senzill basat en nivells per resoldre un problema. Penseu en l’arbre binari següent (que és un gràfic). El nostre objectiu és recórrer el gràfic mitjançant l’algorisme de cerca de amplada-primera.
Abans de començar, heu de familiaritzar-vos amb l’estructura de dades principal implicada en l’algoritme Breadth-First Search.
Una cua és una estructura de dades abstracta que segueix la metodologia First-In-First-Out (primer s’accedirà a les dades inserides primer). Està obert als dos extrems, on sempre s’utilitza un extrem per inserir dades (cola) i l’altre per eliminar dades (cola).
Ara fem un cop d'ull als passos que comporta recórrer un gràfic mitjançant la cerca de amplada-primer:
Pas 1: Feu una cua buida.
Pas 2: Seleccioneu un node inicial (visiteu un node) i inseriu-lo a la cua.
Pas 3: Sempre que la cua no estigui buida, extreu el node de la cua i inseriu-ne els nodes fills (explorant un node) a la cua.
Pas 4: Imprimiu el node extret.
No us preocupeu si esteu confós, ho entendrem amb un exemple.
Mireu el gràfic següent: utilitzarem l'algorisme Breadth-First Search per recórrer el gràfic.
En el nostre cas, assignarem el node ‘a’ com a node arrel i començarem a recórrer cap avall i seguirem els passos esmentats anteriorment.
La imatge anterior mostra el procés de punta a punta de l'algorisme de cerca per amplada. Deixeu-me explicar-ho amb més profunditat.
- Assigneu ‘a’ com a node arrel i inseriu-lo a la cua.
- Extraieu el node 'a' de la cua i inseriu els nodes secundaris de 'a', és a dir, 'b' i 'c'.
- Imprimeix el node 'a'.
- La cua no està buida i té els nodes 'b' i 'c'. Com que ‘b’ és el primer node de la cua, extraiem-lo i inserim els nodes secundaris de ‘b’, és a dir, el node ‘d’ i ‘e’.
- Repetiu aquests passos fins que la cua quedi buida. Tingueu en compte que els nodes que ja s'han visitat no s'han d'afegir a la cua de nou.
Vegem ara el pseudocodi de l'algorisme Breadth-First Search.
Pseudocodi de l'algorisme de cerca per amplada-primera
Aquí teniu el pseudocodi per implementar l'algorisme de cerca de amplada:
Entrada: s com a node d'origen BFS (G, s) deixa que Q sigui cua. Q.enqueue (s) marca s com a visitats mentre que (Q no està buit) v = Q.dequeue () per a tots els veïns w de v al gràfic G si w no es visita Q.enqueue (w) marca w com a visitat
Al codi anterior, s'executen els passos següents:
- (G, s) s’introdueix, aquí G és el gràfic i s és el node arrel
- Es crea i inicialitza una cua 'Q' amb el node d'origen 's'
- Tots els nodes secundaris de 's' estan marcats
- Extraieu les 's' de la cua i visiteu els nodes secundaris
- Processar tots els nodes secundaris de v
- Emmagatzema w (nodes fills) a Q per visitar encara més els seus nodes fills
- Continueu fins que aparegui 'Q' buit
Abans d’acabar el bloc, vegem algunes aplicacions de l’algorisme Breadth-First Search.
Aplicacions de l'algorisme de cerca de amplada
Breadth-first Search és un mètode senzill de recorregut de gràfics que té una àmplia gamma d'aplicacions. A continuació, es mostren algunes maneres interessants d’utilitzar Bread-First Search:
Rastrejadors als motors de cerca: Breadth-First Search és un dels principals algorismes utilitzats per indexar pàgines web. L’algorisme comença a recórrer des de la pàgina d’origen i segueix tots els enllaços associats a la pàgina. Aquí cada pàgina web es considerarà com un node en un gràfic.
Sistemes de navegació GPS: Breadth-First Search és un dels millors algorismes que s’utilitzen per trobar ubicacions veïnes mitjançant el sistema GPS.
Cerqueu el camí més curt i l'arbre d'abast mínim per obtenir un gràfic sense ponderar: Quan es tracta d’un gràfic no ponderat, calcular el camí més curt és bastant senzill, ja que la idea darrere del camí més curt és triar un camí amb el menor nombre d’arestes. Breadth-First Search pot permetre-ho recorrent un nombre mínim de nodes a partir del node d'origen. De la mateixa manera, per a un arbre que abasta, podem utilitzar qualsevol dels dos mètodes, Breadth-First Search o Depth-first traversal, per trobar un arbre que abasta.
converteix la data de la cadena a la data a Java
Emissió: La creació de xarxes fa ús del que anomenem paquets per a la comunicació. Aquests paquets segueixen un mètode de recorregut per arribar a diversos nodes de xarxa. Un dels mètodes de recorregut més utilitzats és Breadth-First Search. S’utilitza com un algorisme que s’utilitza per comunicar paquets emesos a tots els nodes d’una xarxa.
Xarxa d'igual a igual: Breadth-First Search es pot utilitzar com a mètode de recorregut per trobar tots els nodes veïns d'una xarxa Peer to Peer. Per exemple, BitTorrent utilitza Breadth-First Search per a una comunicació entre iguals.
Així, doncs, es tractava del funcionament de l'algorisme Breadth-First Search. Ara que ja saps recórrer gràfics, estic segur que tens curiositat per obtenir més informació. Aquests són alguns blocs rellevants per mantenir-vos interessats:
Amb això, arribem al final d’aquest bloc. Si teniu cap pregunta sobre aquest tema, deixeu un comentari a continuació i us respondrem.
Si voleu inscriure-us a un curs complet d’Intel·ligència Artificial i Aprenentatge Automàtic, Edureka disposa d’un programa especialitzat que us farà dominar tècniques com l'aprenentatge supervisat, l'aprenentatge sense supervisió i el processament del llenguatge natural. Inclou formació sobre els darrers avenços i enfocaments tècnics en intel·ligència artificial i aprenentatge automàtic, com ara aprenentatge profund, models gràfics i aprenentatge de reforç.