Os materiais didáticos aqui disponibilizados estão licenciados através de Creative Commons Atribuição-SemDerivações-SemDerivados CC BY-NC-ND. Você possui a permissão para visualizar e compartilhar, desde que atribua os créditos do autor. Não poderá alterá-los e nem utilizá-los para fins comerciais.
Atribuição-SemDerivações-SemDerivados
CC BY-NC-ND
Cursos / Jogos Digitais / Inteligência Artificial para Jogos / Aula
Retome o exemplo da viagem de Santa Cruz para Pau dos Ferros, agora para entender o outro tipo de busca.
Na busca em largura, ou BFS, a ideia é que você explore todos os vizinhos do vértice em uma mesma profundidade antes de verificar os próximos vértices. No fim das contas você vai realizar os mesmos processamentos, só que em uma ordem diferente! Essa busca é mais sistemática e explora primeiro os vértices que estão mais próximos da origem, dirigindo-se gradativamente aos vértices mais distantes. É a ideia oposta da busca em profundidade: ao invés de tentar achar logo um caminho, ele vai verificando todos os caminhos do grafo até encontrar um que seja o destino desejado.
Para implementar essa ideia, parta para uma abordagem iterativa, utilizando uma Fila (lembra da Aula 03? A mesminha! ). Você vai pegar seu vértice de origem, Santa Cruz, e vai sair adicionando todos os vizinhos dele: Mossoró, Natal e Caicó. Todos esses vértices serão colocados em uma fila para serem processados. Após isso, o primeiro que foi colocado na fila torna-se o atual, e os seus vizinhos que ainda não estão na fila serão então inseridos no final. Perceba que esses novos vizinhos só serão processados quando todos os três vizinhos de Santa Cruz forem avaliados.
Dessa forma, você vai fazendo uma varredura do grafo pelos níveis de vértices que estão mais próximos do ponto de origem, e os nós mais distantes serão atingidos no final do algoritmo. Essa abordagem é boa para momentos em que você quer encontrar o primeiro caminho possível com o menor número de percursos no grafo (isso faz mais sentido quando o grafo não tem peso, em que o número de arestas do caminho seria equivalente ao seu custo!). O pseudocódigo desse algoritmo é ilustrado pelas linhas do Código 03 abaixo:
Função BFS(int inicial, int destino){ Fila próximos Insira o nó inicial na fila Enquanto a fila não está vazia{ Processa o próximo da fila Retira o próximo elemento da fila Marca o elemento como visitado Para cada vizinho do próximo{ Insere o vizinho na fila Marca o vizinho como visitado } }}Hum… ainda está confuso, hein? Já sei, já sei, você quer as imagens... No caso da busca em largura, os vértices em amarelo vão representar os vértices inseridos na fila de avaliação pelo algoritmo, enquanto os outros mantêm o mesmo significado do que foi anteriormente visto no algoritmo DFS.
Como você pôde observar na Figura 16, o caminho final dessa iteração foi chegar a Pau dos Ferros através de Caicó, vértice a partir do qual Pau dos Ferros foi inserido na fila. Da mesma forma que o algoritmo anterior, vou colocar um exemplo de implementação utilizando a linguagem C# (Código 04). Esse exemplo busca o primeiro caminho possível de um ponto inicial até um ponto final.
using System.Collections;using System.Collections.Generic;using UnityEngine;public class Algoritmos : MonoBehaviour { //matriz de adjacência para o grafo RN private int [,] grafo = new int[5,5] { {0, 40, 10, 20, 45}, {40, 0, 40, 30, 10}, {10, 40, 0, 8, -1}, {20, 30, 8, 0, 35}, {45, 10, -1, 35, 0}}; //Nós que já foram visitados, inicia todos como não visitados private int[] visitados = new int[5]{0,0,0,0,0}; //Nomes das cidades string[] cidades = new string[5]{"Natal", "Mossoró", "Santa Cruz", "Caicó", "Pau dos Ferros"}; //Nó inicial - 0 representa Natal private int inicio = 0; //Nó final - 3 representa Caicó private int fim = 3; string caminho = ""; void Start () { print("COMECANDO A BUSCA"); Busca(inicio, fim); } // Update is called once per frame void Update () {} //Busca void Busca(int start, int finish){ //Em largura //BFS(start, finish) }//Algoritmo BFS, montando para parar no primeiro caminho que encontrar void BFS(int atual, int alvo){ //Fila de nós a serem processados Queue<int> fila = new Queue<int>(); int prox, cont = 0; //Coloca o nó inicial na fila e marca como visitado fila.Enqueue(atual); visitados[atual] = 1; //Enquanto a fila não secar while(fila.Count > 0){ //Pega o próximo na fila prox = fila.Peek(); visitados[prox] = 1; if(cont != 0) caminho += " -> "; caminho += cidades[prox]; //Remove ele da fila fila.Dequeue(); //Coloca os vizinhos na fila, e marca como visitado for(int i=0; i<5; i++){ if(grafo[prox, i] > 0 && visitados[i] == 0){ if(i == alvo) caminho += " -> " + cidades[i]; else{ fila.Enqueue(i); } visitados[i] = 1; } } //Se chegou no fim if(visitados[alvo] == 1) break; //Atualiza contador auxiliar da impressão cont++; } //Imprime o primeiro caminho que encontrou print(caminho);}E com isso você já fica com duas ferramentas poderosas para trabalhar. Apesar de suas aplicações na área de jogos, esses algoritmos não se limitam apenas a esse campo, podendo ser encontrados na resolução de diversos problemas na área de redes, circuitos, otimização de algoritmos, engenharia de software e vários outros campos da computação! Então é muito importante entender a ideia de funcionamento e brincar com a implementação desses algoritmos para aumentar o seu arsenal como programador.
Perceba uma coisa: com esses algoritmos você consegue verificar se existe um caminho de A até B, e até achar todos os caminhos que existem entre os dois! Mas eles não são direcionados para achar o menor caminho: aquele que te leva com o menor custo possível de um ponto a outro - a principal problemática que foi discutida no início das aulas de “Descoberta de caminhos”!
Não se desespere! Mature um pouco o conteúdo dessa aula, que na próxima você terá o gran finale! Conhecerá dois algoritmos voltados para essas tarefas: o algoritmo de Djikstra e o algoritmo A*!
Não consegue conter a emoção, hein? Clique aqui para ver o próximo episódio.
Até lá!
Versão 5.3 - Todos os Direitos reservados