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
O Dijkstra é um dos algoritmos clássicos da área de grafos. Ele é comumente utilizado em situações em que se deseja encontrar o menor caminho de um vértice origem para todos os outros vértices do grafo, mas também pode ser adaptado para encontrar o menor caminho entre dois vértices específicos. Como? É só parar ele no meio do caminho.
O algoritmo é baseado nas técnicas de programação dinâmica para obter uma boa performance. Calma, eu não vou explicar em detalhes o que é programação dinâmica, isso em si daria uma disciplina de 60 horas do curso! A ideia bem simplificada (mas olhe, é BEM simplificada) é salvar e reutilizar resultados que você já encontrou uma vez na execução do algoritmo, para não ter de calcular de novo. O algoritmo vai “lembrando” dos resultados e, quando precisa de algo que ele já sabe, por exemplo, o custo para chegar em um vértice que ele já calculou não precisa refazer as contas, apenas usa o que já está armazenado. A ideia é simples, a implementação não.
O algoritmo de Dijkstra segue o seguinte fluxo:
Uma característica interessante desse algoritmo é que ele testa vários caminhos até cada vértice, mas salva apenas o menor que foi encontrado ao longo da execução. Por exemplo, para um vértice X, se ele salva o menor custo de chegar a X, então todos os caminhos que passam por X usarão esse custo. Ele não precisa ficar recalculando esse valor toda vez que encontrar um caminho que passa por X, ele apenas utiliza o que já foi calculado anteriormente. No Código 01 pode-se ver o pseudocódigo do algoritmo.
Djikstra(Grafo g, Vértice origem){ distancia[origem] = 0 Cria conjunto de vertices Não_Visitados Para cada vértice v do grafo g{ Se v!= origem{ distancia[v] = INFINITO } anterior[v] = INDEFINIDO Insere v em Não_Visitados } Enquanto Não_Visitados não for VAZIA{ Procura vértice com menor distância, denominado u Remove u de Não_Visitados Para cada i vizinho de u{ custo = distancia[u] + g[u, i] Se custo < distancia[i] { distancia[i] = custo anterior[i] = u } } } return distancia, anterior }É difícil visualizar como ele funciona, não é mesmo? Imagine como se fosse uma busca sistemática, só que ela vai salvando os valores do caminho encontrado, e não precisa retornar em nenhum momento. É quase como se o caminho fosse uma “onda” que vai varrendo os vértices do grafo e atualizando com os menores caminhos possíveis, até chegar ao ponto de origem. Veja um exemplo com o mapa da seção anterior em que você partirá do mesmo ponto.
Assuma que o custo de movimentação entre os blocos é 1, e não há diferença entre movimento vertical e horizontal (da mesma forma que foi feito no exemplo anterior):
Foi processado o primeiro vértice (origem, marcado de verde) e atualizadas as distâncias dos vizinhos a partir dele. Esse processo será repetido até chegar no vértice destino.
Os vértices visitados passam a ser coloridos de vermelho e não serão mais explorados (o valor contido já é o menor caminho possível até ele). O vértice atual em exploração continua marcado como verde.
A partir de agora, eu vou “queimar” algumas etapas na sequência senão o pessoal que faz as imagens vai desmaiar de exaustão! Você verá a exploração de vários vértices simultaneamente, mas a ideia é repetir o processo de um por um. Dessa forma tem-se garantia de o caminho até o vértice será sempre o menor!
Todos os vértices em uma distância de 3 que tem vizinhos.
Todos os vértices que percorreram uma distância de 4 casas.
Todos os vértices que percorreram uma distância de 5.
Todos os vértices em uma distância de 3 que tem vizinhos.
Ao explorar todos os vértices que percorreram uma distância de 6, você encontrará um que chega até o destino. Como todas as distâncias são unitárias, tem-se a garantia de que esse primeiro que chegou é o menor caminho, que seguindo o algoritmo pode ser expresso pelo seguinte desenho:
Perceba que existem mais dois caminhos que possuem o mesmo custo: o que passa por (4,2) e o que passa por (5,2). Qualquer um desses três caminhos satisfazem a condição de ser o menor caminho entre o bloco (4,1) e o bloco (4,8).
Para esse mapa do exemplo, não é possível ver tanta vantagem no algoritmo de Dijkstra frente às outras buscas. Porém, quando o cenário começa a ficar mais complexo, ele torna-se mais eficaz do que as buscas para a solução do caminho:
Mesmo assim, esse algoritmo ainda precisa visitar um grande número de vértices para achar a resposta correta. Sem entrar em muitos detalhes de complexidade de algoritmos, suponha que, se o seu mapa tiver 5000 blocos, ele ainda quebra bem o galho. Mas em um mapa com 1.000.000 de blocos, aí os seus caminhos iam demorar muito tempo para serem calculados! E não é difícil pensar mapas grandes, dado o tamanho de alguns cenários em jogos atuais! Por esse motivo, o algoritmo de Dijkstra tradicional não é tão usado para achar o caminho entre dois pontos, mas sim uma otimização que foi criada a partir dele: o algoritmo A*.
Versão 5.3 - Todos os Direitos reservados