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
No algoritmo DFS, percorre-se o grafo em termos de profundidade. Essa noção relaciona-se ao quão longe do vértice de origem o caminho vai parar dentro do grafo: a quantas arestas do vértice original o vértice atual do caminho se encontra? Se o caminho passa por uma aresta, a profundidade é de um. Se passa por três arestas, a profundidade é de três. O nome busca em profundidade advém de o algoritmo estar sempre tentando ir o mais “profundo” (distante) possível do vértice origem na sua busca pelo vértice destino. Também ocorre uma grande variação da profundidade ao longo da execução, uma vez que, ao não encontrar mais caminho para seguir em frente, o algoritmo retorna para o vértice anterior e tenta achar uma nova rota a partir dele, explorando vizinhos que ainda não foram visitados.
Calma, vou explicar um pouco melhor. No grafo do estado do RN, imagine que você quer fazer um caminho entre Santa Cruz e Pau dos Ferros. O vértice inicial da viagem é Santa Cruz, mas quem são os vizinhos dele?
Ora, os vizinhos são todos os vértices que têm uma aresta conectando com Santa Cruz, nesse caso, Natal, Mossoró e Caicó. Ao procurar um caminho para Pau dos Ferros, você poderia começar por qualquer um desses vizinhos. Então escolha Caicó, pra poder comer uma bolachinha na manteiga!
Em uma busca em profundidade, os outros vizinhos de Santa Cruz não serão explorados nesse momento: primeiramente serão explorados os vizinhos de Caicó, que estão em uma profundidade maior no caminho (em Santa Cruz você deu zero passos, em Caicó, já deu um passo). Faça isso sucessivamente (explore o vértice em dois, três, mil passos!) até chegar no destino. Depois que terminar de explorar, pode voltar para os vértices em níveis anteriores e continuar explorando outros caminhos e vizinhos que ainda não foram verificados. Captou a mensagem?
Observe o pseudocódigo do algoritmo abaixo (Código 01), talvez facilite um pouco a sua percepção de como isso ocorre:
Função DFS(int atual, int destino){ Adiciona o vértice atual ao caminho; Marca como vértice como visitado; Se atual == destino imprime/retorna o caminho construído Senão{ Para cada um dos vizinhos não visitados de atual{ DFS(vizinho, destino) //Se você quiser todos os caminhos //Desmarca o vizinho como visitado //Retira o vizinho do caminho } } }
Ainda não, né? Então veja as ilustrações abaixo! Os vértices verdes representam o ponto atual do caminho, os vértices em vermelho os pontos já visitados e os vértices amarelos são os próximos vizinhos não visitados que podem ser escolhidos. Os vértices em azul são pontos não visitados e que não são vizinhos do ponto atual.
Uma observação a fazer é que a escolha do próximo vértice a ser explorada foi aleatória, você poderia ter feito um percurso distinto seguindo as regras e estaria correto da mesma forma! Nesse ponto, foi traçado um caminho em que você parte de Santa Cruz e passa por Caicó e Mossoró antes de chegar em Pau dos Ferros. Se você quiser interromper o algoritmo porque encontrou um caminho, sem problemas! Ou você pode continuar “rodando” para ver se encontra outros caminhos até o vértice final (vai que tem um melhor!). Nesse caso, o algoritmo vai retornar ao vértice anterior (Mossoró) e colocar algum dos vizinhos ainda não explorados para tentar chegar a Pau dos Ferros novamente. Se no grafo não existirem mais caminhos, o algoritmo simplesmente termina.
Veja a sequência abaixo que mostra a execução do algoritmo no grafo voltando um nível (Mossoró).
Nesse ponto, foi encontrado um caminho que passa por todos os vértices:
Santa Cruz -> Caicó -> Mossoró -> Natal -> Pau dos Ferros
E o que acontece se você quiser voltar dois níveis de profundidade, quando Caicó era a bola da vez? Você não poderá ir novamente para Mossoró, porque é um caminho que já foi explorado. Confira nas figuras abaixo.
Dessa forma, o caminho encontrado foi Santa Cruz, Caicó e Pau dos Ferros, uma rota mais direta! Esse algoritmo é uma recursão simples, mas é muito útil para várias situações na área de jogos. Imagine que você quer fazer um jogo que gera mapas procedurais: fazer um algoritmo que gera os mapas de qualquer jeito não é difícil (pode ser tudo aleatório), mas garantir que o mapa é válido, e que todas as casas são navegáveis, aí a conversa é mais séria… Uma estratégia válida é gerar um mapa e usar uma DFS para varrer e verificar se todas as casas podem ser alcançadas pelo jogador, adaptando o caminho quando ele encontrar falhas. O uso de algoritmos recursivos para explorar todas as possibilidades é uma técnica denominada Backtracking.
Para não ficar apenas nos exemplos abstratos e visuais, veja um exemplo usando o grafo do RN, implementado em C# (Código 02).
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 profundidade DFS(start, finish); } //Algoritmo da busca em profundidade, para achar todos os caminhos void DFS(int atual, int alvo){ string aux; //Monta string do caminho caminho += cidades[atual]; aux = caminho; //Marca ela como visitada visitados[atual] = 1; //Se for a cidade destino if(atual == alvo){ //Chegou bixiga!! print(caminho); } //Senão else{ //Verifica quais são os vizinhos, ou nós que podem ser alcançados a partir do nó atual for(int i=0; i<5; i++){ if(grafo[atual, i] > 0 && visitados[i] == 0){ //Chama a função passando o vizinho como nó atual, adiciona uma seta para ficar bonita a string do caminho caminho += " -> "; DFS(i, alvo); //Na recursão, você desfaz as operações para preparar para executar o próximo passo com os nós que sobraram (se quiser explorar todos os caminhos, backtracking) caminho = aux; visitados[i] = 0; } } } }}A busca em profundidade é um recurso muito utilizado, e que se vale de uma implementação recursiva para manter o código simples e elegante. Mas ela não é o único tipo de busca que pode explorar os vértices do grafo! Existe uma segunda abordagem chamada de busca em largura!
Versão 5.3 - Todos os Direitos reservados