Los métodos de Graph Traversal siempre me han fascinado bastante. Desde realizar una comunicación efectiva entre pares hasta encontrar los restaurantes y cafés más cercanos mediante GPS, los métodos de recorrido tienen un conjunto variado de aplicaciones en el escenario del mundo real. En este blog sobre el algoritmo de búsqueda en amplitud primero, analizaremos la lógica detrás de los métodos de recorrido de gráficos y usaremos ejemplos para comprender el funcionamiento del algoritmo de búsqueda en amplitud primero.
Para obtener un conocimiento profundo de la inteligencia artificial y el aprendizaje automático, puede inscribirse en vivo de Edureka con soporte 24/7 y acceso de por vida.
Aquí hay una lista de temas que serán cubierto en este blog:
- Introducción a Graph Traversal
- ¿Qué es la búsqueda en amplitud?
- Comprender el algoritmo de búsqueda en amplitud primero con un ejemplo
- Pseudocódigo del algoritmo de búsqueda en amplitud primero
- Aplicaciones de búsqueda en amplitud primero
Introducción a Graph Traversal
El proceso de visitar y explorar un gráfico para su procesamiento se denomina recorrido de gráfico. Para ser más específicos, se trata de visitar y explorar cada vértice y borde en un gráfico de modo que todos los vértices se exploren exactamente una vez.
¡Eso suena simple! Pero hay una trampa.
Existen varias técnicas de recorrido de gráficos, como la búsqueda primero en amplitud, la búsqueda en profundidad primero, etc. El desafío es usar un gráfico técnica transversal más adecuada para resolver un problema en particular. Esto nos lleva a la técnica de búsqueda en amplitud primero.
¿Qué es el algoritmo de búsqueda en amplitud primero?
El algoritmo Breadth-First Search es una técnica de desplazamiento de gráficos, en la que se selecciona un nodo inicial aleatorio (nodo de origen o raíz) y se empieza a recorrer el gráfico por capas de tal manera que se visitan y exploran todos los nodos y sus respectivos nodos secundarios.
Antes de avanzar más y comprender la búsqueda en amplitud primero con un ejemplo, familiaricémonos con dos términos importantes relacionados con el recorrido de gráficos:
- Visitando un nodo: Como sugiere el nombre, visitar un nodo significa visitar o seleccionar un nodo.
- Explorando un nodo: Explorando el nodos adyacentes (nodos secundarios) de un nodo seleccionado.
Consulte la figura anterior para comprender mejor esto.
Comprender el algoritmo de búsqueda en amplitud primero con un ejemplo
El algoritmo Breadth-First Search sigue un enfoque simple basado en niveles para resolver un problema. Considere el siguiente árbol binario (que es un gráfico). Nuestro objetivo es recorrer el gráfico utilizando el algoritmo de búsqueda en amplitud primero.
Antes de comenzar, debe estar familiarizado con la estructura de datos principal involucrada en el algoritmo Breadth-First Search.
Una cola es una estructura de datos abstracta que sigue la metodología de primero en entrar, primero en salir (primero se accederá a los datos que se inserten primero). Está abierto en ambos extremos, donde un extremo siempre se usa para insertar datos (poner en cola) y el otro se usa para eliminar datos (quitar de cola).
Ahora, echemos un vistazo a los pasos necesarios para recorrer un gráfico mediante la búsqueda en amplitud primero:
Paso 1: Toma una cola vacía.
Paso 2: Seleccione un nodo inicial (visitando un nodo) e insértelo en la cola.
Paso 3: Siempre que la Cola no esté vacía, extraiga el nodo de la Cola e inserte sus nodos secundarios (explorando un nodo) en la Cola.
Etapa 4: Imprime el nodo extraído.
No se preocupe si está confundido, lo entenderemos con un ejemplo.
Eche un vistazo al gráfico de abajo, utilizaremos el algoritmo de búsqueda en amplitud primero para recorrer el gráfico.
emitir doble a int en java
En nuestro caso, asignaremos el nodo 'a' como nodo raíz y comenzaremos a recorrer hacia abajo y seguiremos los pasos mencionados anteriormente.
La imagen de arriba muestra el proceso de un extremo a otro del algoritmo de búsqueda en amplitud primero. Déjame explicarte esto con más profundidad.
- Asigne 'a' como nodo raíz e insértelo en la cola.
- Extraiga el nodo 'a' de la cola e inserte los nodos secundarios de 'a', es decir, 'b' y 'c'.
- Imprimir nodo 'a'.
- La cola no está vacía y tiene los nodos 'b' y 'c'. Dado que 'b' es el primer nodo de la cola, vamos a extraerlo e insertar los nodos secundarios de 'b', es decir, el nodo 'd' y 'e'.
- Repita estos pasos hasta que la cola se vacíe. Tenga en cuenta que los nodos que ya están visitados no deben agregarse a la cola de nuevo.
Ahora veamos el pseudocódigo del algoritmo de búsqueda en amplitud primero.
Pseudocódigo del algoritmo de búsqueda en amplitud primero
Aquí está el pseudocódigo para implementar el algoritmo de búsqueda en amplitud primero:
Entrada: s como nodo de origen BFS (G, s), deje Q en cola. Q.enqueue (s) marca s como visitado mientras (Q no está vacío) v = Q.dequeue () para todos los vecinos w de v en el Gráfico G si w no es visitado Q.enqueue (w) marca w como visitado
En el código anterior, se ejecutan los siguientes pasos:
- (G, s) es la entrada, aquí G es el gráfico y s es el nodo raíz
- Se crea una cola 'Q' y se inicializa con el nodo de origen 's'
- Todos los nodos secundarios de 's' están marcados
- Extraiga 's' de la cola y visite los nodos secundarios
- Procesar todos los nodos secundarios de v
- Almacena w (nodos secundarios) en Q para visitar sus nodos secundarios
- Continuar hasta que 'Q' sea vacío
Antes de terminar el blog, veamos algunas aplicaciones del algoritmo Breadth-First Search.
Aplicaciones del algoritmo de búsqueda en amplitud primero
La búsqueda primero en amplitud es un método simple de recorrido de gráficos que tiene una sorprendente variedad de aplicaciones. A continuación, se muestran algunas formas interesantes en las que se utiliza Bread-First Search:
Rastreadores en motores de búsqueda: Breadth-First Search es uno de los principales algoritmos que se utilizan para indexar páginas web. El algoritmo comienza a atravesar desde la página de origen y sigue todos los enlaces asociados con la página. Aquí cada página web se considerará como un nodo en un gráfico.
Sistemas de navegación GPS: Breadth-First Search es uno de los mejores algoritmos utilizados para encontrar ubicaciones vecinas mediante el sistema GPS.
Encuentre la ruta más corta y el árbol de expansión mínimo para un gráfico no ponderado: Cuando se trata de un gráfico no ponderado, calcular la ruta más corta es bastante simple, ya que la idea detrás de la ruta más corta es elegir una ruta con el menor número de aristas. Breadth-First Search puede permitir esto atravesando un número mínimo de nodos comenzando desde el nodo de origen. De manera similar, para un árbol de expansión, podemos usar cualquiera de los dos métodos de recorrido, búsqueda primero en anchura o primero en profundidad, para encontrar un árbol de expansión.
Radiodifusión: El trabajo en red hace uso de lo que llamamos paquetes de comunicación. Estos paquetes siguen un método transversal para llegar a varios nodos de red. Uno de los métodos de recorrido más utilizados es la búsqueda primero en amplitud. Se utiliza como un algoritmo que se utiliza para comunicar paquetes difundidos a través de todos los nodos de una red.
Redes de igual a igual: La búsqueda primero en amplitud se puede utilizar como método transversal para encontrar todos los nodos vecinos en una red de igual a igual. Por ejemplo, BitTorrent utiliza Breadth-First Search para la comunicación entre pares.
Así que todo se trataba del funcionamiento del algoritmo de búsqueda en amplitud primero. Ahora que sabe cómo recorrer gráficos, estoy seguro de que tiene curiosidad por saber más. Aquí hay algunos blogs relevantes para mantenerlo interesado:
Con esto llegamos al final de este blog. Si tiene alguna consulta sobre este tema, deje un comentario a continuación y nos pondremos en contacto con usted.
Si desea inscribirse en un curso completo sobre Inteligencia Artificial y Aprendizaje Automático, Edureka cuenta con un que le permitirá dominar técnicas como el aprendizaje supervisado, el aprendizaje no supervisado y el procesamiento del lenguaje natural. Incluye capacitación sobre los últimos avances y enfoques técnicos en inteligencia artificial y aprendizaje automático, como aprendizaje profundo, modelos gráficos y aprendizaje por refuerzo.