[AI - #1]Introdução ao Algorítimo de Dijkstra

[AceStryker 27]

Olá a todos, eu vou começar a "subir o nível" dos meus tópicos para algo mais avançado, vou tentar explicar alguns algorítimos de IA(Inteligência Artificial), estes tutoriais a priori serão um pouco mais teóricos pois você precisa saber quais ferramentas você tem antes de poder usa-las não acha?

 

Este algorítimo foi feito por Edsger Dijkstra em 1959 e é bastante usado em jogos, agora tentarei explicar o motivo.

Como todos devem saber o processador pode sim se assemelhar com o cérebro mas estes dois tem uma coisa muito diferente que faz uma diferença lascada, que é o modo de processar informações, o cérebro usa um "sistema" de semelhança, por exemplo, quando vemos um carro diferente sabemos que é um carro pois na nossa cabeça carro é um objeto de metal que tem 4 rodas e anda nas ruas, mesmo sem saber qual carro que é sabemos que é um carro.O processador é diferente, ele é por base de números, por exemplo, quando ele vê um número se ele for igual à algum que esteja em seu HD ele detectará que já existe um desses, mas se ver um diferente, não importa se seja um pouquinho diferente ou muito diferente ele vai detectar diferente, ele não consegue assemelhar.O desafio de todos os programadores de jogos é fazer cada vez mais que o processador pense por si só, e escolha as melhores opções possíveis, e para isso inventaram a inteligência Artificial.

 

Como o processador só vê números, precisamos ajeitar nosso programa para que tudo o que ele faça, ele faça por números para facilitar nosso algorítimo, o algorítimo de Dijkstra é baseado em um grafo(lembra da teoria dos grafos?), e este sempre escolherá o caminho menos, vamos supor aqui o seguinte, precisamos ir da cidade A para a cidade B:

 

(Gif da wikipédia)

 

Vamos entender esta animação, vemos que o programa a priori vê qual é o caminho melhor para ir para o próximo vértice:

• de 1 à 6 temos 14
  
• de 1 à 3 temos 9
  
• de 1 à 2 temos 7
  

 

Então o melhor caminho é de 1 à 2!

 

• de 2 à 4 temos 15
  
• de 2 à 3 temos 10
  

 

Então o melhor caminho é de 2 à 3, mas para chegar ao 3, é mais fácil ir de 1 à 3 pois 9 < 10 + 7, então devemos ir de 1 à 3

 

• de 3 à 4 temos 11
  
• de 3 à 6 temos 2
  

 

Então o melhor caminho é de 3 à 6

Depois de 6 a 5 porque só tem essa opção kk

 

Como você deve ter percebido, este algorítimo na teoria dos grafos é um de estratégia gulosa, pois ele só vê a melhor alternativa do momento

 

Espero que tenham entendido o artigo, os créditos vão todos à mim!Abração,

AceStryker.