Os métodos Graph Traversal sempre me fascinaram. Desde a realização de uma comunicação ponto a ponto eficaz até encontrar os restaurantes e cafés mais próximos usando GPS, os métodos de passagem têm um conjunto variado de aplicações no cenário do mundo real. Neste blog sobre o algoritmo de pesquisa em largura primeiro, discutiremos a lógica por trás dos métodos de travessia de grafos e usaremos exemplos para entender o funcionamento do algoritmo de pesquisa em largura.
Para obter conhecimento aprofundado de Inteligência Artificial e Aprendizado de Máquina, você pode se inscrever para por Edureka com suporte 24 horas por dia, 7 dias por semana e acesso vitalício.
Aqui está uma lista de tópicos que serão coberto neste blog:
- Introdução ao gráfico transversal
- O que é a pesquisa em amplitude?
- Compreendendo o algoritmo de pesquisa em amplitude com um exemplo
- Pseudocódigo do algoritmo de pesquisa em amplitude primeiro
- Aplicações da ampla pesquisa
Introdução ao gráfico transversal
O processo de visitar e explorar um gráfico para processamento é chamado de percurso de gráfico. Para ser mais específico, trata-se de visitar e explorar cada vértice e aresta em um gráfico de forma que todos os vértices sejam explorados exatamente uma vez.
Isso parece simples! Mas há um problema.
Existem várias técnicas de travessia de gráficos, como Pesquisa em Largura, Pesquisa em Profundidade e assim por diante. O desafio é usar um gráfico técnica transversal mais adequada para resolver um problema específico. Isso nos leva à técnica de Pesquisa em Largura.
O que é o algoritmo de pesquisa em amplitude primeiro?
O algoritmo de pesquisa ampla é uma técnica de passagem de gráfico, em que você seleciona um nó inicial aleatório (nó de origem ou raiz) e começa a atravessar a camada do gráfico de forma que todos os nós e seus respectivos nós filhos sejam visitados e explorados.
Antes de prosseguirmos e entendermos a pesquisa ampla com um exemplo, vamos nos familiarizar com dois termos importantes relacionados à travessia do gráfico:
- Visitando um nó: Assim como o nome sugere, visitar um nó significa visitar ou selecionar um nó.
- Explorando um nó: Explorando o nós adjacentes (nós filhos) de um nó selecionado.
Consulte a figura acima para entender melhor isso.
Compreendendo o algoritmo de pesquisa em amplitude primeiro com um exemplo
O algoritmo de pesquisa em amplitude segue uma abordagem simples e baseada em níveis para resolver um problema. Considere a árvore binária abaixo (que é um gráfico). Nosso objetivo é percorrer o gráfico usando o algoritmo de pesquisa em amplitude primeiro.
Antes de começarmos, você deve estar familiarizado com a estrutura de dados principal envolvida no algoritmo de pesquisa em amplitude.
Uma fila é uma estrutura de dados abstrata que segue a metodologia First-In-First-Out (os dados inseridos primeiro serão acessados primeiro). É aberto em ambas as extremidades, onde uma extremidade é sempre usada para inserir dados (enfileirar) e a outra é usada para remover dados (desenfileirar).
Agora, vamos dar uma olhada nas etapas envolvidas na passagem de um gráfico usando a pesquisa em amplitude:
Passo 1: Pegue uma fila vazia.
Passo 2: Selecione um nó inicial (visitando um nó) e insira-o na Fila.
Etapa 3: Desde que a Fila não esteja vazia, extraia o nó da Fila e insira seus nós filhos (explorando um nó) na Fila.
programa de classificação de mesclagem simples em c ++
Passo 4: Imprima o nó extraído.
Não se preocupe se você estiver confuso, vamos entender isso com um exemplo.
Dê uma olhada no gráfico abaixo, usaremos o algoritmo de pesquisa em amplitude para percorrer o gráfico.
Em nosso caso, vamos atribuir o nó 'a' como o nó raiz e começar a percorrer para baixo e seguir as etapas mencionadas acima.
A imagem acima mostra o processo de ponta a ponta do algoritmo de pesquisa em amplitude primeiro. Deixe-me explicar isso com mais detalhes.
- Atribua 'a' como o nó raiz e insira-o na fila.
- Extraia o nó 'a' da fila e insira os nós filhos de 'a', ou seja, 'b' e 'c'.
- Imprimir o nó ‘a’.
- A fila não está vazia e tem os nós 'b' e 'c'. Uma vez que 'b' é o primeiro nó na fila, vamos extraí-lo e inserir os nós filhos de 'b', ou seja, o nó 'd' e 'e'.
- Repita essas etapas até que a fila fique vazia. Observe que os nós que já foram visitados não devem ser adicionados à fila novamente.
Agora vamos dar uma olhada no pseudocódigo do algoritmo de pesquisa em amplitude.
Pseudocódigo do algoritmo de pesquisa em amplitude primeiro
Este é o pseudocódigo para implementar o algoritmo de pesquisa em amplitude:
Entrada: s como o nó de origem BFS (G, s), seja Q fila. Q.enqueue (s) marca s como visitada enquanto (Q não está vazio) v = Q.dequeue () para todos os vizinhos w de v no Gráfico G se w não é visitado Q.enqueue (w) marca w como visitado
No código acima, as seguintes etapas são executadas:
- (G, s) é a entrada, aqui G é o gráfico e s é o nó raiz
- Uma fila 'Q' é criada e inicializada com o nó de origem 's'
- Todos os nós filhos de 's' são marcados
- Extraia 's' da fila e visite os nós filhos
- Processa todos os nós filhos de v
- Armazena w (nós filhos) em Q para visitar posteriormente seus nós filhos
- Continue até que 'Q' seja vazio
Antes de encerrarmos o blog, vamos dar uma olhada em algumas aplicações do algoritmo de pesquisa em amplitude.
Aplicações do algoritmo de pesquisa em amplitude
A pesquisa ampla é um método simples de passagem de gráfico que possui uma gama surpreendente de aplicações. Aqui estão algumas maneiras interessantes em que o Bread-First Search está sendo usado:
Rastreadores em motores de busca: A pesquisa ampla é um dos principais algoritmos usados para indexar páginas da web. O algoritmo começa a percorrer a página de origem e segue todos os links associados à página. Aqui, cada página da web será considerada um nó em um gráfico.
Sistemas de navegação GPS: A Pesquisa em Largura é um dos melhores algoritmos usados para encontrar localizações vizinhas usando o sistema GPS.
Encontre o caminho mais curto e a árvore de abrangência mínima para um gráfico não ponderado: Quando se trata de um gráfico não ponderado, calcular o caminho mais curto é bastante simples, pois a ideia por trás do caminho mais curto é escolher um caminho com o menor número de arestas. A pesquisa ampla pode permitir isso percorrendo um número mínimo de nós a partir do nó de origem. Da mesma forma, para uma árvore estendida, podemos usar um dos dois métodos de pesquisa em largura ou de passagem em profundidade para encontrar uma árvore estendida.
Transmissão: A rede usa o que chamamos de pacotes para comunicação. Esses pacotes seguem um método transversal para alcançar vários nós de rede. Um dos métodos de travessia mais comumente usados é a pesquisa em amplitude. Ele está sendo usado como um algoritmo usado para comunicar pacotes transmitidos por todos os nós de uma rede.
Rede ponto a ponto: A pesquisa ampla pode ser usada como um método de passagem para encontrar todos os nós vizinhos em uma rede ponto a ponto. Por exemplo, o BitTorrent usa a Pesquisa em Largura para a comunicação ponto a ponto.
Então, tudo se resumia ao funcionamento do algoritmo de pesquisa em amplitude. Agora que você sabe como percorrer os gráficos, tenho certeza de que está curioso para saber mais. Aqui estão alguns blogs relevantes para mantê-lo interessado:
Com isso, chegamos ao fim deste blog. Se você tiver alguma dúvida sobre este tópico, deixe um comentário abaixo e entraremos em contato com você.
Se você deseja se inscrever em um curso completo de Inteligência Artificial e Aprendizado de Máquina, Edureka tem uma curadoria especial isso o tornará proficiente em técnicas como aprendizado supervisionado, aprendizado não supervisionado e processamento de linguagem natural. Inclui treinamento sobre os mais recentes avanços e abordagens técnicas em Inteligência Artificial e Aprendizado de Máquina, como Aprendizado Profundo, Modelos Gráficos e Aprendizado por Reforço.