Algoritmo de Busca A Estrela (A*)

olá sejam bem-vindos essa aula que nós vamos trabalhar com outro algoritmo de busca aqui também ele é da área de inteligência artificial que é chamado da busca a estrela e você também vai encontrar a asterisco para referenciar esse algoritmo e esse é um dos algoritmos mais importantes da área de buscas e inteligência artificial inclusive ele que foi o algoritmo que deu ideia para implementação dos sistemas de gps e além disso esse algoritmo é muito utilizado em jogos por exemplo em jogos de tiro vamos supor que você está fugindo do inimigo o inimigo é o computador

e quando o inimigo ele encontra você ou ele enxerga você ele vai traçar a menor rota da posição que ele está até a posição que você está para ele conseguir por exemplo te matar tem muitas aplicações práticas principalmente na área de jogos se você fizer uma pesquisa sobre o algoritmo a estrela você vai encontrar várias aplicações com relação a jogos caso você conhece aquela ferramenta e unity que a para desenvolvimento de jogos existem muitas implementações desse algoritmo a estrela e nós vamos utilizar ele agora para resolver esse problema da busca de arad até bucareste a

ideia dele é utilizar a tabela de heurísticas que nós usamos na busca gulosa que nós temos a distância em linha reta de uma cidade até o objetivo e também finalmente agora vamos utilizar essa distância pela estrada só para nós recapitularmos esse valor de 140 indica a quilometragem que você deve percorrer de arad até civil e esse valor de 366 ele não é uma distância pela estrada e a distância em linha reta de arad até bucareste já considerado somente uma heurística uma forma que você vai utilizar para resolver o problema somente para ajudar o algoritmo vamos

dar início então começando por harazi nós vamos agora expandir quem são os adjacentes de ar así que a ser indy cível e times ohara vamos considerar as distâncias em linha reta zerind 374 conforme a tabela civil 253 conforme a tabela timisoara 329 conforme a tabela agora vamos utilizar a distância pela estrada de arad até dirindi são 75 km de arad até se meu 140 in the arade até timisoara 118 agora nós vamos fazer um somatório desses valores 374 que é heurística em linha reta mas a distância que você vai percorrer pela estrada nós temos por

exemplo 449 esse somatório de arad até syringe o custo é 449 de sybil somamos 140 mais 253 ou valor é 393 de arad até timisoara custo é 447 quer dizer que nesse algoritmo você utiliza a heurística e o quanto você já andou pela estrada o quanto que você precisa andar para chegar em uma determinada cidade acaba sendo um algoritmo muito mais eficiente podemos utilizar novamente um vetor ordenado para inserirmos esses valor o menor valor é o 393 que é de sybil então nós vamos escolher novamente ir por civil vamos expandir os adjacentes de sybil veja

que nós temos o fagaras o rinico e também por aldeia vamos agora buscar os valores da heurística ea distância em linha reta ou ladeia 380 conforme tabela rinico 193 conforme a tabela pagar a 178 agora vamos buscar os valores pela estrada de sybil até cada uma dessas cidades de sybil até hora dei a 151 km de sybil até rinico 80 km de sybil até fagaraz a inove quilômetros vamos fazer agora o somatório da heurística distância em linha reta mais a distância real pela estrada moradei a531 veja que deu um valor bem alto pois você estaria

voltando você está se afastando do objetivo rinico 273 e fagaras 277 pela busca gulosa se você lembra ele foi por fagaras pois ele tem a menor distância em linha reta porém nesse caso nós temos o menor custo que há 273 por rinico quer dizer que vamos por essa cidade expandindo os adjacentes não visitados temos craiova e pitesti agora o que nós precisamos fazer é considerar a heurística ea distância em linha reta é de pitesti até objetivo 98 de craiova até objetivo 160 conforme a tabela agora vamos pegar a distância real pela estrada rinico até pitesti

97 km rinico até craiova 146 km vamos fazer o somatório pitesti 195 craiova 306 quer dizer que ele vai pôr pitesti vamos agora expandir os adjacentes não visitados de pitesti temos nesse caso somente o bucareste a heurística distância em linha reta de bucareste até bucareste tem o valor zero e à distância pela estrada de pitesti até bucareste o 101 quer dizer que eu custo dessa solução é somente 101 nesse caso só tem um nó se você por exemplo tivesse outro nós para cá com certeza a bucareste daí é o menor valor é por causa do

valor da distância em linha reta então quer dizer que essa que é a solução você vai sair de arad vai para sybil renico pitesti e bucareste vamos fazer agora um comparativo desses dois algoritmos para nós sabermos qual é a distância em quilômetros que você vai percorrer berardi até civil 140km é e decidiu até rinico mais 80 220 km de rinico até pitesti mais 97 km de pitesti até bucareste mais 101 com esse algoritmo a estrela nós vamos percorrer pela estrada 418 km agora vamos ver quantos quilômetros nós vamos andar com o algoritmo de busca gulosa

ele pegou uma rota diferente de árabe até civil a 140 km e ele foi por vagas de sybil até falhas mais 99 km e de fagaras até bucareste mas 211 km veja que ele anda 450 km com gulosa com outro algoritmo a estrela 418 quer dizer que nós temos 32 km de diferença entre um algoritmo e outro conforme você notou algoritmo a estrela ele é muito mais eficiente do que a busca gulosa pelo fato de que ele utiliza além da heurística que é uma informação sobre o problema a distância real entre as cidades nesse exemplo

nós estamos considerando somente as distâncias mas claro que por exemplo esse caminho por fagaras 32 km a mais mas vamos supor eu fiz um caminho que não tenha pedágio então quer dizer que o custo financeiro vai ser menor do que você passar por essas outras cidades e vamos supor que passando por esse caminho você precisa entrar no centro dessas cidades então quer dizer que eu percurso pode demorar mais e número de horas então você pode levar em consideração vários fatores e além de colocar por exemplo esse valor de 211 que é somente a distância você

pode colocar mais heurísticas em cada uma dessa distância como por exemplo o curso do caminho é um custo alto médio baixo considerando o pedágio é você poderia por exemplo adicionará quantos pedágios existem em cada um desses trechos poderia indicar seu trecho é perigoso ou não é perigoso você tem muitos assaltos em determinadas partes da estrada ou então qual é a rota que tem mais os políticos entre fagaras e bucareste tem poucos pontos turísticos mas entre o único e teste tem vários pontos turísticos assim o usuário pode escolher eu quero projeto para fazer um passeio ou

um trajeto para ir mais rápido então você pode adicionar uma série de heurísticas de acordo com o problema que você estiver trabalhando com esse fechamos o entendimento da busca estrela e também fizemos um comparativo com a busca gulosa e na próxima aula vamos fazer a respectiva implementação obrigado e até lá