If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

Busca em largura e seus usos

No tutorial introdutório, você jogou com um personagem fazendo-o se mover num labirinto para atingir um objetivo. Você começou dizendo que o objetivo estava à distância de zero passos dele mesmo. Então você descobriu todos os quadrados que estavam a um passo do objetivo. Depois os que estavam a dois passos, três passos e assim por diante até que você chegou ao quadrado onde o personagem começou. Se você registrou de qual quadrado distante k você veio para chegar a um quadrado à distância k+1 você poderia voltar para encontrar a rota do personagem ao objetivo.
Aqui está a figura que vimos no tutorial introdutório:
Agora você deve reconhecer isto como um grafo não direcionado. Cada vértice corresponde a um quadrado que não é parte de uma parede, e cada aresta é incidente aos quadrados adjacentes.
O caminho encontrado para o procedimento acima tem uma propriedade importante: nenhuma outra rota do personagem até o objetivo segue por menos quadrados. Isso por que usamos um algoritmo conhecido como amplitude de busca para encontra-lo. Amplitude de busca, também conhecido como BFS (em inglês Breadth-first search), encontra o caminho mais curto para um dado vértice origem para todos os outros vértices, em termos das arestas dos caminhos.
Aqui está um outro exemplo da pesquisa por amplitude: o jogo dos "seis degrais de Kevin Bacon". Aqui, jogadores tentam conectar atores de filmes e atrizes com Kevin Bacon de acordo com uma sequência de qem apareceu com quem em um filme. Quanto menor a cadeia, melhor, e é incrível quantos atores e atrizes podemos ligar a Kevin Bacon em uma cadeia de seis ou menos. Como exemplo, olhe Kate Bell, uma atriz australiana. Ela estava no MacBeth com Nash Edgerton em 2006; Edgerton estava em The Matrix Reloaded com Laurence Fishburne em 2003; e Fishburne estava em Mystic River com Kevin Bacon em 2003. Portanto, o número de Kate Bell para Kevin Bacon é 3. De fato, há muitas maneiras de encontrar que o número de Kate Bell para Kevin Bacon é 3. Você pode procurar por qualquer número do ator Kevin Bacon no site the Oracle of Bacon website.
Como você já deve ter adivinhado, o site Oracle of Bacon mantêm um gráfico indireto no qual cada vértice corresponde a um ator ou atriz, e se duas pessoas aparecerem no mesmo filme, então há um incidente de borda no vértice deles. Uma pesquisa de amplitude do vértice do Kevin Bacon encontra o caminho mais curto para todos qualquer outro ator ou atriz.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.

Quer participar da conversa?

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.